Red-Black Tree Delete
Deleting a red node never breaks a Red-Black invariant. Deleting a black node creates a "double-black" deficit that must be pushed up or resolved via recolouring/rotation depending on the sibling's colour and its children's colours.
- Category
- Trees
- Time complexity
- O(log n)
- Space complexity
- O(1) per fixup
Pseudocode
delete as in a normal BST if removed node was red: done if black: fix the double-black — recolour sibling/parent or rotate, depending on sibling shape
Reference implementation
# delete; if removed node was black, fix double-black:
if sibling.color == BLACK and both_nephews_black:
sibling.color = RED # push double-black up to parent
else:
rotate(parent) # + recolor to absorb it locally