AVL trees introduction

Why it matters

Lesson 4 showed that a balanced tree keeps its height near log n, but it built the tree all at once from a sorted array. Real programs add and remove values over time, so they need a tree that stays balanced after every change. The AVL tree is the first such tree, and it is the simplest one to understand. You will rarely write one in a job, but interviewers ask how its rotations work, and the same ideas sit inside the red-black trees that power std::map and std::set.

This lesson explains the balance factor, the rotations that repair an unbalanced node, and the four cases that tell you which rotation to use. Then you will run an AVL insert in C++ and read its output, so you can check the reasoning yourself.

Start with a seesaw

Think of a playground seesaw with children sitting on each side. If one side gets much heavier, the seesaw tilts and the children slide. A good fix is to move the pivot, so the load is spread out again, without changing the order in which the children sit from left to right.

An AVL node works the same way. Each node has a left side and a right side, and the height of each side can be measured. When one side becomes two levels taller than the other, the node tilts. We repair the tilt by moving the pivot. The repair must keep the BST rule, so the values stay in sorted order.

The name AVL comes from the two inventors, Adelson-Velsky and Landis, who published the idea in 1962.

The balance factor

The balance factor of a node is the height of its left subtree minus the height of its right subtree. In an AVL tree, every node's balance factor must be -1, 0 or +1. A value of 0 means the two sides are equal. A value of +1 means the left side is one level taller. A value of -1 means the right side is one level taller.

A height of an empty subtree is 0, and a single node has height 1. Here is a small example. The node 20 has a left child 10 and no right child. Its left subtree has height 1 and its right subtree has height 0, so its balance factor is 1 minus 0, which is +1. That is allowed.

Now add 30 as the right child of 20. Both sides of 20 have height 1, so its balance factor becomes 0. That is also allowed.

If the balance factor of a node becomes +2 or -2, the node is out of balance. The AVL insert then repairs it with a rotation. Balance factors of +2 or -2 can only appear after an insert or a delete, and they appear at the first node on the path back to the root that has gone wrong.

Rotations

A rotation rearranges a few links around two nodes. The result is a different shape with the same inorder sequence, so the BST rule still holds. Think of it as lifting one node up and moving another node down, while keeping the sorted order.

A right rotation is used when the left side is too tall. The left child x moves up, and the node y moves down to become x's right child. The subtree that sat between x and y moves over from x to y, because its values are between x's and y's values.

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

Check the picture. Before the rotation, A is less than x, x is less than B, B is less than y, and C is larger than y. After the rotation, x is the root, A is still its left child, and y is its right child with B on its left and C on its right. The order A, x, B, y, C has not changed. That is why the rotation keeps the BST rule.

A left rotation is the mirror image. It is used when the right side is too tall. The right child moves up, and the node moves down to the left.

The four cases

When a node becomes unbalanced, there are four possible shapes. The cases are named after the path to the new node. The first direction is the direction from the unbalanced node to its tall child. The second direction is the direction from that child to the new value.

The two single cases use one rotation. The two double cases need two, because one rotation alone would leave the middle node in the wrong place. The double case is easy to remember with one picture: the zig-zag shape needs the child to be straightened first.

The four shapes that unbalance an AVL node, and the balanced tree that all four reach after the fix

The diagram shows the four shapes on top, and the single balanced tree they all become underneath. Notice that every fix ends with the middle value at the top. That is the rule for three nodes: after a fix, the middle of the three values is the root.

Here is a quick test of the four cases. Each set of three values is inserted in the given order into an empty AVL tree. The program prints the preorder walk, which shows the shape, and the height. The same program is listed in full in the next section, so you can read its functions first.

The output is:

left-left  (30 20 10): preorder 20 10 30 | height 2
right-right(10 20 30): preorder 20 10 30 | height 2
left-right (30 10 20): preorder 20 10 30 | height 2
right-left (10 30 20): preorder 20 10 30 | height 2

All four runs end with the same tree: 20 at the root, 10 on the left and 30 on the right. Three values always end as the middle one at the top. Each run used a different rotation to get there. The first run needed one right rotation, the second one left rotation, and the last two each needed a double rotation.

