avl树合并不能直接拼接因高度差可达2而破坏平衡，需提取t1最大或t2最小节点作根并递归合并；分裂应自顶向下递归避免o(n)遍历；旋转仅需更新三个节点高度；插入/删除后须沿路径回溯检查并修复失衡。
AVL 树节点合并：为什么不能直接拼接左右子树
直接把两棵 AVL 树 T1 和 T2 的根连到一个新节点下，大概率破坏高度平衡——哪怕 T1 和 T2 各自平衡，它们的高度差可能达到 2，导致新根的平衡因子为 ±2，违反 AVL 定义。合并必须保证结果仍满足 |height(left) − height(right)| ≤ 1。
典型做法是「提取 T1 的最大节点」或「提取 T2 的最小节点」作为合并根，再递归合并剩余部分。这本质是将合并转为插入：以中间值为 pivot，把 T1 中所有 ≤ pivot 的部分、pivot 自身、T2 中所有 > pivot 的部分重新组装。
- 若
T1高度比T2高 2 以上，必须从T1取最大节点（避免后续多次旋转） - 提取操作本身需维护 AVL 性质：删除最大节点后要回溯调整平衡因子并触发旋转
- 合并时间复杂度为 O(|h₁ − h₂|)，不是 O(1)；最坏情况需遍历较高树的高度
AVL 树节点分裂：按 key 分割时如何避免重复遍历
分裂（split）指给定 key k，将 AVL 树拆成两棵：左树含所有 ≤ k 的节点，右树含所有 > k 的节点。常见错误是先中序遍历收集全部节点再分组重建——这丢了 AVL 的结构优势，且时间退化为 O(n)。
正确做法是自顶向下递归分裂，在每个节点根据 k 与当前节点 key 的关系决定走向，并动态构建左右结果子树：
- 若
k key，则当前节点及其右子树全归右结果，递归分裂左子树得到 (left_left, left_right)，最终左结果 = left_left，右结果 = merge(left_right, node, right_subtree) - 若
k >= node->key，对称处理，注意 merge 必须复用前述安全合并逻辑 - 每次递归调用都可能触发一次合并，因此 split 实际是 O(h) 次 O(h) 合并，总复杂度 O(h²)，h 为原树高
旋转后高度更新：为什么只改三个节点就够了
LL、RR、LR、RL 四种旋转中，只有参与旋转的三个节点（原根、子节点、孙子节点）的高度需要重算；其余节点高度不变，因为它们的子树结构未被改动。错误实现常遍历整条路径回溯更新高度，白白增加 O(h) 开销。
以 RR 旋转为例（右子节点上提）：
- 设原根为
oldRoot，右子为newRoot - 旋转后，
newRoot的右子树不变，其新左子树是oldRoot（原oldRoot的右子已被切走） - 只需按顺序更新：
updateHeight(oldRoot)→updateHeight(newRoot)→ 若newRoot原有父节点，再更新它（但这是上层调用的事） -
updateHeight就是node->height = 1 + max(height(node->left), height(node->right))
insert / erase 后的平衡维护：旋转不是终点，而是中间状态
单次插入或删除最多引发一次失衡，但修复该失衡（一次旋转）后，祖先节点仍可能失衡——因为旋转改变了子树高度，影响了更高层节点的平衡因子。必须沿插入/删除路径向上回溯检查，直到根或某层平衡为止。
- 回溯时不要盲目旋转：先计算当前节点平衡因子，仅当为 ±2 才触发对应旋转
- 删除场景更危险：即使旋转恢复了当前层平衡，其父节点高度可能减少 1，导致父节点失衡，必须继续向上检查
- 常见漏点：在递归 insert 函数中，忘记在递归调用后插入
rebalance(current)，或把 rebalance 放在递归前 - 建议在节点结构里缓存
height字段，并在每次指针修改（如left = ...）后立刻调用updateHeight，而非延迟计算
高度维护真正难的不是旋转逻辑，而是确保每一处指针变更都同步更新高度，且回溯范围不遗漏也不过度——这两点出错，树会悄无声息地变“歪”。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
