AVL树平衡因子必须为左子树高度减右子树高度，空节点高度定义为0；插入/删除后仅更新路径上节点高度，失衡时立即旋转且不再向上更新，四种旋转条件由当前及子节点平衡因子共同决定。
AVL树的平衡因子怎么算才不会错
平衡因子必须是左子树高度减右子树高度，不是反过来。很多初学者在getBalanceFactor里写成rightHeight - leftHeight，结果旋转方向全反了，插入后树反而更失衡。
高度计算要统一用空节点高度为0（不是-1），否则height(nullptr)返回-1会导致平衡因子多算±1，后续所有旋转判断失效。
- 定义
height(Node* n)：若n == nullptr，返回0；否则返回1 + max(height(n->left), height(n->right)) -
getBalanceFactor(Node* n)必须是height(n->left) - height(n->right) - 每次插入/删除后只更新从修改点到根路径上的节点高度，别全树遍历——O(log n)更新，不是O(n)
四种旋转的触发条件和参数顺序别搞混
LL、RR、LR、RL这四种情况由失衡节点的平衡因子和其子节点的平衡因子共同决定，不能只看方向。比如LL型要求：当前节点balance > 1且left->balance > 0（不是≥0）；LR型则是balance > 1且left->balance 。
旋转函数的参数必须是失衡的根节点，返回新根。例如rotateRight(Node* y)里，y是原失衡节点，不是它的左孩子。
立即学习“C++免费学习笔记（深入）”；
-
rotateRight(Node* y)：设x = y->left，T2 = x->right，然后重连x->right = y，y->left = T2 -
rotateLeft(Node* x)：设y = x->right，T2 = y->left，然后y->left = x，x->right = T2 - LR型 = 先对左孩子
rotateLeft(x->left)，再对xrotateRight(x)；RL型相反
插入后回溯更新时，什么时候该旋转、什么时候只调高度
插入递归返回时逐层更新高度并检查平衡因子。只要某层abs(balance) > 1，立刻旋转，**旋转后不再继续向上更新高度**——因为旋转已重构子树，其高度可能变化，但父节点的高度需等旋转返回后再重新计算。
- 插入返回后，在当前节点先
updateHeight(node)，再int bf = getBalanceFactor(node) - 若
bf > 1且node->left->balance >= 0→ LL；若bf > 1且node->left->balance → LR - 旋转函数返回新根，必须用该返回值覆盖原父指针（比如
root = rotateRight(root)），否则链断裂 - 旋转完成后，直接return新根，**不要接着调
updateHeight**——旋转内部已保证子树高度正确，上层会自然重算
为什么删除比插入更容易出bug
删除后失衡可能出现在多层，且同一节点可能需要连续两次旋转（比如先RL再LL），但更常见的是漏掉“旋转后仍不平衡”的情况：一次旋转只能修复局部，父节点仍可能失衡，所以必须让旋转返回新子树根，并在递归回溯中持续检查。
- 删除后更新高度前，先确认子节点是否非空——
if (node->left) updateHeight(node->left)，空指针解引用是常见段错误 - 删除叶子节点最简单；删只有一个孩子的节点，直接替换；删有两个孩子的节点，用中序后继（右子树最左）替换，**但后继可能也有孩子，不能直接delete后继节点，要递归删除它**
- 删除函数必须返回当前子树新根（可能是旋转后的节点），否则上层指针没更新，树结构就断了
平衡因子计算和旋转方向一旦错一位，整棵树就无法自愈；调试时建议先打印每个节点的val/bf/height三元组，比单步跟指针更直观。