The code

The AVL insert has four parts: a height field, two rotations, a balance helper, and the insert that repairs the tree on the way back up. Read the code in that order.

Each node stores its height in the field h. A helper H returns the height of a node, or 0 for nullptr. update sets a node's height from its children's heights. balance returns the balance factor, which is the left height minus the right height.

rotateRight lifts x above y. It moves x's right subtree into y's left link, which is the subtree B in the picture. Then it makes y the right child of x. The order is important: the code copies x's right subtree into y's left link before it sets x->right to y. If it did the two steps the other way round, that subtree would be lost. After the links are changed, the code updates the heights. It updates y first, because y is now lower, and then x, because x is now the top. A height is computed from the children, so a node must be updated after its children are correct. Getting this order wrong gives wrong heights, and wrong heights give wrong balance factors.

rotateLeft is the mirror image, with the same update order.

The insert function is recursive. It inserts into the correct subtree, exactly as a plain BST would. Then, on the way back up, each node updates its height and checks its balance factor. The check uses the value that was inserted, v, to decide which case applies:

• If the balance is greater than 1 and v is less than the left child's value, the insert went into the left child's left subtree. That is the left-left case, so one right rotation fixes it.
• If the balance is less than -1 and v is greater than the right child's value, the insert went into the right child's right subtree. That is the right-right case, so one left rotation fixes it.
• If the balance is greater than 1 and v is greater than the left child's value, the insert went into the left child's right subtree. That is the left-right case. First rotate the left child left, then rotate the node right.
• If the balance is less than -1 and v is less than the right child's value, the insert went into the right child's left subtree. That is the right-left case. First rotate the right child right, then rotate the node left.

The function returns the node that now sits at the top of this subtree. The parent stores that return value into its link. That is why the insert line reads n->left = insert(n->left, v);. A rotation can change which node is the top of the subtree, so the parent must always store what comes back.

Now the program that inserts the values 1 through 7 in order. A plain BST would make a chain of height 7. The AVL tree stays a perfect tree of height 3.

The output is:

4 2 1 3 6 5 7 
height: 3

Follow the first problem spot. Insert 1 and 2, and the root 1 has a right child 2, with balance factor -1, which is fine. Insert 3, and the node 1 has balance factor -2, because its right side has height 2 and its left side is empty. The new value 3 is greater than the right child 2, so this is right-right. One left rotation at 1 lifts 2 to the root, with 1 as its left child and 3 as its right child. The next inserts follow the same pattern. Each time the right side gets too heavy, a left rotation fixes it, and the tree stays perfect.

Step through the way back up below. Each call to insert finishes its child first and then updates its own height and checks its balance. The moment a check fails is the moment a rotation is applied, and the parent stores the new top of the subtree.

Watching the balance factors

The last program lets you see the balance factor of every node. It reads a list of values from the Input box, inserts them into an AVL tree, and prints each node in preorder with its balance factor. In a correct AVL tree, every number printed must be -1, 0 or 1. Type this into the Input box:

9
10 20 30 40 50 25 5 4 3

The output is:

node 30 balance 1
node 5 balance 0
node 4 balance 1
node 3 balance 0
node 20 balance 0
node 10 balance 0
node 25 balance 0
node 40 balance -1
node 50 balance 0

Every balance factor is -1, 0 or 1, so the tree is a valid AVL tree. The root 30 has a left subtree of height 3 and a right subtree of height 2, so its balance is 1. The node 40 has a right child 50 and no left child, so its balance is -1. The leaves have balance 0. If you see a number outside the range -1 to 1, the insert did not repair the tree on that path.

Compare this output with the inserted order. The values 10, 20, 30, 40 and 50 arrive in sorted order, which would make a chain in a plain BST. The AVL insert rotated the tree several times, so the final shape is short and the balance factors stay small.

Tracing an insert by hand

Before you read the code again, follow four inserts on paper: 1, 2, 3 and 4. Keep a note of the balance factor of every node after each step.

Insert 1. The tree is one node with height 1, and its balance factor is 0.

Insert 2. It goes to the right of 1. Node 1 now has an empty left side of height 0 and a right side of height 1, so its balance factor is 0 minus 1, which is -1. That is allowed, and no rotation happens.

