5.2.3 Red-Black Trees: Deletion

See Figures 4.33 - 4.37.

First, search for an element to be deleted.

• If the element to be deleted is in a node with only left child, swap this node with the one containing the largest element in the left subtree. (This node has no right child).
• If the element to be deleted is in a node with only right child, swap this node with the one containing the smallest element in the right subtree (This node has no left child).
• If the element to be deleted is in a node with both a left child and a right child, then swap in any of the above two ways.

While swapping, swap only the keys but not the colours.

• The item to be deleted is now in a node having only a left child or only a right child. Replace this node with its sole child. This may violate red constraint or black constraint. Violation of red constraint can be easily fixed.
• If the deleted node is block, the black constraint is violated. The removal of a black node y causes any path that contained y to have one fewer black node.
• Two cases arise:

1.

The replacing node is red, in which case we merely colour it black to make up for the loss of one black node.

2.

The replacing node is black.


In this case, we ``bubble'' the ``shortness'' up the tree by repeatedly applying the recolouring transformation of Figure 5.16 until it no longer applies.

Then we perform the transformation in Figure 5.17 if it applies, followed if necessary by one application of Figure 5.18, Figure 5.19, or Figure 5.20.
• RB-deletion requires O(log n) recolourings and at most 3 rotations.
• See Figures 5.21 and 5.22 for two examples.