AVL Trees

The previous lesson left us with a binary search tree that does everything in $O(h)$ time: fast when the tree is bushy, $\Theta (n)$ when a run of sorted insertions stretches it into a height-$\Theta (n)$ path. The fix is to prevent the tree from getting tall: pick a structural invariant that pins height to $O(\log n)$, and restore it after every update. The AVL tree, named for Adelson-Velsky and Landis (1962), is the oldest such scheme and the easiest to reason about, balancing by a direct height constraint at every node.¹

To talk about rebalancing we need one primitive, which the next lesson on balanced search trees treats in full: the rotation. A rotation rearranges three pointers to change a subtree's shape, and so its height, while preserving the BST ordering and running in $O(1)$ time. A right rotation at $y$ lifts its left child $x$ to the root and makes $y$ the right child of $x$; a left rotation is the inverse. That is all we need here: a cheap, order-preserving operation that trades height between siblings.

The AVL invariant

Define the height $h(x)$ of a node as the number of edges on the longest downward path to a leaf, with $h(\text{nil})=-1$. The balance factor is

and the invariant says exactly $bf(x)\in \{-1,0,+1\}$ for every node. We store $h(x)$ (or, equivalently, $bf(x)$) in each node and keep it current as the tree changes; both a search and an in-order walk ignore the field entirely, so a read-only operation on an AVL tree is just a BST operation.

A node with $bf=-2$ is left-heavy past tolerance, $bf=+2$ right-heavy; these are the two illegal states an update can create, and the two we must repair.

Height is logarithmic

The invariant forces a logarithmic height bound. The cleanest argument is extremal: ask how few nodes an AVL tree of a given height can possibly contain. A sparse tree is the dangerous case, so if even the sparsest legal tree is bushy, all of them are.

The recurrence is easiest to believe by drawing it. Each minimal tree is a root whose children are the two previous minimal trees — the same doubling-back structure as the Fibonacci numbers themselves:

The minimal-node trees are the Fibonacci trees: the sparsest height-$h$ AVL tree is a root over a Fibonacci tree of height $h-1$ and one of height $h-2$. Because $1.44{\log }_{2}n<2{\log }_2(n+1)$, an AVL tree is provably shorter than the worst-case red-black tree of the same size, so its lookups touch fewer nodes. With $h=O(\log n)$ guaranteed, search, $\text{Insert}$, $\text{Delete}$, $\text{Min}$, and successor all run in $O(\log n)$ worst-case time.³

def minimal_avl_nodes(target_height: int) -> int:
  """
    The minimum number of nodes N(h) in an AVL tree of the given height,\n
    from the Fibonacci-style recurrence N(h) = N(h-1) + N(h-2) + 1 with\n
    N(0) = 1 and N(1) = 2. These minima are realized by the Fibonacci trees\n
    and underpin the 1.44*log2(n) height bound. A height of -1 (the empty\n
    tree) has 0 nodes.\n
  """
  if target_height < 0:
    return 0
  if target_height == 0:
    return 1

  previous: int = 1  # N(0)
  current: int = 2    # N(1)
  for _ in range(2, target_height + 1):
    previous, current = current, current + previous + 1
  return current

Insertion: rebalancing on the way up

We insert a key exactly as in a plain BST: descend to a leaf position and attach the new node. That can only push heights up along the single root-to-leaf path we just walked, so we retrace it upward, recomputing $h$ at each node. Let $z$ be the lowest node whose balance factor has become $\pm 2$. Its imbalance was caused by the new node landing in one of four positions relative to $z$, named by the two steps down the heavy path from $z$ toward the insertion:

• LL: left child left-heavy, a single right rotation at $z$.
• RR: right child right-heavy, a single left rotation at $z$.
• LR: left child right-heavy, a left rotation at the child, then a right rotation at $z$.
• RL: right child left-heavy, a right rotation at the child, then a left rotation at $z$.

Consider the LL case. Node $z$ has balance $-2$, its left child $y$ leans left, and the new node sits under $y$'s left child $x$. A single right rotation at $z$ lifts $y$ into $z$'s place, hangs $z$ as $y$'s right child, and rehomes $y$'s old right subtree as $z$'s new left subtree.

The height bookkeeping makes the repair exact. Measure heights at the moment of violation: say $T_3$ and $T_4$ have height $h$, and $x$'s subtree has height $h+1$ because it contains the new node. Then $y=1+\max (h+1,h)=h+2$, and $z$'s two subtrees have heights $h+2$ and $h$: balance $-2$, the violation. After the right rotation, $z$ roots $T_3$ and $T_4$ (both height $h$), so $z$ has height $h+1$ and balance $0$; $y$ roots $x$ (height $h+1$) and $z$ (height $h+1$), so $y$ has height $h+2$ and balance $0$. Before the insertion, $z$'s height was $1+\max (h+1,h)=h+2$ — exactly the height $y$ has now. The subtree presents the same height to its parent as before the insert, so no ancestor's balance factor changes, and the repair is complete.

