Self-Balancing Trees

Two different strategies, guaranteed worst-case balance and self-adjusting recency, for keeping a BST's height from ever collapsing into a linked list

Introduction

Lesson 8 ended on an open problem: a plain BST's O(h) guarantee is worthless if nothing stops h from drifting toward n, exactly what happened when we inserted already-sorted data and got a height-4 chain out of 5 nodes. Self-balancing trees close that gap. This lesson covers two very different strategies for doing it: Red-Black trees, which use a coloring rule to guarantee height never exceeds roughly 2 log₂(n) no matter what, and splay trees, which don't guarantee anything about any single operation, but instead drag whatever you just accessed straight to the root, so the things you use most become the fastest to reach again.

The Red-Black Invariant

A red-black tree is a BST where every node is colored either red or black, and five rules are always maintained:

  1. Every node is red or black
  2. The root is always black
  3. Every missing child (a "leaf") counts as black
  4. A red node's children are always both black, no two reds in a row on any path
  5. Every path from a node down to any of its leaves passes through the same number of black nodes

Rules 4 and 5 are the ones doing the real work. Together they guarantee the longest possible root-to-leaf path is never more than twice the length of the shortest one, since red nodes can never cluster and black nodes are evenly spread. That caps the height at roughly 2 log₂(n), still O(log n), just with a slightly larger constant than a perfectly balanced tree.

Rotations: The Shared Primitive

Both trees in this lesson, and AVL trees too, restore their invariant using the same basic move: a rotation. It re-parents a small group of nodes without touching the BST ordering invariant from Lesson 8, everything left of a node stays left of it, everything right stays right. A right rotation on x pulls its left child y up into x's spot and pushes x down to become y's right child. The only subtree that switches parents is B, which moves from y's right to x's left:

Before: rotate_right(x)

xyCAB

After: rotate_right(x)

yAxBC

Reading either tree left to right gives the identical in-order sequence A, y, B, x, C, which is exactly why a rotation never breaks the BST ordering (A, B, C are arbitrary subtrees). The two amber nodes are the only ones that change roles. rotate_left is the exact mirror image, pulling a right child up instead:

def rotate_left(tree, x) -> None:
    y = x.right
    x.right = y.left
    if y.left is not None:
        y.left.parent = x
    y.parent = x.parent
    if x.parent is None:
        tree.root = y
    elif x is x.parent.left:
        x.parent.left = y
    else:
        x.parent.right = y
    y.left = x
    x.parent = y

def rotate_right(tree, x) -> None:
    y = x.left
    x.left = y.right
    if y.right is not None:
        y.right.parent = x
    y.parent = x.parent
    if x.parent is None:
        tree.root = y
    elif x is x.parent.right:
        x.parent.right = y
    else:
        x.parent.left = y
    y.right = x
    x.parent = y

A rotation is O(1): it only rewires a handful of pointers. Every rebalancing operation in this lesson is built entirely out of calls to these two functions.

How Red-Black Trees Rebalance on Insert

A new node is always inserted red (inserting it black would instantly break rule 5). If its parent is already black, nothing else needs to happen. If the parent is red, rules 4 just broke, and fixing it depends on the color of the node's "uncle" (its parent's sibling):

Case 1: Uncle is redRecolor parent and uncle black, grandparent red, then re-check from the grandparent
Case 2: Uncle is black, "triangle" shapeRotate the parent to straighten it into a line, which becomes Case 3
Case 3: Uncle is black, "line" shapeRecolor parent black and grandparent red, then rotate the grandparent

Case 1 is pure recoloring, no rotation needed:

# Case 1: the new node's "uncle" is red.
# Recolor and push the problem up to the grandparent instead of rotating.
if uncle_is_red:
    parent.color = BLACK
    uncle.color = BLACK
    grandparent.color = RED
    node = grandparent   # keep checking from here up

Cases 2 and 3 use the rotations from the previous section instead. Rather than write out all six mirrored cases here, let's just watch the algorithm handle the exact scenario that broke a plain BST in Lesson 8: inserting 1, 2, 3, 4, 5 in already-sorted order.

Red-Black Tree After Inserting 1-5 in Order

2black, root1black4black3red5red

Figure 1: Height 2, versus the height-4 straight line the same input produced in Lesson 8

Behind the scenes: inserting 3 triggers Case 3 (a rotation, since 3's uncle, 1's missing left child, is black), inserting 4 triggers Case 1 (a recolor, since its uncle, node 1, is red), and inserting 5 triggers Case 3 again. Three small local fixes, and the same sorted input that degenerated into a straight line in Lesson 8 instead lands at height 2.

Splay Trees: Balance Through Access Pattern

A splay tree keeps no color bits and enforces no height guarantee at all. Instead, every single insert or search ends by dragging the node you just touched all the way up to the root, using one of three rotation patterns depending on its position relative to its grandparent:

ZigThe node's parent is already the root, one rotation finishes it
Zig-zigNode and parent lean the same direction, rotate the grandparent, then the parent
Zig-zagNode and parent lean opposite directions, rotate the parent, then the (new) parent again
Zig-zig Is Not Two Separate Zigs

It's tempting to think "just rotate up one level at a time until you reach the root." That's a different, weaker algorithm. The zig-zig pattern specifically rotates the grandparent first, then the parent, which is what gives splay trees their balancing guarantee. Naive repeated single rotations don't have the same provable performance.

Building a Splay Tree

class SplayNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "SplayNode | None" = None
        self.right: "SplayNode | None" = None
        self.parent: "SplayNode | None" = None
