AVL树插入后仅当某节点平衡因子变为2或-2时才必须旋转，且该节点是从插入点向上首个失衡的祖先；旋转类型由新节点在失衡节点左右子树中的插入位置决定：LL/RR为外侧插入需单旋，LR/RL为内侧插入需双旋。
AVL树插入后什么时候必须旋转？
不是每次插入都触发旋转，只在某个节点的平衡因子（左子树高度减右子树高度）变成 2 或 -2 时才需要调整。关键在于：这个失衡节点不一定是新插入的叶子，而是从插入点向上第一个满足 |bf| == 2 的祖先节点。
常见错误是“一看到高度差就立刻转”，结果多转或转错方向。真正要处理的是该失衡节点及其两个孩子构成的局部子树——后续旋转类型完全由这个三节点结构决定。
四种旋转场景怎么判断？看的是插入路径，不是单纯左右子树高度
旋转类型取决于新节点插入到了失衡节点哪一侧、以及它在那一侧的哪个“分支”：是外侧（LL / RR）还是内侧（LR / RL）。不能只看左右子树谁高，而要看新增节点相对于失衡节点的“拐弯方向”。
-
LL：插入到左子节点的左子树 → 右旋一次 -
RR：插入到右子节点的右子树 → 左旋一次 -
LR：插入到左子节点的右子树 → 先对左子节点左旋，再对当前节点右旋 -
RL：插入到右子节点的左子树 → 先对右子节点右旋，再对当前节点左旋
示例：若节点 A 失衡（bf = 2），其左孩子 B 的右子树增高了，说明新增节点在 B 的右侧 → 属于 LR 型，必须先 rotateLeft(B) 再 rotateRight(A)，缺一不可。
立即学习“C++免费学习笔记（深入）”；
rotateLeft 和 rotateRight 必须更新高度，且顺序不能反
旋转本身只是指针重连，但 AVL 的核心约束靠 height 字段维持。漏更新高度会导致后续判断失衡位置出错，甚至无限循环调用旋转。
典型实现中，旋转函数末尾必须显式调用 updateHeight()（或直接计算）更新涉及节点的高度。且更新顺序有依赖：比如 rotateLeft 中，要先更新原根节点（现在是左孩子）的高度，再更新新根节点的高度。
Node* rotateRight(Node* y) {
Node* x = y->left;
y->left = x->right;
x->right = y;
updateHeight(y); // 先更新 y（下层）
updateHeight(x); // 再更新 x（上层）
return x;
}
删除操作比插入更难平衡，别跳过双旋转的递归回溯
插入最多引发一次双旋转（LR/RL），而删除可能让父节点再次失衡，必须沿插入/删除路径向上逐层检查并旋转。很多人只处理了第一次失衡，就返回了，结果树依然不平衡。
正确做法是在递归删除后，立即重新计算当前节点高度，并检查平衡因子。若失衡，按前述规则旋转；旋转完成后，**仍需再次更新新根高度**，并返回该新根——否则上层拿到的仍是旧指针，高度信息错乱。
最容易被忽略的是：一次 rotateRight 后，若原节点 y 仍有父节点，那个父节点的子指针必须指向旋转返回的新根 x，而不是继续指向 y。这要求所有旋转调用都用 node = rotateRight(node) 这种赋值方式，而非无返回的 void 版本。
