---
title: AVL Trees
module: Data Structures
moduleNumber: 4
lessonNumber: 4
order: 404
summary: |
  An AVL tree is the first balanced BST: at every node the two subtrees' heights
  differ by at most $1$. A Fibonacci-style minimal-node argument forces height
  $h \le 1.44\log_2 n = O(\log n)$, so search, insert, and delete are all
  $O(\log n)$. Insertion rebalances with at most one of four rotation cases
  (LL, RR, LR, RL); deletion may rotate all the way to the root.
topics: [Balanced Trees]
sources:
  - book: CLRS
    ref: "Problem 13-3 — AVL Trees"
  - book: Skiena
    ref: "§3.4 — Balanced Search Trees"
  - book: Erickson
    ref: "Ch. — Balanced Binary Search Trees"
practice:
  - title: 'Balanced Binary Tree'
    slug: balanced-binary-tree
    difficulty: Easy
  - title: 'Insert into a Binary Search Tree'
    slug: insert-into-a-binary-search-tree
    difficulty: Medium
  - title: 'Delete Node in a BST'
    slug: delete-node-in-a-bst
    difficulty: Medium
  - title: 'Convert Sorted List to Binary Search Tree'
    slug: convert-sorted-list-to-binary-search-tree
    difficulty: Medium
---

The previous lesson left us with a [binary search tree](/algorithms/data-structures/binary-search-trees) 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.[^erickson-avl]

To talk about rebalancing we need one primitive, which the next lesson on
[balanced search trees](/algorithms/data-structures/balanced-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

> **Invariant (AVL).** At every node $x$, the heights of its left and right
> subtrees differ by at most $1$.

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

$$
bf(x) = h(\text{right}(x)) - h(\text{left}(x)),
$$

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.

> **Lemma (minimal-node / Fibonacci-tree bound).** Let $N(h)$ be the minimum
> number of nodes in an AVL tree of height $h$. Then
> $$N(h) = N(h-1) + N(h-2) + 1, \qquad N(0)=1,\ N(1)=2,$$
> and consequently an AVL tree on $n$ nodes has height
> $h \le 1.4404\log_2(n+1) = O(\log n)$.

> **Proof.** A height-$h$ AVL tree has a root, plus two subtrees, the taller of
> which has height $h-1$. To make the tree as sparse as possible we make the other
> subtree as short as the invariant allows, namely $h-2$, and recursively make
> both subtrees minimal. Hence $N(h) = 1 + N(h-1) + N(h-2)$ with $N(0)=1$
> (a single node) and $N(1)=2$. The first few values are
> $N(2) = 1 + 2 + 1 = 4$, $N(3) = 1 + 4 + 2 = 7$, $N(4) = 1 + 7 + 4 = 12$,
> $N(5) = 20$ — each is one more than the sum of the previous two. This is the
> Fibonacci recurrence shifted by a constant: adding $1$ to both sides gives
> $N(h)+1 = (N(h-1)+1)+(N(h-2)+1)$, the exact Fibonacci recurrence for the
> sequence $M(h) = N(h)+1$, with base values $M(0) = 2 = F_3$ and
> $M(1) = 3 = F_4$. Matching bases and matching recurrences force
> $M(h) = F_{h+3}$ for all $h$, so $N(h) = F_{h+3} - 1 \ge F_{h+2} - 1$.[^clrs-avl]
> Since $F_k \ge \phi^{\,k-2}$ with $\phi = \tfrac{1+\sqrt5}{2} \approx 1.618$,
> we get $N(h) \ge \phi^{\,h} - 1$: a tree of height $h$ has at least
> $\phi^{\,h} - 1$ nodes. Inverting, any AVL tree with $n$ nodes and height $h$
> satisfies
>
> $$
> n \ge \phi^{\,h} - 1
> \;\Longrightarrow\;
> \phi^{\,h} \le n+1
> \;\Longrightarrow\;
> h \le \log_\phi(n+1) = \frac{\log_2(n+1)}{\log_2 \phi}
> = \frac{\log_2(n+1)}{0.6942\ldots} \approx 1.4404\,\log_2(n+1).
> \qquad\square
> $$

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:

$$
% caption: Minimal AVL trees of heights $0$ through $3$. Each is a root (accent) over the
%          two preceding minimal trees, giving $N(h) = 1 + N(h-1) + N(h-2)$: the height-$3$
%          tree is a root over the height-$2$ tree (left) and the height-$1$ tree (right),
%          $N(3) = 1 + 4 + 2 = 7$.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=4.5mm, inner sep=0},
  lab/.style={draw=none, font=\scriptsize, black},
  >=stealth, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  % h = 0
  \node[draw=acc, very thick, fill=acc!15] (a) at (0,0) {};
  \node[lab] at (0,-3.6) {N(0) = 1};
  % h = 1
  \node[draw=acc, very thick, fill=acc!15] (b) at (2,0) {};
  \node (b1) at (1.6,-1.0) {};
  \draw (b)--(b1);
  \node[lab] at (1.8,-3.6) {N(1) = 2};
  % h = 2
  \node[draw=acc, very thick, fill=acc!15] (c) at (4.4,0) {};
  \node (c1) at (3.8,-1.0) {};
  \node (c2) at (5.0,-1.0) {};
  \node (c11) at (3.4,-2.0) {};
  \draw (c)--(c1); \draw (c)--(c2); \draw (c1)--(c11);
  \node[lab] at (4.4,-3.6) {N(2) = 4};
  % h = 3
  \node[draw=acc, very thick, fill=acc!15] (d) at (8.4,0) {};
  \node (dl) at (7.3,-1.0) {};
  \node (dl1) at (6.6,-2.0) {};
  \node (dl2) at (8.0,-2.0) {};
  \node (dl11) at (6.2,-3.0) {};
  \node (dr) at (9.5,-1.0) {};
  \node (dr1) at (9.1,-2.0) {};
  \draw (d)--(dl); \draw (d)--(dr);
  \draw (dl)--(dl1); \draw (dl)--(dl2); \draw (dl1)--(dl11);
  \draw (dr)--(dr1);
  \node[lab] at (8.4,-3.6) {N(3) = 1 + 4 + 2 = 7};
