/** 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");
if (d <= 0) throw new Error("rotation error");
left[d] = b;
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];