合并两棵平衡二叉搜索树

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

假设给出了两个平衡的二叉搜索树，例如AVL或红黑树。创建一个函数，将两个平衡的bst组合到平衡的二叉搜索树中。假设第一棵树有m个元素，第二棵有n个元素。归并函数必须是O(m+n)时间。

树的大小被假定为下列解的输入。如果没有通过遍历树来指定大小，则可以确定大小。

方法一(将第一个树元素插入到第二个树中):

将第一个BST的所有元素逐个插入到第二个BST中。尝试将一个元素插入到一个自平衡BST中需要Logn时间(参见此)，其中n是BST的大小。因此，该过程的时间复杂度为Log(n) + Log(n+1)…日志(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++程序:

输出:

下面是合并树的顺序遍历10 30 60 90 100 110 130 400

C程序:

输出:

下面是合并树10 30 60 90 100 110 130 400的inorder1遍历

方法三(基于dll的就地合并):

• 要合并树，我们可以使用双链表。具体步骤如下。
• 然后，将两个二叉搜索树转换为一个双链表(请参阅这篇文章了解这一步)。
• 合并两个排序的链表。
• 使用步骤2中合并的列表生成平衡二叉搜索树。(有关此步骤的更多信息)

该方法的时间复杂度也是O(m+n)，并且是就地转换。

c++程序:

输出:

合并后的数据按照10 30 60 90 100 110 130 400的顺序进行树状遍历

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

辅助空间: O(1)，因为总有多余的空间。