合并两个平衡二叉搜索树

在本教程中，我们将学习如何合并两个平衡二叉搜索树。

假设给出两个平衡二叉搜索树，例如 AVL 树或红黑树。创建一个函数，将提供的两个平衡 BST 组合成一个平衡二叉搜索树。假设第一棵树有 m 个元素，第二棵树有 n 个元素。我们的合并函数必须是 O(m+n) 时间复杂度。

在以下解决方案中，假设树的大小作为输入给出。如果未指定，我们可以通过遍历树来确定大小。

方法 1（将第一棵树的元素插入第二棵树）

将第一个 BST 的所有元素逐个插入到第二个 BST 中。尝试将元素插入自平衡 BST 需要 Logn 时间（参阅此链接），其中 n 是 BST 的大小。因此，此过程的时间复杂度为 Log(n) + Log(n+1)... Log(m+n-1)。此表达式的值将在 mLogn 和 mLog(m+n-1) 之间变化。作为优化，我们可以选择较小的树作为第一棵树。

方法 2（合并中序遍历）

• 对第一棵树进行中序遍历，并将结果保存在一个临时数组 arr1[] 中。此过程需要 O(m) 时间。
• 对第二棵树进行中序遍历，并将结果保存在另一个临时数组 arr2[] 中。此过程需要 O(n) 时间。
• 步骤 1 和 2 中形成的数组是排序数组。将两个排序数组合并成一个 m + n 数组。此过程需要 O(m+n) 时间。
• 使用此帖子中描述的技术，从合并后的数组创建一棵平衡树。此过程需要 O(m+n) 时间。

此方法的时间复杂度为 O(m+n)，优于方法 1。即使输入 BST 不平衡，此过程也需要 O(m+n) 时间。

此方法的实现如下所示。

C++ 程序

输出

Following is Inorder traversal of the merged tree 
10 30 60 90 100 110 130 400

C 语言程序

输出

Following is inorder1 traversal of the merged tree 
10 30 60 90 100 110 130 400

方法 3（基于 DLL 的原地合并）

• 为了原地合并树，我们可以使用双向链表。步骤如下。
• 原地将两个二叉搜索树转换为双向链表（此步骤请参考此帖子）。
• 合并两个排序链表。
• 使用步骤 2 合并后的链表生成一个平衡二叉搜索树。（有关此步骤的更多信息）

此方法的时间复杂度也是 O(m+n)，并且它进行原地转换。

C++ 程序

输出

The merged data is traversed tree in order as shown below 
10 30 60 90 100 110 130 400

时间复杂度为 O(N + M)，其中 N 和 M 是给定树中的节点数。

辅助空间：O(1)，因为总是存在额外的空间。