连接/合并/连接两个 AVL 树
假设我有两棵 AVL 树，并且第一棵树中的每个元素都小于第二棵树中的任何元素。将它们连接成一棵 AVL 树的最有效方法是什么？我到处搜索但没有发现任何有用的东西。
Assume that I have two AVL trees and that each element from the first tree is smaller then any element from the second tree. What is the most efficient way to concatenate them into one single AVL tree? I've searched everywhere but haven't found anything useful.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
假设你可以销毁输入树：
因此，整个操作可以在 O(log n) 内完成。
编辑：再想一想，在以下算法中推理旋转更容易。它也很可能更快：
假设右边的树更高（另一种情况是对称的）：
n为该元素。 O(log n)left高 1 个节点。令r为该节点。 O(log n)用值为 n 的新节点以及子树
left和r替换该节点。 O(1)通过构造，新节点是 AVL 平衡的，其子树 1 比
r高。相应地增加其父级的余额。 O(1)
Assuming you may destroy the input trees:
Thus, the entire operation can be performed in O(log n).
Edit: On second thought, it is easier to reason about the rotations in the following algorithm. It is also quite likely faster:
Assuming that the right tree is taller (the other case is symmetric):
lefttree (rotating and adjusting its computed height if necessary). Letnbe that element. O(log n)left. Letrbe that node. O(log n)replace that node with a new node with value n, and subtrees
leftandr. O(1)By construction, the new node is AVL-balanced, and its subtree 1 taller than
r.increment its parent's balance accordingly. O(1)
一种超简单的解决方案（无需对树之间的关系进行任何假设）是这样的：
两个步骤都是 O(n)。它的主要问题是它需要 O(n) 的额外空间。
One ultra simple solution (that works without any assumptions in the relations between the trees) is this:
Both steps are O(n). The major issue with it is that it takes O(n) extra space.
我读到的这个问题的最佳解决方案可以在这里找到< /a>.如果您纠正此问题，则与 meriton 的答案非常接近：
在算法的第三步向左导航直到到达子树与左树高度相同的节点。这并不总是可能的（参见反例图像）。执行此步骤的正确方法是两次查找高度为
h或h+1的子树，其中h是左树的高度The best solution I read to this problem can be found here. Is very close to meriton's answer if you correct this issue:
In the third step of the algorithm navigates left until you reach the node whose sub tree has the same height as the left tree. This is not always possible, (see counterexample image). The right way to do this step is two find for a subtree with height
horh+1wherehis the height of the left tree我怀疑您只需要步行一棵树（希望是较小的）并将其每个元素单独添加到另一棵树。 AVL 插入/删除操作并非旨在处理一次添加整个子树。
I suspect that you'll just have to walk one tree (hopefully the smaller) and individually add each of it's elements to the other tree. The AVL insert/delete operations are not designed to handle adding a whole subtree at a time.