## 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:
• Every node is either black or red
• Root and null pointers are black
• There are no consecutive red nodes (i.e. red node must have black parent).
• All root-leaf paths contain the same number of black nodes.
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:
• If the node has a single red son/edge, then it is the left son/edge.
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.
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.