合并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),我使用我自己的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)

很明显,推理/操作的数量与合并树的大小成比例,因此算法O(N)的复杂性也是如此.