number of rotations in AVL tree

[c_weed]

With AVL trees when does a removeElement operation require Θ(log n) trinode restructuring (rotations)? From wikipiedia removing a node "time required is O(log n) for lookup, plus a maximum of O(log n) rotations on the way back to the root, so the operation can be completed in O(log n) time."

I don't understand because what does n represent? The input size? That doesn't make any sense we pass removeElement a key and a tree.

I thought removing any element from an AVL tree requires a single rotation, why do they say Θ(log n) rotations?

[anduril462]

I don't see them use Θ in there, just big-O. But still, it's O(log n) rotations because when you delete a node and replace it with a node from lower in the tree, you may need to rotate each node on the way back up from the replacement node to keep the tree and it's subtrees in balance. An AVL tree, by definition, must have the tree and all it's subtrees in balance.

[CornedBee]

n is the number of nodes currently in the tree.