7.1 AVL Trees: Properties and Operations

AVL trees are self-balancing binary search trees that automatically maintain a balanced structure after every insertion and deletion. This balance guarantee is what makes them useful: while a plain BST can degrade to $O(n)$ height if you insert sorted data, an AVL tree always stays at $O(\log n)$ height, keeping search, insertion, and deletion fast.

AVL Tree Properties

An AVL tree is a BST with one extra rule: for every node in the tree, the heights of its left and right subtrees can differ by at most 1. This is called the height-balance property.

• Balance factor of a node is defined as $height(left\ subtree) - height(right\ subtree)$
• For a tree to be AVL-valid, every node's balance factor must be $-1$, $0$, or $1$
• Stated formally: $|height(left\ subtree) - height(right\ subtree)| \leq 1$ for all nodes

Why does this matter? This constraint keeps the tree's overall height at $O(\log n)$ for $n$ nodes. You can prove this using Fibonacci-like minimum AVL trees: the minimum number of nodes in an AVL tree of height $h$ satisfies $N(h) = N(h-1) + N(h-2) + 1$, which grows exponentially. That means height grows only logarithmically with $n$.

A null (empty) subtree has height $-1$ by convention, and a leaf node has height $0$. Getting this convention right matters when you're computing balance factors during implementation.

AVL Tree Operations

Insertion

Insertion is a two-phase process:

1. Insert like a normal BST. Walk down the tree comparing keys, and place the new node at the appropriate leaf position.
2. Walk back up to the root, updating heights and checking the balance factor at each ancestor node.
3. If any node's balance factor becomes $-2$ or $2$, the tree is unbalanced at that node. Perform the appropriate rotation (see below) to fix it.

One key detail: after an insertion, you only ever need one rotation (single or double) to restore balance. Once you fix the first unbalanced ancestor, all ancestors above it will also be balanced. This is not true for deletion.

Deletion

Deletion works similarly but with an important difference:

1. Delete like a normal BST. If the node has two children, replace it with its in-order successor (or predecessor), then delete that successor node.
2. Walk back up from the deleted node's parent to the root, updating heights and checking balance factors.
3. If any node is unbalanced, perform the appropriate rotation.

Unlike insertion, a single deletion can require multiple rotations along the path to the root. Each rotation can reduce the height of a subtree, which may unbalance an ancestor further up.

Time Complexity

All three core operations run in $O(\log n)$ worst-case time:

• Search: Standard BST search. Since the height is $O(\log n)$, you visit at most $O(\log n)$ nodes.
• Insertion: The BST insertion walk is $O(\log n)$. Rebalancing requires at most one rotation, which is $O(1)$. Total: $O(\log n)$.
• Deletion: The BST deletion walk is $O(\log n)$. Rebalancing may require up to $O(\log n)$ rotations in the worst case, but each rotation is $O(1)$, so the total is still $O(\log n)$.

Rotations for AVL Rebalancing

Rotations are the mechanism that restores balance. There are four cases, determined by where the imbalance is and which direction the heavy subtree leans. Think of it as: first identify the unbalanced node, then look at its heavy child's balance factor to pick the right rotation.

Single Rotations:

• Right Rotation (RR): The node has balance factor $+2$ and its left child has balance factor $+1$ or $0$ (left-left case). The left child becomes the new subtree root, and the original node becomes its right child.
• Left Rotation (LL): The node has balance factor $-2$ and its right child has balance factor $-1$ or $0$ (right-right case). The right child becomes the new subtree root, and the original node becomes its left child.

Double Rotations:

• Left-Right Rotation (LR): The node has balance factor $+2$ and its left child has balance factor $-1$ (left-right case).

  1. Perform a left rotation on the left child.
  2. Perform a right rotation on the unbalanced node.

• Right-Left Rotation (RL): The node has balance factor $-2$ and its right child has balance factor $+1$ (right-left case).

  1. Perform a right rotation on the right child.
  2. Perform a left rotation on the unbalanced node.

A quick way to remember: if the imbalance and the heavy grandchild are on the same side (left-left or right-right), you need a single rotation. If they're on opposite sides (left-right or right-left), you need a double rotation that first straightens the path, then rotates.