AVL 树 · 自平衡插入

AVL 树 · 自平衡插入

已经给好 height（按边数，空树 = -1）和两个旋转 leftRotate / rightRotate。请补全 insert：先做普通 BST 插入，回溯时算平衡因子 bf = height(左) - height(右)，若 |bf| = 2 就按四种情况旋转修复：

| 失衡形态 | 条件 | 修复 |
|---|---|---|
| 左左 LL | bf>1 且 v<t->left->value | rightRotate(t) |
| 右右 RR | bf<-1 且 v>t->right->value | leftRotate(t) |
| 左右 LR | bf>1 且 v>t->left->value | 先 leftRotate(t->left)，再 rightRotate(t) |
| 右左 RL | bf<-1 且 v<t->right->value | 先 rightRotate(t->right)，再 leftRotate(t) |

建完整棵 AVL 后，程序会输出它的前序遍历——只要旋转正确，树形（也就是前序）就对。

输入

• 第 1 行：整数 n；第 2 行：n 个整数，按此顺序插入。

输出

• 一行：最终 AVL 树的前序遍历（每个值后跟一个空格）。

示例：输入 3 / 10 20 30 → 输出 20 10 30 （连续插入触发右右型，对 10 左旋，20 升为根）。