<p>Section 3 of Brodal et al.'s <a href="http://arxiv.org/abs/1009.3134" rel="nofollow">"D$^2$-Tree: A New Overlay with Deterministic Bounds"</a> shows how to update a weight-balanced tree in $O(1)$ amortized time, but the worst-case time is still $\Omega(\lg n)$.</p>

CC BY-SA 3.0
2013-03-31T22:56:44.470Z
2013-11-10T07:01:54.687Z
2013-11-10T07:01:54.687Z
jbapple
<p>In Kurt Mehlhorn's monograph "Data Structures and Algorithms 1: Sorting and Searching", he poses the following question  (III.9.22):</p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>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.</p>

<p>Any ideas on how to maintain $p(v)$?</p>

<p>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.)</p>

<p><a href="http://www.mpi-inf.mpg.de/~mehlhorn/DatAlgbooks.html" rel="nofollow">Mehlhorn's monograph is available electronically in an updated form that unfortunately leaves out III.9.</a></p>

<ds.data-structures>
Local updates in weight-balanced search trees
jbapple
# Local updates in weight-balanced search trees

(Asked by: username_0 on 2012-09-22)

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.](http://www.mpi-inf.mpg.de/~mehlhorn/DatAlgbooks.html)

**Tags:** ds.data-structures


---

## 1 answers

### Answer by username_0 on 2013-03-31. Score: 2

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


---

