A binary search tree can answer an ordered-set query by discarding one subtree at each comparison. That sounds efficient, but the number of comparisons depends on the tree's height. Insert the keys into an ordinary empty search tree in that order: every key becomes the right child of the previous one. Searching for 5 then visits all five nodes. The ordering rule alone does not keep the tree shallow.
An AVL tree adds a local height condition. Its value is that a condition we can check and repair near an update implies a useful bound for the whole tree. We will prove that implication, then distinguish two jobs of a rotation: preserving which keys the tree stores, and restoring its height condition. Deletion deserves particular care because a successful repair can shorten a subtree and expose another imbalance above it.
State the ordered-set contract first
Assume distinct keys with a fixed total order. Each node stores one key, two child links and its subtree height. Inserting an existing key leaves the set unchanged; deleting an absent key also leaves it unchanged. A map additionally stores a value associated with each key, but we first study the set interface.
Definition 15.1.1
(Search order, height and AVL balance)
At a node with key , every key in its left subtree is smaller than , and every key in its right subtree is larger. The same condition holds recursively in both subtrees. This is the binary-search-tree invariant.
Use edge height: an empty subtree has height , and a leaf has height 0. For a nonempty node ,
Define its balance factor by
An AVL tree is a binary search tree in which every node satisfies .
Nor does the definition require every level to be full. Balance compares the heights of two subtrees at each node, not their numbers of keys.
Common mistake
(Checking balance only at the root)
The tree 10(5(4(3,-),-),15(12,-)) has a root with balance , since the left subtree has height 2 and the right subtree height 1. It is not an AVL tree: node 5 has left height 1 and right height , so its balance is 2.
If the root has height , search visits at most nonempty nodes, then possibly an empty child link. It is therefore enough to bound in terms of the number of stored keys.
Why a local balance condition gives logarithmic height
Let be the minimum number of nodes in an AVL tree of height exactly . The two initial values are and . A height- tree has a child of height . Balance requires its other child to have height at least . Using minimum-size AVL subtrees of those two heights attains the minimum, so for ,
| Height | |||||||
|---|---|---|---|---|---|---|---|
| Minimum nodes |
The recurrence resembles the Fibonacci recurrence. We do not need its closed form to prove a logarithmic bound.
Theorem 15.1.2
(Logarithmic height of AVL trees)
An AVL tree with keys has height . In particular a search visits nodes.
Proof
(A short height bound without solving the recurrence)
Write . For , the recurrence becomes
because increases with height. The initial values satisfy and . Induction, reducing the height by two at each step, gives
An AVL tree with nodes and height has , hence
Thus search takes time. The bound is deliberately loose; its purpose is to establish logarithmic growth directly from the balance invariant.
Proof X-ray
Why shift by one, and why step by two
Substituting removes the added constant, so is purely additive. The step of two is forced by the hypothesis. Balance guarantees only that the shallower child has height at least , not ; using twice would require both children to have height , which holds only for perfectly balanced shapes.
The balance hypothesis cannot be dropped. The search tree built by inserting in increasing order is a chain with and height , whereas an AVL tree must satisfy .
This proof explains what an update must preserve. Merely producing a tree that looks compact in a small example is insufficient: every node must still satisfy the invariant on which the bound depends.
A rotation preserves the entire ordered set
Suppose a node has left child . Write for whole subtrees, possibly empty. A right rotation changes these links:
z y
/ \ / \
y C becomes A z
/ \ / \
A B B C
The middle subtree moves from the right child of to the left child of . It must not be discarded or left attached to both positions. The parent of the displayed subtree must now point to , its new root.
Proposition 15.1.3
(Rotation preserves search order)
Let be the root of a binary search tree with left child , and let , , be the subtrees as in the diagram. The right rotation produces a binary search tree on the same keys, with the same inorder sequence, and it can replace the original subtree inside any larger search tree.
Proof
(Read the same inorder sequence before and after rotation)
Before rotation, search order gives
with the relevant inequalities omitted when a subtree is empty. These inequalities also justify every left and right placement after rotation: belongs left of ; belongs right of and left of ; belongs right of .
Equivalently, the inorder sequence is on both sides. No key is added, lost or duplicated. The rotated subtree therefore represents the same ordered set. Its external lower and upper key bounds remain valid as well, so it can replace the old subtree inside a larger search tree.
This proves preservation of search order. Whether the rotation restores AVL balance depends on the subtree heights; ordering alone cannot prove that second claim.
A left rotation is the mirror image. Both operations change only a constant number of links. Refresh the lower node's stored height first, then the new root's height; the second calculation depends on the first.
Choose repairs using child balance
After one insertion or deletion and the repairs below a node, its balance can only be or 2. If it is 2, its left child is too tall. A single right rotation works when . When , first left-rotate and then right-rotate the original root. That double rotation brings the middle key to the top. The right-heavy cases are symmetric.
| Balance at | Balance at its heavy child | Repair |
|---|---|---|
| Right-rotate | ||
| Left-rotate its left child, then right-rotate | ||
| Left-rotate | ||
| Right-rotate its right child, then left-rotate |
Worked example 15.1.4
(The two insertion shapes are different)
Insert 30, 20, 10 in that order. At 30, the left height becomes 1 and the empty right height is , so its balance is 2. Its left child 20 has balance 1. A single right rotation produces root 20 with children 10 and 30, all balanced.
Instead insert 30, 10, 20. Node 30 again has balance 2, but its child 10 has balance . Right-rotating 30 immediately would leave the new root 10 with a right subtree of height 1 and an empty left subtree: it would still be unbalanced. First left-rotate 10, placing 20 above it, then right-rotate 30. The final tree is again root 20 with children 10 and 30.
The final ordered set is the same in both examples. The intermediate child balance, rather than the set of keys, determines the repair.
Proposition 15.1.5
(Insertion repair restores the old subtree height)
Let be the lowest ancestor of a newly inserted node whose balance becomes , if there is one. The single or double rotation chosen from the table above makes every node of the repaired subtree balanced, and the repaired subtree has the height that the subtree rooted at had before the insertion. Consequently no ancestor of changes height or balance because of the insertion.
Proof
(Heights after the single and the double rotation)
For insertion, let be the lowest ancestor that becomes unbalanced. Before insertion its heavy child had height and its other child height . Insertion raises the heavy child's height to . In the left-left case, use the rotation diagram above: after insertion, has height , while and have height . Right rotation makes height and the new root height .
In the left-right case, let be the root of 's right subtree after insertion. Node has height ; its two children have heights at most . The outer subtrees, to the left of and the right of , both have height . The double rotation makes and children of . Each now has height , so the new root has height . The right-heavy cases are symmetric.
Both repairs therefore restore exactly the subtree's height before insertion. Ancestors above see no net height increase. One single or double repair suffices, although we still traversed a path of logarithmic length to find the insertion point and update heights.
Deletion can stop a height change or propagate it
Ordinary search-tree deletion first removes a node with at most one child. If the requested node has two children, copy its inorder successor's key into it, then delete that successor from the right subtree. The successor is the least key in that subtree, so it has no left child. The ordering inequalities remain valid, and the set loses exactly the requested key. In a map, copy the associated value together with the key.
Repair balance while returning along the path from the node physically removed. A removed key's old position does not tell us which rotation to use; inspect the current heavy child's balance instead.
Worked example 15.1.6
(A heavy child of balance zero belongs to the single-rotation case)
Start with root 4, left subtree rooted at 2 with leaf children 1 and 3, and right subtree rooted at 6 with right leaf 7. The whole tree has height 2. Delete 7, leaving 6 as a leaf; root 4 has balance 1 and remains balanced.
Now delete 6. At root 4 the child heights are 1 and , so its balance becomes 2. Its left child 2 has balance zero. Right-rotate 4:
4 2
/ / \
2 becomes 1 4
/ \ /
1 3 3
After rotation, node 4 has height 1 and balance 1; node 2 has height 2 and balance . All nodes are balanced. The repaired subtree still has height 2, its height before deleting 6. An ancestor above this subtree would see no height decrease, so this particular repair would stop further height propagation.
The zero case occurs in deletion and is included in the and rows of the repair table. A rule remembered only from the inserted key's direction misses it.
Other deletion repairs reduce the subtree height, so an ancestor can become unbalanced too.
Worked example 15.1.7
(Two ancestors need rotations in one deletion)
Use the notation k(left,right), with - for an empty child; a bare key is a leaf. Start from
8(5(3(2(1,-),4),7(6,-)),11(10(9,-),12))
This is an AVL tree containing keys 1 through 12. Its left subtree has height 3, its right subtree height 2, and the root height 4. Delete leaf 12. At node 11, the left height is 1 and the right height is ; right-rotating 11 produces 10(9,11). That subtree's height has fallen from 2 to 1. Root 8 now has child heights 3 and 1, so it also needs repair. Its left child 5 has balance 1; right-rotate 8 to obtain
5(3(2(1,-),4),8(7(6,-),10(9,11)))
The final height is 3. Two distinct ancestors needed rotations during one deletion. Stopping after the first repaired node would leave root 8 unbalanced.
Return the repaired root, and maintain heights locally
The following Python code records the pointer and height rules explicitly. insert and erase return the possibly changed root; the caller must keep it, for example root = erase(root, key). Keys must have a consistent total order. No recursive traversal is used to recalculate a stored height: refresh reads only the two children's stored heights.
class Node:
def __init__(self, key):
self.key = key
self.left = self.right = None
self.height = 0
def height(v):
return -1 if v is None else v.height
def refresh(v):
v.height = 1 + max(height(v.left), height(v.right))
def balance(v):
return height(v.left) - height(v.right)
def rotate_right(z):
y = z.left
z.left = y.right
y.right = z
refresh(z)
refresh(y)
return y
def rotate_left(z):
y = z.right
z.right = y.left
y.left = z
refresh(z)
refresh(y)
return y
def rebalance(v):
refresh(v)
if balance(v) == 2:
if balance(v.left) < 0:
v.left = rotate_left(v.left)
return rotate_right(v)
if balance(v) == -2:
if balance(v.right) > 0:
v.right = rotate_right(v.right)
return rotate_left(v)
return v
def insert(v, key):
if v is None:
return Node(key)
if key < v.key:
v.left = insert(v.left, key)
elif key > v.key:
v.right = insert(v.right, key)
else:
return v
return rebalance(v)
def erase(v, key):
if v is None:
return None
if key < v.key:
v.left = erase(v.left, key)
elif key > v.key:
v.right = erase(v.right, key)
else:
if v.left is None:
return v.right
if v.right is None:
return v.left
successor = v.right
while successor.left is not None:
successor = successor.left
v.key = successor.key
v.right = erase(v.right, successor.key)
return rebalance(v)
The rotation routines require their displayed child to exist. The balance conditions in rebalance guarantee that requirement. Moreover, rebalance assumes that both child subtrees are already AVL trees with correct stored heights and that the current node came from one ordinary update. It repairs that situation; it is not a general procedure for balancing an arbitrarily malformed tree.
Common mistake
(Discarding the returned root)
Running erase(root, 10) on 20(10,30(-,40)) returns the new root 30 with tree 30(20,40), because node 20 becomes right-heavy by 2 after losing its left leaf. A caller that writes erase(root, 10) without assigning the result still holds node 20, which is now a left child of 30 with no right subtree: keys 30 and 40 are unreachable from it. Write root = erase(root, 10).
Each returning stack frame does constant work and at most two rotations. The original tree has logarithmic height, so insertion and deletion take worst-case time, including the successor search. The recursive stack uses space; nodes use total storage. Deletion may repair several ancestors, but there are only logarithmically many ancestors to visit.
Counterexample mode
A correct-looking root does not certify a correct tree
After the two-ancestor deletion example, suppose a program repairs node 11 and stops. The right subtree rooted at 10 is a valid AVL tree. The inorder traversal of the whole structure is still sorted and still contains exactly the intended keys. Nevertheless, root 8 has balance 2. Testing sorted order alone would miss the defect.
Three separate assertions matter: the key order is valid; each stored height equals one plus the maximum child height; and each balance factor has absolute value at most one. A stale height can conceal an imbalance even when all pointer links are correct. These assertions describe different mathematical obligations.
Exercises and worked solutions
Quick check
(1. Use the height convention consistently)
An AVL tree contains ten keys. Can its height be 4? Can it have height 3? Use the minimum-node recurrence rather than the loose logarithmic upper bound.
Solution · Solution 1
Height 4 is impossible because . Height 3 is possible. A complete height-2 tree has seven nodes; add three children in available positions on the next level while retaining local balance. More explicitly, 4(2(1,3),8(6(5,7),9(-,10))) has ten keys, height 3 and balance magnitude at most one at every node.
Quick check
(2. Locate the missing subtree in a rotation)
Before a right rotation, root 40 has left child 20. The right subtree of 20 is rooted at 30. Where must that subtree be attached after rotation, and which key inequalities justify the move?
Solution · Solution 2
It becomes the left subtree of 40, while 40 becomes the right child of 20. Every key in the moved subtree lies strictly between 20 and 40. Thus it belongs to the right of 20 and the left of 40 both before and after rotation. Leaving it at its old child link while also attaching 40 there would either lose it or corrupt the tree links.
Quick check
(3. Trace a right-left insertion)
Insert 10, 30, 20 into an empty AVL tree. Give the first unbalanced node, both relevant balance factors, the repair sequence and the final height.
Solution · Solution 3
Node 10 has balance and its right child 30 has balance 1. Right-rotate 30 first, then left-rotate 10. The final root is 20 with leaf children 10 and 30, so its height is 1. A single left rotation at the original root would not suffice.
Quick check
(4. Delete a node with two children)
In 20(10,30(25,40)), delete 20 using the inorder successor. What key replaces it, which physical node is removed, and what tree remains after any necessary balance check?
Solution · Solution 4
The successor is 25. Copy 25 into the root and remove the original leaf 25 from the right subtree. The result is 25(10,30(-,40)), of height 2. Root 25 has balance , node 30 has balance , and the leaves have balance 0, so no rotation is required. The set loses 20 and still contains exactly one copy of 25.
Quick check
(5. Explain why one deletion repair need not finish the job)
In the twelve-key deletion example, give the child heights at root 8 immediately after repairing node 11. Why must the returning recursive call continue to rebalance root 8?
Solution · Solution 5
The left height is still 3, while the repaired right subtree now has height 1. Root 8 therefore has balance 2. The first rotation preserved ordering and repaired its own subtree, but shortened that subtree; it did not repair the ancestor's newly exposed imbalance. The second right rotation restores AVL balance there and gives the final root 5.
Quick check
(6. Distinguish constant-time height updates from recursive measurement)
Why does the code keep a stored height at every node? If refresh instead recursively counted the entire current subtree on every return, would the logarithmic height bound alone prove logarithmic update time?
Solution · Solution 6
Stored child heights make each refresh constant-time, so a logarithmic number of returning frames gives logarithmic total work. A recursive height measurement at the root can already inspect all nodes. Thus logarithmic tree height would no longer imply logarithmic update time. The structural bound limits the number of frames; the implementation must also bound the work within each frame.