\end{tikzpicture}
$$

The minimal-node trees are the **Fibonacci trees**: the sparsest height-$h$
AVL tree is a root over a [Fibonacci](/algorithms/foundations/asymptotic-analysis) 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, $\textsc{Insert}$, $\textsc{Delete}$,
$\textsc{Min}$, and successor all run in $O(\log n)$ worst-case time.[^skiena-avl]

$$
% caption: The sparsest AVL tree of height $4$ — a Fibonacci tree with the minimum
%          $N(4)=F_7-1=12$ nodes. Each node's two subtrees differ in height by exactly $1$
%          (the extreme the invariant allows): the root sits over a minimal height-$3$
%          tree and a minimal height-$2$ tree, recursively. Subtree heights are labeled.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=6mm, inner sep=0, font=\scriptsize},
  >=stealth, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  \node[draw=acc, very thick, fill=acc!15] (r) at (0,0) {4};
  % --- T(3) subtree (left) ---
  \node (l) at (-3,-1.1) {$3$};
  \node (l2) at (-4.4,-2.2) {$2$};
  \node (l1) at (-1.9,-2.2) {$1$};
  \node (l2a) at (-5.1,-3.3) {$1$};
  \node (l2b) at (-3.8,-3.3) {$0$};
  \node (l2a0) at (-5.6,-4.4) {$0$};
  \node (l11) at (-2.3,-3.3) {$0$};
  % --- T(2) subtree (right) ---
  \node (rr) at (2.6,-1.1) {$2$};
  \node (rr1) at (1.7,-2.2) {$1$};
  \node (rr0) at (3.5,-2.2) {$0$};
  \node (rr10) at (1.2,-3.3) {$0$};
  % edges
  \draw (r)--(l); \draw (r)--(rr);
  \draw (l)--(l2); \draw (l)--(l1);
  \draw (l2)--(l2a); \draw (l2)--(l2b); \draw (l2a)--(l2a0);
  \draw (l1)--(l11);
  \draw (rr)--(rr1); \draw (rr)--(rr0); \draw (rr1)--(rr10);
\end{tikzpicture}
$$

::impl{algo="avl_tree#minimal_avl_nodes"}

## 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.

