Data structure and Algorithm Analysis

1. [10 points]

Consider a Binary Search Tree.

(a) Draw all valid Binary Search Trees for the four nodes 1, 2, 3, 5.

(b) Look up Catalan Numbers on the internet, and compute the nth Catalan number for n = 4. Compare this

number to the number of Binary Search Trees you came up with above.

2. [10 points]

(a) Draw all valid Binary Red Black Trees for the four nodes 1, 2, 3, 5. Label each of your nodes R or B for Red/Black. Note the corresponding Black Height of each of the nodes in your Red Black Trees, to help convince yourself it is a valid Red Black tree.

(b) At least for one of your Red Black Trees, give a full explanation of why it is a valid Red Black Tree, and how you determined the Black Height of the nodes.

3. [10 points]

Show schematics of Red Black trees with Black Height 3, that have either the shortest or the longest possible simple path from the root node to a descendant leaf (nil node). What is the maximum ratio between the longest and the shortest possible simple paths?

4. [10 points]

Consider a Red Black tree that already has 41; 38; 31; 12 inserted. Draw the resulting Red Black tree (you can use for help https://www.cs.usfca.edu/galles/visualization/RedBlack.html). Now consider adding the node 19. Show all the stages of the insert fix up and write down what cases these changes correspond to (from what we learned). Again, you can use the animation for help, but explain what was done in terms of the cases. Finally, explain why the final tree after inserting 19 is a valid Red Black tree.