Algorithms
(a) What is a binary search tree rotation, and how are rotations useful in the
creation of efficient search tree algorithms? [2 marks]
(b) Write pseudocode for a recursive function select(x, i) which, given a
binary search tree with root node x, executes a sequence of rotations to move
the i
th largest node to the root of the tree and returns a pointer to the new
root node. [6 marks]
(c) Making use of select to deal with tricky cases, write pseudocode for a
recursive function delete(x, k) which deletes the node containing key value
k from the tree and returns a pointer to the new root node. [5 marks]
(d) Write a more efficient version of delete which does not use recursion or
rotation to perform its work. How does its time complexity compare with
your answer to part (c)? [7 marks]