Как создать AVL-дерево из ArrayList значений за O (n) раз?

Question

Мое назначение - создать дерево AVL из списка значений отсортированного массива за время O (n), где n - количество значений

Я работал над этим, но я не могу получить O (n) время, лучшее, что я могу получить, это O (nlog (n))

Моя проблема в том, что каждый раз, когда вставляется узел, который вызывает несбалансированное дерево, я должен сделать еще один цикл, чтобы найти несбалансированный узел и применить ротацию (и), чтобы снова сбалансировать дерево.

Любая помощь очень ценится, спасибо!

Answer 1

Как насчет создания полного сбалансированного дерева с несколькими узлами на самом низком уровне, которые, возможно, отсутствуют, например, для 6 элементов, создайте

      o
    /   \
   o     o
  / \    /
 o   o  o

Затем выполните обход inorder, и когда вы посещаете i-й узел, установите его ключ на A [i].

Это допустимое дерево AVL, поскольку у каждого узла есть левый и правый дочерний элемент, высота которого отличается не более чем на единицу.

Исходное дерево можно построить в O (n), а обход по порядку в O (n), поэтому сложность составляет O (n).

Между прочим, в полусвязанной ноте есть метод, называемый heapify, для построения кучи (mix или max) из массива целых чисел, который O (n) для массива длины n, даже если вставка в кучу равна O (log n) - хитрость заключается в том, чтобы сделать это снизу вверх.

Answer 2

Вставка - O(logn), поэтому, никто не может сделать лучше, чем O(nlogn) при вставке.На самом деле, вы не должны вставлять в AVL-дерево.Вы должны просто создать дерево.Создайте все узлы и выберите значения из массива при создании новых узлов.Не ищите / ищите нужное вам значение, просто возьмите его, массив отсортирован.

Учитывая список, который содержит 5 элементов и отсортирован, например [1,2,3,4,5], что будет корнем дерева?Как насчет 7 элементов?10?...?

После того, как вы получите корень, какой будет корень левого поддерева.Какой список посмотреть?Какую часть списка вы должны хранить в левом поддереве?

Вот и все.