11. AVL Trees

The invariant and why it controls height#

Use the lecture's edge-count convention: an empty tree has height $-1$ and a leaf has height 0. Define the balance factor of a nonempty node $t$ by

$$b(t)=h(t_L)-h(t_R).$$

Positive means left-heavy; negative means right-heavy. An AVL tree requires $b(t)\in\{-1,0,1\}$ at every node, in addition to the BST ordering invariant. Left-heavy by one is allowed. Left-heavy by two needs repair.

To see why this forces logarithmic height, ask for the fewest nodes that can support height $h$. Call that count $N(h)$. For a tallest child of height $h-1$, the other child must have height at least $h-2$ to satisfy balance. Thus

$$N(-1)=0,\quad N(0)=1,\quad N(h)=1+N(h-1)+N(h-2).$$

The first counts are 0,1,2,4,7,12,20,33 for heights $-1$ through 6. This is a Fibonacci-like recurrence: the minimum node count grows exponentially with height, so height grows logarithmically with node count. The lecture gives a tighter approximation with coefficient about $1.44\log_2 n$; the important guarantee is $h=O(\log n)$, without any assumption about insertion order.

Practice. Can an AVL tree with root 4, left subtree 2 with children 1 and 3, and right leaf 5 be valid even though its left subtree has three times as many nodes as its right?

Store height to make balance checks cheap#

Computing ordinary tree height recursively visits all nodes of a subtree. Calling that repeatedly during insertion does not give a constant-time balance check. Store the height in each node instead:

#include <assert.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct avlNode ANode;
struct avlNode { int item, height; ANode *left, *right; };
int height(const ANode *t) { return t == NULL ? -1 : t->height; }
void updateHeight(ANode *t) {
    int l = height(t->left), r = height(t->right);
    t->height = 1 + (l > r ? l : r);
}
int balance(const ANode *t) {
    return height(t->left) - height(t->right);
}
ANode *avlNew(int v) {
    ANode *p = malloc(sizeof *p);
    if (p == NULL) abort();
    *p = (ANode){.item = v, .height = 0, .left = NULL, .right = NULL};
    return p;
}

balance above expects a nonnull node; callers check that first. Reading a child's cached height takes $O(1)$ even for a large child subtree. The cache is an additional invariant: its stored value must equal the actual height after every completed operation.

The lecture image uses small labels next to keys for heights. A label 3 next to root 6 means its longest path has three edges, not that the key has become 3.

Only ancestors of an inserted or physically removed node can acquire changed heights. Recompute from bottom to top, so a parent's inputs are already correct. If a child of height 0 and an empty child of height $-1$ belong to node 5, its height becomes $1+\max(0,-1)=1$.

Rotations must maintain metadata#

The links are the rotations from 10. Balancing Binary Search Trees, but now update the old root first and the new root second:

ANode *avlRotateRight(ANode *t) {
    assert(t != NULL && t->left != NULL);
    ANode *r = t->left;
    t->left = r->right;
    r->right = t;
    updateHeight(t);
    updateHeight(r);
    return r;
}
ANode *avlRotateLeft(ANode *t) {
    assert(t != NULL && t->right != NULL);
    ANode *r = t->right;
    t->right = r->left;
    r->left = t;
    updateHeight(t);
    updateHeight(r);
    return r;
}

After rotating right at 7, node 7 has leaf children 6 and 9, so its height is 1. Then promoted root 4 has children of heights 1 and 1, so its height is 2. Updating 4 first would read the old, stale height of 7.

The rotation changes only two node heights; the internal heights of the transferred subtrees stay unchanged. Both updates are $O(1)$, so a metadata-aware rotation remains constant time.

Practice. Why can a correct-looking pointer diagram still fail as an AVL implementation?

Four local repair cases#

An insertion or deletion changes one child subtree's height by at most one. If both child subtrees were already AVL and are repaired before returning, an affected parent can become unbalanced by two. Inspect which child is taller and whether that child leans inward or outward.

The names describe the direction from the unbalanced parent toward the taller child's taller side. They do not name the direction of the final rotation. The equality cases matter especially after deletion.

For a small LL example, insert 3,2,1: 3 has balance +2, and child 2 has +1. Rotate right at 3 to make 2 root with leaves 1 and 3. The mirrored RR example inserts 1,2,3 and rotates left at 1.

For LR, insert 3,1,2. Parent 3 is left-heavy, but child 1 is right-heavy: the path bends inward. Rotating right immediately would leave a chain rooted at 1. First rotate left at 1, turning the branch into the LL shape 3←2←1; then rotate right at 3. The final root is 2 with leaves 1 and 3.

