AVL树节点合并需满足高度差≤1且子树均为AVL树，三种策略为：一、根节点提升法（适用于高度差≤1，递归调整）；二、中序归并建树法（O(n+m)，严格平衡）；三、双旋转桥接法（插入桥接节点后旋转至平衡）。

一、理解AVL树节点合并的核心约束

在AVL树中执行节点合并操作时，不能简单地拼接两棵子树，必须确保合并后整棵树仍满足AVL性质：任意节点的左右子树高度差绝对值不超过1，且左右子树本身均为AVL树。合并通常发生在两个互不相交的AVL树之间，要求目标树所有键值严格小于源树所有键值。以下提供三种符合该约束的递归合并策略。

二、基于根节点提升的合并方法

该方法选取键值范围居中的树作为新根，将另一棵树作为其子树插入，并沿路径向上递归调整平衡因子。适用于两树高度差≤1的情形，可避免全局重构。

1、比较两棵AVL树T1和T2的高度h1与h2；

2、若h1 ≥ h2，则以T1的最右节点r为候选根，从T1中删除r并保留其左子树T1'；

3、将r的右指针指向T2，构造临时树r→left = T1'，r→right = T2；

4、从r开始向上回溯至T1原根，对路径上每个节点调用updateHeightAndBalance()函数更新高度与平衡因子；

5、对每个失衡节点执行对应旋转（LL/LR/RR/RL），旋转后继续向上检查父节点是否失衡。

三、基于中序遍历序列归并的合并方法

该方法先将两棵AVL树分别进行中序遍历得到有序数组，再归并为单一有序数组，最后按AVL建树规则（取中点为根）递归构建新树。虽时间复杂度为O(n+m)，但能严格保证结果为高度平衡的AVL树。

1、对T1执行中序遍历，将节点值依次存入vector arr1；

2、对T2执行中序遍历，将节点值依次存入vector arr2；

3、调用归并函数merge(arr1, arr2)生成升序vector merged；

4、定义递归函数buildAVL(const vector& v, int l, int r)，返回构建的子树根指针；

C++14

C++14 对 C++11 的修正与增强版本，适合旧系统维护和较老工具链兼容。

下载

5、在buildAVL中，若l > r则返回nullptr；否则取mid = (l + r) / 2，创建新节点val = v[mid]；

6、递归构建左子树：v[l..mid-1]，赋给新节点left；递归构建右子树：v[mid+1..r]，赋给新节点right；

7、每次返回前调用updateHeight(node)更新当前节点高度。

四、基于双旋转桥接的在线合并方法

该方法不破坏原有结构，通过构造一个“桥接节点”连接两树，并利用两次旋转快速恢复平衡。适用于T1最大键

1、创建新节点bridge，key = x，其中x满足max(T1)

2、设置bridge→left = T1，bridge→right = T2；

3、计算bridge左右子树高度差：diff = height(T1) - height(T2)；

4、若diff == 2，则对bridge执行rightRotate(bridge)；

5、若diff == -2，则对bridge执行leftRotate(bridge)；

6、旋转后检查新根的平衡因子，若仍为±2，则在对应子树内再次执行相同方向旋转直至平衡。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！