平衡因子必须通过左右子树高度差实时计算，即getbalancefactor()直接返回getheight(left)−getheight(right)；推荐节点中缓存height字段，并在插入/删除后自底向上更新路径上节点的高度，旋转时仅重算2~3个相关节点的height，空节点高度设为-1以确保叶子高度为0。
平衡因子怎么实时算，别存字段
平衡因子本质是左右子树高度差，实时计算比维护字段更可靠——只要子树高度能算准，平衡因子就不会错。关键在 height() 函数必须是 O(1) 查表或 O(h) 递归但带缓存，否则每次调 getBalanceFactor() 都触发全子树遍历，AVL 就慢成线性。
推荐做法：节点结构里存 height 字段，增删后自底向上更新。不是“不存”，而是“只在必要路径上更新”，避免冗余计算。
-
height初始设为 1（叶子节点） - 每次旋转后，只重算参与旋转的 2~3 个节点的
height，公式：node->height = 1 + std::max(getHeight(node->left), getHeight(node->right)) -
getBalanceFactor()直接返回getHeight(node->left) - getHeight(node->right)，不递归
四种旋转怎么写才不出错
LL、RR、LR、RL 旋转不是靠记忆口诀，而是看失衡节点和插入路径的相对方向。真正容易出错的是指针重连顺序和高度更新时机——先改指针再算高，或者漏更新某个节点的 height，都会导致后续判断失效。
以 LR 为例（左子节点右孩子插入导致失衡）：先对左子节点做 LL 旋转（即 rotateLeft(node->left)），再对当前节点做 RR 旋转（rotateRight(node)）。注意中间节点的父指针、子指针、高度三者必须同步修正。
- 所有旋转函数返回新根节点，调用方必须接收并重连父指针
- 旋转后，原根和新根的
height必须立刻重算；中间节点（如 LR 中的 left->right）也要重算 - 不要在旋转中直接修改
parent指针——除非你实现了双向链表；AVL 通常只依赖 child 指针，靠递归回溯自然修复父关系
插入后从下往上回溯时，什么情况下必须旋转
插入返回后，每层递归检查当前节点平衡因子：若为 2 或 -2，说明此处失衡，必须旋转。但注意——不能只看当前层，必须确保子树已平衡后再判断，否则可能多旋或漏旋。
- 插入递归返回时，先更新当前节点
height，再算getBalanceFactor() - 平衡因子为 2：说明左子树高，需看左子节点的平衡因子——若 ≥0 是 LL，若
- 平衡因子为 -2：说明右子树高，看右子节点的平衡因子——若 ≤0 是 RR，若 >0 是 RL
- 旋转后，该层子树恢复平衡，
height通常不变或减 1，无需继续向上检查（除非你实现的是严格自底向上修复，那要继续）
为什么删除比插入更容易破坏平衡
插入最多引发一次旋转，而删除可能造成多层连续失衡——因为删掉一个节点后，某条路径变短，上面多个祖先的平衡因子都可能从 ±1 变成 ±2。必须沿父指针一路回溯，每层都检查并修复。
常见坑：删除后没重置被删节点的父指针，导致回溯路径断裂；或者用“找中序后继替换”时，忘了对后继节点做同样回溯。
- 删除后，从被删节点的父节点开始向上回溯，直到根或某层未失衡为止
- 若某层旋转后高度变化（比如从 h→h−1），其父节点的
height和平衡因子也必须更新 - 使用
std::stack显式保存路径比依赖递归更可控，尤其在手动管理内存时不易栈溢出
实际写的时候，最常被忽略的是高度更新的边界：空节点 height 必须定义为 0，否则 max(0, 0) + 1 = 1 才对；还有旋转后忘记把新根的父指针置 nullptr（如果用了 parent 指针），会导致后续遍历进入死循环。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
