假设我有两棵 AVL 树,并且第一棵树中的每个元素都小于第二棵树中的任何元素。将它们连接成一棵 AVL 树的最有效方法是什么?我到处搜索,但没有发现任何有用的东西。
问问题
20227 次
4 回答
32
假设您可能会破坏输入树:
- 删除左树最右边的元素,并用它构造一个新的根节点,其左孩子为左树,其右孩子为右树: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) - 在右树中,向左导航,直到到达其子树最多比 高 1 的节点
left
。让r
成为那个节点。O(log n) 将该节点替换为值为 n 的新节点,以及子树
left
和r
. O(1)
通过构造,新节点是 AVL 平衡的,其子树 1 高于r
.相应地增加其父母的余额。O(1)
- 并像插入后一样重新平衡。O(log n)
于 2010-01-10T14:50:20.467 回答
4
一个超简单的解决方案(无需对树之间的关系进行任何假设即可工作)是:
- 将两棵树合并到一个合并数组中(同时迭代两棵树)。
- 从数组构建 AVL 树 - 将中间元素作为根,并递归地应用于左右两半。
这两个步骤都是 O(n)。它的主要问题是它需要 O(n) 额外的空间。
于 2011-01-17T21:15:01.690 回答
3
我读到的这个问题的最佳解决方案可以在这里找到。如果您更正此问题,则非常接近Meriton的答案:
在算法的第三步中,向左导航,直到您到达其子树与左树具有相同高度的节点。这并不总是可能的,(参见反例图像)。执行此步骤的正确方法是两次查找具有高度的子树h
或左树的高度h+1
在哪里h
于 2014-10-29T18:29:12.320 回答
0
我怀疑你只需要走一棵树(希望更小),然后将它的每个元素单独添加到另一棵树。AVL 插入/删除操作并非旨在一次处理添加整个子树。
于 2010-01-10T14:12:53.040 回答