Given a WAVL tree with pointers to its' minimum and maximum, we will add two operations:

Insert-Max: given an element, which is bigger than all other elements in the tree, add it as the right child of the maximum element, and update the max pointer.

Delete-Min: find the successor of the minimum element, delete the minimum element and update the min pointer.

Rebalancing after inserting and deleting elements will be as in regular WAVL tree.

We are given a sorted array of $n$ elements and an empty WAVL tree.

We will do $n$ Insert-Max operations on all elements of the array, from smallest to biggest, and then we will do $n$ Delete-Min operations.

I would like to find the worst cast bound for one operation in the described sequence of operations, which will cover both Insert-Max and Delete-Min.

We know that the amortized cost of a rebalancing operation is WAVL tree is $O(1)$, but I'm not sure what can be said about the worst case.

Any help is appreciated.

  • $\begingroup$ The worst case is probably $O(\log n)$. This is usually the case for balanced binary trees. Presumably the textbook mentions this. $\endgroup$ – Yuval Filmus Feb 14 '18 at 15:45
  • $\begingroup$ @YuvalFilmus Is that because the rebalancing can go all the way up to the root, and the tree height is bounded by $O(\log n)?$ $\endgroup$ – Itay4 Feb 14 '18 at 15:47
  • $\begingroup$ Yes, everything is linear in the depth, and the depth is $O(\log n)$. In fact, $O(\log n)$ is an upper bound – it's probably better to state the worst case as $\Theta(\log n)$. $\endgroup$ – Yuval Filmus Feb 14 '18 at 16:22
  • $\begingroup$ @YuvalFilmus So you are saying that this is true for every balanced binary tree? WAVL has no advantage over AVL here? $\endgroup$ – Itay4 Feb 14 '18 at 16:33
  • $\begingroup$ The Wikipedia page compares these two data structures. $\endgroup$ – Yuval Filmus Feb 14 '18 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.