AVL tree

How an AVL tree works

Step by step

1. Start empty. Insert 10, then 20 - it lands right of 10. Balance factors read 0 and -1, all within range.
2. Insert 30: it attaches right of 20, and 10's balance factor drops to -2. The invariant is broken at 10.
3. 30 went right of 10's right child - Right-Right. One left rotation about 10: 20 becomes the root, 10 and 30 its children.
4. Insert 5 as 10's left child. The root's balance factor moves to +1 - legal, so nothing rotates.
5. Insert 3: node 10 hits +2, and 3 sits left of 10's left child 5 - Left-Left. Rotate right about 10.
6. 5 now heads that subtree with 3 and 10 as children. Five keys, height 3 - the minimum possible - despite two forced repairs.

Complexity

Reference implementation

def height(n):  return n.height if n else 0
def balance(n): return height(n.left) - height(n.right) if n else 0

def rotate_right(y):
    x, t2 = y.left, y.left.right
    x.right, y.left = y, t2                     # rotate
    y.height = 1 + max(height(y.left), height(y.right))
    x.height = 1 + max(height(x.left), height(x.right))
    return x                                     # x is the new subtree root

def rotate_left(x):
    y, t2 = x.right, x.right.left
    y.left, x.right = x, t2
    x.height = 1 + max(height(x.left), height(x.right))
    y.height = 1 + max(height(y.left), height(y.right))
    return y

def insert(node, k):
    if node is None:
        return Node(k)
    if k < node.key:   node.left  = insert(node.left, k)
    elif k > node.key: node.right = insert(node.right, k)
    else:              return node

    node.height = 1 + max(height(node.left), height(node.right))
    b = balance(node)
    if b > 1 and k < node.left.key:   return rotate_right(node)   # LL
    if b < -1 and k > node.right.key: return rotate_left(node)    # RR
    if b > 1:                                                     # LR
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if b < -1:                                                    # RL
        node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

const h = (n) => (n ? n.height : 0);
const bal = (n) => (n ? h(n.left) - h(n.right) : 0);

function rotateRight(y) {
  const x = y.left;
  y.left = x.right;
  x.right = y;
  y.height = 1 + Math.max(h(y.left), h(y.right));
  x.height = 1 + Math.max(h(x.left), h(x.right));
  return x;
}

function rotateLeft(x) {
  const y = x.right;
  x.right = y.left;
  y.left = x;
  x.height = 1 + Math.max(h(x.left), h(x.right));
  y.height = 1 + Math.max(h(y.left), h(y.right));
  return y;
}

Common pitfalls

• Refreshing heights in the wrong order after a rotation. The demoted node is now a child, so its height must be recomputed before the promoted node's - reversed, both are stale.
• Forgetting that a rotation returns a new subtree root. The parent must be relinked to it, as in node.left = rotateLeft(node.left) - otherwise the rotated nodes leak out of the tree.
• Fixing Left-Right with a single right rotation. That just mirrors the imbalance into Right-Left; the left child must first be rotated left, then the node rotated right.
• Choosing the case by comparing the inserted key works during insert, but delete-time rebalancing has no inserted key - there you must read the child's balance factor instead.
• Recomputing heights recursively on demand. That makes every insert O(n); the design depends on each node caching its own height and updating it in O(1).

Where it is used

• Ordered maps where lookups dominate writes - AVL's stricter balance keeps searches slightly shorter than a red-black tree's.
• In-memory indexes that need hard worst-case bounds rather than average-case comfort.
• The canonical whiteboard exercise for rotations - the same mechanics reappear in red-black trees, treaps, and B-trees.
• Any workload that might see sorted or adversarial insertion order, where a plain BST would quietly degrade to O(n).

Frequently asked questions