+
+ // 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];
+ else (left[p] == slot ? left : right)[p] = right[slot]; // fix parent's pointer
+ parent[right[slot]] = p;
+ left[leftmost(right[slot])] = left[slot]; // fix our successor-leaf's fake right ptr
+ balance(right[slot], p);
+
+ // fast path; it has no right child, so we replace it with its left child
+ } else if (right[slot] <= 0) {
+ if (p == 0) root = left[slot];
+ else (left[p] == slot ? left : right)[p] = left[slot]; // fix parent's pointer
+ parent[left[slot]] = p;
+ right[rightmost(left[slot])] = right[slot]; // fix our successor-leaf's fake right ptr
+ balance(left[slot], p);
+
+ // node to be deleted has two children, so we replace it with its left child's rightmost descendant
+ } else {
+ int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot);
+ left[left_childs_rightmost] = left[slot];
+ right[left_childs_rightmost] = right[slot];
+ if(left[slot] > 0) parent[left[slot]] = left_childs_rightmost;
+ if(right[slot] > 0) parent[right[slot]] = left_childs_rightmost;
+ parent[left_childs_rightmost] = parent[slot];
+ if (p == 0) root = left_childs_rightmost;
+ else (left[p] == slot ? left : right)[p] = left_childs_rightmost; // fix parent's pointer
+ balance(left_childs_rightmost, p);