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

Question

假设我有两个AVL树，并且第一个树中的每个元素都比第二个树中的任何元素都小。最有效的方法是将它们连接成一个单独的AVL树，但我已经搜索了所有地方，都没有找到有用的信息。

- liviucmg

---

谢谢您的问题，但我认为它更适合于：https://cs.stackexchange.com/ - ChaosPredictor

Answer 1

假设您可以破坏输入的树：

1. 从左树中删除最右边的元素，并使用它构建一个新的根节点，其左子节点是左树，右子节点是右树：O（log n）
2. 确定并设置该节点的平衡因子：O（log n）。在（临时）违反不变式的情况下，平衡因子可能超出范围{-1,0,1}
3. 旋转以将平衡因子恢复到范围内：O（log n）旋转：O（log n）

因此，整个操作可以在O（log n）中执行。

编辑：经过再次考虑，以下算法中旋转的推理更容易。这也很可能更快：

1. 确定两个树的高度：O（log n）。 假设右树更高（另一种情况对称）：
2. 从左侧树中删除最右侧的元素（如果需要旋转并调整其计算的高度）。让n成为那个元素。O（log n）
3. 在右树中向左导航，直到到达其子树最多比左侧小1。让r成为那个节点。O（log n）

4. 用值n和子树left和r替换该节点。O(1)
   通过构造，新节点是AVL平衡的，其子树比r高1。

5. 相应地增加其父项的平衡。O(1)

6. 然后像插入后一样重新平衡。O（log n）

- meriton

---

你确定吗？（也许你是对的，但我只是好奇。）假设左边的树比右边的树小得多，即浅得多。为什么O(log n)次旋转可以恢复AVL属性？如何决定在哪里进行旋转？ - Dale Hagglund

好的观点。我发现证明另一个算法更容易（参见我的编辑答案）。 - meriton

我需要一些时间来理解你所说的“用（left，n，r）替换该节点”的意思。建议重新表述。 - ripper234

我认为你的回答有一个错误的细节。在你上一个算法的第三步中，你说要向左导航，直到到达其子树与左子树高度相同的节点。让r是该节点。这并非总是可能的，这里提供反例。这一步正确的做法是找到一个子树，其高度为左子树的高度h或h+1，其中h是左子树的高度。 - rareyesdev

是的，当然；否则生成的树将不能保持AVL平衡。我已经编辑过了以澄清。在此期间，我还整合了@agarwaen的反馈意见。 - meriton

Answer 2

一种非常简单的解决方案（无需假定树之间的关系）如下：

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

这两个步骤都是O（n）级别的。它的主要问题在于需要额外的O（n）空间。

- ripper234

---

第一步不是 O(n log(n)) 吗？ - technical_difficulty

主要问题是它的时间复杂度不是对数级别的。 - enedil

Answer 3

我读到的解决此问题的最佳方案可以在这里找到。如果您更正了此问题，它非常接近meriton的答案：

在算法的第三步向左导航，直到到达其子树与左侧树具有相同高度的节点。这并非总是可能的（请参见反例图像）。完成此步骤的正确方法是查找高度为h或h+1的子树，其中h是左子树的高度。

- rareyesdev

Answer 4

我猜你只能遍历其中一棵树（希望是较小的那棵），并逐个将其元素添加到另一棵树中。AVL插入/删除操作不适用于一次添加整个子树。

- Dale Hagglund

---

我有一种感觉它可以使用线性方法完成。使用天真的方法需要 O(n log n) 的时间。 - avakar

这需要O(n log n)的时间复杂度 -> 比meriton的解决方案慢得多。 - inspectorG4dget

@meriton的解决方案确实非常好，但它假设(a)一个树中的每个节点都严格小于另一个树中的每个节点，(b)您可以访问原始avl树数据结构，以及(c)可以直接在树节点上执行旋转。如果(a)不成立，或者低级别的树操作对您不可用（最有可能是因为您正在使用avl库），那么您可能需要回退到将较小树中的每个节点插入到较大树中。 - Dale Hagglund