Balanced Search Trees

The previous lesson ended with a problem: a binary search tree’s height depends on insertion order, and sorted input turns the tree into a linked list.

The solution is to check the tree after every change and rearrange it whenever imbalance occurs. This lesson’s subject is the operation that performs the rearrangement, and two classic rule sets that say when to apply it.

Rotation

Rotation is a local operation that changes a tree’s height by redirecting a link. Its most important property is that it does not break the ordering invariant.

    right rotation (about y)          left rotation
         (y)                (x)              (x)                (y)
        /   \              /   \            /   \              /   \
     (x)     C     →      A    (y)        A     (y)     →    (x)     C
    /   \                     /   \            /   \        /   \
   A     B                   B     C          B     C      A     B

In a right rotation, x moves up and y moves down; subtree B moves from x’s right to y’s left. Nothing changes in terms of ordering: the relation A < x < B < y < C holds in both forms. The only thing that changes is height.

A rotation writes a fixed number of links; its cost is $O(1)$.

class AVLNode:
    def __init__(self, value: int) -> None:
        self.value = value
        self.left: "AVLNode | None" = None
        self.right: "AVLNode | None" = None
        self.height = 0                      # leaf: 0


def h(node: AVLNode | None) -> int:
    return -1 if node is None else node.height


def update(node: AVLNode) -> None:
    node.height = 1 + max(h(node.left), h(node.right))


def balance(node: AVLNode | None) -> int:
    """Left height minus right height."""
    return 0 if node is None else h(node.left) - h(node.right)


def rotate_right(y: AVLNode) -> AVLNode:
    x = y.left
    y.left = x.right                # subtree B changes place
    x.right = y
    update(y); update(x)     # the lower node is updated first
    return x                             # new root


def rotate_left(x: AVLNode) -> AVLNode:
    y = x.right
    x.right = y.left
    y.left = x
    update(x); update(y)
    return y

The order of the height update matters: the lower node must be updated first, because the height of the one above depends on it.

AVL Tree

An AVL tree enforces the following condition at every node:

The difference between the left and right subtrees’ heights is at most one.

This difference is the node’s balance factor. Its value must be $-1$, $0$, or $+1$; when it becomes $\pm 2$, there is imbalance, and it is corrected.

The condition is strict, and in exchange it gives a tight height bound: the height of an AVL tree with $n$ nodes never exceeds $1.44 \log_2 n$. Search, insertion, and deletion are therefore always $O(\log n)$ — a degenerate case is impossible.

Four Cases

Imbalance after insertion arises in four forms. Their names describe the path from the unbalanced node to the inserted node.

Case	Symptom	Fix
Left–left	Balance $> 1$, left child’s balance $\geq 0$	Right rotation
Right–right	Balance $< -1$, right child’s balance $\leq 0$	Left rotation
Left–right	Balance $> 1$, left child’s balance $< 0$	Rotate the left child left, then rotate right
Right–left	Balance $< -1$, right child’s balance $> 0$	Rotate the right child right, then rotate left

In the last two cases a single rotation is not enough: the imbalance is “zigzag” shaped, and it is first straightened out, then corrected.

def insert_avl(root: AVLNode | None, value: int) -> AVLNode:
    if root is None:
        return AVLNode(value)
    if value < root.value:
        root.left = insert_avl(root.left, value)
    elif value > root.value:
        root.right = insert_avl(root.right, value)
    else:
        return root                                   # duplicate value

    update(root)
    d = balance(root)

    if d > 1 and balance(root.left) >= 0:             # left–left
        return rotate_right(root)
    if d < -1 and balance(root.right) <= 0:           # right–right
        return rotate_left(root)
    if d > 1:                                         # left–right
        root.left = rotate_left(root.left)
        return rotate_right(root)
    if d < -1:                                        # right–left
        root.right = rotate_right(root.right)
        return rotate_left(root)
    return root


def inorder(node, result=None):
    result = [] if result is None else result
    if node is not None:
        inorder(node.left, result)
        result.append(node.value)
        inorder(node.right, result)
    return result


# Sorted insertion: this would degenerate in a plain search tree.
root = None
for value in (3, 7, 10, 12, 25, 30):
    root = insert_avl(root, value)

print(inorder(root))        # [3, 7, 10, 12, 25, 30]
print(root.value)             # 12   — the root settled in the middle on its own
print(h(root))                # 2    — this would be 5 in a degenerate tree

Inserting the six values in ascending order produced a chain of height five in the previous lesson. The AVL rule keeps the height at two on the same input; the rotations ran on their own during insertion.

At most one rotation (or a double rotation) is needed after an insertion; height updates are performed along the path down from the root. The cost of insertion therefore stays $O(\log n)$.

Red–Black Trees

The second classic family tracks balance not with heights but with colors. Every node is colored red or black, and four invariants are maintained:

1. The root is black.
2. A red node’s children are black — two red nodes cannot be consecutive.
3. Every path from the root to any empty link contains the same number of black nodes.
4. Empty links count as black.

The third condition ensures the tree is perfectly balanced in terms of “black height.” The longest path can be at most twice the shortest — because the longest path alternates red and black, while the shortest is entirely black. From this the height bound follows:

$$h \leq 2 \log_2 (n + 1)$$

This is looser than AVL’s $1.44 \log_2 n$ bound; the tree can be slightly deeper. In exchange, the amount of rearrangement needed to maintain balance is small: a constant number of rotations suffices for insertion and deletion, whereas in AVL a chain of rotations up to the root’s path can occur during deletion.

Choosing Between the Two Families

Criterion	AVL	Red–black
Height bound	$\approx 1.44 \log_2 n$	$\approx 2 \log_2 n$
Search	Slightly faster	Slightly slower
Insert/delete	More rotations	Fewer rotations
Suited to	Read-heavy	Write-heavy

General-purpose libraries’ ordered map and ordered set structures mostly use red–black trees: more predictable update cost is worth more, in general use, than the difference in search speed.

The shared cost of both families is code complexity. Deletion cases are especially numerous and are a common source of error in hand-written implementations. The skip list from the Linear Structures topic is an alternative, since it gives the same expected cost with far shorter code — the difference is that its guarantee is expected, not certain.

Summary

• Rotation is a constant-cost operation that changes height by redirecting links while preserving the ordering invariant.
• In an AVL tree every node’s balance factor must be $-1$, $0$, or $+1$; a violation is fixed with one of four cases.
• Zigzag-shaped imbalances (left–right, right–left) are first straightened with a single rotation.
• The AVL height bound is about $1.44 \log_2 n$; a degenerate case is impossible.
• A red–black tree tracks balance with color invariants; its bound is looser but it requires fewer rotations on update.
• AVL is preferred under a read-heavy load, red–black under a write-heavy one.

Next Step

In binary trees, balance is repaired after the fact with rotations. A different approach is to hold more than one key per node and keep all of the tree’s leaves at the same depth. The next lesson takes up 2-3 trees, which build on this idea.