avl节点合并不能直接拼接左右子树，因会破坏平衡因子导致|height(left)−height(right)|≥2；必须拼接后自底向上修复，每次旋转后显式更新当前及父节点高度，空节点高度定义为−1。
AVL节点合并为什么不能直接拼接左右子树
因为合并后大概率破坏平衡因子，height(left) - height(right) 可能突变为 ±2 甚至更大。直接把一棵树挂到另一棵树最右/最左节点上，等于在叶子层新增深度，但根节点的平衡因子不会自动重算——AVL 的约束是全局性的，必须从修改点向上逐层回溯调整。
合并两棵AVL树的正确前提条件
只有当 tree1 的最大键值 tree2 的最小键值 时，才能安全合并（即 tree1 全体小于 tree2）。否则无法保证二叉搜索树性质，更谈不上 AVL 平衡。实际中常用于归并两个已排序且不重叠的数据集，比如日志分片、区间索引合并。
- 若不满足该序关系，先做中序遍历+归并排序再重建，时间复杂度升至
O(n + m) - 允许其中一棵为空：直接返回另一棵，高度和平衡因子不变
- 不允许修改原树结构？需深拷贝节点，但
merge本身不负责内存管理，调用方需明确所有权语义
递归合并的核心步骤与旋转触发点
设 tree1 较小、tree2 较大，取 tree2 最左节点（即其最小值）作为新根，将 tree1 挂为其左子树，原 tree2 的左子树挂为新根的右子树——但这只是初步拼接。真正关键在自底向上回溯时检查每个祖先节点的 balanceFactor：
int balanceFactor = getHeight(node->left) - getHeight(node->right);
if (balanceFactor == 2) {
if (getHeight(node->left->left) >= getHeight(node->left->right))
rotateRight(node); // LL
else
rotateLeftRight(node); // LR
} else if (balanceFactor == -2) {
if (getHeight(node->right->right) >= getHeight(node->right->left))
rotateLeft(node); // RR
else
rotateRightLeft(node); // RL
}
-
getHeight()必须是O(1)查询，所以每个节点要缓存height字段，插入/删除/合并后及时更新 - 旋转后，被转节点及其直系父节点的高度几乎一定变化，必须重新计算（不能只靠递归返回值推导）
- 合并过程实际是“拼接 + 自底向上修复”，不是边递归边旋转；否则在中间层提前旋转可能让上层失去修复依据
容易被忽略的高度更新时机和边界case
很多人在 rotateRight 后只更新了旧根和新根的高度，却忘了：旋转改变了子树拓扑，其祖父节点的高度也可能变——但祖父节点不在当前递归栈帧里。所以必须在每次旋转返回后，显式调用 updateHeight() 更新当前节点，并在递归返回时再次更新父节点高度。
- 空节点高度定义为
-1（不是 0），否则叶子节点高度算成 0，其父节点高度会错算为 1 而非真实 1 - 合并后若某节点左右子树高度差为 0，仍要调用
updateHeight()，因为父层依赖这个值判断是否失衡 - 使用
std::shared_ptr管理节点时，旋转中交换指针不触发析构，但裸指针需确保无内存泄漏——合并算法本身不 new/delete，只重连指针
真正的难点不在旋转逻辑，而在高度字段像多米诺骨牌一样层层依赖；少一次 updateHeight()，就可能让某层误判平衡状态，后续所有修复都失效。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
