(d) (2 points) Balance the following tree via a double-rotation. Draw the result after each rotation. 35 3. (2 points) Insert 62 into the following AVL Tree and perform the necessary rotation(s). Draw the tree just after insertion (but before (each) rotation) and draw the final tree. 50 70 20 42) 60 80 65 4. (3 points) Show the result of inserting 2, 1, 4, 5, 9, 3, 6, 7 into an initially empty AVI tree. 5. Say we delete element 5 from the following AVI-tree 25 10 4355 delete 5 45 76 95 (a) (1 point) After the deletion, what is the deepest node whose subtree is no longer an AVL Tree? (b) (1 point) What kind(s) of rotation is necessary? (c) (2 points) Draw the new tree after the rotation. (d) (1 point) After the rotation do we have an AVL tree? If not, specify and perform any more needed rotations and draw the resulting tree 6. (3 points) Show the result of insert 5, 1, 19, 25, 17,21,20,9, 15, 14 into a BST using splay insertion. 7. (2 points) Perform a splay search(7) on the following BST and draw the result. 4 7