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

Question

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

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. 在右侧树中,向左导航,直到到达其子树最多比1高1的节点left.让我们r成为那个节点.O(log n)

4. 用值为n的新节点替换该节点,并使用子树left和r.O(1)
   通过构造,新节点是AVL平衡的,其子树1高于r.

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

6. 和插入后的重新平衡一样.O(log n)

Answer 2

一个超简单的解决方案(在树之间的关系中没有任何假设的情况下工作)是这样的:

1. 将两个树合并为一个合并数组(同时迭代两个树).
2. 从数组构建一个AVL树 - 将中间元素作为根,并递归地应用于左半部分和右半部分.

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