Skip to content
Tutorials Center
My learning

Topics

Lesson 98 of 225 ยท Trees

Self-Balancing Trees: AVL

Learn AVL trees in Python: balance factor, left and right rotations, the LL, RR, LR and RL cases, insert and delete with rebalancing, and the height guarantee.

In the previous lessons a plain binary search tree had one fatal weakness: its speed depends on its shape. Insert sorted keys and it collapses into a chain where every operation costs O(n). A self-balancing tree repairs its own shape after every insertion and deletion so the height always stays close to log n. Then search, insert and delete are all guaranteed O(log n), no matter what order the data arrives in.

The AVL tree, invented in 1962 by Adelson-Velsky and Landis, was the first such structure. Its rule is simple and strict: for every node, the heights of the left and right subtrees differ by at most 1. When an insertion or deletion breaks the rule, a small local rearrangement called a rotation fixes it. Understanding rotations is the whole lesson; after that, AVL insertion is about twenty lines of code.

Height, balance factor and the AVL rule

Here we measure height in nodes (a single node has height 1, an empty subtree has height 0), and store each node's height inside the node so we never recompute it.

The balance factor of a node is height(left) - height(right). In a valid AVL tree it is always -1, 0 or +1.

TEXT
 balance factor +2          balance factor 0           balance factor -2
 (left-heavy: too tall)     (perfectly even)           (right-heavy: too tall)

        30                       20                          10
       /                        /  \                           \
     20                        10   30                         20
    /                                                            \
  10                                                              30

Notice that the tree on the left is a valid binary search tree. It is just lopsided. The rotations below reshape it without changing the BST order, so the inorder sequence stays exactly the same.

Rotations

A rotation is a local change of three pointers that moves one node up and one down while keeping the BST rule intact.

A right rotation around y lifts its left child x into y's place. Because x > everything in x.left and x < y, the subtree that was between them (x.right, call it B) fits exactly as y's new left child:

TEXT
Right rotation at y                      Left rotation at x is the mirror

        y                x                   x                  y
       / \              / \                 / \                / \
      x   C    ->      A   y               A   y      ->      x   C
     / \                  / \                 / \             / \
    A   B                B   C               B   C           A   B

In both pictures the inorder order is A x B y C. Nothing is reordered; subtrees merely change parents. The cost is O(1): a few pointer assignments and two height updates.

Python Rotations keep the inorder sequence

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The order of the two update calls matters: after a rotation the old parent has become a child, so its height must be recomputed before the new parent's.

The four imbalance cases

When you insert a key, only the nodes on the path from the root to the new leaf can become unbalanced. Walk back up that path (the recursion does this for free), recompute heights, and at the first node whose balance factor reaches +2 or -2, apply one of four fixes. Name each case by where the new key landed relative to the unbalanced node:

Case Cause Fix
Left-Left (LL) Inserted into the left subtree of the left child Right rotation at the node
Right-Right (RR) Inserted into the right subtree of the right child Left rotation at the node
Left-Right (LR) Inserted into the right subtree of the left child Left rotation at the left child, then right rotation at the node
Right-Left (RL) Inserted into the left subtree of the right child Right rotation at the right child, then left rotation at the node
TEXT
LL: insert 30, 20, 10                                  LR: insert 30, 10, 20

      30                20                                30             30             20
     /                 /  \                              /              /              /  \
   20       ->       10    30                          10      ->     20      ->     10    30
  /                                                       \           /
10                                                         20       10
   right rotation at 30                      left rotation at 10, then right rotation at 30

The double cases exist because a single rotation does not help when the heavy grandchild is on the inside: rotating a zig-zag just moves the zig-zag to the other side. First straighten it into a line (the first rotation), then lift the middle node (the second).

How do you tell which case you are in? Look at the balance factor of the heavy child:

  • node has balance +2 (left-heavy): if the left child's balance is >= 0 it is LL, if it is < 0 it is LR.
  • node has balance -2 (right-heavy): if the right child's balance is <= 0 it is RR, if it is > 0 it is RL.

The full AVL insert

Python AVL tree with insert and rebalancing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All four cases turn a three-node chain into the same balanced tree with 20 at the top. The last example inserts six keys: inserting 30 triggers an RR fix, inserting 50 triggers a second one, and 25 fits without any rotation. The checker is_avl confirms that the final tree obeys the rule and that every stored height is correct.

One more fact makes the algorithm cheap: after an insertion, at most one rebalancing step (a single or double rotation) is needed, because the fix restores the subtree to its height from before the insert. After a deletion, rotations may be needed at several levels up the path, but never more than O(log n) of them.

