HW6. Succinct trees (15th of Oct, 23.59)
EX1. 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 before. Try to provide descriptions how to access 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 smallest nr 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 nr of different trees. Compare the growth rate of catalan numbers vs 22n. Plot the numbers (use logarithmic axes to fit larger values on plots). Are they in Theta() relationship (exactly the same growth rate)?
EX3. Insert 7, 8, 6, 9, 10, 3, 12 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 21). Show how the child of 9 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 generalised node sequence representation: level-wise (starting from slide 36) or depth-first (starting from slide 39) representation;
- the other using the parenthesis representation (starting from slide 42).
Argue, which one seems most natural and describe the same operations (finding child of 12 and parent of 9) on both of them.
EX5. Describe two further operations - subtree size and 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.
EX6. (bonus 2p) Consider the van Emde Boas tree implementation for 64-bit integers. How large would be the data structure (in bits) if you insert 1 million values distributed uniformly randomly across 64-bit integers. In comparison, count the size of the similarly organised tree data structure if implemented explicitly as a tree with pointers.