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.
- 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.
- What about the other way around? Can we turn any red-black tree into a
(2,4)-tree?
- 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.
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.