假设我有两棵 AVL 树,并且第一棵树中的每个元素都小于第二棵树中的任何元素。将它们连接成一棵 AVL 树的最有效方法是什么?我到处搜索,但没有发现任何有用的东西。
原文由 liviucmg 发布,翻译遵循 CC BY-SA 4.0 许可协议
我怀疑你只需要走一棵树(希望更小),然后将它的每个元素单独添加到另一棵树。 AVL 插入/删除操作并非旨在一次处理添加整个子树。
原文由 Dale Hagglund 发布,翻译遵循 CC BY-SA 2.5 许可协议
3 回答2k 阅读✓ 已解决
2 回答3.9k 阅读✓ 已解决
2 回答3.2k 阅读✓ 已解决
1 回答3.2k 阅读✓ 已解决
1 回答2.7k 阅读✓ 已解决
3 回答3.4k 阅读
1 回答3.3k 阅读
假设您可能会破坏输入树:
因此,整个操作可以在 O(log n) 中执行。
编辑:再想一想,在以下算法中更容易推理旋转。它也很可能更快:
假设右树更高(另一种情况是对称的): 2. 从
left
树中删除最右边的元素(必要时旋转并调整其计算高度)。让n
成为那个元素。 O(log n) 3. 在右树中,向左导航,直到您到达一个节点,其子树最多比left
高 1。让r
成为那个节点。 O(log n) 4. 将该节点替换为值为 n 的新节点,以及子树left
和r
。 O(1)通过构造,新节点是 AVL 平衡的,其子树 1 高于
r
。相应地增加其父母的余额。 O(1)
并像插入后一样重新平衡。 O(log n)