合并2个不同的AVL树 [英] Merging 2 DIFFERENT AVL trees

问题描述

假设我有两个AVL树和，我知道他们各自的大小。然而，我不知道是否有重复的节点，或任何其他信息。什么是对他们在新的AVL树合并的最有效方法是什么？原来的树木可以被摧毁。

解决方案

1. 在转换你的树 T1 和 T2 来排序列表 L1 和 L2
2. 合并 L1 和 L2 成排序列表→
3. 转换→成树 T 试。

IIRC这一切的操作都是O（N），所以完全合并也将是O（N）。

如果你再$ P $的AVL树psentation可以有效地在它们之间迭代（例如，使用后指针，延续，懒惰的评价等），你应该能够做到这一点还没有中间的列表。

更新：作为编程语言似乎是C / C ++，你可以暂时滥用的AVL节点estructures是在一个链表节点，稍后再重新使用它们的输出树

更新2 ：@hwlau：这是O（N），我已经使用的Prolog自己的AVL实现可检查它的avl.pl 这个测试程序的 avl_test.pl 的，用于检查操作合并大小1，2，4，8，16的AVL树时的数目，...

这是输出：

 定时avl_merge，尺寸：128
％1,790推论，0.000 CPU为0.001秒（0％CPU，无限的嘴唇）
定时avl_merge，尺寸：256
％3,591推论，0.010 CPU 0.002秒（430％的CPU，359100嘴​​唇）
定时avl_merge，尺寸：512
％7176推论，0.030 CPU 0.028英寸秒（107％的CPU，239200嘴唇）
...
定时avl_merge，大小：32000
％451839推论，0.490 CPU在0.499秒（98％的CPU，922120嘴唇）
定时avl_merge，大小：64000
％903682推论，0.900 CPU在0.964秒（93％的CPU，1004091嘴唇）
定时avl_merge，大小：128000
％1807363推论，2.420 CPU在2.559秒（95％的CPU，746844嘴唇）
 

及其显而易见的推论/操作次数正比于合并的树木的大小和算法O（N）。这样的复杂性

Assume that I have two AVL trees and that I know their respective sizes. However, I don't know if there are repeated nodes, or any other information. What would be the most efficient way to merge them in a new AVL tree? The original trees can be destroyed.

解决方案

1. Convert your trees T1 and T2 to sorted lists L1 and L2
2. Merge L1 and L2 into a sorted list L
3. Convert L into a tree T again.

IIRC all this operations are O(N), so the full merge will also be O(N).

If your representation of AVL trees allows to iterate over them efficiently (for instance, using backpointers, continuations, lazy evaluation, etc.) you should be able to do it also without the intermediate lists.

Update: as your programming language seems to be C/C++ you could temporarily abuse your AVL node estructures to be nodes in a linked list and later reuse them again for the output tree.

Update 2: @hwlau: this is O(N), I have checked it using my own AVL implementation in Prolog available from avl.pl and this test program avl_test.pl that checks the number of operations when merging AVL trees of size 1, 2, 4, 8, 16, ...

This is the output:

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

这篇关于合并2个不同的AVL树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！