1. Write a program to perform random operations on splay trees. Count the total number of rotations performed over the sequence. How does the running time compare to AVL trees and unbalanced binary search trees?
2. Write ef?cient functions that take only a pointer to the root of a binary tree, T, and compute
a. the number of nodes in T
b. the number of leaves in T
c. the number of full nodes in T
What is the running time of your routines?