Эффективный алгоритм построения дерева AVL из большой коллекции

Question

у меня есть большой Дерево АВЛ который я создаю несколько раз во время программы из несортированной коллекции (позже он будет использоваться для вставки/удаления элементов).

Есть ли лучший алгоритм, чем использование простой вставки в каждый элемент?Будет ли эффективнее сначала отсортировать коллекцию, а затем попытаться собрать ее по-другому?

Профилирование моего приложения показывает, что это здание AVL является горячей точкой.

Answer 1

Если бы данные удобно помещались в память, я бы действительно ожидал, что сначала выполнить быструю сортировку и построить на ее основе дерево будет быстрее, чем выполнять все обычные вставки.

Чтобы построить дерево из массива, действуйте рекурсивно, разделив дерево на три части:средний элемент, левая часть и правая часть;обе части должны иметь одинаковый размер (+-1), затем сформируйте из этих частей деревья.Это гарантирует, что полученное дерево почти сбалансировано (оно будет идеально сбалансировано, если количество элементов равно 2^n-1).Создание дерева должно возвращать высоту дерева, чтобы вы могли удобно разместить баланс в каждом узле.

Редактировать:Предполагая, что Ян Пиумарта дерево.ч, я считаю, что этот алгоритм должен помочь:

Node* tree_build(int key[], int value[], int L, int R) // L and R inclusive
{

  int M;
  Node *middle;
  int lh, rh;

  if(L == R)
    return Node_new(key[L], value[L]);

  if(L+1 == R) {
    Node *left = Node_new(key[L], value[L]);
    Node *right = Node_new(key[R], value[R]);
    left->tree.avl_right = right;
    left->tree.avl_height = 1;
    return left;
  }

  // more than two nodes
  M = L + (R-L)/2;
  middle = Node_new(key[M], value[M]);
  middle->tree.avl_left = tree_build(key, value, L, M-1);
  middle->tree.avl_right = tree_build(key, value, M+1, R);
  lh = middle->tree.avl_left->tree.avl_height;
  rh = middle->tree.avl_right->tree.avl_height;
  middle->tree.avl_height = 1 + (lh > rh ? lh:rh);
  return middle;
}