 prove that the depth of random binary search tree (depth of the deepest nodeis (log )on average give precise expression for the minimum number of nodes in an avl tree of height what is the minimum number of nodes in an avl tree of height show the result of inserting into an initially empty avl tree keys are inserted in order into an initially empty avl tree prove that the resulting tree is perfectly balanced write the remaining procedures to implement avl single and double rotations design linear-time algorithm that verifies that the height information in an avl tree is correctly maintained and that the balance property is in order write nonrecursive function to insert into an avl tree show that the deletion algorithm in figure is correct how many bits are required per node to store the height of node in an -node avl treeb what is the smallest avl tree that overflows an -bit height counter write the functions to perform the double rotation without the inefficiency of doing two single rotations show the result of accessing the keys in order in the splay tree in figure show the result of deleting the element with key in the resulting splay tree for the previous exercise show that if all nodes in splay tree are accessed in sequential orderthe resulting tree consists of chain of left children figure tree for exercise