A splay tree is a binary search tree with amortised complexity O(log(n)) per operation.

(i) What is meant by amortised complexity? [1 mark]

(ii) Draw the three different splay rotations that may be applied when the target node is the left child of its parent. Take care to include the location of subtrees before and after each rotation. [9 marks]

(iii) Why is a red–black tree a better general-purpose search structure than a splay tree? Under what circumstances would you choose to implement a splay tree in preference to a red–black tree, and why? [4 marks]

(b) Heapsort is an O(n log(n)) sorting algorithm based on the heap data structure. (i) What is the heap property? [1 mark]

(ii) Briefly describe how heapsort is related to the classic quadratic-time selection sort algorithm, explaining how heapsort manages to sort more efficiently. [5 marks]