AVL 树插入一个节点后如何恢复平衡？

简化版

先像普通 BST 一样把新节点插到叶子位置，然后从插入点沿路径回到根，逐个更新祖先的高度、检查平衡因子。遇到第一个失衡（|BF|=2）的节点，按 LL/RR/LR/RL 做对应旋转即可。关键结论：AVL 插入最多只需一次旋转（单旋或双旋）就能恢复整棵树的平衡，之后更上层的节点高度也会随之复原。

详细版

插入分三步：

BST 插入：按值大小找到空位，新建节点挂上去（新节点初始高度为 1、平衡因子为 0）。
回溯更新高度：从新节点往上回到根，每经过一个祖先就重新计算它的高度 height = max(左高, 右高) + 1。
检查并旋转：在回溯过程中遇到第一个 |BF|=2 的节点，判断失衡类型做旋转。

TreeNode insert(TreeNode node, int val) {
    if (node == null) return new TreeNode(val);
    if (val < node.val)      node.left  = insert(node.left,  val);
    else if (val > node.val) node.right = insert(node.right, val);
    else return node;                          // 值重复，不插

    update(node);                              // 更新高度
    return rebalance(node);                    // 检查平衡因子并按类型旋转
}

rebalance 里根据 BF 判断 LL/RR/LR/RL 并旋转。

完整版教学

一、为什么插入最多一次旋转

这是 AVL 插入最重要的结论。插入一个节点只会让「从插入点到根这条路径上」的节点高度可能 +1。当遇到第一个失衡的祖先并对它旋转后，旋转会把这棵子树的高度恢复到插入前的值——也就是说旋转后，这棵子树对更上层的高度贡献没有变化，上面的节点也就不再失衡了。所以一次旋转（单旋算一次、双旋也算一次调整）就够了，不需要继续往上调整。

这和删除形成鲜明对比：删除可能需要一路旋转到根（见 AVL 删除）。插入「一次搞定」是 AVL 的一个好性质。

二、回溯更新高度是关键

AVL 靠每个节点存的高度字段来算平衡因子，所以插入后必须自底向上更新沿途祖先的高度。用递归实现时，这一步天然发生在「递归返回的路上」——先递归插入子树，返回后更新当前节点高度、再检查平衡，正好是自底向上的顺序。

三、四种失衡的判定与处理

在某个失衡节点（|BF|=2）上，结合它和较高孩子的平衡因子判断类型：

TreeNode rebalance(TreeNode node) {
    int bf = bf(node);
    // 左偏
    if (bf > 1) {
        if (bf(node.left) < 0) node.left = leftRotate(node.left); // LR：先左旋左孩子
        return rightRotate(node);                                 // LL / LR 收尾：右旋
    }
    // 右偏
    if (bf < -1) {
        if (bf(node.right) > 0) node.right = rightRotate(node.right); // RL：先右旋右孩子
        return leftRotate(node);                                      // RR / RL 收尾：左旋
    }
    return node;   // 平衡，无需旋转
}

判断口诀还是「同向单旋、拐弯双旋」：失衡节点和高孩子同号就单旋，异号就先把孩子转成同号（掰直）再单旋。

四、走一个例子

依次插入 1, 2, 3：

插 1、2 正常 → 插 3 后节点 1 的 BF=-2（RR 型）
  1                    2
   \      左旋 1      / \
    2     ——→        1   3
     \
      3

如果不平衡就退化成链，AVL 通过这一次左旋把它变成了完美平衡的树。

五、复杂度

时间 O(log n)：BST 插入下降 O(log n) + 回溯更新/旋转 O(log n)，旋转本身 O(1)。
旋转次数：最多 1 次（单旋或双旋）。
空间 O(log n)：递归栈（等于树高）。

六、常见误区与追问

考点	正确口径
插入位置	按 BST 规则插入到叶子
失衡检测	回溯更新高度并检查平衡因子
修复方式	LL/RR 单旋，LR/RL 双旋

insert like BST
update height upward
if balance > 1 or < -1:
  choose LL/RR/LR/RL rotation

AVL 插入的旋转点是从新节点向上遇到的第一个失衡祖先。

误区：AVL 插入前就能确定旋转类型。 必须先按 BST 插入，再回溯看失衡节点和插入方向。
误区：平衡因子只要不等于 0 就要旋转。 AVL 允许平衡因子为 -1、0、1，绝对值超过 1 才失衡。
误区：LR 和 RL 只需要一次旋转。 LR/RL 是内侧插入导致的折线结构，需要先对子节点旋转，再对失衡节点旋转。
追问：为什么插入通常一次旋转就够？ 在第一个失衡祖先处旋转后，该子树高度恢复到插入前的高度，祖先不再继续失衡。
追问：高度更新顺序是什么？ 先更新较低层节点，再更新旋转后的新子树根，避免用旧高度判断。
追问：复杂度是多少？ AVL 高度 O(log n)，插入查找和回溯都在树高内，时间 O(log n)。

七、加强记忆

AVL 插入三步：BST 插到叶子 → 自底向上更新祖先高度 → 遇到第一个 |BF|=2 的节点按 LL/RR/LR/RL 旋转。核心结论：插入最多一次旋转就能恢复整树平衡（因为旋转会把子树高度复原到插入前，上层不再失衡），这点优于删除。判断类型仍是「同向单旋、拐弯双旋」。整体 O(log n)。

简化版

详细版