A splay tree is a binary search tree with amortised complexity O(log(n)) peroperation.
(i) What is meant by amortised complexity?
(ii) Draw the three different splay rotations that may be applied when thetarget node is the left child of its parent. Take care to include the locationof subtrees before and after each rotation.
(iii) Why is a red-black tree a better general-purpose search structure than asplay tree? Under what circumstances would you choose to implement asplay tree in preference to a red-black tree, and why?