Insert 3. It goes to the right of 2. Node 2 now has balance -1, which is allowed. Node 1 has balance 0 minus 2, which is -2, so it is out of balance. The new value 3 is greater than 1's right child 2, so the insert went into the right child's right subtree. That is the right-right case, and one left rotation at 1 fixes it. The rotation lifts 2 to the root, with 1 on its left and 3 on its right. Both children are leaves, so the root's balance is 0.

Insert 4. It goes to the right of 3. Node 3 now has balance -1, which is allowed. The root 2 has a left side of height 1 and a right side of height 2, so its balance is -1, which is also allowed. No node is out of range, so no rotation happens. The tree has height 3.

The counter program in this lesson prints exactly these results: one rotation for insert 3, none for insert 4, and height 3 after insert 4. If your hand trace and the program disagree, check the balance factor of each node on the path, because a wrong height is the usual cause.

Counting the rotations

Rotations are the work an AVL tree does to stay balanced, so it helps to count them. This program adds a global counter. Each rotation adds one to it, and the program prints how many rotations each insert needed, along with the height after the insert. Only the two rotation functions change, and the insert is the same as before.

The output is:

insert 1: 0 rotation(s), height 1
insert 2: 0 rotation(s), height 2
insert 3: 1 rotation(s), height 2
insert 4: 0 rotation(s), height 3
insert 5: 1 rotation(s), height 3
insert 6: 1 rotation(s), height 3
insert 7: 1 rotation(s), height 3
insert 8: 0 rotation(s), height 4
insert 9: 1 rotation(s), height 4
insert 10: 1 rotation(s), height 4
total rotations: 6

Two patterns stand out. Some inserts need no rotation at all, and the ones that do need exactly one, because this sequence never needs a double rotation. The height rises only at inserts 1, 2, 4 and 8, which are the powers of two. A tree of height h holds up to 2 to the power h minus 1 nodes, so the height has to go up each time the count passes one of those limits. The AVL tree reaches each new level as late as the balance rules allow, and it does so with only a few rotations.

Deletion in an AVL tree

Delete works in two stages. First it removes the node, using the three cases from lesson 2, and for a node with two children it copies the successor. Then it walks back up the path it followed. At each node it updates the height and checks the balance factor, and it rotates when the balance falls outside the range -1 to 1.

Delete is harder than insert in one way. An insert adds one leaf, so at most one fix is needed. A delete removes a node, so the heights can drop on several nodes along the path, and each of them may need a rotation. A delete can therefore perform up to O(log n) rotations, one at each level on the way up.

The case choice also changes. Insert knows the value that was added, so it can compare that value with the child's value. Delete has no new value to compare with. Instead, it looks at the balance of the taller child. Take a node that is too heavy on the right, with balance -2. If its right child leans right or is level, one left rotation at the node fixes it. If the right child leans left, the double rotation is needed, because the child must be straightened first. The mirror case works the same way. Practice exercise 8 of this lesson writes that rule as code.

The goal stays the same for both operations: every node must end with a balance factor of -1, 0 or 1. Delete is the operation that makes this check on the way up matter most, because it is the one that can remove a node from the shorter side.

Complexity

An AVL tree with n nodes has height at most about 1.44 log2 n. The constant is a little larger than the 1 you get from a perfect tree, but it is still logarithmic, so search, insert and delete all cost O(log n) in the worst case. That is the guarantee a plain BST does not give.

An insert causes at most one single or double rotation. A double rotation is two single rotations, so the cost of the rotations is O(1). The insert walks down one path, which costs O(log n), and it updates the heights on the way back up, which also costs O(log n).

The price is extra work. Each node stores a height, which costs a few bytes per node. The code is more involved, and every insert does more bookkeeping than a plain BST insert. For most workloads that is a good trade, because the worst case becomes predictable.

What happens inside

A rotation changes only a handful of links. The nodes involved are x, y and the subtree B that moves from one to the other. Everything else stays where it was, so the rotation is cheap, and it does not copy any data.

