串联/合并/加入两个AVL树 [英] Concatenating/Merging/Joining two AVL trees

问题描述

假设我有两个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.

推荐答案

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

Assuming you may destroy the input trees:

1. 删除对左树最右边的元素，并用它来建立一个新的根节点，其左孩子是左树，它的右子是正确的树：O（log n）的
2. 确定和设置该节点的平衡因子：O（log n）的。在（临时）违反不变，余量因子可以是范围外{-1，0，1}
3. 旋转，以获得平衡因子放回范围：O（log n）的旋转：O（log n）的

因此​​，整个操作可以为O执行（log n）的。

Thus, the entire operation can be performed in O(log n).

编辑：关于第二个想法，很容易推理在以下算法的旋转。它也很可能更快：

On second thought, it is easier to reason about the rotations in the following algorithm. It is also quite likely faster:

1. 确定两个树的高度：O（log n）的。假设正确的树高（另一种情况是对称的）。
2. 从左边的树中删除最右边的元素。让N是该元素。 （如果有必要调整其计算的高度）：O（log n）的
3. 在右侧树中，导航离开，直到到达其子具有相同的高度左树的节点。设r是该节点。 O（log n）的
4. 替换（左，N，R），该节点。通过构造，此节点是除R 1更高。相应地增加其母公司的资产负债。 O（1）
5. 重新平衡，就像您在插入后。 O（log n）的

这篇关于串联/合并/加入两个AVL树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！