连接/合并/连接两个 AVL 树

Question

假设我有两棵 AVL 树，并且第一棵树中的每个元素都小于第二棵树中的任何元素。将它们连接成一棵 AVL 树的最有效方法是什么？我到处搜索但没有发现任何有用的东西。

Answer 1

假设您可能会破坏输入树：

1. 删除左树最右边的元素，并用它构造一个新的根节点，其左子节点是左树，右子节点是右树：O(logn)
2. 确定并设置该节点的平衡因子：O(log n)。在（暂时）违反不变量的情况下，平衡因子可能超出范围 {-1, 0, 1}
3. 旋转以使平衡系数回到范围内：O(log n) 次旋转：O(logn)

因此，整个操作可以在 O(log n) 内完成。

编辑：再想一想，在以下算法中更容易推理出旋转。它也很可能更快：

1. 确定两棵树的高度：O(log n)。
   假设右边的树更高（另一种情况是对称的）：
2. 删除最右边的元素 left 树（如有必要，旋转并调整其计算的高度）。让 n 是那个元素。O(logn)
3. 在右侧树中，向左导航，直到到达子树最多比以下高 1 的节点： left. 。让 r 是那个节点。O(logn)

4. 用值为 n 的新节点和子树替换该节点 left 和 r. 。复杂度(1)
   通过构造，新节点是AVL平衡的，并且它的子树1比 r.

5. 相应地增加其父级的余额。复杂度(1)

6. 并像插入后一样重新平衡。O(logn)

Answer 2

一种超级简单的解决方案（无需对树之间的关系进行任何假设即可工作）是这样的：

1. 将两棵树合并排序到一个合并数组中（同时迭代两棵树）。
2. 从数组构建一棵 AVL 树 - 将中间元素作为根，并递归地应用于左半部分和右半部分。

两个步骤都是 O(n)。它的主要问题是它需要 O(n) 的额外空间。

Answer 3

我读到的这个问题的最佳解决方案可以找到 这里. 。非常接近 梅顿如果您纠正此问题，则答案是：

在算法的第三步中 向左导航，直到到达子树与左树高度相同的节点. 。这并不总是可能的（参见反例图像）。执行此步骤的正确方法是两次查找具有高度的子树 h 或者 h+1 在哪里 h 是左树的高度

Answer 4

我怀疑，你只需要步行一棵树（希望较小）和单独添加每个它的元素，其他的树。的AVL插入/删除操作没有被设计成处理在每次添加一个整个子树。