THINK FIRST·CODE LATER

← All labs

How tall can an AVL tree be?

Problem

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, in long);
  • maxNodes(h) = 2^(h+1) − 1;
  • maxHeight(n) — the tallest AVL tree with n keys (the largest h with N(h) ≤ n) and minHeight(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

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

d13-6-data-1.txt

6
7 100 1000000
What your program must print for d13-6-data-1.txt
 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

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < d13-6-data-1.txt

Windows PowerShell does not understand <:

Get-Content d13-6-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.