The RR case is the exact mirror: $z$ has balance $+2$, its right child $y$ leans right, and the new node sits under $y$'s right child $x$. A single left rotation at $z$ lifts $y$, hangs $z$ as $y$'s left child, and rehomes $y$'s old left subtree $T_2$ as $z$'s new right subtree. The same bookkeeping applies with left and right exchanged.

The LR case cannot be fixed by a single rotation: the heavy path zig-zags, so we first rotate the child to straighten it into an LL shape, then finish with the right rotation at $z$. Here $z$ has balance $-2$, its left child $y$ leans right, and the offending grandchild $x$ is $y$'s right child. A left rotation at $y$ lifts $x$ above $y$; the subtree is now left-left-heavy, and a right rotation at $z$ completes the repair, leaving $x$ as the new root.

The bookkeeping for LR: at the violation, $T_1$ and $T_4$ have height $h$, and $x$'s subtree has height $h+1$ — its children $T_2$ and $T_3$ have heights $h$ and $h-1$ in some order, whichever one received the new node. So $y$ has height $h+2$ and $z$ is at balance $-2$. After the double rotation, $x$ is the root; its left child $y$ roots $T_1$ (height $h$) and $T_2$ (height $\le h$), so $h(y)=h+1$; its right child $z$ roots $T_3$ (height $\le h$) and $T_4$ (height $h$), so $h(z)=h+1$. Both have balance $0$ or $\pm 1$, legal, and $x$'s height is $h+2$, again exactly $z$'s pre-insert height, so the violation cannot propagate. One subtlety worth noticing: after an LR repair, exactly one of $y,z$ ends up with balance $\pm 1$ (whichever lost the shorter of $T_2,T_3$), and $x$ ends at balance $0$.

The RL case is the mirror of LR — the heavy path zig-zags right-then-left, so we straighten with a right rotation at the child before the left rotation at $z$:

In every case the rebalanced subtree ends up with the same height it had before the insertion, which is the decisive fact:

So insertion is $O(\log n)$ to descend, $O(\log n)$ to walk back up adjusting heights, and at most a double rotation ($\le 2$ rotations) to repair: $O(\log n)$ overall. The dispatch is driven entirely by the stored heights:

A worked insertion sequence

Insert the keys $10,20,30,40,50,25$ into an empty AVL tree, in that order. This sequence is the sorted-order input that destroys a plain BST, plus one out-of-order key at the end to force a double rotation.

• Insert 10, 20. $10$ becomes the root; $20$ its right child. Heights: $h(20)=0$, $h(10)=1$, balance factors $0$ and $+1$. Legal.
• Insert 30. It lands as $20$'s right child. Retracing: $bf(20)=+1$, fine; but $bf(10)=h(20)-h(\text{nil})=1-(-1)=+2$. The lowest violation is $z=10$, its right child $20$ leans right: RR. One left rotation at $10$ gives $20$ as root with children $10$ and $30$, all balance factors $0$, and $\text{Insert-Fixup}$ stops.
• Insert 40. Path $20\to 30$, attach right. Retracing: $bf(30)=+1$, $bf(20)=+1$. No violation, no rotation.
• Insert 50. Path $20\to 30\to 40$, attach right. Retracing: $bf(40)=+1$, then $bf(30)=+2$ — the lowest violation is $z=30$, not the root. Its right child $40$ leans right: RR again. A left rotation at $30$ yields the subtree $40$ over $30$ and $50$; the tree is now $20$ over $10$ and $40(30,50)$, and $bf(20)=+1$ is legal, so retracing stops.
• Insert 25. Path $20\to 40\to 30$, attach as $30$'s left child. Retracing: $bf(30)=-1$, fine; $bf(40)=-1$ with $h(40)=2$, fine; $bf(20)=h(40)-h(10)=2-0=+2$. Violation at $z=20$, and this time its right child $40$ leans left: the zig-zag RL case, with $y=40$ and $x=30$. First a right rotation at $40$ straightens the path ($30$ lifts above $40$), then a left rotation at $20$ lifts $30$ to the root.

