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

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

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

  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的新节点替换该节点,并将子树和r替换。 O(1)
    通过构造,新节点是AVL平衡的,其子树1比r高。

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

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

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

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

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

我在这里可以找到解决这个问题的最佳解决方案。 如果你纠正这个问题,非常接近meriton的答案:

在算法的第三步中, 向左导航,直到到达其子树与左树具有相同高度的节点 。 这并不总是可行的(参见反例图像)。 执行此步骤的正确方法是找到高度为hh+1的子树,其中h是左树的高度 反

我怀疑你只需要走一棵树(希望更小),然后将每个树的元素分别添加到另一棵树上。 AVL插入/删除操作不是为处理一次添加整个子树而设计的。