Exercises 1. 4. 2021: More (a,b)-trees

Ex. 1: (2,4)-trees vs red-black trees

Red-black tree is a BST that is balanced by maintaining following invariants: It can be useful to consider edge color instead: The color of an edge is the color of the lower end-point. I.e. parent-edge of a red node is red, parent-edge of a black node is black.
  1. Show, that every (2,4)-trees is in fact a red-black tree. That is, desing a simple mapping that transforms given (2,4)-tree into a valid red-black tree. Note that we are not really looking for an algorithm but for mapping in the mathematical sense. Hint: Try to represent each node of a (2,4)-tree as a red-black tree.
  2. What about the other way around? Can we turn any red-black tree into a (2,4)-tree?
  3. Left-leaning red-black tree (LLRBT) maintains additional invariant: Show, that there is a 1-1 correspondence between (2,4)-trees and left leaning red-black trees. That is, desing a mapping between (2,4)-trees and LLRBT that assigns a unique LLRBT to any (2,4)-tree (or a unique (2,4)-tree to any LLRBT, which is the same thing).

Ex. 2: Amortized (a, 2a-1)-trees

In the lecture we saw that any sequence of \(m\) Inserts and Deletes in a (a, 2a)-tree modifies only \( \mathcal{O}(m)\) nodes in total (starting with an empty tree).
Show that this bound does not work for (a, 2a-1)-trees. That is, for any \(n\) and \(m\) design a sequence of \(m\) operations on a tree with \(\Theta(n)\) nodes that modifies \(\Omega(m\log(n))\) in total.
Start with (2,3)-trees, then generalize your construction to any (a,2a-1)-trees.
You may start with any (valid) \(n\)-node tree you design. Once your argument is finished, check that you can actually create such tree from an empty tree.