AVL Tree: Self-balancing Insert
height (by edges, empty = -1) and the two rotations leftRotate / rightRotate are provided. Complete insert: do a normal BST insert, then on the way back up compute bf = height(left) - height(right) and rotate to fix when |bf| = 2, in four cases:
| Imbalance | Condition | Fix |
|---|---|---|
| Left-Left | bf>1 && v<t->left->value |
rightRotate(t) |
| Right-Right | bf<-1 && v>t->right->value |
leftRotate(t) |
| Left-Right | bf>1 && v>t->left->value |
leftRotate(t->left) then rightRotate(t) |
| Right-Left | bf<-1 && v<t->right->value |
rightRotate(t->right) then leftRotate(t) |
After building the AVL, the program prints its preorder — if your rotations are correct, the shape (preorder) will match.
Input
- Line 1: integer
n; line 2:nintegers inserted in this order.
Output
- One line: preorder of the final AVL tree (a space after each value).
Example: input 3 / 10 20 30 → output 20 10 30 (the run triggers a Right-Right case; left-rotate at 10 lifts 20 to the root).