The heights are the key memory. Without them, the insert would have to compute the height of each subtree again on every visit, which would cost O(n) per insert. Storing a height in each node costs one int per node and makes the balance check O(1).

The recursion uses the call stack. The insert goes down one path and comes back up, so the stack holds at most h frames. For an AVL tree, h is at most about 1.44 log2 n, so the stack is small even for large trees.

On the way back up, each call does the same three things: it updates the height of its node, computes the balance factor, and rotates if the balance is out of range. The rotations happen at the nodes on the path, and no other node is touched. That locality is why the insert stays cheap.

Common mistakes and what you see

Mistake 1: forgetting to update the height. If update(n) is missing, the heights never change after the first insert. Every balance factor is then 0, so no rotation happens, and the tree becomes a chain. The output of such a program on the values 1 to 7 is:

1 2 3 4 5 6 7 
height: 1

The preorder line shows the chain, and the height is reported as 1 for the root, which is wrong. Both symptoms come from the same missing line. The fix is to call update(n) before reading the balance.

Mistake 2: updating heights in the wrong order after a rotation. In rotateRight, the node y moves down, so its height must be recomputed first, while its children are correct. Then x, which is now the top, is updated from its new child y. Reversing the order gives x a height computed from an out-of-date y, and the balance factors go wrong higher up.

Mistake 3: not returning the new top of the subtree. A rotation can change the root of the subtree it works on. If the parent keeps the old link and ignores the return value, the parent still points at the node that is now below. The tree then has a node in two places or loses a subtree. Always store the return value into the parent's link, as the insert does.

Mistake 4: using the wrong double-rotation order. In the left-right case, the left child must be rotated left before the node is rotated right. If you rotate the node right first, the values are no longer in the right shape, and the tree stays unbalanced. Check the four cases against the table one at a time.

Mistake 5: checking balance only at the root. Every node on the path back to the root can be unbalanced after an insert. The recursive insert checks each node on the way up, which is why the check is inside the recursive function, not outside it.

Mistake 6: comparing the new value with the wrong node. The double-rotation tests compare v with the child's value. Using the node's own value instead gives the wrong case, because v tells you which side of the child the new value went to. Read each if with the question "which side did the value go to?" in mind.

Debugging walkthrough: a tree whose balance factor is 2

Suppose the report shows a balance factor of 2 or -2 at some node after insert. That means the rotation check failed for that node. Start by printing the balance factor of each node after each insert. The first insert that leaves a node outside the range -1 to 1 is the one to study.

Next, look at which case the value falls into. Write down the path from the unbalanced node to the new value, with the direction of each step. A path of left then left is left-left, and so on. Compare your path with the four cases in the table.

Last, check the heights. Print the height of the unbalanced node and its children. If the heights are wrong, the update is missing or in the wrong order. If the heights are right but the rotation did not happen, the case test is wrong.

This method works for any tree bug. Compare the printed numbers with what you expect on paper, and find the first place where they differ.

Variations and edge cases

Delete. Deleting can leave a node out of balance too, and the fix uses the same rotations. The difference is that the child used for the case test may have balance 0, and then a single rotation fixes the tree instead of a double one. This module does not implement delete for AVL, but the idea is the same.

Duplicates. The insert in this lesson ignores duplicates, so a duplicate insert returns the same node without changes. The heights and balances stay as they were.

The smallest trees. A single node has balance 0. Two nodes give a balance of 1 or -1, and both are allowed. The first unbalanced shape appears with three nodes.

Sorted and reverse sorted input. Both give a perfect tree of height about log n, as the program on 1 to 7 showed. That is the reason AVL trees are used when input is sorted.

Storing the balance factor instead of the height. Some implementations store only the balance factor, which takes fewer bits. The rotations work the same way, but the update code must adjust the balance factors by the rules for each rotation.

Interview questions and real-world use

A common interview question is "insert into an AVL tree". Write the insert, then name the four cases, and say which rotation fixes each one. Explain why the height is stored, and why the check happens on the way back up. If asked about cost, say O(log n) worst case.

A second question asks why you would use an AVL tree instead of a plain BST. The answer is the worst-case guarantee. A plain BST can degrade on sorted input, but an AVL tree stays near log n on any input.

