c++ - 合并 2 个不同的 AVL 树

Question

假设我有两棵 AVL 树并且我知道它们各自的大小。但是，我不知道是否有重复的节点，或任何其他信息。将它们合并到新的 AVL 树中的最有效方法是什么？原来的树可以被破坏。

Answer 1

1. 将你的树转换为排序列表T1和T2L1L2
2. 合并L1并L2进入排序列表L
3. 再次L变成一棵树T。

IIRC 所有这些操作都是 O(N)，所以完全合并也是 O(N)。

如果您对 AVL 树的表示允许有效地迭代它们（例如，使用反向指针、延续、惰性求值等），那么您应该也可以在没有中间列表的情况下做到这一点。

更新：由于您的编程语言似乎是 C/C++，您可以暂时滥用您的 AVL 节点结构作为链表中的节点，然后再次将它们重用于输出树。

更新 2：@hwlau：这是 O(N)，我已经使用我自己在 Prolog 中的 AVL 实现进行了检查，该程序可从avl.pl和这个测试程序avl_test.pl中检查合并大小为 1 的 AVL 树时的操作数， 2, 4, 8, 16, ...

这是输出：

timing avl_merge, size: 128
% 1,790 inferences, 0.000 CPU in 0.001 seconds (0% CPU, Infinite Lips)
timing avl_merge, size: 256
% 3,591 inferences, 0.010 CPU in 0.002 seconds (430% CPU, 359100 Lips)
timing avl_merge, size: 512
% 7,176 inferences, 0.030 CPU in 0.028 seconds (107% CPU, 239200 Lips)
...
timing avl_merge, size: 32000
% 451,839 inferences, 0.490 CPU in 0.499 seconds (98% CPU, 922120 Lips)
timing avl_merge, size: 64000
% 903,682 inferences, 0.900 CPU in 0.964 seconds (93% CPU, 1004091 Lips)
timing avl_merge, size: 128000
% 1,807,363 inferences, 2.420 CPU in 2.559 seconds (95% CPU, 746844 Lips)

Its obvious that the number of inferences/operations is proportional to the size of the merged trees and so the complexity of the algorithm O(N).

Answer 2

它不是最有效的，但绝对是最容易实现的。您可以将第二棵树中的所有节点添加到第一棵树。您不需要从第二棵树中删除节点。然后，您只需破坏第二棵树并因此获得第一棵树。时间复杂度为O(N*log(N))。