In Kurt Mehlhorn's monograph "Data Structures and Algorithms 1: Sorting and Searching", he poses the following question (III.9.22):
Design a balanced tree scheme where the worst case rebalancing cost after an insertion or deletion is $O(\log \log n)$. Hint: Use weight-balanced trees. If $n$ elements are stored then rebalance up to height $O(\log \log n)$ as described in the text. With every node $v$ of height $\log \log n$ associate a pointer which points to an ancestor $p(v)$ of $v$ in the tree. If a transaction goes through $v$ then we also rebalance $p(v)$, if necessary, and advance $p$ one step towards the root. Show that the root balance of nodes of height $\log \log n$ or more cannot deteriorate too much.
It is not obvious to me how a slowly-moving $p(v)$ can keep nodes of height $\Omega(\log \log n)$ but $o(\log n)$ balanced. My intuition is that these nodes must be cared to more frequently than I can manage with the "one ancestor pointer" system.
Any ideas on how to maintain $p(v)$?
There has been some work on reducing the cost of updates at a known location in weight-balanced trees, but I'm not aware of any weight-balanced tree with $o(\lg n)$ worst-case updates. (Treaps are weight balanced and have $O(1)$ expected-time updates.)