RL is its mirror. The following original three-node lesson inserts 10,30,20 and shows both rotations, including the still-unbalanced intermediate state. Watch the inward bend straighten before the parent rotates.

Read the highlighted pseudocode against the C below: avlInsert follows the comparison path, returns an updated child, and avlRebalance reads cached heights. For the negative parent factor and positive right-child factor, the helper first assigns t->right = avlRotateRight(t->right), then returns avlRotateLeft(t). Each rotation changes a fixed number of pointers and height fields, hence $O(1)$ time. The descent and return visit at most $O(\log(n+1))$ nodes because the pre-operation tree is AVL. The player deliberately distinguishes the inserted, temporarily unbalanced state from the repaired result.

The ordering inequalities from the rotation note ensure each step remains a BST. The combination restores balanced child heights because the former middle key becomes parent of the two outer keys; it redistributes the oversized path rather than merely exchanging which end is tall.

Practice. Root 40 has balance +2; its left child 20 has balance -1. Which operation comes first, and why is a single right rotation insufficient in general?

One shared rebalance helper#

/* Children must already be AVL and have correct cached heights. */
ANode *avlRebalance(ANode *t) {
    if (t == NULL) return NULL;
    updateHeight(t);
    int b = balance(t);
    if (b > 1) {
        if (balance(t->left) < 0)
            t->left = avlRotateLeft(t->left);
        return avlRotateRight(t);
    }
    if (b < -1) {
        if (balance(t->right) > 0)
            t->right = avlRotateRight(t->right);
        return avlRotateLeft(t);
    }
    return t;
}

This helper is intended for a tree arising from one AVL insertion/deletion along a recursive path, so imbalance magnitude is at most two after child repairs. It is not a global converter for an arbitrary badly skewed BST. Applying one local repair to a general chain need not establish balance everywhere.

Insertion: repair on the return path#

ANode *avlInsert(ANode *t, int v) {
    if (t == NULL) return avlNew(v);
    if (v < t->item) t->left = avlInsert(t->left, v);
    else if (v > t->item) t->right = avlInsert(t->right, v);
    else return t; // No duplicate occurrence.
    return avlRebalance(t);
}

The descent is ordinary BST insertion. The difference is the return: retain the updated child, then recalculate the current height and repair the current subtree. Only the search-path ancestors need checking because no other subtree changed. The client must retain root = avlInsert(root, v) because rotations can change the entire root.

Lecture LL example#

Start with root 6, left subtree root 2 (left 1, right 5 with left 3), and right subtree root 9 with left 8. Insert 7: take right at 6, left at 9, left at 8. Seven becomes 8's left leaf.

On return, 8 gets height 1 and balance +1. Node 9 now has left height 1 and empty right height $-1$, so balance is +2. Child 8 is left-heavy, giving LL: rotate right at 9. The right subtree of 6 now has root 8 and leaves 7,9. Root 6 remains balanced.

Lecture LR example#

Return to the same initial tree and insert 4 instead. The comparison path is 6→2→5→3→null on 3's right. Three becomes height 1, still balanced. Node 5 has left height 1 and right height $-1$, balance +2; its left child 3 has balance -1, so this is LR.

Rotate left at 3, promoting 4 over 3. Then rotate right at 5, promoting 4 over 5. The repaired local subtree has root 4 and leaves 3 and 5. Heights at 2 and 6 are recomputed using that result, as shown on the right:

The bottom-up order is doing two jobs: each returned subtree is a valid AVL tree, and its height is accurate for its parent. That recursive invariant proves the final result is AVL. At the first unbalanced ancestor after insertion, the repair restores the subtree's pre-insertion height, so no further structural insertion repair is needed above it; the generic recursive code can still check all ancestors safely.

Practice. In the LR example, why is 5 repaired before checking root 6?

Search and complexity#

Search is exactly ordinary BST search. Balance factors are irrelevant to deciding left or right; they matter because they bound how many such decisions are needed.

For $n$ stored keys, AVL height is $O(\log(n+1))$. Insertion descends one path and performs $O(1)$ work per returning ancestor: a cached-height update, balance comparisons, and at most two local rotations. Therefore worst-case insertion is $O(\log(n+1))$, and so is worst-case search. Finding a root key is still $O(1)$; the guarantee is a worst-case upper bound, not the claim that every query traverses every level.

Recursive insertion uses $O(\log(n+1))$ auxiliary stack space; iterative search can use $O(1)$. The stored tree uses $\Theta(n)$ nodes with an additional height field per node. Constructing a tree by $n$ successive AVL insertions takes $O(n\log(n+1))$ worst-case time, unlike one operation on an existing tree. Traversing every key still takes $\Theta(n)$: balance cannot remove the obligation to visit/output $n$ values.

