THINK FIRST·CODE LATER

← All labs

AVL Rotation Log

Problem

Read an integer n, then n integer keys, and insert them one by one into an initially empty AVL tree. After each insertion print one line:

  • Insert K: no rotation if the tree did not need rebalancing,
  • Insert K: C at Z if a rebalancing happened, where C is the case (LL, RR, LR or RL) and Z is the key of the lowest unbalanced node,
  • Insert K: duplicate if K was already in the tree (the tree does not change).

After all insertions print the root key (none for an empty tree) and how many single (LL/RR) and double (LR/RL) rotations were performed.

Input:

7 10 20 30 25 28 27 27

Output:

Insert 10: no rotation
Insert 20: no rotation
Insert 30: RR at 10
Insert 25: no rotation
Insert 28: LR at 30
Insert 27: RL at 20
Insert 27: duplicate
Root: 25
Single: 1, Double: 2

Classify the case from the balance factors: bf(Z) = +2 is LL when Z's left child has bf ≥ 0 and LR otherwise; bf(Z) = −2 is RR when Z's right child has bf ≤ 0 and RL otherwise.

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-2-data-1.txt

7 10 20 30 25 28 27 27
What your program must print for d13-2-data-1.txt
Insert 30: RR at 10
Insert 25: no rotation
Insert 28: LR at 30
Insert 27: RL at 20
Insert 27: duplicate
Root: 25
Single: 1, Double: 2

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-2-data-1.txt

Windows PowerShell does not understand <:

Get-Content d13-2-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.