Write AvlVersusBst. Read n and n keys. Insert them, in order, into a plain BST and into an AVL tree (store each node's height; after inserting, rebalance with the LL / LR / RR / RL rotations on the way back up; count every single rotation). Print both heights, the AVL root and rotation count, and the average number of key comparisons needed to find each of the n keys in each tree.
For the input
7
1 2 3 4 5 6 7
the program prints
Keys: 7
BST height: 6, AVL height: 2
AVL root: 4, rotations: 4
Average comparisons per search: BST 4.00, AVL 2.43