- Suppose I want to insert the values 7, 8, 3, 1, 4, 9, 2 into a splay tree in that order. Sketch out the splay tree after each of the insertions have been made (i.e. seven diagrams total).
- Suppose I take the final tree from Problem 1 and then delete the values 9, 3, 4 in that order. Sketch out the splay tree after each of the deletions have been made (i.e. three diagrams total).
- Suppose I want to insert the values 7, 8, 3, 1, 4, 9, 2 into a (2,4) tree in that order. Sketch out the (2,4) tree after each of the insertions have been made (i.e. seven diagrams total).
- Suppose I take the final tree from Problem 3 and then delete the values 9, 3, 4 in that order. Sketch out the (2,4) tree after each of the deletions have been made (i.e. three diagrams total).
- Can we use a splay tree to sort n comparable elements in O(n log n) time in the worst case scenario? Why or why not?
- Prove that if I insert the values from 1 to n into a splay tree in ascending order, I will end up with a linked list of values starting at n and decrementing down to 1 in reverse order.