Worst Case for AVL Tree Balancing after Deletion

After deleting a node in an AVL tree, self-balancing (zig-zag rotation or the left-right balancing) maintains O(logn) time that is not guaranteed in other unbalanced trees (like BST).

The Balancing operation is said to be O(logn).

What is the worst case for balancing? (I guess it will require balancing at every node all the way up till the root)

Any specific type of tree providing the worst case?

• We know that the worst case can't be worse than $O(\log n)$ because it does a constant amount of operations at each level towards the root, and there are at most $O(\log n)$ levels up towards the root. We don't usually care to find an explicit example since we've already proven it can't get worse. – orlp Jul 11 at 14:44

, where $$T_n$$ is a tree with $$T_{n-1}$$ as a left child and $$T_{n-2}$$ as a right child ($$T_1=T_2=$$single-node tree).
On this example, if you remove 19, then node 18 must be rebalanced. After that, node 13 must be rebalanced. Essentially, you will have a rebalance at every level above node 20. You can build an arbitrary large such tree. I didn't check, but it should be simple to prove that removing the rightmost node always suffices for the worst case.