Question 7 (9 marks)

Consider the following splay tree :

 
      5
     /
    4
   /
  3

Based on the above answer the following questions:

1. Give an example of a key that would result in a worst case scenario for splay insertion in terms of time complexity. State the number of comparisons performed and show the resulting splay tree and state exactly what sequence of rotations were used.

2. Give an example of a key that would result in the worst case scenario for splay insertion in terms of the resulting height of the tree. Assume you are inserting into the origina tree, not the tree from your answer in part A. State the number of comparisons performed and show the resulting splay tree and state exactly what sequence of rotations were used.

3. Explain how your answers from part a and b relate the amortised time complexity of splay tree insertion and search.

4. Show the trees that would have resulted from performing the same insertions using normal root insertion.

Type the answer to this question into the file called q7.txt and submit it using the command:

$ submit q7

The above command will make a copy of q7.txt as your answer for this question.