14. Deletion in red-black trees

Preparation

Suppose we delete a node z, and there are 3 cases of z in a binary search tree:
(i) z is a leaf;
(ii) z has only one child;
(iii) z has two children.

For situation iii, then we do as follow:

1. let y be the successor of z in the RBT, Copy the content of y (not its color) to node z,
2. node y then is “spliced out”, where y only has only the right child in the binary search tree.

Adjust the color of the node

1. If y was RED, the new tree is already a red-black tree, done.
2. If y was BLACK, the new tree due to the removal of y has several types of red-black property violations:
   --Case one: If y was the tree root, the new root might be RED
   --Case two: If both the parent and the child of y are RED, they now have the relationship between the parent and the child
3. Case three: Any path passing through y now has fewer BLACK nodes.

Suppose the color of y was BLACK and x is the sole child of y in the tree.

1. If y was the root and a red child x of y now becomes the new root, then Property 2 of the RBT is violated.
2. If both x and p[y] are RED before the deletion of y, then Property 4 of the RBT is violated.
3. The removal of y causes any path containing y has a black node less. This causes Property 5 of the RBT to be violated.

We correct the above errors by saying that node x has an “extra” BLACK color.

To restore Property 5, we consider four cases:
Case 1: x’s sibling w is red
Case 2: x’s sibling w is black, and both children of w are black
Case 3: x’s sibling w is black, w’s left child is red and w’s right child is black.
Case 4: x’s sibling w is black, and the right child of w is red

The key idea is that in each case the number of black nodes from the subtree root to each of the subtrees α,β,... is preserved by the transformation.

The general strategy:
(a) Transform Case 1 to Case 2 and Case 3 to Case 4.
(b) Solve Case 2 and Case 4, respectively.

Deal with conflicts

Case 1: x’s sibling w is red.

1. Since w must have black children, swap the colors of w and p(x),
2. and then perform a left-rotation on p(x) without violating any of red-black tree properties.
3. The new sibling of x, which is one of the w’s children prior to the rotation, now is black. Thus, Case 1 has been converted to Case 2.

Cases 2, 3, and 4 occur when w is black, they are distinguished by the colors of w′s children.

Case 2: x’s sibling w is black, and both children of node w are black.
Since w is black, take one black off from both x and w, leaving x with only one black and leaving (or coloring) w red.

To compensate for removing one black from x and w, we add an extra black to p(x), which originally either red or black. If p(x) was red, now it is black, done; otherwise, node p(x) now becomes new node x, i.e., p(x) now has double black on it.

Notice that the node x (with double black) has been pushed one-layer higher, where a layer near to the tree root is a higher layer.

The above procedure continues until it reaches the tree root or is converted into one of the other three cases. If the tree root becomes double black, remove the extra black, and Property 5 of the RBT is still held.

This case takes O(h) time where h is the height of the RBT.

Case 3: x’s sibling w is black, w’s left child is red while w’s right child is black.
Swap the colors of w and its left child left(w), then perform a right rotation on w without violating any of the red-black tree properties.

The verification of the red-black tree properties can be done by checking whether any path passes through w still contains the same number of black nodes from its source node to a leaf before and after this transformation.

The new sibling w of x now is a black node with a red right child, this becomes Case 4.

Case 4: x’s sibling w is black, and the right child of w is red.

By performing some color changes and performing a left rotation on node p(x), the extra black of x can be removed, making it a single black without violating any red-black tree properties.

Analysis on Deletion in red-black trees

Theorem: Given a RBT containing N nodes, the removal of one node from it takes OlogN) time if the resulting tree is still a RBT.

The sketch of the proof: Since the height of any red-black tree is O(logN),each of Cases 1, 3 and 4 takes O(1) time by performing a left or right rotation and re-coloring, while Case 2 takes O(h) time, where h is the height of the red-black tree and h = O(logN) by the lemma in slides 5-6 of Lecture 13. Thus, the deletion operation takes O(logN) time.