Создание дерева AVL из дерева двоичного поиска

Question

Мне нужно предложить алгоритм, который берет BST (двоичное дерево поиска), T1, который имеет ключи 2^(n + 1) - 1 и создает дерево AVL с одинаковыми ключами. Алгоритм должен быть эффективным с точки зрения худшей и средней сложности времени (как функция от n).

Я не уверен, как мне подойти к этому. Понятно, что минимальный размер BST, который имеет ключи 2^(n + 1) - 1, равен n (и это будет так, если он будет полным/сбалансированным), но как это мне помогает?

Существует прямой вперед метод, который должен пройти по дереву, каждый раз добавляя корень T1 к дереву AVL, а затем удаление его из T1:

• Поскольку T1 не может быть сбалансированы удалениями может стоить о (п) в худшем случае
• Вставить в AVL будет стоить O (Log п)
• Есть 2^(n + 1) - 1

Так что в сумме это будет стоить O(n*logn*2^n), и это смешно дорого.

Но почему я должен удалить из T1? Я плачу много и не без оснований. Так что я подумал, почему бы не с помощью обхода дерева над T1, и для каждого узла я посещаю, добавить его к дереву AVL:

• Есть 2^(n + 1) - 1 узлов так обход будет стоить O(2^n) (после посещения каждого узла)
• Добавление текущего узла каждый раз, когда к AVL будет стоить O(logn)

Таким образом, в общей сложности, который будет стоить O(logn * 2^n). , и это самая лучшая временная сложность, о которой я мог подумать, вопрос в том, можно ли это сделать быстрее? как в O(2^n)? Каким-то образом, чтобы вставка в дерево AVL стоила только O (1)?

Надеюсь, я был ясен и что мой вопрос здесь.

Большое спасибо,

Ноам

Answer 1

Там это алгоритм, который уравновешивает BST и работает в линейном времени под названием Day Stout Warren Algorithm

В основном все это делает преобразование BST в отсортированный массив или связанный список, выполнив обход в порядке (O (n)). Затем он рекурсивно берет средний элемент массива, делает его корнем и делает его дочерние элементы средними элементами левого и правого подмассивов соответственно (O (n)).Вот пример,

 UNBALANCED BST 
      5 
     / \ 
     3  8 
      /\ 
      7 9 
      / \ 
      6  10 


     SORTED ARRAY 
     |3|5|6|7|8|9|10| 

Теперь вот рекурсивные вызовы и в результате дерево,

DSW(initial array) 

      7 
7.left = DSW(left array) //|3|5|6| 
7.right = DSW(right array) //|8|9|10| 

      7 
      /\ 
      5 9 
5.left = DSW(|3|) 
5.right = DSW(|6|) 
9.left = DSW(|8|) 
9.right = DSW(|10|) 

      7 
      /\ 
      5 9 
     /\/\ 
     3 6 8 10