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

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

最佳答案

将树的T1和T2转换为排序列表L1和L2

将L1和L2合并到排序列表中L

再次将L转换为树T。

IIRC的所有这些操作均为O(N)，因此完全合并也将为O(N)。

如果您的AVL树表示形式允许有效地对其进行迭代(例如，使用反向指针，连续性，惰性评估等)，则无需中间列表，您也应该能够做到这一点。

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

更新2 :@hwlau:这是O(N)，我已经使用avl.pl中可用的Prolog中的我自己的AVL实现对其进行了检查，并且该测试程序avl_test.pl在合并大小为1、2的AVL树时检查了操作数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)

很明显，推理/运算的数量与合并树的大小成正比，因此算法的复杂度为O(N)。

关于c++ - 合并2个不同的AVL树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/4458489/