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.)Mehlhorn's monograph is available electronically in an updated form that unfortunately leaves out III.9.
Local updates in weight-balanced search trees
ds.data structures