Red Black Tree

Red-Black Properties

A Red-Black Tree is a BST with additional color property (red/black). Properties: (1) Every node is red or black. (2) Root is black. (3) All leaves (NIL) are black. (4) Red nodes have black children (no two reds in a row). (5) Every path from node to descendant leaves has same number of black nodes. Guarantees height ≤ 2*log₂(n+1).

Rotations

Insertion Fixup

Insert as red node in BST. If parent is black, done. If parent is red, violations: (1) parent red, uncle red → recolor parent, uncle, grandparent. (2) parent red, uncle black, node is right child → left rotate parent. (3) parent red, uncle black, node is left child → recolor, right rotate grandparent. Repeat until root or parent black.

Deletion

Deletion more complex. Replace node with successor/predecessor if has two children. If deleted node was black, fixup needed for double-black violation. Cases: sibling red → rotate, recolor; sibling black with red child → rotate sibling; sibling black with black children → recolor sibling, move double-black up.