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?