Real libraries mostly use red-black trees rather than AVL trees. Red-black trees do fewer rotations on each insert and delete, which suits code that changes the tree often. AVL trees are a good choice when lookups are much more common than changes, because their shape is more strictly balanced. Knowing both is useful when you read the source of a container, or when you design an index for a read-heavy system.

When you compare the two trees in an interview, name the trade-off in one sentence. An AVL tree is stricter, so its lookups touch the fewest levels. A red-black tree does fewer rotations on each change, so frequent updates cost less. Then say which workload you would choose and why. A read-heavy index that is built once and searched many times suits AVL. A container that is updated all the time, such as a scheduler's list of timers, suits red-black, because the cost of each change matters more than a slightly taller tree.

Practice

Try these before you open the solutions. Compile with g++ -std=c++17 -Wall -g -fsanitize=address,undefined. The insert and rotation code from this lesson is the starting point for each exercise.

1. Easy. Insert 30, 20 and 10 into an AVL tree in that order. Which case is this, and what is the final shape?

2. Easy. Insert 10, 30 and 20 in that order. Which case is it, and what fixes it?

3. Easy. Explain in one sentence why a rotation keeps the BST rule.

4. Medium. Write bool isAVL(Node* root) that returns true when every node has a balance factor of -1, 0 or 1. Hint: compute heights and check each node in one pass, as in lesson 4.

int checkAVL(Node* n) {
    if (!n) return 0;
    int lh = checkAVL(n->left);
    if (lh == -1) return -1;
    int rh = checkAVL(n->right);
    if (rh == -1) return -1;
    if (abs(lh - rh) > 1) return -1;
    return 1 + max(lh, rh);
}
 
bool isAVL(Node* root) {
    return checkAVL(root) != -1;
}

5. Medium. Insert the values 1 to 10 in order into an AVL tree. Write down the final height, and explain why it is the same as the lesson's result for 1 to 7, plus one level.

6. Medium. Add a counter to the rotation functions, so that main can print how many rotations an insert sequence needed. Insert 1 to 7 and print the count.

int rotations = 0;
 
Node* rotateRight(Node* y) {
    rotations++;
    Node* x = y->left;
    y->left = x->right;
    x->right = y;
    update(y);
    update(x);
    return x;
}
 
Node* rotateLeft(Node* x) {
    rotations++;
    Node* y = x->right;
    x->right = y->left;
    y->left = x;
    update(x);
    update(y);
    return y;
}

7. Medium. Explain why the double rotation in the left-right case cannot be replaced by one right rotation.

8. Hard. Write the rotation choice using the child's balance factor, without comparing the inserted value. Given an unbalanced node n with balance greater than 1, pick the correct fix. Explain why the balance of the left child decides the case.

Node* rebalance(Node* n) {
    int b = balance(n);
    if (b > 1) {
        if (balance(n->left) < 0) n->left = rotateLeft(n->left);   // left-right
        return rotateRight(n);                                     // finishes left-left, or left-right
    }
    if (b < -1) {
        if (balance(n->right) > 0) n->right = rotateRight(n->right); // right-left
        return rotateLeft(n);                                        // finishes right-right, or right-left
    }
    return n;
}

9. Hard. Prove that an AVL tree of height h has at least F(h + 2) - 1 nodes, where F is the Fibonacci sequence with F(1) = F(2) = 1. Explain why this gives the bound of about 1.44 log2 n on the height.

10. Hard. Explain why the insert in this lesson does at most two rotations for one insert, even though the path back up can be long.

What you now know

• The balance factor of a node is its left height minus its right height, and an AVL tree keeps it at -1, 0 or 1.
• A rotation moves a few links so that a tall side becomes shorter, and it keeps the inorder order.
• The four cases are left-left, right-right, left-right and right-left, and the double cases need two rotations.
• The insert updates heights and checks balance on the way back up, and it stores the new subtree top into the parent's link.
• Update heights in the right order after a rotation, lower node first.
• An AVL tree keeps its height near log n, so its operations cost O(log n) in the worst case.

The next part of the module is the assignment. It puts everything from this module into one project.