Слияние n деревьев AVL

Если у вас есть k разных деревьев, то вам нужно сделать всего (k - 1) слияний, чтобы собрать их вместе в одно дерево. Так что вопрос в том, сколько времени займет каждое слияние.

Предположим, вы принимаете стратегию, согласно которой вы всегда объединяете два самых маленьких дерева вместе в любой момент времени. Если у вас есть m доступных деревьев, когда вы делаете это, то второе по величине дерево будет доминировать во время выполнения слияния. Этот размер не превышает (n - 1) / (k - 1), что происходит, когда наименьшее дерево имеет только один элемент, а все остальные деревья содержат все элементы. Это означает, что если вы сделаете k слияний, стоимость будет

N - 1   N - 1   N - 1         N - 1
----- + ----- + ----- + ... + -----
K - 1   K - 2   K - 3           1

Но это (n - 1)H(k - 1), где H(k-1) - это (k-1)st гармонический номер. Тогда все это выражение равно O(n log k), поэтому общая работа, проделанная при слиянии, равна O (n log k).

Однако вдобавок ко всему у вас должен быть простой способ найти два самых маленьких дерева в каждой точке. Это можно сделать с помощью очереди приоритетов, в которой деревья хранятся в порядке убывания размера. У вас будет k - 1 раундов выполнения двух исключений из дерева, за которыми следует одна постановка в очередь, поэтому общее время для всех операций с очередью с приоритетом равно O (k log k). Это также O(n log k), поэтому общее время выполнения алгоритма равно O(n log k).

Я почти уверен, что вы не можете добиться большего, чем это, потому что вы можете начать с каждого из n узлов в их собственном дереве AVL (k = n). Если бы вы могли выполнить слияние быстрее, чем (n log n), то вы могли бы сортировать быстрее, чем (n log n), используя только сравнения, построив дерево AVL, сформированное путем слияния всех меньших деревьев, а затем выполняя неупорядоченный обход за O (n) время сортировки лучше, чем (n log n), что известно как невозможное.

Надеюсь это поможет!