Balanced
Trees

The promise of binary search trees

A BST offers O(log n) search, insert, and delete — but only when the tree is balanced. The height determines the worst-case cost of every operation.

• Balanced tree — height O(log n), operations are fast
• Degenerate tree — height O(n), operations degrade to a linked list
• Balancing guarantees a logarithmic height bound regardless of insertion order
• Without balancing, sorted input produces the worst case every time

The cost of imbalance

Binary Search Tree invariant

For every node x: all keys in the left subtree are less than x.key, and all keys in the right subtree are greater.

Balanced BST:          Degenerate BST:

       50                  10
      /  \                   \
    30    70                  20
   / \   / \                   \
  20 40 60 80                   30
                                 \
                                  40
                                   \
                                    50

Why sorted input kills a plain BST

Inserting [10, 20, 30, 40, 50] into a naive BST produces a right-skewed chain. Every operation becomes O(n).

• Search — must traverse the entire chain
• Insert — always appends at the deepest point
• Delete — restructuring offers no height reduction

Definition

An AVL tree (Adelson-Velsky & Landis, 1962) is a BST where, for every node, the heights of the left and right subtrees differ by at most 1.

Balance factor

BF(node) = height(left subtree) - height(right subtree)

Height guarantee

Strict balance

LL Rotation (Right Rotation)

  BF=+2                  BF=0
    z                      y
   / \     rotate         / \
  y   T4  right(z)       x   z
 / \     -------->      / \ / \
x   T3                T1 T2 T3 T4
/ \
T1 T2

Node y becomes the new root. z becomes y's right child. T3 moves from y's right to z's left.

RR Rotation (Left Rotation)

BF=-2                   BF=0
  z                       y
 / \     rotate          / \
T1  y   left(z)         z   x
   / \  -------->      / \ / \
  T2  x              T1 T2 T3 T4
     / \
    T3 T4

Mirror of LL. Node y becomes root. z becomes y's left child.

LR Rotation (Left-Right)

Step 1: Left rotate y     Step 2: Right rotate z

    z          z                  x
   / \        / \                / \
  y   T4 -> x   T4  ->        y   z
 / \        / \               / \ / \
T1  x      y   T3           T1 T2 T3 T4
   / \    / \
  T2 T3  T1 T2

First rotate left at y, then rotate right at z.

RL Rotation (Right-Left)

Step 1: Right rotate y    Step 2: Left rotate z

  z            z                  x
 / \          / \                / \
T1  y   ->  T1   x    ->      z   y
   / \          / \           / \ / \
  x   T4      T2  y         T1 T2 T3 T4
 / \              / \
T2 T3            T3 T4

Mirror of LR. First rotate right at y, then rotate left at z.

Insertion algorithm

1. Standard BST insert at the correct leaf position
2. Walk back up the path to the root, updating heights
3. At the first node with |BF| = 2, perform the appropriate rotation
4. At most one rotation (single or double) is needed per insertion

Deletion algorithm

1. Standard BST delete (in-order successor for 2-child case)
2. Walk back up the path, updating heights
3. At each node with |BF| = 2, perform the appropriate rotation
4. Unlike insertion, deletion may require O(log n) rotations

Complexity

The five properties

Height guarantee

Black-height

The black-height of a node is the number of black nodes on any path from that node (exclusive) down to a NIL leaf. Property 5 ensures this is well-defined.

Rotation guarantee

Why colours?

The colour constraints encode balance information implicitly. Property 4 (no consecutive reds) and Property 5 (equal black-height) together force the longest path to be at most twice the shortest.

Intuition via 2-3-4 mapping

Every Red-Black tree is isomorphic to a 2-3-4 tree:

Colour constraints at a glance

Insertion procedure

1. Standard BST insert; colour the new node red
2. If the parent is black, done — no violation
3. If the parent is red, check the uncle (parent's sibling)

Case analysis (parent is red)

Rotation count

Overview

Deletion is the most complex Red-Black operation. Removing a black node reduces the black-height on that path, creating a "double-black" deficit.

Procedure

1. Standard BST delete (find in-order successor if needed)
2. If removed node was red, done
3. If black, replacement carries extra "black" (double-black)
4. Fix up the double-black by case analysis

Double-black fix-up cases

Definition

A 2-3 tree is a perfectly balanced search tree where every internal node has either 2 or 3 children, and all leaves are at the same depth.

Node types

Insertion

1. Search down to the correct leaf
2. Add the key to the leaf node
3. If overflow (3 keys), split: push middle key up to parent
4. Splitting may cascade up; if root splits, height increases by 1

Properties

Extension of 2-3 trees

A 2-3-4 tree adds a 4-node (3 keys, 4 children). This directly corresponds to a Red-Black tree.

Insertion strategies

• Bottom-up: insert, then split overflowing nodes back up
• Top-down: pre-emptively split any 4-node on the way down — guarantees the leaf has room

Equivalence to Red-Black trees

2-node:    [B]          Black node, no red children
3-node:    [B]-R        Black with one red child
4-node:  R-[B]-R        Black with two red children

Top-down 2-3-4 insertion maps directly to top-down Red-Black insertion with colour flips.

Sedgewick's simplification (2008)

A Left-Leaning Red-Black (LLRB) tree adds one extra invariant: red links lean left. This eliminates half the cases in standard Red-Black tree operations.

Operations simplified

Core helpers

rotateLeft(h)     // fix right-leaning red link
rotateRight(h)    // temporarily create right-leaning red
flipColours(h)    // split a 4-node (both children red)

Correspondence

Arne Andersson's simplification (1993)

An AA tree is a Red-Black tree with an additional constraint: right children cannot be red. Equivalently, only right-leaning "horizontal" links at the same level are allowed.

Level-based formulation

• Leaf nodes have level 1
• A left child's level is strictly less than its parent's level
• A right child's level is equal to or one less than its parent's level
• A right grandchild's level is strictly less than its grandparent's level

Two operations only

Insert and delete

• Insert: BST insert, then skew and split back up
• Delete: BST delete, decrease levels if needed, then skew and split back up

Lazy rebalancing

Scapegoat trees do not maintain any auxiliary information (no heights, no colours, no levels). Instead, they detect and fix imbalance lazily.

How it works

1. Insert: BST insert; if depth exceeds log1/α(n), find a scapegoat ancestor
2. Scapegoat: highest node where size(child) > α × size(node)
3. Rebuild: flatten subtree into sorted array, rebuild as perfectly balanced BST
4. Delete: mark-and-lazy-rebuild when too many deleted

The alpha parameter

Complexity

Balance by subtree size

Weight-balanced trees (BB[α] trees, Nievergelt & Reingold, 1973) maintain balance based on the size of subtrees rather than height.

Weight-balance condition

size(left)  >= alpha * size(node)
size(right) >= alpha * size(node)

Typical alpha: 2/11 to 1/4
Bound: alpha <= 1 - 1/sqrt(2) ~ 0.293

Advantages

• Order-statistic operations come for free — each node stores subtree size
• rank(x), select(k), range_count(lo, hi) are all O(log n)
• Well-suited for persistent/functional implementations
• Merging and splitting are efficient

Used in practice

Path copying

A persistent data structure preserves all previous versions. Instead of modifying in place, each update creates a new path from the modified node to the root.

Version 1:         Version 2 (insert 25):

      30                30'
     / \               / \
   20   40    ->     20'  40   (shared)
  /                 / \
10               10   25  (new)

Shared: 10, 40 (unchanged)
New:    30', 20', 25
Cost:   O(log n) new nodes per update

Tree choices for persistence

Applications