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

Question

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

Answer 1

1. 将树 T1 和 T2 转换为排序列表 L1 和 L2
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、2、4、8、16 的 AVL 树时检查操作数，...

这是输出:

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)。