$$
% caption: The LL case — a left-left-heavy subtree fixed by one right rotation at $z$
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0},
  tri/.style={draw, isosceles triangle, isosceles triangle apex angle=60,
    shape border rotate=90, minimum size=5mm, inner sep=1pt},
  level distance=12mm,
  level 1/.style={sibling distance=28mm},
  level 2/.style={sibling distance=14mm}]
  \definecolor{acc}{HTML}{2348F2}
  % before: z (bf -2) over y over x
  \begin{scope}
    \node (z) {$z$}
      child {node (y) {$y$}
        child {node (x) {$x$}
          child {node[tri] {$T_1$}}
          child {node[tri] {$T_2$}}
        }
        child {node[tri] {$T_3$}}
      }
      child {node[tri] {$T_4$}};
  \end{scope}
  % arrow
  \draw[->, thick, draw] (2.6,-1.7) -- node[draw=none, above, font=\footnotesize] {righ\/t} node[draw=none, below, font=\footnotesize] {rotate $z$} (4.6,-1.7);
  % after: y at root, z to its right
  \begin{scope}[xshift=7.2cm]
    \node[draw=acc, very thick, fill=acc!15] (y2) {$y$}
      child {node (x2) {$x$}
        child {node[tri] {$T_1$}}
        child {node[tri] {$T_2$}}
      }
      child {node (z2) {$z$}
        child {node[tri] {$T_3$}}
        child {node[tri] {$T_4$}}
      };
  \end{scope}
\end{tikzpicture}
$$

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.

$$
% caption: The RR case — a right-right-heavy subtree fixed by one left rotation at $z$
%          (the mirror of LL).
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0},
  tri/.style={draw, isosceles triangle, isosceles triangle apex angle=60,
    shape border rotate=90, minimum size=5mm, inner sep=1pt},
  level distance=12mm,
  level 1/.style={sibling distance=28mm},
  level 2/.style={sibling distance=14mm}]
  \definecolor{acc}{HTML}{2348F2}
  % before: z (bf +2) over y over x
  \begin{scope}
    \node (z) {$z$}
      child {node[tri] {$T_1$}}
      child {node (y) {$y$}
        child {node[tri] {$T_2$}}
        child {node (x) {$x$}
          child {node[tri] {$T_3$}}
          child {node[tri] {$T_4$}}
        }
      };
  \end{scope}
  % arrow
  \draw[->, thick, draw] (2.6,-1.7) -- node[draw=none, above, font=\footnotesize] {left} node[draw=none, below, font=\footnotesize] {rotate $z$} (4.6,-1.7);
  % after: y at root, z to its left
  \begin{scope}[xshift=7.2cm]
    \node[draw=acc, very thick, fill=acc!15] (y2) {$y$}
      child {node (z2) {$z$}
        child {node[tri] {$T_1$}}
        child {node[tri] {$T_2$}}
      }
      child {node (x2) {$x$}
        child {node[tri] {$T_3$}}
        child {node[tri] {$T_4$}}
      };
  \end{scope}
\end{tikzpicture}
$$

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.

$$
% caption: The LR case — left rotation at $y$, then right rotation at $z$ (a double
%          rotation)
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0},
  tri/.style={draw, isosceles triangle, isosceles triangle apex angle=60,
    shape border rotate=90, minimum size=4.5mm, inner sep=1pt},
  level distance=11mm,
  level 1/.style={sibling distance=22mm},
  level 2/.style={sibling distance=11mm}]
  \definecolor{acc}{HTML}{2348F2}
  % stage 0: z over y(left-heavy node) over x(=right child of y)
  \begin{scope}
    \node (z) {$z$}
      child {node (y) {$y$}
        child {node[tri] {$T_1$}}
        child {node (x) {$x$}
          child {node[tri] {$T_2$}}
          child {node[tri] {$T_3$}}
        }
      }
      child {node[tri] {$T_4$}};
  \end{scope}
  \draw[->, thick, draw] (2.3,-1.6) -- node[draw=none, above, font=\footnotesize] {left $y$} (3.7,-1.6);
  % stage 1: now LL-heavy: z over x over y
  \begin{scope}[xshift=5.2cm]
    \node (z1) {$z$}
      child {node (x1) {$x$}
        child {node (y1) {$y$}
          child {node[tri] {$T_1$}}
          child {node[tri] {$T_2$}}
        }
        child {node[tri] {$T_3$}}
      }
      child {node[tri] {$T_4$}};
  \end{scope}
  \draw[->, thick, draw] (7.5,-1.6) -- node[draw=none, above, font=\footnotesize] {righ\/t $z$} (8.9,-1.6);
  % stage 2: x at root, y left, z right
  \begin{scope}[xshift=10.4cm]
    \node[draw=acc, very thick, fill=acc!15] (x2) {$x$}
      child {node (y2) {$y$}
        child {node[tri] {$T_1$}}
        child {node[tri] {$T_2$}}
      }
      child {node (z2) {$z$}
        child {node[tri] {$T_3$}}
        child {node[tri] {$T_4$}}
      };
  \end{scope}
