AVL tree

Prerequisites

• Binary search tree insert and search.
• Height of a tree (see Binary tree basics).
• Pointer rewiring.

The analogy

How it works

Start with one rotation by hand

The balance factor of a node is height(left) − height(right) and must stay in −1, 0, +1. Insert 30, 20, 10 in that order. Predict, then open "Check".

Finish the picture: the zig-zag case

Now insert 30, 10, 20: 10 goes left of 30, then 20 goes right of 10. 30 has balance factor +2 again.

• One right rotation at 30. Predict whether it fixes the tree.
  Check

  No: 10 would become the root with 30 as its right child and 20 under 30, leaning the other way (balance −2).

• Rotate left at 10, then right at 30. Predict the result.
  Check

  The left rotation turns 30 → 10 → 20 into 30 → 20 → 10, the left-left case; the right rotation then gives 20 with children 10 and 30.

The rule in plain words

After each insert or delete, walk back up the path, updating heights. At the first node whose balance factor is ±2, rotate.

Left-left: rotate right. Right-right: rotate left. Left-right: rotate left at the child, then right. Right-left: rotate right at the child, then left.

The code

Read this code after you have done the rotation by hand. It will make more sense.

typedef struct Node { int val, h; struct Node *left, *right; } Node;

int ht(Node *t) { return t ? t->h : -1; }        /* empty tree: height -1 */
void fix(Node *t) { int l = ht(t->left), r = ht(t->right); t->h = 1 + (l > r ? l : r); }
int balance(Node *t) { return ht(t->left) - ht(t->right); }   /* must stay in -1..1 */

Node *rotate_right(Node *y) {          /* y's left child x becomes the root */
    Node *x = y->left;
    y->left = x->right;                /* x's right subtree moves under y */
    x->right = y;
    fix(y); fix(x);                    /* y is now lower: fix it first */
    return x;
}

Node *rotate_left(Node *x) {           /* mirror image of rotate_right */
    Node *y = x->right;
    x->right = y->left;
    y->left = x;
    fix(x); fix(y);
    return y;
}

flowchart TD
  A{"balance factor of the node?"} -->|"+2: left heavy"| B{"left child's balance?"}
  A -->|"-2: right heavy"| C{"right child's balance?"}
  A -->|"-1, 0, +1"| OK["no rotation"]
  B -->|"+1 or 0 (left-left)"| R["rotate right"]
  B -->|"-1 (left-right)"| LR["rotate left at child, then right"]
  C -->|"-1 or 0 (right-right)"| L["rotate left"]
  C -->|"+1 (right-left)"| RL["rotate right at child, then left"]
          

How fast is it?

The balance rule forces even the sparsest AVL tree to have many nodes, which caps the height:

A rotation changes three pointers and two heights, which is $O(1)$. An insert needs at most one single or double rotation; a delete may need one per level, still $O(\log n)$.

Common mistakes

• Using a single rotation for a zig-zag (left-right or right-left) case.
• Forgetting that the rotated subtree's new root must be linked back into its parent.
• Mixing the height conventions, so leaves get balance factors that look wrong.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Every operation is $O(\log n)$ because the balance rule keeps the height below $1.44 \log_2 n$.
• Rotations keep the tree a valid BST because they never change the in-order sequence of keys.
• A rotation is $O(1)$ because it rewires a fixed number of pointers.
• Zig-zag cases need two rotations because the heavy grandchild sits in the middle.
• Heights are fixed bottom-up because a parent's height depends on its children's.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is AVL rebalancing like adjusting a baby's mobile?
   Sample answer

   When one side gets too heavy, you move the hanging point to balance it without changing what hangs where; a rotation moves a node up while keeping the key order.

2. Walk through inserting 30, 20, 10 into an AVL tree.
   Sample answer

   After 10, node 30 has balance +2 (left-left case), so rotate right at 30: 20 becomes the root with 10 and 30 as children.

3. Why does rotate_right call fix(y) before fix(x)?

   A good answer says which node is lower after the rotation.

   Sample answer

   After rotating, y is x's child. x's height depends on y's, so y must be updated first.

4. So what is an AVL tree, in one sentence?
   Sample answer

   A self-balancing BST where every node's subtrees differ in height by at most one, kept that way with rotations.

5. Why does the insertion order 30, 10, 20 need two rotations?

   A good answer describes the shape.

   Sample answer

   The path to 20 goes left then right, a zig-zag. A single right rotation just mirrors the imbalance; rotating left at 10 first turns it into a straight left-left line that one right rotation fixes.

6. What do search, insert, delete and one rotation cost?
   Sample answer

   Search, insert and delete are $O(\log n)$; a single rotation is $O(1)$.

7. Why is an AVL tree better than a plain BST for sorted input?
   Sample answer

   A plain BST becomes a chain with $O(n)$ operations; the AVL tree rotates as it goes and stays $O(\log n)$ high.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the $1.44 \log_2 n$ bound and the height-update order. I'd keep the mobile analogy, the 30-20-10 right rotation, the four cases, and "guaranteed $O(\log n)$".

External resources

• VisuAlgo: AVL tree: switch to "AVL" and watch rotations happen on insert.
• GeeksforGeeks: AVL tree: the four rotation cases with diagrams.
• Wikipedia: AVL tree: history, height bound and comparison with red-black trees.
• MIT OCW 6.006: lecture on balanced binary trees.

Videos

• YouTube search: AVL tree rotations: pick a walkthrough of all four cases.