Splay Trees Exercises

1. Discuss with your neighbor:
   1. What a Splay tree is (and is not)
   2. The main advantage(s) of using a Splay tree?
   3. The Big-Ohs for Splay trees operations:

      	Average-case	Worst-case
      Retrieval
      Insertion
      Deletion
      Traversal

   What does amortized mean?
2. Review the splaying handout
3. Insert the numbers 1, 2, ... 5 into a Splay tree.
   Draw the tree after each insertion.
   Draw the tree after each Zig, Zig-zag and Zig-zig rotation.
   (Note: If it's helpful, identify which node is k₁, k₂, ...)
   (Note: Double check that after each rotation that it's still a BST.)
   
4. Insert the numbers 1, 5, 2, 6, 3, 7, 4, 8 into a Splay tree.
   Draw the tree after each insertion.
   Draw the tree after each Zig, Zig-zag and Zig-zig rotation.
   

Last Modified: