Question 4.17 and 4.19 its from c++

Exercises 4.17 Prove that the depth of a random binary search tree (depth of the deepest no O(log N), on average. node) is 4.18 *a. G ive a precise expression for the minimum number of nodes in an AVL tree of height h b. What is the minimum number of nodes in an AVL tree of height 15? 4.19 Show the result of inserting 2, 1,4,5, 9, 3, 6, 7 into an initially empty AVL tree. 4.20 Keys 1,2,...,2k 1 are inserted in order into an initially empty AVL tree. Prove that the resulting tree is perfectly balanced. 21 Write the remaining procedures to implement AVL single and double rotations. 4.22 Design a linear-time algorithm that verifies that the height information in an AVL tree is correctly maintained and that the balance property is in order. 23 Write a nonrecursive function to insert into an AVL tree. 24 Show that the deletion algorithm in Figure 4,47 is corect 25 a. How many bits are required per node to store the height of a node in an N-node AVL tree? b. What is the smallest AVL tree that overflows an 8-bit height counter? Write the functions to perform the double rotation without the inefficiency of doing 26 two single rotations. 27 Show the result of accessing the keys 3, 9, 1, 5 in order in the splay tree in