How many rotations can a single AVL insertion trigger, and how does deletion compare?

## The claim, stated precisely After a single AVL **insertion**, at most **one** rebalancing operation is performed — either one single rotation or one double rotation, which is conventionally counted as one repair (two link-level turns). After a single AVL **deletion**, up to **O(log n)** rebalancing operations may be performed, one at each level along the path back to the root. Both operations still cost O(log n) time in total. ## Why insertion stops after one repair Work through the heights. Before the insertion, let the lowest node that will become unbalanced be `z`, and say the subtree rooted at `z` had height `h`. The insertion adds one node in `z`'s taller side, pushing that subtree to height `h+1` and `z` to a balance factor of magnitude 2. Now apply the rotation for the case at hand. In both the zig-zig and zig-zag repairs, the new subtree root ends with children whose heights differ by at most one, and the resulting subtree height is `h` again — exactly what it was before the key arrived. That is the whole argument. `z`'s parent sees a subtree of unchanged height, so its own stored height and balance factor are unchanged, and so on all the way to the root. The retrace can break out of its loop the moment it performs a rotation. It is also why the frequently-heard answer "an insert may cascade rotations up the tree" is wrong: the cascade is precisely what the height-restoration property rules out. One caveat worth stating: the retrace still walks upward until it either rotates or reaches a node whose height did not change. Updating heights along that path is O(log n) work. "At most one rotation" is a claim about the *restructuring*, not about the whole operation. ## Why deletion can cascade Deletion is the opposite. Removing a node can shorten a subtree from height `h` to `h-1`. If that unbalances an ancestor `z`, the repair rotates — and here the arithmetic differs: depending on the balance factor of the taller child, the repaired subtree can come out at height `h-1` rather than `h`. In other words the repair itself shortens the subtree. A shorter subtree is a height change visible to `z`'s parent, which may now be out of balance, which is repaired, which may shorten again. In the worst case this repeats at every level, giving up to about `log n` rotations for one deletion. A nice way to see that this worst case is real rather than theoretical: build the sparsest legal AVL tree of a given height — the Fibonacci-shaped tree with the minimum node count — and delete the single leaf on the short side. Every ancestor in turn becomes deficient, and the repair marches all the way to the root. This is also where the `>= 0` form of the case test earns its keep. After an insertion, the taller child of the violating node is never level, so the zig-zig/zig-zag distinction is unambiguous. After a deletion it *can* be level, and that case must be routed to the single rotation — the one whose repaired subtree keeps its height, which incidentally stops the cascade early. ## What this does and does not cost | Operation | Descent | Height updates on retrace | Rebalancings | Total | |---|---|---|---|---| | Search | O(log n) | — | 0 | O(log n) | | Insert | O(log n) | O(log n) | at most 1 | O(log n) | | Delete | O(log n) | O(log n) | up to O(log n) | O(log n) | So the asymmetry is a **constant-factor** story on the write path, not a complexity story. A candidate who says "deletion is asymptotically worse because of the cascade" has confused a bigger constant with a bigger order of growth. Each rotation relinks a fixed number of references, so `log n` of them still amount to O(log n) work — the same order as the descent that had to happen anyway. ## Why interviewers ask this It separates people who memorised "AVL rebalances in O(log n)" from people who can reason about *why* a local repair does or does not propagate. The reasoning tool — track what happens to the subtree's height, and ask whether the parent can tell anything changed — is the same tool used for every self-balancing structure, and for a good many other recursive data-structure arguments besides. ## The practical consequence If you are sizing the write side of a workload, insertions are cheaper than the folklore suggests and deletions are the case to measure. Where deletions are frequent, some implementations use lazy deletion (mark a node as removed, rebuild periodically) precisely to keep the cascading repair off the hot path — trading space and a periodic rebuild for a flatter latency profile on writes.