Two properties show in this trace. Repairs fire rarely — six inserts triggered three, four rotations in all — and each fires at the lowest violated node only, never higher, because the repair restores the subtree's pre-insert height. And the sorted prefix $10,20,30,40,50$, which would have built a height-$4$ path in a plain BST, ends up at height $2$: the tree handles adversarial order at $O(1)$ rotations per insert.

Deletion: the same cases, but up the whole path

Deletion starts as in a BST, splicing out the node, or its in-order successor if it has two children, then retraces the path to the root updating heights, applying exactly the same four rotation cases at any node that reaches $|bf|=2$. The one difference is consequential. A rotation that repairs an insertion preserves the subtree's height, but a rotation that repairs a deletion can shrink the subtree by one. That shorter subtree may unbalance the node's parent, which may unbalance its parent, and so on. Deletion can therefore trigger up to $O(\log n)$ rotations cascading toward the root, though each is still $O(1)$, so the operation remains $O(\log n)$.³

The asymmetry has a precise cause. An insertion grows the taller side, and the rotation cuts it back to exactly the old height, so no ancestor's balance changes. A deletion shrinks a side, and a rotation can only redistribute height, not create it: when the rotation at $z$ finishes, the repaired subtree often stands one shorter than before the delete, and the parent must re-check its own balance against a subtree that genuinely changed size. The retracing loop stops early in exactly two situations: at a node whose balance factor moves from $0$ to $\pm 1$ (one subtree shrank, but the node's height is set by the other and is unchanged), or after a rotation in which the lifted child had balance $0$ (that rotation preserves the subtree's height). Otherwise the height drop keeps propagating.

Concretely, take the sparsest height-$3$ AVL tree on the keys $1,\dots ,7$ arranged as $5$ over $3(2(1),4)$ and $7(6)$, and delete $6$. Node $7$ becomes a leaf, legal by itself, but at $5$ the balance is now $h(7)-h(3)=0-2=-2$. The left child $3$ leans left ($bf(3)=-1$), so this is LL: one right rotation at $5$. The result, $3$ over $2(1)$ and $5(4,7)$, is a legal AVL tree of height $2$ — one shorter than the original. A single leaf deletion shrank the whole tree, and if this tree were itself a subtree, the shrink would arrive at its parent exactly as in the schematic above. Fibonacci trees realize the worst case: every node is already at balance $\pm 1$, so a deletion on the short side of each ancestor can force a rotation at every level, $\Theta (\log n)$ of them.

AVL versus red-black

AVL and red-black trees both guarantee $O(\log n)$ height, but they sit at opposite ends of a tradeoff. The AVL height-difference invariant is strict: $h\le 1.44{\log }_{2}n$, noticeably shorter than red-black's $2{\log }_2(n+1)$, so AVL lookups are faster, the structure of choice for read-heavy workloads. The cost falls on updates: AVL trees track exact heights and may rotate to repair even small imbalances, whereas red-black trees tolerate looser balance and rely on cheap recolorings, doing fewer rotations per update. Roughly: AVL is more rigidly balanced and faster to search; red-black is cheaper to mutate, which is why it backs most standard-library ordered maps.⁴

from collections.abc import Iterator
from typing import Generic, Optional, TypeVar
from comparable import Comparable


Key = TypeVar("Key", bound=Comparable)


class AVLNode(Generic[Key]):
  """
    One node of an AVL tree: its key, its left and right child links, and\n
    the cached height of the subtree rooted here. A leaf has height 0 and a\n
    missing (nil) child is treated as height -1.\n
  """

  def __init__(self, key: Key) -> None:
    self.key: Key = key
    self.left: Optional[AVLNode[Key]] = None
    self.right: Optional[AVLNode[Key]] = None
    self.height: int = 0

  def __repr__(self) -> str:
    return f"AVLNode({self.key!r})"


def _height(node: Optional[AVLNode[Key]]) -> int:
  """
    The cached height of a subtree, with the nil convention h(nil) = -1.\n
  """
  return node.height if node is not None else -1


def _balance_factor(node: AVLNode[Key]) -> int:
  """
    The balance factor bf(node) = h(right) - h(left): negative is\n
    left-heavy, positive is right-heavy, legal values are -1, 0, +1.\n
  """
  return _height(node.right) - _height(node.left)


def _update_height(node: AVLNode[Key]) -> None:
  """
    Recompute a node's height from its children's cached heights.\n
  """
  node.height = 1 + max(_height(node.left), _height(node.right))


class AVLTree(Generic[Key]):
  """
    An ordered set of comparable keys kept height-balanced.\n
    Supports membership, insertion, deletion, and an in-order traversal that\n
    yields keys in sorted order.\n
  """

  def __init__(self) -> None:
    self.root: Optional[AVLNode[Key]] = None
    self.size: int = 0

  def __len__(self) -> int:
    return self.size

  def __contains__(self, key: Key) -> bool:
    return self._search(self.root, key) is not None

  def __iter__(self) -> Iterator[Key]:
    yield from self._in_order(self.root)

  def _search(
    self, node: Optional[AVLNode[Key]], key: Key
  ) -> Optional[AVLNode[Key]]:
    """
      The node holding `key` in the subtree at `node`, or None if absent.\n
    """
    current: Optional[AVLNode[Key]] = node
    while current is not None:
      if key < current.key:
        current = current.left
      elif current.key < key:
        current = current.right
      else:
        return current
    return None

  def _rotate_right(self, root: AVLNode[Key]) -> AVLNode[Key]:
    """
      Right rotation at `root`: lift its left child into root's place,\n
      hang root as that child's right child, and rehome the child's old\n
      right subtree as root's new left subtree. Returns the new subtree root.\n
    """
    pivot = root.left
    assert pivot is not None  # a right rotation only runs with a left child.
    moved_subtree: Optional[AVLNode[Key]] = pivot.right
    pivot.right = root
    root.left = moved_subtree

    # the lower node (root) must be re-measured before the lifted pivot.
    _update_height(root)
    _update_height(pivot)
    return pivot

  def _rotate_left(self, root: AVLNode[Key]) -> AVLNode[Key]:
    """
      Left rotation at `root`, the mirror image of `_rotate_right`.\n
      Returns the new subtree root.\n
    """
    pivot = root.right
    assert pivot is not None  # a left rotation only runs with a right child.
    moved_subtree: Optional[AVLNode[Key]] = pivot.left
    pivot.left = root
    root.right = moved_subtree

    _update_height(root)
    _update_height(pivot)
    return pivot

  def _rebalance(self, node: AVLNode[Key]) -> AVLNode[Key]:
    """
      Restore the AVL invariant at `node` after its height was updated,\n
      dispatching on the balance factor into one of the four cases\n
      (LL, RR, LR, RL). Returns the subtree's (possibly new) root.\n
    """
    _update_height(node)
    balance: int = _balance_factor(node)

    # left-heavy: either LL (single right) or LR (left child, then right).
    if balance < -1:
      left_child = node.left
      assert left_child is not None  # left-heavy implies a left child exists.
      if _balance_factor(left_child) > 0:
        node.left = self._rotate_left(left_child)  # LR straightens to LL
      return self._rotate_right(node)

    # right-heavy: either RR (single left) or RL (right child, then left).
    if balance > 1:
      right_child = node.right
      assert right_child is not None  # right-heavy implies a right child exists.
      if _balance_factor(right_child) < 0:
        node.right = self._rotate_right(right_child)  # RL straightens to RR
      return self._rotate_left(node)

    return node

  def insert(self, key: Key) -> bool:
    """
      Add `key` to the tree, rebalancing on the way up.\n
      Returns False (and leaves the tree unchanged) if the key is present.\n
    """
    inserted: bool
    self.root, inserted = self._insert(self.root, key)
    if inserted:
      self.size += 1
    return inserted

  def _insert(
    self, node: Optional[AVLNode[Key]], key: Key
  ) -> tuple[AVLNode[Key], bool]:
    """
      Insert `key` into the subtree at `node`, returning the new subtree\n
      root and whether a node was actually added.\n
    """
    if node is None:
      return AVLNode(key), True

    if key < node.key:
      node.left, inserted = self._insert(node.left, key)
    elif node.key < key:
      node.right, inserted = self._insert(node.right, key)
    else:
      return node, False  # duplicate keys are ignored

    return self._rebalance(node), inserted

  def delete(self, key: Key) -> bool:
    """
      Remove `key` from the tree, rebalancing on the way up.\n
      Returns False if the key was not present.\n
    """
    deleted: bool
    self.root, deleted = self._delete(self.root, key)
    if deleted:
      self.size -= 1
    return deleted

  def _delete(
    self, node: Optional[AVLNode[Key]], key: Key
  ) -> tuple[Optional[AVLNode[Key]], bool]:
    """
      Delete `key` from the subtree at `node`, returning the new subtree\n
      root (or None) and whether a node was removed.\n
    """
    if node is None:
      return None, False

    if key < node.key:
      node.left, deleted = self._delete(node.left, key)
    elif node.key < key:
      node.right, deleted = self._delete(node.right, key)
    else:
      # found it: splice out, handling zero, one, or two children.
      if node.left is None:
        return node.right, True
      if node.right is None:
        return node.left, True

      # two children: replace key with the in-order successor, then
      # delete that successor from the right subtree.
      successor: AVLNode[Key] = self._min_node(node.right)
      node.key = successor.key
      node.right, _ = self._delete(node.right, successor.key)
      deleted = True

    return self._rebalance(node), deleted

  def _min_node(self, node: AVLNode[Key]) -> AVLNode[Key]:
    """
      The left-most (minimum-key) node of a non-empty subtree.\n
    """
    current: AVLNode[Key] = node
    while current.left is not None:
      current = current.left
    return current

  def minimum(self) -> Optional[Key]:
    """
      The smallest key in the tree, or None if the tree is empty.\n
    """
    return self._min_node(self.root).key if self.root is not None else None

  def maximum(self) -> Optional[Key]:
    """
      The largest key in the tree, or None if the tree is empty.\n
    """
    if self.root is None:
      return None

    # walk right links to the largest key.
    current: AVLNode[Key] = self.root
    while current.right is not None:
      current = current.right
    return current.key

  def height(self) -> int:
    """
      The height of the tree in edges, with -1 for an empty tree.\n
    """
    return _height(self.root)

  def _in_order(self, node: Optional[AVLNode[Key]]) -> Iterator[Key]:
    """
      Yield the keys of the subtree at `node` in ascending order.\n
    """
    if node is not None:
      yield from self._in_order(node.left)
      yield node.key
      yield from self._in_order(node.right)

from typing import Any, Protocol, TypeVar


class Comparable(Protocol):
  """
    Anything orderable with `<` (int, float, str, tuple, date, …).\n
  """

  # `other` is position-only so built-ins (int, str, …), whose dunder
  # operands are position-only, structurally satisfy the protocol.
  def __lt__(self, other: Any, /) -> bool: ...
  def __gt__(self, other: Any, /) -> bool: ...
  def __le__(self, other: Any, /) -> bool: ...
  def __ge__(self, other: Any, /) -> bool: ...

The balance spectrum

The AVL tree (Adelson-Velsky and Landis, 1962) was the first self-balancing binary search tree, and its height-difference idea led to a family of variants that trade the strictness of differ by at most $1$ for cheaper maintenance.

Relaxing the balance factor. Allow subtree heights to differ by up to $k$ instead of $1$ and you get $k$-balanced or HB($k$) trees: taller, so lookups touch a few more nodes, but rebalanced less often. Pushing the same idea the other way, weak AVL (WAVL) trees (Haeupler, Sen, and Tarjan, 2015) use a rank rule that interpolates between AVL and red-black, an untouched WAVL tree is as short as an AVL tree, but after deletions it degrades gracefully toward red-black balance, doing at most one rotation per deletion where an AVL tree can cascade. WAVL is a clean answer to exactly the AVL-vs-red-black tension this lesson closes on: it aims for AVL's short trees with red-black's cheap deletes.

Why the four cases are really two. The LL/RR/LR/RL taxonomy is a special case of a general fact: any single imbalance is fixable by one or two rotations, and the double cases (LR, RL) are just rotate the child to reduce to a single case, then rotate the parent. The same double-rotation appears verbatim in red-black insert-fixup's Case 2-then-3, which is no coincidence: both are the standard way to straighten a zig-zag before a zig-zig.

Where AVL wins today. Because AVL trees are the shortest of the common balanced BSTs, they remain the pick for in-memory indexes and language runtimes whose workloads are lookup-dominated, some database in-memory indexes and the Linux kernel's earlier scheduler used AVL-style structures. When updates dominate, red-black or WAVL win; when the data lives on disk, neither, the fan-out of a B-tree beats any binary tree.⁵

Takeaways

• An AVL tree is a BST with the invariant that every node's two subtrees differ in height by at most $1$, i.e. its balance factor $bf(x)\in \{-1,0,+1\}$; each node stores its height (or balance).
• A minimal-node / Fibonacci-tree argument gives $N(h)=N(h-1)+N(h-2)+1$, so $N(h)=F_{h+3}-1$ and height $h\le 1.44{\log }_{2}n=O(\log n)$, hence all operations are worst-case $O(\log n)$.
• Insertion descends as a BST, retraces the path updating heights, and repairs the lowest unbalanced node with one of four cases, LL (right), RR (left), LR (left-then-right), RL (right-then-left), using $O(1)$ rotations, because the fix restores the subtree's prior height.
• Deletion uses the same four cases but its rotations can shrink a subtree, so the rebalancing may cascade up to the root, taking $O(\log n)$ rotations.
• Versus red-black trees: AVL is more rigidly balanced (shorter, faster lookups) but does more rotations per update.