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

2021-12-22 00:00:00 algorithm data-structures c c++ avl-tree

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

Assume that I have two AVL trees and that each element from the first tree is smaller then any element from the second tree. What is the most efficient way to concatenate them into one single AVL tree? I've searched everywhere but haven't found anything useful.

推荐答案

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

Assuming you may destroy the input trees:

  1. 移除左树最右边的元素，并用它来构造一个新的根节点，其左孩子是左树，右孩子是右树:O(log n)
  2. 确定并设置该节点的平衡因子:O(log n).在(临时)违反不变量的情况下，平衡因子可能超出范围 {-1, 0, 1}
  3. 旋转使平衡因子回到范围内:O(log n) 旋转:O(log n)

因此，整个操作可以在 O(log n) 中执行.

Thus, the entire operation can be performed in O(log n).

再想一想，在以下算法中更容易推理旋转.它也很可能更快:

On second thought, it is easier to reason about the rotations in the following algorithm. It is also quite likely faster:

  1. 确定两棵树的高度: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 高.

  1. Determine the height of both trees: O(log n).
    Assuming that the right tree is taller (the other case is symmetric):
  2. remove the rightmost element from the left tree (rotating and adjusting its computed height if necessary). Let n be that element. O(log n)
  3. In the right tree, navigate left until you reach a node whose subtree is at most one 1 taller than left. Let r be that node. O(log n)

  4. replace that node with a new node with value n, and subtrees left and r. O(1)
    By construction, the new node is AVL-balanced, and its subtree 1 taller than r.

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

increment its parent's balance accordingly. O(1)

相关文章