Алгоритм объединения двух деревьев AVL за O (logn) время - PullRequest
Новая
       68

Алгоритм объединения двух деревьев AVL за O (logn) время

1 голос
/ 04 апреля 2020

Итак, я пытаюсь выяснить алгоритм объединения двух деревьев AVL за O (logn), где n - общее число целых чисел в обоих деревьях и также нечетно. В этой задаче целые числа в деревьях отличаются друг от друга. Кроме того, каждый узел деревьев хранит размер поддерева, укорененного в нем. Я думал о добавлении элементов меньшего дерева в большее, но я не знал, как go доказать, что это займет O (logn) время. У кого-нибудь есть какие-либо предложения относительно того, как я мог бы go об этом?

1 Ответ

0 голосов
/ 04 апреля 2020

Это невозможно.

Подтверждение : Предположим, у вас есть алгоритм для объединения двух деревьев поиска AVL в O(logn), и пусть он будет A(T1,T2)

Теперь мы представляем новый алгоритм сортировки: Sort(A) (1) 

Sort(A):
  Let T_i be an AVL tree consisting only of A_i  // O(1) n times, total O(n).
  curr_size = 1
  while curr_size < size(A):
    Let T_i, T_j be two trees of size curr_size  // O(1)
    // Assume without loss of generality i < j.
    if there are such T_i,T_j:
      T_i = A(T_i,T_j)  // O(log(curr_size))
    else:
      curr_size = curr_size * 2  // O(1)
  return in_order(T_0)  // O(n) by in-order traversal.

Сложность алгоритма: 

T(n) = n/2 * log(2) + n/4 * log(4) + n/8 * log(8) + ... + 2*log(n/2) + log(n)

Объяснение

Сначала нам нужно объединить все деревья размера 1 с деревьями размера 2. Это требует n / 2 слияний, каждое из которых занимает O (log (2)). Затем, объедините получившиеся n / 2 деревьев с деревьями размера 4. Это делается n / 4, каждый O (log4), ... наконец, у нас есть два дерева, и мы объединяем их один раз, и это занимает O (n).

Это дает нам формулу: 

T(n) = sum (n/2^i * log(2^i)) for i=1,2,3,...,logn

Мы могли бы сделать еще немного алгебры, но я взял ярлык и перевел его на Wolfram alpha , что дает нам: 

T(n) = 2n -log(n) -2

Поскольку приведенное выше является линейным, это означает, что наш алгоритм сортировки общего назначения Sort (A) является линейным.

Но сортировка Omega(nlogn).

Это означает что-то не так - поэтому предположение, что такой алгоритм A(T1,T2) существует, а сложность O(logn) неверна.

QED

( 1) Для простоты алгоритм принимает размер (A) = 2^i для некоторых i в N. Это ограничение можно ослабить, не меняя заключение, а лишь меняя усложнение алгоритма.

...