class SplayTree:
    def __init__(self) -> None:
        self.root: "SplayNode | None" = None

    def _rotate_left(self, node: SplayNode) -> None:
        pivot = node.right
        node.right = pivot.left
        if pivot.left is not None:
            pivot.left.parent = node
        pivot.parent = node.parent
        if node.parent is None:
            self.root = pivot
        elif node is node.parent.left:
            node.parent.left = pivot
        else:
            node.parent.right = pivot
        pivot.left = node
        node.parent = pivot

    def _rotate_right(self, node: SplayNode) -> None:
        pivot = node.left
        node.left = pivot.right
        if pivot.right is not None:
            pivot.right.parent = node
        pivot.parent = node.parent
        if node.parent is None:
            self.root = pivot
        elif node is node.parent.right:
            node.parent.right = pivot
        else:
            node.parent.left = pivot
        pivot.right = node
        node.parent = pivot

    def _splay(self, node: SplayNode) -> None:
        while node.parent is not None:
            grandparent = node.parent.parent
            if grandparent is None:
                # Zig: parent is the root, one rotation finishes the job
                if node is node.parent.left:
                    self._rotate_right(node.parent)
                else:
                    self._rotate_left(node.parent)
            elif node is node.parent.left and node.parent is grandparent.left:
                # Zig-zig: node and parent are both left children
                self._rotate_right(grandparent)
                self._rotate_right(node.parent)
            elif node is node.parent.right and node.parent is grandparent.right:
                # Zig-zig: node and parent are both right children
                self._rotate_left(grandparent)
                self._rotate_left(node.parent)
            elif node is node.parent.right and node.parent is grandparent.left:
                # Zig-zag: node and parent are on opposite sides
                self._rotate_left(node.parent)
                self._rotate_right(node.parent)
            else:
                self._rotate_right(node.parent)
                self._rotate_left(node.parent)

    def insert(self, value: int) -> None:
        if self.root is None:
            self.root = SplayNode(value)
            return
        current = self.root
        while True:
            if value < current.value:
                if current.left is None:
                    current.left = SplayNode(value)
                    current.left.parent = current
                    self._splay(current.left)
                    return
                current = current.left
            elif value > current.value:
                if current.right is None:
                    current.right = SplayNode(value)
                    current.right.parent = current
                    self._splay(current.right)
                    return
                current = current.right
            else:
                self._splay(current)   # already present, just bring it to the root
                return

    def search(self, value: int) -> bool:
        current = self.root
        while current is not None:
            if value == current.value:
                self._splay(current)
                return True
            current = current.left if value < current.value else current.right
        return False
tree = SplayTree()
for value in [5, 3, 8, 1, 4]:
    tree.insert(value)

print(tree.root.value)     # the most recently inserted value

tree.search(1)
print(tree.root.value)     # 1 just got splayed straight to the root
Expected Output:
4
1

The zig-zig pattern is easiest to see starting from a worst-case shape: a left-skewed chain, exactly the failure case from Lesson 8. Splaying the deepest node still finds it in one pass down and rebuilds the tree on the way back up:

# A worst-case left-skewed chain, exactly Lesson 8's degenerate shape
#   5
#  /
# 4
# /
#3
# /
#2
# /
#1
tree = SplayTree()
node_5 = SplayNode(5)
node_4 = SplayNode(4)
node_3 = SplayNode(3)
node_2 = SplayNode(2)
node_1 = SplayNode(1)
tree.root = node_5
node_5.left, node_4.parent = node_4, node_5
node_4.left, node_3.parent = node_3, node_4
node_3.left, node_2.parent = node_2, node_3
node_2.left, node_1.parent = node_1, node_2

tree._splay(node_1)
print(tree.root.value)
Expected Output:
1

After Splaying the Deepest Node to the Root

1new root4253

Figure 2: Two zig-zig steps turned a 5-deep chain into a tree of height 3, with 1 now instant to reach

One splay doesn't guarantee a perfectly balanced tree, notice 3 is still three levels deep. What it guarantees is that whatever you access next gets cheaper, which is a fundamentally different promise than a red-black tree makes.

Red-Black vs Splay: Two Different Promises

Red-Black TreeSplay Tree
Per-operation guaranteeWorst-case O(log n), alwaysNo single-operation guarantee
Long-run guaranteeO(log n) per operationAmortized O(log n) per operation
Extra bookkeeping1 color bit per nodeNone, just rotations on access
Best suited forPredictable latency (databases, kernels)Skewed, repeat-heavy access patterns (caches)

"Amortized" here means the same thing it meant for Lesson 2's dynamic array resizing: a single splay can touch O(n) nodes in the worst case, but a proof based on tracking a potential function shows that cost is always paid back by cheaper operations later, averaging out to O(log n) across any sequence of operations. Unlike a red-black tree, though, no single splay ever comes with an individual guarantee, only the running average does.

Key Takeaways

  • Red-black trees bound height with a coloring rule - no two consecutive red nodes, and every path has equal black-height
  • Rotations are the shared primitive - O(1) pointer rewiring that preserves the BST ordering invariant from Lesson 8
  • Red-black insertion fixup is either a recolor (Case 1) or a rotation (Cases 2-3), both bounded by the tree's height
  • Splay trees move whatever you just accessed to the root, using zig-zig/zig-zag double rotations, not naive repeated single rotations
  • Red-black trees guarantee every operation is fast; splay trees only guarantee the average is - pick based on whether you need predictable latency or benefit from access locality
Data Structures & AlgorithmsLesson 10