Red-Black Tree Deletion

This page contains information about Red-Black Tree (RBT) deletion.

RBT deletion uses the same algorithm as a BST, but with extra cases to make sure the properties of a RBT is maintained.

If the deleted node and replacement node is red:

If the deleted node is black and the replacement node is red:

If the deleted node is black and the replacement isn't red:

It gets a bit more complex. UW Madison uses a 'Black marker' to mark a node as having extra blackness to make up for the black node we just removed.

There are 4 cases to resolve a node with a black marker.

Case 1: The "far" niece is red (pictured as the first case, second step in the diagram).

  1. Rotate the parent and sibling nodes
  2. Colorswap the parent and sibling nodes
  3. Recolor the "far" niece red

This will resolve the black marker completely, leaving you with a correct RBT.

Case 2: Sibling is black and nieces are null or black (pictured as the second case in the diagram).

  1. Recolor sibling node red
  2. Move black marker up to parent node

If the parent node is red, then the black marker will turn it red. Otherwise, you need to repeat the procedure with the parent node as the new node

Case 3: The sibling is red (pictured as the third case in the diagram).

  1. Rotate parent node and sibling node
  2. Colorswap parent node and sibling node
  3. Run the black marker node through Case 2

Case 4: The "close" niece is red (pictured as the first case, first step in the diagram).

  1. Rotate "close" niece and sibling nodes
  2. Colorswap "close" niece and sibling nodes
  3. Run the black marker node through Case 1

For more information...

Check out the Wikipedia article!