Weekly Note 12, DM42, fall 2006

Discussion Section November 27

• In the lecture, we proved that red-black trees have amortized constant rebalancing. Try to do the same for (a,b)-trees, i.e., trees in the style of B-trees, where each node is required to have at least a and at most b children, and all leaves are at the same depth. In the leaves, the "children" are pointers to the actual values stored. The root is allowed to have as little as 2 children.
  • Design the rebalancing operations in the style of the lecture (where we ignored the keys and simply focused on structure). Thus, you simply draw tree structures with boxes which can be more or less full (between a and b) and for insertion an extra element to be included and for deletion a marked element to be deleted. Clearly insertion and deletion can create imbalance problems in the form of nodes with b+1 or a-1elements. The operations should be designed to fix such a problem when possible and otherwise move it closer to the root (where it has to be possible to fix it). Notice that for things to work out, it is necessary that b≥2a-1.
  • Show that if b=2a-1, then rebalancing is Ω(log n).
  • Show that if b≥2a, then rebalancing is amortized O(1). Use the potential function from red-black trees as inspiration. One of the two ingredients in that potential function corresponds to a node with a children and the other corresponds to a node with b children.

Lecture November 29

• Self-Adjusting Lists and Splay Trees [K90]

Announcements

• The discussion section on November 22 was based on:

  Multi-Dimensional Priority Queues

  Yuzheng Ding, Mark Allen Weiss.
  The K-D Heap: An Efficient Multi-Dimensional Priority Queue.
  Third International Workshop on Algorithms and Data Structures
  Lecture Notes in Computer Science 709.
  Springer-Verlag, 1993, 302-313.
  ISBN 3-540-57155-8.