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.


1 Answer 1


Section 3 of Brodal et al.'s "D$^2$-Tree: A New Overlay with Deterministic Bounds" shows how to update a weight-balanced tree in $O(1)$ amortized time, but the worst-case time is still $\Omega(\lg n)$.


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.