/** the number of elements in the tree */
public final int treeSize() { return root == 0 ? 0 : size[root]; }
-
+
/** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
public final synchronized void insertNode(int index, Object o) {
if(o == null) throw new Error("can't insert nulls in the balanced tree");
int c = left[d];
if (d <= 0) throw new Error("rotation error");
left[d] = b;
- if(size[b] <= 3) // b is now a leaf
- right[b] = -d;
- else
- right[b] = c;
+ right[b] = c <= 0 ? -d : c;
parent[b] = d;
parent[d] = p;
if(c > 0) parent[c] = b;
+
if (p == 0) root = d;
else if (left[p] == b) left[p] = d;
else if (right[p] == b) right[p] = d;
// we found the node to delete
} else {
-
// fast path: it has no children
if (left[slot] <= 0 && right[slot] <= 0) {
if (p == 0) root = 0;
int[] side = left[p] == slot ? left : right;
side[p] = side[slot]; // fix parent's pointer
}
-
// fast path: it has no left child, so we replace it with its right child
} else if (left[slot] <= 0) {
if (p == 0) root = right[slot];