Слияние 2 РАЗЛИЧНЫХ деревьев AVL - PullRequest
Новая
       13

Слияние 2 РАЗЛИЧНЫХ деревьев AVL

5 голосов
/ 16 декабря 2010

Предположим, у меня есть два дерева AVL и я знаю их соответствующие размеры.Однако я не знаю, есть ли повторяющиеся узлы или какая-либо другая информация.Какой самый эффективный способ объединить их в новое дерево AVL?Оригинальные деревья могут быть уничтожены.

Ответы [ 2 ]

5 голосов
/ 16 декабря 2010
  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 , который проверяет количество операций при объединении деревьев AVL размером 1, 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).

2 голосов
/ 16 декабря 2010

Это не самый эффективный, но, безусловно, самый простой в реализации. Вы можете просто добавить все узлы из второго дерева в первое. Вам не нужно удалять узлы из второго дерева. Тогда вы просто уничтожаете второе дерево и в результате получаете первое дерево. Сложность времени составляет O(N*log(N)).

...