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.