AVL树平衡因子必须为左子树高度减右子树高度，节点需存储height字段并沿路径向上更新，范围仅限−1、0、1；失衡时按LL、LR、RR、RL四种形态对应右旋、先右后左、左旋、先左后右旋转，插入删除后须自底向上逐层updateHeight并rebalance。
AVL树的平衡因子怎么算才不会错
平衡因子必须是左子树高度减右子树高度，不是反过来。很多初学者在 getBalanceFactor 里写成 rightHeight - leftHeight，结果旋转逻辑全反了，树越插越歪。
实际计算时别手写递归求高——每次插入都重新遍历整棵子树太慢。应该在节点结构里存 height 字段，插入/删除后沿路径向上更新，时间复杂度从 O(n) 降到 O(log n)。
-
height初始设为 1（单节点高度为 1），空节点高度为 0 - 更新公式固定为：
node->height = 1 + max(getHeight(node->left), getHeight(node->right)) - 平衡因子范围只能是 -1、0、1；超出就得旋转
四种旋转什么时候用哪种
不是看平衡因子正负决定左旋还是右旋，而是看「失衡节点」和「较高子节点」的「较高孙子节点」三者相对位置。核心判断依据是：LL、LR、RR、RL 四种形态。
LL 型（左左）：当前节点平衡因子 > 1，且左孩子平衡因子 ≥ 0 → 右旋
RR 型（右右）：当前节点平衡因子
LR 型（左右）：当前节点平衡因子 > 1，且左孩子平衡因子
RL 型（右左）：当前节点平衡因子 0 → 先对右孩子右旋，再对当前节点左旋
- 注意：LR/RL 中第一次旋转后，原孩子的
height必须先更新，再更新当前节点 - 旋转后所有涉及节点的
height都要重算，漏掉一个就可能导致后续判断失效 - 旋转函数返回新根节点，调用处必须用返回值覆盖原指针，比如：
root = rotateRight(root)
插入后如何正确回溯更新和旋转
AVL 插入不是插完就完了，关键在递归返回时检查并修复路径上每个祖先节点。很多人只在插入点做一次平衡，忽略了上面可能还存在失衡。
立即学习“C++免费学习笔记（深入）”；
标准做法是让插入函数返回更新后的子树根，并在每一层返回前调用 updateHeight 和 rebalance：
Node* insert(Node* node, int key) {
if (!node) return new Node(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node; // 重复键不插入
<pre class='brush:php;toolbar:false;'>updateHeight(node); // 必须先更新高度
return rebalance(node); // 再平衡，可能返回新根}
-
rebalance里根据平衡因子触发对应旋转，旋转后仍要调用updateHeight（因为结构变了） - 即使某层没旋转，也要返回当前节点——否则父层指针会断
- 如果使用智能指针或引用传参，要注意旋转后 root 的所有权转移
为什么删除比插入更容易出 bug
删除节点时，若该节点有两个子节点，常规做法是找中序后继（右子树最左节点）替换，但替换后那个后继节点本身可能失衡——而很多人只对被删节点的父节点做一次平衡，漏掉了后继节点原来的位置。
正确做法是：无论删的是叶子、单子节点还是双子节点，都要从「实际被删的那个节点位置」开始向上回溯平衡。也就是说，中序后继被挖走后，要从它原来的位置（即右子树的最左路径）一路向上更新和旋转。
- 删除函数也必须返回新子树根，不能 void
- 后继节点被摘下后，它的父节点的
left指针要置 nullptr，否则残留指针会导致后续 height 计算错误 - 某些实现把删除拆成「找后继→复制值→删后继」三步，第二步复制值不改变树结构，第三步才是真正的删除点，平衡必须从第三步的位置出发
实际写的时候，getHeight、getBalanceFactor、rotateLeft、rotateRight 这四个函数最好先单独测通，再组合进插入/删除流程。最容易被忽略的是高度更新时机和旋转后指针赋值——这两处出错，树看起来“平衡”了，其实子树高度全乱，下次插入立刻崩。