\end{tikzpicture}
$$

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$:

$$
% caption: The RL case — right rotation at $y$, then left rotation at $z$ (the mirror of
%          LR). Here $z$ has balance $+2$, its right child $y$ leans left, and the
%          offending grandchild $x$ is $y$'s left child; the double rotation lifts $x$ to
%          the root.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0},
  tri/.style={draw, isosceles triangle, isosceles triangle apex angle=60,
    shape border rotate=90, minimum size=4.5mm, inner sep=1pt},
  level distance=11mm,
  level 1/.style={sibling distance=22mm},
  level 2/.style={sibling distance=11mm}]
  \definecolor{acc}{HTML}{2348F2}
  % stage 0: z over T1, y(leans left) with x as left child
  \begin{scope}
    \node (z) {$z$}
      child {node[tri] {$T_1$}}
      child {node (y) {$y$}
        child {node (x) {$x$}
          child {node[tri] {$T_2$}}
          child {node[tri] {$T_3$}}
        }
        child {node[tri] {$T_4$}}
      };
  \end{scope}
  \draw[->, thick, draw] (2.3,-1.6) -- node[draw=none, above, font=\footnotesize] {righ\/t $y$} (3.7,-1.6);
  % stage 1: now RR-heavy: z over x over y
  \begin{scope}[xshift=5.2cm]
    \node (z1) {$z$}
      child {node[tri] {$T_1$}}
      child {node (x1) {$x$}
        child {node[tri] {$T_2$}}
        child {node (y1) {$y$}
          child {node[tri] {$T_3$}}
          child {node[tri] {$T_4$}}
        }
      };
  \end{scope}
  \draw[->, thick, draw] (7.5,-1.6) -- node[draw=none, above, font=\footnotesize] {left $z$} (8.9,-1.6);
  % stage 2: x at root, z left, y right
  \begin{scope}[xshift=10.4cm]
    \node[draw=acc, very thick, fill=acc!15] (x2) {$x$}
      child {node (z2) {$z$}
        child {node[tri] {$T_1$}}
        child {node[tri] {$T_2$}}
      }
      child {node (y2) {$y$}
        child {node[tri] {$T_3$}}
        child {node[tri] {$T_4$}}
      };
  \end{scope}
\end{tikzpicture}
$$

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

> **Key fact.** After rebalancing the lowest unbalanced node $z$, every ancestor
> of $z$ regains the height it had before the insert, so no ancestor is
> unbalanced. **Insertion fixes at most one node and uses $O(1)$ rotations.**

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:

```algorithm
caption: $\textsc{Insert-Fixup}$ — retrace the insertion path, repairing the lowest violation
$x \gets \text{parent of the new leaf}$
while $x \ne \text{nil}$ do
  $h(x) \gets 1 + \max\parens{h(left(x)),\, h(right(x))}$
  $b \gets h(right(x)) - h(left(x))$ // balance factor of $x$
  if $b = -2$ then // left-heavy: LL or LR
    if $h(left(left(x))) \ge h(right(left(x)))$ then
      $\textsc{Right-Rotate}(x)$ // LL
    else
      $\textsc{Left-Rotate}(left(x))$ ; $\textsc{Right-Rotate}(x)$ // LR
    break // height restored, ancestors safe
  else if $b = +2$ then // right-heavy: RR or RL
    if $h(right(right(x))) \ge h(left(right(x)))$ then
      $\textsc{Left-Rotate}(x)$ // RR
    else
      $\textsc{Right-Rotate}(right(x))$ ; $\textsc{Left-Rotate}(x)$ // RL
    break
  $x \gets parent(x)$
```

