Red Black Tree
A Red-Black tree is a self-balancing binary search tree where each node carries an extra one-bit color attribute: red or black. Five invariants define a va...
Five Properties That Guarantee Balance
A Red-Black tree is a self-balancing binary search tree where each node carries an extra one-bit color attribute: red or black. Five invariants define a valid Red-Black tree. First, every node is either red or black. Second, the root is black. Third, every null leaf (a sentinel nil node) is black. Fourth, if a node is red, both its children must be black (no two consecutive red nodes on any path). Fifth, all paths from any node to its descendant null leaves must contain the same number of black nodes. This last property is called the black-height invariant.
These five rules together guarantee that the longest path from root to a leaf is at most twice as long as the shortest path. Since the shortest path has only black nodes and the longest alternates red and black, the ratio is at most two to one. This ensures the tree height is O(log N), keeping all operations efficient.
Red-Black trees are used in the C++ STL map and set, Java TreeMap and TreeSet, and Linux kernel process scheduling structures — making them one of the most practically deployed tree structures in existence.
Insertion, Recoloring, and Rotation
Insertion in a Red-Black tree begins exactly like a BST insertion: find the correct leaf position and attach the new node. The new node is always colored red. This may violate the fourth property (no consecutive reds) if the parent is also red. The fix depends on the color of the uncle node (the sibling of the parent).
If the uncle is red, recolor the parent and uncle to black and the grandparent to red, then move the violation check up to the grandparent. If the uncle is black, perform a rotation (left-left, right-right, left-right, or right-left case — matching AVL). After the rotation, recolor the rotated nodes appropriately. The process continues up the tree until no violation exists or the root is reached (the root is then recolored black).
Deletion is more complex: it handles a double-black node that arises when a black node is removed. The fix involves examining sibling and nephew colors and performing at most three rotations. Both insertion and deletion run in O(log N) time with at most two rotations for insertion and three for deletion — fewer than AVL in the worst case.
Worked Example and Practical Comparison
Worked example: insert 10, 20, 30 into an empty Red-Black tree. Insert 10 as root, color black. Insert 20 as right child of 10, color red — no violation since parent is black. Insert 30 as right child of 20, color red — violation, parent 20 is red and uncle (left child of 10) is null (black). This is a right-right case. Left-rotate at 10: 20 becomes the new root, 10 becomes its left child, 30 stays its right child. Recolor: 20 becomes black, 10 becomes red. The tree now satisfies all five properties with height one.
The black-height of the resulting tree is one (not counting null sentinels). All paths from root to null leaves pass through exactly one black node (the root itself, since 10 and 30 are red).
Interview tip: you rarely need to implement a Red-Black tree from scratch in an interview. Instead, be prepared to explain the color invariants and why they ensure O(log N) height. Mention that Red-Black trees guarantee O(log N) worst-case time for insert, delete, and search, making them strictly better than plain BSTs for dynamic datasets where the insertion order cannot be controlled.