Other balanced trees: red-black, 2-3, B-tree, splay

AVL is not the only balanced tree. The one used most in practice is the red-black tree: Java’s TreeMap and TreeSet classes keep a red-black tree inside. Databases and file systems use B-trees. This week we see four structures. In the exam, red-black questions are “insert in order, draw with colors”, and 2-3 / B-tree questions are “show the splits”. The splay tree usually comes up as a concept question.

They all have the same goal: keeping the height of the tree at O(log n). Their methods differ:

The rules of a red-black tree

Every node is red or black. The tree is a BST and obeys these rules:

1. The root is black.
2. Null links (empty leaves) count as black.
3. The children of a red node cannot be red (no two reds in a row).
4. Every path from a node down to any null has the same number of black nodes. This number is called the black height (black-height).

Why does it work? By rule 4, every path has the same number of blacks. By rule 3, on the longest path the reds can only be scattered one by one between the blacks. So the longest path is at most twice the shortest path. From this we get $height \le 2\log_2(n+1)$.

         20B
        /   \
      10B    30B        2 blacks on every path
        \                (excluding nulls)
        15R

Insertion: the cases

Insertion is first a normal BST insertion. The new node is always inserted red. Why red? If you inserted black, the number of blacks on that path would increase and rule 4 would break everywhere. Inserting red breaks at most rule 3, and fixing that is easy locally.

Call the new node x, its parent p, its grandparent g, and the other child of the grandparent the uncle u.

A null uncle counts as black. The case with a rotation happens at most once and insertion ends there. Recoloring can repeat up to the root, but each step is O(1), so the total is O(log n).

PITFALL · Look at the uncle, not the sibling. The decision is made by the color of the parent’s sibling. The new node’s own sibling decides nothing.

Worked example: 30, 20, 10, 25, 27, 5, 1

+30: the root, black. +20: the parent is black, done. +10: the parent 20 is red, the uncle (the right of 30) is null, so black. The path is left-left: a right rotation at 30, 20 becomes black, 30 becomes red.

    30B           20B
    /            /   \
  20R    ==>   10R    30R
  /
10R

+25: red, to the left of 30. The parent 30 is red, the uncle 10 is red: recolor. 10 and 30 become black, 20 becomes red, then black again because it is the root.

       20B
      /   \
    10B    30B
          /
        25R

+27: to the right of 25. The parent 25 is red, the uncle (the right of 30) is null: black. The path from the grandparent (30) is left-right, so x is inside. First a left rotation at 25 (27 moves up), then a right rotation at 30. 27 becomes black, 30 becomes red.

       20B
      /   \
    10B    27B
          /   \
        25R    30R

+5: to the left of 10, the parent is black: done. +1: to the left of 5. The parent 5 is red, the uncle (the right of 10) is null: black. The path is left-left: a right rotation at 10, 5 becomes black, 10 becomes red.

         20B
       /     \
     5B       27B
    /  \     /   \
  1R   10R  25R   30R

The trace printed by the program (the colored level order after each insertion):

+30 -> 30B
+20 -> 30B 20R
+10 -> 20B 10R 30R
+25 -> 20B 10B 30B 25R
+27 -> 20B 10B 27B 25R 30R
+5 -> 20B 10B 27B 5R 25R 30R
+1 -> 20B 5B 27B 1R 10R 25R 30R

On every root-to-null path there are 2 black nodes (excluding nulls), and there is no red-red.

TIP · The textbook version. The textbook (Weiss) describes top-down red-black insertion: while going down, it recolors in advance every node with two red children, so there is no need to go back up. The resulting tree may sometimes differ. In the exam, check which version is asked for; the traces on this page were made with the bottom-up version.

2-3 trees

In a 2-3 tree every internal node is either a 2-node (1 key, 2 children) or a 3-node (2 keys, 3 children). All leaves are at the same depth. There are no rotations; balance is kept by splitting.

The insertion rule:

1. Find the leaf where the key belongs, and insert it there in order.
2. If the leaf now has 3 keys, there is an overflow: the median key moves up to the parent, and the remaining two become two separate nodes.
3. If the parent overflows too, the same operation repeats above. If the root overflows, a new root is created and the tree grows by one level.

The tree grows upward. That is why all leaves always stay at the same depth.

+10 +20      +30: [10 20 30] overflows
[10 20]         [20]
               /    \
            [10]    [30]

+40 +50:  [30 40 50] overflows, 40 moves up
          [20 40]
         /   |   \
      [10] [30]  [50]

2-3-4 trees and the red-black connection

A 2-3-4 tree also allows a 4-node (3 keys, 4 children). Insertion is usually done top-down: every 4-node met on the way down is split in advance, so there is guaranteed room when the leaf is reached.

The real point: every 2-3-4 tree corresponds one-to-one to a red-black tree. A 2-node is a single black node. A 3-node is a black node + one red child. A 4-node is a black node + two red children. The red-black case “uncle red, recolor” is the splitting of a 4-node in the 2-3-4 tree. The black height being the same everywhere corresponds to all leaves being at the same depth in a 2-3-4 tree.

B-trees

A B-tree is a generalization of the 2-3 idea. In a B-tree of order m:

• Every node holds at most m - 1 keys and m children.
• Every internal node except the root has at least $\lceil m/2 \rceil$ children (that is, at least $\lceil m/2 \rceil - 1$ keys).
• All leaves are at the same depth.

A 2-3 tree is a B-tree with m = 3. In real systems m is in the hundreds, because a node is matched to a disk block (for example 4 KB). Reading a block from disk is much slower than comparing hundreds of keys in memory. Since the height is about $\log_m n$, with m = 200 millions of records fit in 3-4 levels.

A trace of insertion with m = 5 (a node holds at most 4 keys; when the 5th key arrives, the median moves up):

+12 +4 +30 +8 -> [4, 8, 12, 30]
+22 -> overflow, 12 moves up
  L0: [12]
  L1: [4, 8] [22, 30]
+1 +17 +26 +3 ->
  L0: [12]
  L1: [1, 3, 4, 8] [17, 22, 26, 30]
+40 -> the right leaf overflows, 26 moves up
  L0: [12, 26]
  L1: [1, 3, 4, 8] [17, 22] [30, 40]

Databases generally use a B+ tree: all data stays in the leaves, the internal nodes only guide the way, and the leaves are linked to each other (range queries become fast).

Splay trees

A splay tree keeps no balance information (height, color) at all. Instead, after every access (search, insert), the accessed node is moved to the root with rotations (splaying). The idea: data used recently will be accessed again soon, so keeping it at the root pays off.

There are three kinds of steps (x is the accessed node, p the parent, g the grandparent):

A single operation can take O(n) (accessing the bottom of a chain). But since a zig-zig step roughly halves the path, the total cost of m consecutive operations is O(m log n). This is called amortized O(log n). It is very fast in practice in cache-like usage.

access 3 in 10(5(3,7),15): zig-zig
       10              3
      /  \              \
     5    15    ==>      5
    / \                   \
   3   7                   10
                          /  \
                         7    15

Common mistakes