Red-black trees
A red-black tree is a binary search tree that rebalances itself. A few coloring rules keep its height in O(log n), whatever the insertion order.
Why a self-balancing tree?
In a plain binary search tree (BST), inserting 1, 2, 3, 4, 5 in that order produces a "linked list": every node has a single right child. Searching becomes O(n). A red-black tree prevents this by fixing the shape of the tree after every insertion and deletion.
The properties
- It is a binary search tree.
- Every node is either red or black.
- The root is always black.
- NULL pointers (empty leaves) count as black nodes.
- A red node always has two black children: there are never two reds in a row.
- From any node, every path down to a NULL contains the same number of black nodes (the black height).
Together, these rules guarantee that the height never exceeds 2 · log₂(n + 1). The longest path (red, black, red, black…) is at most twice as long as the shortest one (all black).
Rotations
A rotation rearranges three nodes without breaking the BST order. It moves a child up and its parent down.
A rotation only touches three pointers: it runs in O(1).
Insertion
First insert as in a BST, then color the new node red. A red node does not change the black height; the only possible problem is two reds in a row. We then look at the parent and the uncle (the parent's sibling).
| Situation | Fix |
|---|---|
| Case #1: black parent | Nothing to do. |
| Case #2: red parent, black uncle, straight line | Parent → black, grandparent → red, then rotate the grandparent away from the line. Done. |
| Case #2b: red parent, black uncle, zig-zag | Rotate the parent to get a straight line; the old parent becomes the new node, then apply case #2. |
| Case #3: red parent, red uncle | Parent and uncle → black, grandparent → red. Repeat from the grandparent. |
If the root ends up red (after a case #3), recolor it black.
Example: insert 10, 20, 30, 15, 12
- 10 becomes the black root.
- 20: its parent 10 is black → case #1.
- 30: parent 20 is red, uncle NULL (black), and 10 → 20 → 30 is a straight line to the right → case #2. 20 becomes black, 10 becomes red, rotate left at 10. Result: 20 (black) with 10 and 30 (red).
- 15: parent 10 is red, uncle 30 is red → case #3. 10 and 30 become black, 20 becomes red, then black again since it is the root.
- 12: parent 15 is red, uncle NULL is black, and 10 → right → left is a zig-zag → case #2b. Rotate right at 15, then case #2: 12 becomes black, 10 becomes red, rotate left at 10.
A NULL counts as a black node. A missing uncle therefore always means case #2 or #2b.
Deletion
Deleting a red node never causes trouble. Deleting a black node removes a black from a path: that spot is marked double black, a node that "counts twice", and the double black is then eliminated.
Basic rules
- Rule #1: the node is a red leaf → remove it.
- Rule #2: the node has one child → the child (necessarily red) takes its place and becomes black.
- Rule #3: the node has two children → copy the value of its predecessor (the maximum of the left subtree), then delete the predecessor with whichever rule applies to it.
- Rule #4: the node is a black leaf → replace it with a double black NULL.
Eliminating the double black
Look at the double black's sibling, then at the sibling's children. To avoid mixing up sides, we talk about the far child (on the side opposite the double black) and the near child.
| Case | Situation | Fix |
|---|---|---|
| 4.1 | Red sibling | Sibling → black, parent → red, rotate the parent toward the double black. Not finished: check again with the new sibling. |
| 4.2 | Black sibling, both its children black | Sibling → red. If the parent was red, it becomes black and we are done; otherwise it becomes double black and we continue from it. |
| 4.3 | Black sibling, near child red, far child black | Sibling → red, near child → black, rotate the sibling outward. Not finished: leads to case 4.4. |
| 4.4 | Black sibling, far child red | Far child → black, sibling → parent's color, parent → black, rotate the parent toward the double black. Done. |
Common pitfalls
Successor or predecessor? Many courses use the successor for rule #3. Here, we use the predecessor. Both are valid, but they lead to different cases: check your course's convention.
Cases 4.1 and 4.3 never finish. Another case must always follow them.
Order of operations. In a case with a rotation, recolor first, then rotate. Doing it the other way gives the same final tree, but makes the reasoning harder to follow.
If the far child is red, it is case 4.4, even when the near child is red too.
Complexity
| Operation | Worst case |
|---|---|
| Search | O(log n) |
| Insertion | O(log n), at most 2 rotations |
| Deletion | O(log n), at most 3 rotations |
In Java, TreeMap and TreeSet are implemented with a red-black tree; in C++, so is std::map in most standard libraries.