The height guarantee

Why is an AVL tree's height O(log n)? Ask the opposite question: what is the smallest number of nodes N(h) an AVL tree of height h can have? To be as thin as possible, the root has one subtree of height h - 1 and the other of height h - 2 (the biggest imbalance allowed):

TEXT
N(h) = N(h-1) + N(h-2) + 1      with N(0) = 0 and N(1) = 1

This is the Fibonacci recurrence, so N(h) grows exponentially (about 1.618 times per level). Turn it around: the height of an AVL tree with n nodes is at most about 1.44 * log2(n). A perfect tree would have log2(n), so AVL is at most 44% taller than the ideal, and that is the worst case.

Python AVL height guarantee vs a plain BST

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For 1,000 sorted keys the plain BST is a chain 1,000 nodes tall, while the AVL tree stays around 10 levels. The first line of output lists the thinnest possible AVL trees: height 10 needs at least 143 nodes, so no AVL tree with fewer nodes can be that tall.

Deletion

Deleting from an AVL tree is a BST deletion (leaf, one child, or replace by the inorder successor) followed by the same rebalance call on every node on the way back up. The only difference from insertion is that fixing one node can shorten that subtree, which may unbalance an ancestor, so the rebalance has to be applied at every level of the path, not just once.

Python AVL delete with rebalancing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Even after four deletions from the left half, the height stays 4 and the root is still 8: whenever a subtree got too short, rebalance repaired it on the way back up. Try deleting more keys and watch the root and height change.

AVL versus other structures

Structure Search Insert Delete Height bound
Plain BST O(h) O(h) O(h) up to n - 1
AVL tree O(log n) O(log n) O(log n) at most about 1.44 log2 n
Red-black tree O(log n) O(log n) O(log n) at most 2 log2 n

AVL trees are more strictly balanced, so lookups are slightly faster, but they perform more rotations on updates. Red-black trees balance more loosely, so writes are cheaper; this is why many standard libraries use them. See Red-Black Trees, Splay and Treaps for the comparison. For data on disk, B-trees win.

In Python you will rarely write an AVL tree for production: a dict covers lookups, bisect covers static sorted data, and third-party sortedcontainers covers dynamic sorted data. But AVL rotations are the foundation for understanding every other balanced tree, and they are a favorite interview topic.

Common mistakes

  • Updating heights in the wrong order after a rotation: lower node first, then the new root of the subtree.
  • Using the wrong double rotation. LR means a left rotation on the left child first, then a right rotation on the node. Say it out loud as "fix the inside, then lift".
  • Forgetting to reassign the returned subtree root (node.left = rotate_left(node.left)). Rotations return a new root; if you drop it, the tree loses nodes.
  • Not rebalancing on the way up after a delete at every level.
  • Mixing height conventions (nodes vs edges) so balance factors come out wrong: pick one, and make None match it.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the AVL rule?

    The balance factor (height of left minus height of right) must be -1, 0 or +1 for every node, not only the root.
  2. 2. A node has balance factor +2 and its left child has balance factor -1. Which fix applies?

    The heavy part is the inside (right) side of the left child: the Left-Right case. Straighten it with a left rotation on the left child, then rotate the node right.
  3. 3. Which property does a rotation preserve?

    Rotations only change parent-child links; the left-to-right order of the keys (the inorder traversal) stays identical.
  4. 4. Keys 1 to 7 are inserted in ascending order into an empty AVL tree. What is the height (in nodes) of the result?

    Rotations turn the sorted input into a perfect tree: 7 nodes fit into height 3, with 4 at the root.
  5. 5. Roughly how tall can an AVL tree with n nodes be?

    The sparsest AVL trees follow a Fibonacci recurrence, which grows exponentially with height, so the height is logarithmic in n.

Summary

  • An AVL tree is a BST that keeps every node's balance factor (left height minus right height) within -1, 0, +1, giving O(log n) search, insert and delete.
  • A rotation is an O(1) local rearrangement that changes the shape but not the inorder order.
  • Four imbalance cases: LL (right rotation), RR (left rotation), LR (left then right), RL (right then left); the child's balance factor tells you which one you have.
  • Store heights in the nodes and call one rebalance on every node along the path back up after an insert or delete.
  • The height is at most about 1.44 log2 n because the thinnest AVL trees follow the Fibonacci recurrence.
  • Next: other balanced trees trade strictness for cheaper updates (red-black), simplicity (treap) or disk friendliness (B-trees).

Next: Red-Black Trees, Splay and Treaps