Add a local height invariant to search order
An AVL tree preserves binary-search ordering while keeping the heights of each node’s left and right subtrees within one. The rule applies at every node, not just the root. An ordinary search tree can become a chain after sorted insertions and approach linear lookup time. Repairing imbalance keeps AVL height logarithmic in element count. Here an empty subtree has height zero and a leaf has height one. Other consistent conventions are possible, but height differences and stored metadata must use the same convention. A correct-looking root does not establish that a deeper subtree still satisfies the balance invariant.
Insert30,20,10 and rotate right
Insert30,20,10 into an empty ordinary search tree. Twenty becomes the left child of thirty and ten the left child of twenty. At node thirty, left height is two and right height is zero, violating AVL balance. A right rotation at thirty makes twenty the new root, with ten on the left and thirty on the right. Raising the middle key preserves the binary-search ordering. A rotation is not permission to discard key order; parent references and any transferred middle subtree must be reconnected correctly. The small trace isolates the structural transformation, while a general implementation must handle those surrounding links and metadata as well.
Repair an inside bend with two rotations
Insertion30,10,20 creates a left-right bend: twenty lies to the right of ten beneath thirty’s left side. A single right rotation at thirty does not provide the intended repair. Rotate left at ten and then right at thirty to obtain twenty with children ten and thirty. The right-left case is symmetric. Choose repair from the imbalanced node and relevant subtree heights, rather than memorizing names without tracking key ranges. A direction test tailored only to the inserted key can fail when reused for deletion. Explaining which key intervals each subtree contains makes both single and double rotations easier to verify.
Update metadata after reconnecting children
An implementation storing height recomputes it as one plus the maximum child height. After a rotation, update the node moved downward before the node moved upward; otherwise later calculations can use stale metadata. A tree can still return correct keys temporarily while carrying incorrect heights that break a later insertion or deletion. Define duplicate-key behavior as well: reject duplicates, replace values, or follow a documented multiset representation. Arbitrarily scattering equal keys across children makes lookup and removal assumptions unclear. Verify structure, stored heights, and duplicate policy separately rather than considering successful searches alone sufficient evidence of a correct balanced-tree implementation.
Deletion can propagate repairs toward the root
Deletion combines ordinary search-tree removal, possibly using a successor, with updates reflecting reduced subtree height. Repairing one local imbalance can still change height above it, so always stopping after the first repair is not generally sufficient. Logarithmic lookup, insertion, and deletion bounds assume maintained balance and an appropriate cost model, such as constant-time key comparisons. Long-string comparisons, allocation, and cache behavior add concrete implementation costs. A lower tree height does not prove the fastest wall-clock time for every input. Separate the structural guarantee from those costs when comparing AVL trees with red-black trees, arrays, or other ordered containers.
Check invariants recursively
Tests should verify that inorder traversal equals the expected sorted sequence, every node’s height difference is at most one, and stored heights match independently recomputed values. Include sorted and reverse insertions, alternating keys, missing-key removal, and root deletion. The30,20,10 and30,10,20 traces illustrate different repairs rather than report timing. A general implementation should also be compared with a reference set or map under mixed insertion and deletion. If reporting rotation counts or execution time, preserve the executed workload and environment. Structural reasoning and measured performance provide different evidence, and neither should be claimed when only the other has actually been checked.