AVL Trees

1AVL: a BST with |BF| at most 1

An AVL tree is a binary search tree that adds one extra rule: at every node the balance factor has absolute value at most 1. The balance factor of a node v is BF(v) = h(v.\mathrm{left}) - h(v.\mathrm{right}), and the height of an empty child is -1. A leaf therefore has BF = 0. The tree is still a BST — left keys smaller, right keys larger — so search still follows one child per level.

Without that height rule a BST can become a single chain, and search degrades to O(n). The AVL rule is what turns the height label into a guaranteed O(\log n).

Figure. A 3-node AVL. Each node is labelled key and balance factor; all three factors are 0.

How to read one node

1. Heights firstHeight of a node is 1 + \max of its children's heights; an empty child is -1.
2. SubtractBF = h(\mathrm{left}) - h(\mathrm{right}). Convention is left minus right — flip the sign and every later case name flips with it.
3. Legal values-1, 0 or 1 is allowed. |BF| = 2 is the moment a rotation is required.

2Worst AVL height is still O(log n)

The sparsest AVL of height h has one side of height h-1 and the other of height h-2 — the most unbalanced shape the |BF| \le 1 rule still allows. So the minimum number of nodes satisfies n(h) = 1 + n(h-1) + n(h-2) with n(0) = 1 and n(1) = 2. That is a Fibonacci recurrence: n(h) = F_{h+3} - 1.

Fibonacci numbers grow as \varphi^h / \sqrt{5}, so inverting gives h = O(\log n). An AVL cannot become a list. A plain BST can.

Figure. Minimum AVL node counts: 1, 2, 4, 7. Each bar is 1 plus the two previous — Fibonacci, not 2^h.

Why the recurrence is Fibonacci

1. Most skewed legalTo minimise nodes at height h, give one child height h-1 and the other h-2.
2. Add the rootn(h) = 1 + n(h-1) + n(h-2).
3. Invertn(h) \ge c \cdot \varphi^h implies h \le O(\log n).

3Four cases: LL, RR, LR, RL

When a node first reaches |BF| = 2, the repair is a rotation named by the first two child steps from that node toward the inserted (or repaired) key. Left-left and right-right are single rotations. Left-right and right-left are a rotation on the child, then a rotation on the node.

A right rotation on y promotes y's left child x and hangs x's old right subtree on y's left. A left rotation is the mirror. Each rotation is O(1) pointer writes. The BST order is preserved because every key that was between x and y stays between them.

Right rotation on y: y's left child x becomes the new subtree root; x's old right subtree T2 becomes y's new left child; y becomes x's right child. BST order is unchanged because every key in T2 still sits between x and y.

Pick the rotation

1. Find the culpritThe lowest node with |BF| = 2 is where you rotate.
2. Read two stepsFrom that node, left then left is LL (right-rotate). Right then right is RR (left-rotate).
3. The mixed casesLR: left-rotate the left child, then right-rotate the node. RL is the mirror.

Right rotation

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

4Insert: BST hang, then rebalance up

AVL insert is ordinary BST insert — hang the new key at the null child where search dies — then walk back toward the root updating heights. The first ancestor whose |BF| becomes 2 is rotated with the matching case. After that one repair (a single or a double rotation) the path above is balanced again, so insert performs at most one rebalance.

The new key itself is never rotated as the first step; the rotation sits at the lowest unbalanced ancestor.

Insert 30 after 10, 20

1. Hang as a BST30 is larger than 10 and 20, so it becomes the right child of 20.
2. Update heightsh(30)=0, h(20)=1, h(10)=2, so BF(10) = -1 - 1 = -2.
3. RR, then left-rotateTwo steps from 10 toward 30 are right, right. Left-rotate at 10. New root 20, children 10 and 30.

AVL insert

def insert(node, key):
    if node is None:
        return Node(key)
    if key < node.key:
        node.left = insert(node.left, key)
    elif key > node.key:
        node.right = insert(node.right, key)
    node.height = 1 + max(h(node.left), h(node.right))
    bf = h(node.left) - h(node.right)
    if bf > 1 and key < node.left.key:
        return rotate_right(node)
    if bf < -1 and key > node.right.key:
        return rotate_left(node)
    if bf > 1 and key > node.left.key:
        node.left = rotate_left(node.left)
        return rotate_right(node)
    if bf < -1 and key < node.right.key:
        node.right = rotate_right(node.right)
        return rotate_left(node)
    return node

Coding lab. Insert 10, 20, 30 and rotate runs in the app, with checks on your output.

5Delete: BST remove, then rebalance every ancestor

AVL delete starts as BST delete: a leaf is dropped; a one-child node is replaced by that child; a two-child node is replaced by its in-order successor (or predecessor) and that successor is deleted. Then every ancestor of the hole updates its height. Unlike insert, several ancestors can now have |BF| = 2, so you may rotate more than once on the way to the root.

The case names are the same four. After a delete the two-step path is read toward the taller remaining child, not toward a newly inserted key.

Delete 30 from a 4-node AVL

1. BST delete30 is a leaf. Remove it.
2. RecomputeRoot 20 now has left height 1 and no right child, so BF(20) = 1 - (-1) = 2.
3. LL, right-rotateThe remaining child 10 is left-heavy (BF = +1). Right-rotate at 20. New root 10, children 5 and 20.

6When to reach for an AVL

An AVL is the right structure when you need an in-memory ordered map or set — search, predecessor, successor, range — and every write must leave the height O(\log n). Language standard libraries often pick a red-black tree instead: the same O(\log n) guarantee with a looser balance rule and fewer rotations on write-heavy traces.

An AVL is the wrong first pick when the keys live on disk or in a huge file. There a B-tree (or B+ tree) wins, because one node holds many keys and one I/O jumps many levels. Do not treat AVL, red-black and B-tree as synonyms for balanced.

Figure. Bars are a qualitative cost sketch, not a shared unit: skew walks n pointers; AVL walks O(\log n) pointers; a B-tree walks a handful of pages.

Pick the balanced tree

1. In-memory ordered mapAVL or red-black. AVL if you want the tighter height; red-black if writes dominate.
2. On disk / huge filesB-tree or B+ tree — high fan-out, few I/Os. An AVL of n pointers is the wrong page layout.
3. Only inserts at the endA sorted array or a hash table may be enough; balance is a write-anywhere cost.