12Module · Goodrich Ch. 11.4–11.6

Week 12 — Search Trees II

Splay trees and amortized splaying, (2,4) multiway search trees, and red-black trees.

Self-adjusting and multiway search trees with amortized analysis.

Theory

Splay trees move recently accessed nodes to the root through rotations, achieving O(log n) amortized cost per operation without storing balance info.

(2,4) trees are multiway search trees where every internal node has 2, 3, or 4 children; all leaves are at the same depth, giving O(log n) operations.

Red-black trees are a binary-tree encoding of (2,4) trees and the backbone of std::map, java.util.TreeMap, and the Linux kernel's CFS scheduler.

Key points

Splay tree splays after every access — both reads and writes.
Red-black invariants: root black, no two consecutive reds, every root-to-NIL path has equal black-height.
Multiway (2,4) trees motivate B-trees for external memory.

Code examples

Splay operation (zig-zig / zig-zag) sketch

# Conceptual: splay(x) moves x to the root via a sequence of:
#   zig         — x is child of root
#   zig-zig     — x and parent are both left (or both right) children
#   zig-zag     — x and parent are opposite children
#
# After every access (search/insert/delete) we splay the touched node
# to amortize the cost of a long path over future operations.

Red-black recolor / rotate after insert

RED, BLACK = 0, 1

def fix_after_insert(tree, z):
    while z.parent and z.parent.color == RED:
        if z.parent is z.parent.parent.left:
            y = z.parent.parent.right
            if y and y.color == RED:           # case 1: recolor
                z.parent.color = BLACK
                y.color = BLACK
                z.parent.parent.color = RED
                z = z.parent.parent
            else:
                if z is z.parent.right:        # case 2: rotate
                    z = z.parent
                    rotate_left(tree, z)
                z.parent.color = BLACK         # case 3
                z.parent.parent.color = RED
                rotate_right(tree, z.parent.parent)
        else:
            ...  # mirror image
    tree.root.color = BLACK