avl树旋转必须严格按ll、lr、rr、rl四种失衡类型处理，依据balancefactor和插入路径选择对应旋转；高度更新需自底向上仅重算2–3个节点；getbalance须判空且空节点高度为−1；插入后须逐层rebalance并更新父指针。
AVL 节点旋转必须区分四种失衡类型，不能只靠“左旋右旋”字面理解
AVL 插入后是否失衡、该用哪种旋转，完全取决于 balanceFactor（左子树高度 − 右子树高度）和插入路径的走向。常见错误是看到“左子树高”就无脑左旋——实际要先判断是“LL”还是“LR”型：若新节点插在左子节点的左子树（node->left->left），才用右旋；若插在左子节点的右子树（node->left->right），必须先对左子节点左旋，再对当前节点右旋。
同理，“RR”与“RL”也需严格对应：
-
balanceFactor == 2 && getBalance(node->left) >= 0→ LL，单次右旋rotateRight balanceFactor == 2 && getBalance(node->left) → LR，先 <code>rotateLeft(node->left)，再rotateRight(node)balanceFactor == -2 && getBalance(node->right) → RR，单次左旋 <code>rotateLeft-
balanceFactor == -2 && getBalance(node->right) > 0→ RL，先rotateRight(node->right)，再rotateLeft(node)
高度更新必须自底向上，且每次旋转后仅重算涉及的 2–3 个节点
很多人在 insert 后从根开始递归更新所有节点高度，这是 O(n) 的浪费。正确做法是在递归回溯时，每层只调用一次 updateHeight(node)，且仅对当前节点及其直系子节点重新计算——因为只有它们的高度可能变化。旋转操作本身也会改变局部拓扑，所以 rotateLeft 和 rotateRight 内部必须立即更新参与旋转的两个节点高度，例如：
Node* rotateLeft(Node* x) {
Node* y = x->right;
x->right = y->left;
y->left = x;
updateHeight(x); // 先更新子节点（原x）
updateHeight(y); // 再更新新父节点（y）
return y;
}
漏掉其中任一 updateHeight，后续 getBalance 就会返回错误值，导致下一次旋转判断失效。
getBalance 实现必须防御空指针，且高度差计算不能硬编码 ±1
getBalance(Node* n) 常见写法是 height(n->left) - height(n->right)，但若 n 为 nullptr，直接访问 n->left 会崩溃。必须先判空：
int getBalance(Node* n) {
if (!n) return 0;
return height(n->left) - height(n->right);
}
同时，height 函数也要统一定义空节点高度为 -1（不是 0），否则平衡因子范围会偏移，导致 LL/RR 判断阈值失效。标准 AVL 定义中，空树高度为 -1，单节点树高度为 0，这样 balanceFactor 的合法范围才是 [-1, 1]，失衡阈值才是 ±2。
insert 后的平衡修复必须在递归返回路径上逐层检查，不能只修第一次失衡点
插入可能引发多层失衡。例如在很深的叶子插入后，从叶子向上回溯，可能连续多个节点 balanceFactor 超出 [-1, 1]。常见错误是修复完某一层后就提前返回，忽略上层仍失衡。正确逻辑是：每次递归返回后，都对当前节点调用 rebalance，并用其返回值更新父节点指针（因为旋转会换根）：
Node* insert(Node* node, int key) {
if (!node) return new Node(key);
if (key key) node->left = insert(node->left, key);
else if (key > node->key) node->right = insert(node->right, key);
else return node; // duplicate
<pre class="brush:php;toolbar:false;">updateHeight(node);
return rebalance(node); // 必须返回，因为旋转后根可能变}
这里 rebalance(node) 返回的是调整后的子树新根，不接住这个返回值，父节点的左右指针就会指向旧节点，树结构断裂。
真正难的不是写出四种旋转，而是让它们在递归插入/删除中被精确触发、高度被精准维护、空指针和边界条件不崩——这些细节一旦错一处，整棵树会在某个特定插入序列下悄然退化成链表，而你还以为它平衡着。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