## 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
  $\textsc{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.

$$
% caption: The final step of the walkthrough. Inserting $25$ pushes node $20$ to balance
%          $+2$ with its right child leaning left — the RL case with $z=20$, $y=40$,
%          $x=30$. A right rotation at $40$ straightens the zig-zag; a left rotation at
%          $20$ lifts $30$ to the root. Every balance factor is legal again and the tree
%          has height $2$, the minimum possible for $6$ nodes.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0, font=\small},
  lab/.style={draw=none, font=\scriptsize, black},
  >=stealth, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  % panel 1: after inserting 25 (violation at 20)
  \node[draw=black, dashed, very thick] (p20) at (0,0) {20};
  \node (p10) at (-1.1,-1.1) {10};
  \node (p40) at (1.1,-1.1) {40};
  \node (p30) at (0.4,-2.2) {30};
  \node (p50) at (1.8,-2.2) {50};
  \node[draw=acc, very thick, fill=acc!8] (p25) at (-0.3,-3.3) {25};
  \draw (p20)--(p10); \draw (p20)--(p40); \draw (p40)--(p30); \draw (p40)--(p50); \draw (p30)--(p25);
  \node[lab] at (-1.3,0.6) {bf +2};
  \draw[->, black] (-0.9,0.45) -- (p20.north west);
  % arrow 1
  \draw[->, thick] (2.6,-1.5) -- node[draw=none, above, font=\footnotesize] {righ\/t 40} (4.2,-1.5);
  % panel 2: after right rotation at 40
  \begin{scope}[xshift=5.6cm]
    \node (q20) at (0,0) {20};
    \node (q10) at (-1.1,-1.1) {10};
    \node (q30) at (1.1,-1.1) {30};
    \node (q25) at (0.4,-2.2) {25};
    \node (q40) at (1.8,-2.2) {40};
    \node (q50) at (2.4,-3.3) {50};
    \draw (q20)--(q10); \draw (q20)--(q30); \draw (q30)--(q25); \draw (q30)--(q40); \draw (q40)--(q50);
  \end{scope}
  % arrow 2
  \draw[->, thick] (8.7,-1.5) -- node[draw=none, above, font=\footnotesize] {left 20} (10.3,-1.5);
  % panel 3: after left rotation at 20
  \begin{scope}[xshift=11.9cm]
    \node[draw=acc, very thick, fill=acc!15] (r30) at (0.6,-0.4) {30};
    \node (r20) at (-0.5,-1.5) {20};
    \node (r40) at (1.7,-1.5) {40};
    \node (r10) at (-1.1,-2.6) {10};
    \node (r25) at (0.1,-2.6) {25};
    \node (r50) at (2.3,-2.6) {50};
    \draw (r30)--(r20); \draw (r30)--(r40); \draw (r20)--(r10); \draw (r20)--(r25); \draw (r40)--(r50);
  \end{scope}
\end{tikzpicture}
$$

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)$.[^skiena-avl]

