![[topimage]](IMADA_en.png)
Exercises
- For Y-Fast Tries, we had to keep the sizes of the small red-black trees in the range [(log M) / 4, 2 log M]. Thus, for deletion, when a tree got too small, we would merge it with a neighbor. If this merge was then above or too close to the high end of the allowed interval, we would split into two even-sized trees (±1). Choose when to split with the aim of maximizing the worst-case distance to one of the extreme points of the allowed interval for any of the up to two trees involved that will be created. (In the lecture, we arbitrarily chose to split if the size exceeded (3/2) log M.)
- Reconsider the operations meld and split from the last exercises, but now in a context where the red-black trees are leaf-oriented, i.e., the real keys are all in the leaves, and the internal nodes just contain routers (that could be copies of existing or old keys), directing a search in the right direction.
- We have argued in class that a single rotation preserves the search tree invariant. Argue more broadly that this is also the case for the following: Consider any connected subgraph of nodes in a search tree (for the single rotation, the subgraph has two nodes). Now, remove all trees hanging off nodes in this subgraph in an in-order fashion and, separately, all the keys of nodes of the subgraph in an in-order fashion. Then rearrange the subgraph into any other connected subgraph. Add the keys to the nodes in-order and attach the trees again, also inorder. Argue that the tree is a search tree.
- Assume writes cost c times more than reads (this is the case on a USB key, for instance). Go through the standard sorting algorithms and determine the asymptotic complexity as a function of both n and c, i.e., you have to calculate number of reads and writes separately. Do any of them have O(cn) writes? Do any of them run in O(n log n + cn)? Can you obtain the latter by sorting in another way?
-
Together we will develop known data structures from basic design ideas.
First, a balance idea for binary search trees: For any node, the height
of its subtrees may differ by at most one. Before the exercises, try
to think about the following questions:
- Which height bound can be guaranteed? A good way to approach this would be to make the tree with the smallest number of nodes for a given height; try small heights first. Can see you a pattern?
- Which problems can insertions and deletions create?
- Can you find at least a partial collection of rebalancing operations that remove these problems? What kind of strategy might be good if we aim for efficiency?