Weekly Note 10, DM42, fall 2006

Discussion Section November 13

1. For van Emde Boa Trees we needed that T(n)=T(√n)+1 had solution T(n)∈O(loglog n) and were motivated by the fact that T(n)=2T(√n)+1 had solution T(n)∈Ω(log n). Prove these two facts.
2. Problem sheet 1 for weekly note 10.
3. Problem sheet 2 for weekly note 10.

Lecture November 15

• Balanced Trees and AVL-Trees [AFL05, AVL].
• Analysis of Red-Black Trees [DSST89, pages 110-111].
• Analysis of B-Trees ((a,b)-trees), if time permits.

Announcements

• Recall that red-black trees are assumed known. Check definitions in [CLRS01] if you have forgotten about the structure.

  For the proof of amortized constant rebalancing of red-black trees, the potential function is: number of configurations where a black node has two black children plus two times the number of configurations where a black node has two red children. The argument is organized as follows: notice first that when a rotation is performed, rebalancing ends after possibly one more rotation. Thus, only recolorings can continue with no constant time upper bound. However, all recolorings, except possibly the last, decrease the potential by at least one. Since updates increase the potential by at most a constant, the result follows.