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.

Your solution

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.

← D13.1 Build an AVL Tree D14.1 Linear Probing Table →