HW6. Succinct trees (21st of Oct, 23.59)
EX1. A binomial tree of degree 4 (or any degree) has a very specific structure. If you would need an implicit structure to represent it, there is exactly one such tree. Draw a binomial tree of degree 4 and number the nodes in some way (you can use post-order, pre-order or any other way that seems reasonable). Now represent the tree as an array where the array index represents the number you gave to the node. Try to provide descriptions on how to access the first child, parent and next sibling as mathematical operations if possible (feel free to use combinations - e.g. choose(i,k) and sums... ) or if not then just as descriptions. These operations are needed to be able to traverse the tree and perform "bubble up" or "bubble down" operations (which you don't have to do here, but this is the motivation).
EX2. In the lectures, we tried to establish what is the information-theoretic bound in the smallest number of bits needed to represent binary trees. Slides claimed that there are up to 22n distinct trees of n nodes, but we also showed that Catalan numbers count the number of different trees. Compare the growth rate of Catalan numbers vs 2^{2n}. Plot the numbers (use logarithmic axes to fit larger values on plots). Are they in Theta() relationship (exactly the same growth rate)?
EX3. Insert 3, 4, 2, 7, 9, 1, 10 into an (unbalanced) BST in this order. Draw the tree. Now make a succinct representation of that tree using the first succinct representation shown in the lecture (starting from slide 18). Show how the child of 7 and parent of 10 can be found using this succinct representation.
EX4. Create two more succinct representations of the same tree:
- choose one from the generalized node sequence representation: level-wise (starting from slide 34) or depth-first (starting from slide 37) representation;
- the other using the parenthesis representation (starting from slide 40).
Argue, which one seems most natural and describe the same operations (finding child of 7 and parent of 10) on both of them.
EX5. Describe two further operations - subtree size and the lowest common ancestor of two nodes using one of the above representations. You can use the same example data, but in case it is too small you can modify it. Why do you need such operations?
EX6. (bonus 2p) Consider the van Emde Boas tree (slide 74 in the lecture about Heaps) implementation for 64-bit integers. How large would be only the data structure in bits (only structure, without data) if you insert 1 million values distributed uniformly randomly across 64-bit integers? In comparison, count the size of the similarly organized tree data structure if implemented explicitly as a tree with pointers. What if you would use a succinct instead?