red-black tree

Red-black tree is a type of self-balancing binary search tree.

Insertion

Inserting a node N into a red-black tree starts with following the standard BST insertion process. Afterwards, we may need to do a series of rotations and color-changing in order to maintain red-black tree properties.

• Let N be the node we just inserted. P is N’s parent. G is N’s grandparent. U is its uncle (parent’s sibling).
• If N is root, set color to black and exit.
• If N is red
  • If P and U are red
    • set P, U to black
    • If G is not root, set G to red #status/to-do

Deletion

Deleting a node N from a red-black tree can also be somewhat involved.

• Case: N is the root and does not have a non-NIL child
  • Solution: Simply remove N. The tree will be empty afterwards.
• Case: N has two non-NIL children
  • Let y be the minimum element in the right subtree (no other element ordered between y and N).
  • By definition, y does not have a left non-NIL child, though it may have a right non-NIL child.
  • Solution: Exchange N and y (parent-child relationships and colors; also check if N is root). Now we can just remove y. If y is red and has no non-NIL child, simply remove it. If y is red and has a non-NIL right child, replace y with that child (remember to color red) and delete y. If y is black, see the other cases.
• Case: N is red and has fewer than 2 non-NIL children
  • Solution: Simply remove N.
  • We can deduce that N must have no non-NIL child, i.e. a red node that does not have two non-NIL children must have no non-NIL child. If some N has exactly one non-NIL child C, then C must be red, since if it were black, N’s NIL child would have a different black depth than C’s NIL descendants, which violates requirement 4. In the one non-NIL child case, N cannot be red, because a red child would violate requirement 3.
• Case: N is black and has exactly one non-NIL child C, and C is red
  • Solution: Paint C black and replace N with C.
• Case: N is black, not root, and has no non-NIL child
  • It’s complicated;to-do