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

Question

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

原文由 liviucmg 发布，翻译遵循 CC BY-SA 4.0 许可协议

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. 从 left 树中删除最右边的元素（必要时旋转并调整其计算高度）。让 n 成为那个元素。 O(log n) 3. 在右树中，向左导航，直到您到达一个节点，其子树最多比 left 高 1。让 r 成为那个节点。 O(log n) 4. 将该节点替换为值为 n 的新节点，以及子树 left 和 r 。 O(1)

通过构造，新节点是 AVL 平衡的，其子树 1 高于 r 。

1. 相应地增加其父母的余额。 O(1)

2. 并像插入后一样重新平衡。 O(log n)

原文由 meriton 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

我怀疑你只需要走一棵树（希望更小），然后将它的每个元素单独添加到另一棵树。 AVL 插入/删除操作并非旨在一次处理添加整个子树。

原文由 Dale Hagglund 发布，翻译遵循 CC BY-SA 2.5 许可协议