![[topimage]](IMADA_en.png)
Exercises
-
Generalize B-trees that you may know from a database course.
The balance idea is that all leaves have the same distance from the root,
but the number of children of a node vary between a minimum of a
and a maximum of b.
- What must we require regarding a and b to allow legal splits and merges of nodes?
- What are the rebalancing problems and how do we design rebalancing operations to fix them? Conclude that rebalancing is worst-case logarithmic time.
- Show that with a minimal choice of b, logarithmic time is also a lower bound for the rebalancing.
- Can you show anything better using a b slightly larger than the minimum requirement.
- Consider turning skip lists into a deterministic (non-probabilistic) data structure, i.e., instead of choosing the level of an element probabilistically hoping that we get the right mix of levels, we decide that in between two elements of level l, l > 1, we must have exactly one or two elements of level l-1. Rethink properties and operations on the structure.
- Try to design a multi-dimensional priority queue. Thus, each item has several priorities (that come from different domains) and we want to be able to make a deletemin in whichever domain, we are currently interested in. Start with dimension 2. Use a heap-shape and let levels have different properties.