Practice. If the tree is already AVL but your implementation calls recursive full-subtree height computations in every balance check, is the insertion automatically $O(\log n)$?

Deletion: follow the physical removal#

BST deletion can shrink a subtree and create imbalance in an ancestor. Use the ordinary deletion cases, then call the same rebalance helper while returning. If the node has two children, copy its successor value and recursively delete that successor from the right subtree.

ANode *avlDelete(ANode *t, int v) {
    if (t == NULL) return NULL;
    if (v < t->item) t->left = avlDelete(t->left, v);
    else if (v > t->item) t->right = avlDelete(t->right, v);
    else {
        if (t->left == NULL || t->right == NULL) {
            ANode *child = t->left != NULL ? t->left : t->right;
            free(t);
            return child;
        }
        ANode *successor = t->right;
        while (successor->left != NULL) successor = successor->left;
        t->item = successor->item;
        t->right = avlDelete(t->right, successor->item);
    }
    return avlRebalance(t);
}
void avlFree(ANode *t) {
    if (t == NULL) return;
    avlFree(t->left);
    avlFree(t->right);
    free(t);
}

The changed deletion path includes the successor's old ancestors, not merely the path to the key originally requested. Copying a value changes no height; physically unlinking the successor can change many heights on the return path. A plain bstJoin is therefore not a drop-in replacement unless its entire modified path also maintains AVL metadata and balance.

For the lecture's deletion of 6 in the tree rooted at 19, successor 11 replaces the key at 6. Eleven's old position inside the subtree rooted at 16 is removed, leaving 12 as 16's left child. Update 16 first, then the replacement node 11, then 19. The final height labels are shown below:

Deletion can trigger multiple repairs#

Insertion repair restores the repaired subtree's old height, but deletion repair may still reduce its height. That change can make its parent unbalanced. Continue checking all ancestors; deletion may need $O(\log n)$ rotations in total while still doing only constant work per path node.

In the lecture RL example, root 9 has left subtree rooted at 5, and taller right subtree rooted at 16 whose own left subtree is rooted at 12. Deleting key 2 promotes its child 3 and shortens the left side. At 5 the balance remains valid, but at 9 the factor becomes -2. Right child 16 is left-heavy, so rotate right at 16, then left at 9. The resulting root is 12:

The lecture's RR example deletes root key 8 using successor 9. The successor is removed from the subtree rooted at 13, leaving 13 left-short and right-heavy. Its right child 17 also leans right, so rotate left at 13. The overall root remains the replacement key 9, while its right subtree now starts at 17:

The zero-balance child case#

After deletion, a parent's factor can be +2 while its left child's factor is zero. Use a single right rotation, exactly as the >=0 LL row states. For example, begin with root 4, left subtree 2 with leaves 1 and 3, and right leaf 5. Delete 5. Root 4 becomes +2, child 2 is 0, and rotating right gives root 2, left 1, right 4 with left 3. The new child heights are 0 and 1, both acceptable.

This cannot be classified by the deleted key's direction alone: deleting on the right can cause the left side to be too tall. Inspect actual child balances. The right-heavy zero-child case is symmetric and needs a single left rotation. The helper deliberately uses <0 for an LR child and >0 for an RL child, so zero falls into the single-rotation branches.

Practice. When deleting a two-child root, why is rebalancing only at the root insufficient?

Practice. Does deletion have the same logarithmic worst-case time bound if it may perform more rotations than insertion?

More exam-style practice#

Work each prompt before opening its answer. State the invariant or cost assumption that makes your reasoning valid.

Question 1. Insert 30,10,20 into an AVL tree. Name the imbalance, rotations and final root.

Question 2. After deleting a node from an AVL tree, why must the algorithm keep examining ancestors even after one rotation repairs the first unbalanced subtree?

Question 3. A node has left-subtree height 2 and right-subtree height 4. Is it AVL-balanced? State what information is needed to choose the repair.

Choosing an AVL representation#

For a set, an AVL tree gives worst-case logarithmic contains, insert and delete without random-input assumptions. It also supports sorted traversal, minimum/maximum and range queries through BST ordering. An ordered array has compact storage and fast searching, but general updates shift a linear number of values. A linked list changes links cheaply only after a linear search for the location. Hash tables offer expected constant-time membership under suitable hashing/load assumptions but do not naturally retain sorted order.

An AVL implementation pays for node allocations, pointer links and height maintenance. That cost is worthwhile when reliable update/search bounds and ordered operations matter. It does not make whole-tree output sublinear, and maintaining height does not automatically give constant-time size: add and maintain a separate size cache if that operation needs it.

Practice. A set changes frequently and must print its values in ascending order regularly. What does AVL offer that a basic unordered array or hash table does not directly provide?