AVL树作为最早被提出的自平衡二叉搜索树，其插入、删除、旋转操作已经被讲得非常透彻，但涉及两棵树的合并时，很多资料要么语焉不详，要么给出的方案直接破坏了平衡性质。本文将以C++为实现语言，完整讲解AVL节点合并算法的递归逻辑，包括高度信息的维护、旋转时机的判断，并给出一份可以直接编译运行的完整源码。
一、合并AVL树的两种主流思路
第一种思路是遍历合并：把其中一棵树的所有节点逐个取出，调用普通的AVL插入函数插入到另一棵树中。这种写法最简单，代码复用度高，但缺点也很明显——如果被合并树的节点数为m，时间复杂度会达到O(m log(n+m))，对于追求性能的场合并不理想。
第二种思路是结构合并，也就是本文的主角。它利用了一个关键性质：AVL树的中序遍历结果是有序序列。如果树A的所有键值都小于树B的所有键值，可以想象在两棵树之间插入一个分隔节点，然后通过递归的方式把三个部分重新组装成一棵平衡树。这种做法在值域分离的情况下可以做到O(log n + log m)量级，效率远高于逐个插入。
当然，实际场景中两棵树的值域往往是交叉的。通用的解法是：选取一棵树的一个节点作为枢纽，用它把另一棵树拆分成左右两半，再递归合并各个部分。不过为了把重心放在平衡维护上，本文先实现值域分离版本，这个版本逻辑最清晰，也是理解更复杂变体的基础。
二、节点结构与高度维护的核心细节
实现之前先把地基打好。AVL树的每个节点除了键值和左右孩子指针，必须保存当前子树的高度。有人习惯存平衡因子，但直接存高度更省事：平衡因子可以由高度差实时算出，而高度又必须在每次结构变化后及时刷新。下面是节点定义：
struct AVLNode {
int key;
int height; // 以该节点为根的子树高度，空节点高度为0
AVLNode* left;
AVLNode* right;
AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
};
// 获取节点高度，空指针返回0，避免空引用判断散落各处
int getHeight(AVLNode* node) {
return node ? node->height : 0;
}
// 更新高度：取左右子树高度较大者加一
void updateHeight(AVLNode* node) {
if (node) {
int lh = getHeight(node->left);
int rh = getHeight(node->right);
node->height = (lh > rh ? lh : rh) + 1;
}
}
// 平衡因子 = 左子树高度 - 右子树高度
int getBalance(AVLNode* node) {
return node ? getHeight(node->left) - getHeight(node->right) : 0;
}这里有一个非常容易踩的坑：updateHeight的调用顺序。无论是插入还是旋转，都必须先更新孩子的高度，再更新父节点的高度，因为父节点的高度依赖于孩子的最新值。如果顺序写反，高度信息就会失真，后续的平衡判断全部失效，树会在无声中退化成普通二叉搜索树，查找性能悄悄下降却很难察觉。建议在写测试时随机插入大量数据后校验每个节点的平衡因子绝对值是否小于等于1，可以及时发现这类隐藏错误。
三、四种旋转操作与递归平衡修复
旋转是AVL树的灵魂。失衡只有四种形态：LL、RR、LR、RL。其中LL对应右旋，RR对应左旋，LR和RL则需要两次旋转。先看最基础的两个单旋实现：
// 右旋：处理LL型失衡
AVLNode* rotateRight(AVLNode* y) {
AVLNode* x = y->left;
AVLNode* T2 = x->right;
x->right = y; // x升为新根
y->left = T2; // x原来的右子树挂到y的左侧
updateHeight(y); // 注意顺序：先低处的y，再高处的x
updateHeight(x);
return x;
}
// 左旋：处理RR型失衡
AVLNode* rotateLeft(AVLNode* x) {
AVLNode* y = x->right;
AVLNode* T2 = y->left;
y->left = x;
x->right = T2;
updateHeight(x);
updateHeight(y);
return y;
}有了单旋，双旋就是组合调用：LR型先对左子树做左旋，变成LL型再整体右旋；RL型先对右子树做右旋，变成RR型再整体左旋。把这些旋转封装成一个统一的再平衡函数，递归的每一层返回之前调用它，就能保证任何路径上的失衡都被就地修复：
// 在节点node处检查并修复失衡，返回新的子树根
AVLNode* rebalance(AVLNode* node) {
updateHeight(node);
int balance = getBalance(node);
// LL型
if (balance > 1 && getBalance(node->left) >= 0)
return rotateRight(node);
// LR型
if (balance > 1 && getBalance(node->left) < 0) {
node->left = rotateLeft(node->left);
return rotateRight(node);
}
// RR型
if (balance < -1 && getBalance(node->right) <= 0)
return rotateLeft(node);
// RL型
if (balance < -1 && getBalance(node->right) > 0) {
node->right = rotateRight(node->right);
return rotateLeft(node);
}
return node; // 平衡正常，直接返回
}需要说明的是判断条件里对等于号的处理。在插入场景中，失衡节点的子节点平衡因子一般不会为0，但在删除和合并场景中，子节点平衡因子为0是可能的，此时单旋即可恢复平衡，这也是上面代码在LL分支写大于等于0、RR分支写小于等于0的原因。漏掉这个等号会导致某些情况下的失衡无法被正确修复。
四、合并算法的递归实现与完整源码
现在进入正题。值域分离情况下，树a的所有键小于树b的所有键，另有一个键值pivot介于两者之间，合并函数的目标是返回一棵包含三者所有节点且平衡的新树。递归的核心思想是：比较两棵树根的高度，把较高的那棵作为主体，将较矮的树与主体的一部分递归合并后挂到对应侧。具体来说，如果a的高度大于等于b，就把a的右子树与b、pivot继续合并，作为a的新右子树，最后对a做再平衡；反之则处理b的左子树。每一次递归，至少有一棵树的高度下降一层，因此递归深度是两树高度之和的量级。
#include <iostream>
#include <algorithm>
struct AVLNode {
int key;
int height;
AVLNode* left;
AVLNode* right;
AVLNode(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
};
int getHeight(AVLNode* n) { return n ? n->height : 0; }
void updateHeight(AVLNode* n) {
if (n) n->height = std::max(getHeight(n->left), getHeight(n->right)) + 1;
}
int getBalance(AVLNode* n) {
return n ? getHeight(n->left) - getHeight(n->right) : 0;
}
AVLNode* rotateRight(AVLNode* y) {
AVLNode* x = y->left;
y->left = x->right;
x->right = y;
updateHeight(y);
updateHeight(x);
return x;
}
AVLNode* rotateLeft(AVLNode* x) {
AVLNode* y = x->right;
x->right = y->left;
y->left = x;
updateHeight(x);
updateHeight(y);
return y;
}
AVLNode* rebalance(AVLNode* node) {
updateHeight(node);
int bf = getBalance(node);
if (bf > 1 && getBalance(node->left) >= 0)
return rotateRight(node);
if (bf > 1) {
node->left = rotateLeft(node->left);
return rotateRight(node);
}
if (bf < -1 && getBalance(node->right) <= 0)
return rotateLeft(node);
if (bf < -1) {
node->right = rotateRight(node->right);
return rotateLeft(node);
}
return node;
}
// 普通插入，用于构建测试数据
AVLNode* insert(AVLNode* node, int key) {
if (!node) return new AVLNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else
return node; // 忽略重复键
return rebalance(node);
}
// 合并：a中所有键 < pivot < b中所有键
AVLNode* mergeTrees(AVLNode* a, AVLNode* b, int pivot) {
if (!a) {
// 退化情况：直接把pivot插入b
return insert(b, pivot);
}
if (!b) {
return insert(a, pivot);
}
if (getHeight(a) >= getHeight(b)) {
// 以a为主，递归合并a的右子树
a->right = mergeTrees(a->right, b, pivot);
return rebalance(a);
} else {
// 以b为主，递归合并b的左子树
b->left = mergeTrees(a, b->left, pivot);
return rebalance(b);
}
}
// 中序遍历验证有序性
void inorder(AVLNode* node) {
if (!node) return;
inorder(node->left);
std::cout << node->key << " ";
inorder(node->right);
}
int main() {
AVLNode* a = nullptr;
AVLNode* b = nullptr;
for (int k = 2; k <= 20; k += 3) a = insert(a, k); // 2,5,8,11,14,17,20
for (int k = 23; k <= 40; k += 3) b = insert(b, k); // 23,26,29,32,35,38
AVLNode* merged = mergeTrees(a, b, 22);
inorder(merged); // 输出应为2 5 8 11 14 17 20 22 23 26 29 32 35 38
std::cout << std::endl;
return 0;
}注意mergeTrees里有一个逻辑细节：当a较高时，pivot比a中所有键都大，但比b中所有键都小，所以递归要往a的右侧走，把a的右子树与b在pivot分隔下继续合并；b较高时则对称地往b的左侧走。递归终止条件是某棵树为空，此时退化为一次普通插入。这个算法没有任何节点的新建或销毁，纯粹是指针的重新连接，所以合并操作不产生额外的内存分配开销。
五、复杂度分析与常见错误排查
时间复杂度方面，由于每层递归至少让一棵树下降一个高度，总递归深度不超过两棵树的高度之和，即O(ha + hb)，对平衡树而言就是O(log n + log m)，加上每层常数次的旋转，整体效率非常可观。对比逐节点插入的O(m log(n+m))，当两棵树规模相当时，结构合并的优势能达到数量级级别。
实践中最常见的错误有三个。第一是忘记在mergeTrees递归返回后调用rebalance，导致树最终失衡——建议每处递归调用后立刻接上再平衡。第二是前提条件被破坏：算法要求a的所有键严格小于pivot、pivot严格小于b的所有键，如果输入不满足，中序遍历结果就会乱序，且这种错误不会报错，只能靠遍历输出来发现。第三是旋转函数里updateHeight的调用顺序写反，造成高度缓存出现脏数据，这是最隐蔽的一类bug，强烈推荐写一个独立的校验函数，递归检查每个节点的高度是否等于子树高度最大值加一、平衡因子绝对值是否不超过1，在调试阶段反复调用。
最后补充一点扩展：如果两棵树的值域存在交叉，可以先用其中一棵树的根节点作为分割键，调用split操作把另一棵树按该键拆成两半，再分别与对应子树递归合并。split和merge是一对对偶操作，掌握了本文的merge实现，再去理解split乃至基于两者构建的平衡树高级应用，都会顺畅许多。