avl树平衡因子应通过节点height字段实时计算，插入/删除后仅沿路径向上更新o(log n)个节点高度，旋转后必须重算涉及节点height并返回新根以维护bst性质。
平衡因子怎么实时算，别每次递归遍历整棵树
平衡因子本质是左右子树高度差，但每次调用 getBalanceFactor() 都走一遍递归求高，时间复杂度 O(n)，完全违背 AVL 树设计初衷。正确做法是让每个节点自己存 height 字段，在插入/删除后沿路径向上更新——只改从修改点到根的 O(log n) 个节点。
常见错误是把 height 当成只读缓存，或者在旋转后忘了重算新子树根的高度。必须保证：每次旋转结束时，参与旋转的三个节点（如 LL 旋转中的 A、B、C）的 height 全部重置，且按公式 height = 1 + max(left->height, right->height) 计算（空指针统一视为 -1）。
-
height字段类型建议用int，初始化为 0（单节点树高度为 0），空子树设为 -1 - 插入后回溯更新时，若某节点高度没变，可提前终止；变了才继续往上
- 不要在
getBalanceFactor()里现场算高度，直接返回left->height - right->height
四种旋转怎么写才不丢节点、不错顺序
LL、RR、LR、RL 旋转不是“交换指针”这么简单，核心是重构局部拓扑结构，且必须保证 BST 性质（左小右大）不变。最容易出错的是指针赋值顺序和父子关系重连——比如 LL 旋转中，原根 node 变成右子，但它的左子要挂到新根的右子上，而新根原来的右子得变成 node 的左子。
实操建议：所有旋转函数统一返回新的子树根节点（即旋转后的上层节点），调用处直接用返回值覆盖父节点对应指针。这样避免悬空指针，也方便递归回溯时接续。
- LL 旋转：新根是
node->left，node->left = newRoot->right必须在newRoot->right = node之前执行 - LR 旋转：先对
node->left做 RR，再对node做 LL；两次旋转都必须接收并使用返回值 - 旋转后务必重算涉及节点的
height：新根、原根、以及可能变动的孙子节点（如 LR 中中间节点）
插入后什么时候触发旋转，检查范围有多大
AVL 插入后，失衡只可能出现在从插入点向上到第一个平衡因子绝对值 >1 的祖先节点之间，且最多只需一次旋转（LL/RR）或一次双旋（LR/RL）。关键不是“查全树”，而是回溯路径上第一个失衡点——找到就旋，旋完该子树恢复平衡，其父节点高度可能变化，但平衡因子不会超限（数学可证）。
错误做法是插完遍历所有节点找 balance == 2/-2，或者在每个递归层都检查并尝试旋转。这既慢又容易重复旋转。
- 插入递归返回时，每层计算当前节点新
height和balance - 若
abs(balance) > 1，立即执行对应旋转，并返回旋转后的新根 - 旋转后该子树高度可能减 1，需通知父层重新评估——所以回溯不能中断，但旋转只做一次
删除后平衡逻辑比插入更麻烦，为什么
删除可能导致某路径上多个节点依次失衡，因为删掉一个叶子或单子节点后，父节点高度降 1，进而导致祖父节点平衡因子变化，甚至从 0 变成 ±2。而且删除后的旋转可能需要连续调整——比如一次 LL 旋转变矮了，父节点仍失衡，得继续旋。
实操上，删除后的回溯必须走到根，不能像插入那样找到第一个失衡点就停。但旋转策略仍是“遇到失衡就旋”，只是可能连旋多次。
- 删除后回溯时，即使当前节点 balance 在 [-1,1] 内，也要更新 height 并继续向上——因为父节点高度依赖它
- 某节点旋转后，其新高度可能比原来小 1，导致父节点 balance 改变，必须继续检查父层
- 注意：删除时若节点有两个子节点，用中序前驱/后继替换后，实际删除的是叶子或半叶子——那个被删的节点才是触发回溯的起点
平衡最难的部分不在旋转本身，而在高度维护的时机和传播方式：height 必须精确、及时、只更新必要节点；旋转必须返回新根并强制父指针重连；删除后的回溯不能偷懒跳过。这些细节错一点，树就 silently 不平衡了。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
