1. 2.

3.

(a) What is the average cost of find on a binary search tree generated by the insertion of the elements: 9,7, 12, 10, 3, 11,6, 4,8 into an empty tree. Show your working. (b) Write down six insertion orders of the numbers in the set: 1,2,3,4 That will create a degenerated binary search tree. Hint a degenerated binary search tree is one of maximal depth for its number of elements. (c) Prove by induction that a tree with n nodes has n-1 edges. (d) Draw a sequence of diagrams showing the insertion of the values: [13,11, 9,27,19,21,3] into an empty AVL tree. You must: Show the resulting tree immediately after each insertion step (that is before any balancing has taken place) Indicate the node(s) at which each rotation is performed. Where there is a double rotation, show the tree after each single rotation. Show the resulting tree after balancing operation(s)