连接/合并/连接两个AVL树
假设我有两个AVL树,并且第一个树中的每个元素都小于第二个树中的任何元素。 将它们连接成一个单独的AVL树的最有效方法是什么? 我到处搜索,但没有找到任何有用的东西。
假设你可能会破坏输入树:
- 删除左侧树的最右边元素,并使用它构造一个新的根节点,其左子节点是左侧树,右侧子节点是右侧树:O(log n)
- 确定并设置该节点的平衡因子:O(log n)。 在(临时)违反不变量时,平衡因子可能超出范围{-1,0,1}
- 旋转以使平衡系数回到范围:O(log n)旋转:O(log n)
因此,整个操作可以在O(log n)中执行。
编辑:第二个想法,在下面的算法中更容易推理旋转。 它也可能更快:
- 确定两棵树的高度:O(log n)。
假设正确的树更高(另一种情况是对称的): - 从
left
树中删除最右边的元素(必要时旋转并调整其计算高度)。 设n
是那个元素。 O(log n) - 在右侧树中,向左导航,直到到达其子树最多比
left
高1的节点。 设r
为该节点。 O(log n) -
用值为n的新节点替换该节点,并将子树和
r
替换。 O(1)
通过构造,新节点是AVL平衡的,其子树1比r
高。 -
相应地增加其父母的余额。 O(1)
- 和插入后的重新平衡。 O(log n)
一个超简单的解决方案(在树之间的关系中没有任何假设的情况下工作)是这样的:
- 将两个树合并为一个合并的数组(同时迭代两个树)。
- 从数组构建一个AVL树 – 将中间元素作为根,并递归地应用于左半部分和右半部分。
两个步骤都是O(n)。 它的主要问题是需要额外的O(n)空间。
我在这里可以找到解决这个问题的最佳解决方案。 如果你纠正这个问题,非常接近meriton的答案:
在算法的第三步中, 向左导航,直到到达其子树与左树具有相同高度的节点 。 这并不总是可行的(参见反例图像)。 执行此步骤的正确方法是找到高度为h
或h+1
的子树,其中h
是左树的高度
我怀疑你只需要走一棵树(希望更小),然后将每个树的元素分别添加到另一棵树上。 AVL插入/删除操作不是为处理一次添加整个子树而设计的。