3
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – orlp
    Commented Jul 11, 2020 at 14:44

1 Answer 1

Reset to default
4
$\begingroup$

To make a lot of rebalancing, you would like to make your AVL tree as imbalanced as possible. And the worst case is a Fibonnachi-like tree: enter image description here

, 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks @Dmitry, got it! $\endgroup$
    – alienated-vocalist-251
    Commented Jul 13, 2020 at 5:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.