The AVL condition limits the height. Write AvlLimits:
minNodes(h)— the fewest nodes an AVL tree of height h can have: N(h) = 1 + N(h − 1) + N(h − 2), with N(0) = 1 and N(−1) = 0 (compute it with a loop, inlong);maxNodes(h)= 2^(h+1) − 1;maxHeight(n)— the tallest AVL tree with n keys (the largest h with N(h) ≤ n) andminHeight(n)(the smallest h with maxNodes(h) ≥ n).
Read a number of rows and print the table for h = 0 … rows; then, for each n until the end of input, print the range of AVL heights, log₂ n, the ratio worst height / log₂ n, and the height n − 1 that a plain BST may reach.
For the input
6
7 100 1000000
the program prints
h fewest nodes most nodes
0 1 1
1 2 3
2 4 7
3 7 15
4 12 31
5 20 63
6 33 127
n = 7: AVL height between 2 and 3 (log2 n = 2.8, ratio 1.07); a plain BST may reach 6
n = 100: AVL height between 6 and 8 (log2 n = 6.6, ratio 1.20); a plain BST may reach 99
n = 1000000: AVL height between 19 and 27 (log2 n = 19.9, ratio 1.35); a plain BST may reach 999999