$$
% caption: Why deletion cascades. A rotation that repairs the subtree at $z$ leaves it one
%          shorter (height $h\to h-1$), so the height drop propagates to the parent $p$:
%          with its other subtree still height $h$, $p$'s balance becomes $\pm 2$ and must
%          itself be rotated — and that rotation can shorten $p$, unbalancing $p$'s
%          parent, all the way to the root. (Insertion never does this: its repair
%          restores the original height.)
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0, font=\small},
  tri/.style={draw, isosceles triangle, isosceles triangle apex angle=54,
    shape border rotate=90, minimum size=5mm, inner sep=1pt, font=\scriptsize},
  >=stealth, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  % before: p over z(rebalanced subtree, now h-1) and a sibling of height h
  \node (p) at (0,0) {$p$};
  \node[draw=acc, very thick, fill=acc!15] (z) at (-1.2,-1.3) {$z$};
  \node[tri, minimum size=8mm] (sib) at (1.2,-1.3) {$h$};
  \node[tri] (zl) at (-2.0,-2.5) {};
  \node[tri] (zr) at (-0.4,-2.5) {};
  \draw (p)--(z); \draw (p)--(sib); \draw (z)--(zl); \draw (z)--(zr);
  \node[draw=none, font=\scriptsize, acc, align=center] at (-1.2,-3.3) {rotated:\\heigh\/t h-1};
  \node[draw=none, font=\scriptsize, black, align=center] at (2.8,0.1) {$p$ now\\un\/balanced};
  \draw[->, black] (2.0,0.0) -- (p.east);
  % propagation arrow up
  \node[draw=none, font=\scriptsize, black] (up) at (0,1.3) {to $p$'s paren\/t ...};
  \draw[->, black] (p.north) -- (up.south);
\end{tikzpicture}
$$

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, \ldots, 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.

$$
% caption: A concrete cascade seed. Deleting $6$ from this minimal height-$3$ tree drops
%          $7$ to a leaf and pushes $5$ to balance $-2$ (LL); the right rotation at $5$
%          repairs it but leaves the tree at height $2$, one shorter — a change the
%          parent of this subtree (if any) would have to absorb in turn.
\begin{tikzpicture}[
  every node/.style={circle, draw, minimum size=7mm, inner sep=0, font=\small},
  >=stealth, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  % panel 1: before, deleting 6
  \node[draw=black, dashed, very thick] (a5) at (0,0) {5};
  \node (a3) at (-1.2,-1.1) {3};
  \node (a7) at (1.2,-1.1) {7};
  \node (a2) at (-1.9,-2.2) {2};
  \node (a4) at (-0.5,-2.2) {4};
  \node[fill=black!15] (a6) at (0.6,-2.2) {6};
  \node (a1) at (-2.4,-3.3) {1};
  \draw (a5)--(a3); \draw (a5)--(a7); \draw (a3)--(a2); \draw (a3)--(a4);
  \draw (a7)--(a6); \draw (a2)--(a1);
  \node[draw=none, font=\scriptsize, black] (bf) at (1.6,0.6) {bf -2};
  \draw[->, black] (bf.west) -- (a5.north east);
  % arrow
  \draw[->, thick] (2.6,-1.4) -- node[draw=none, above, font=\footnotesize] {delete 6} node[draw=none, below, font=\footnotesize] {righ\/t 5} (4.4,-1.4);
  % panel 2: after rotation
  \begin{scope}[xshift=6.6cm]
    \node[draw=acc, very thick, fill=acc!15] (b3) at (0,0) {3};
    \node (b2) at (-1.2,-1.1) {2};
    \node (b5) at (1.2,-1.1) {5};
    \node (b1) at (-1.8,-2.2) {1};
    \node (b4) at (0.6,-2.2) {4};
    \node (b7) at (1.8,-2.2) {7};
    \draw (b3)--(b2); \draw (b3)--(b5); \draw (b2)--(b1); \draw (b5)--(b4); \draw (b5)--(b7);
  \end{scope}
\end{tikzpicture}
$$

## 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.[^skiena-balanced]

::impl{algo="avl_tree#AVLTree"}

## 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](/algorithms/data-structures/b-trees) beats any binary tree.[^btb-avl]

## 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**.

[^erickson-avl]: **Erickson**, Ch. — Balanced Binary Search Trees: the height-balance invariant and its restoration by rotation after each update.
[^clrs-avl]: **CLRS**, Problem 13-3 — AVL Trees: the Fibonacci minimal-node recurrence $N(h)=N(h-1)+N(h-2)+1$ and the $O(\log n)$ height bound; insertion via $\textsc{Balance}$ with $O(1)$ rotations.
[^skiena-avl]: **Skiena**, §3.4 — Balanced Search Trees: AVL operations are $O(\log n)$; deletion may rebalance along the full root path.
[^skiena-balanced]: **Skiena**, §3.4 — Balanced Search Trees: the AVL-vs-red-black tradeoff — tighter balance and faster search versus cheaper update.
[^btb-avl]: Adelson-Velsky & Landis, "An algorithm for the organization of information" (1962), the original AVL tree; Haeupler, Sen & Tarjan, "Rank-balanced trees" (WAVL, 2015), interpolating between AVL and red-black balance.