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

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

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

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


algorithm avl-tree
person Lothar    schedule 18.08.2009    source источник
comment
Можете ли вы использовать дерево AVL в качестве своей коллекции (во всем приложении), тогда вам нужно будет отсортировать его только один раз?   -  person Justin    schedule 18.08.2009

Ответы (1)


arrow_upward
1
arrow_downward

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

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

Правка: если исходить из tree.h Яна Пиумарты, я считаю, что этот алгоритм должен сделать свое дело:

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;
}
person Martin v. Löwis    schedule 18.08.2009
comment
Если ключ данных является чем-то поддающимся сортировке по интервалам, сортировка может быть еще быстрее. Сложность построения дерева AVL, как вы описываете, составляет O (n). - person Kathy Van Stone; 18.08.2009
comment
Да, я также ожидал бы, что это будет быстрее, особенно потому, что ключевые сравнения могут быть дорогими. Но я надеялся увидеть какой-нибудь псевдокод или ссылку на библиотеку AVL, которая содержит подобную функцию, поскольку я должен сказать, что нахожу всю балансировку и вращения довольно сложными. - person Lothar; 18.08.2009
comment
@Lothar: см. мое редактирование. Если вам нужен код, который действительно вам поможет, как минимум, вы должны опубликовать свое определение узла. - person Martin v. Löwis; 19.08.2009
comment
Я написал короткую запись в блоге по этой методике. При условии, что вы примете надлежащие меры предосторожности, чтобы убедиться, что исходный массив в порядке, это может закончиться во много раз быстрее, чем выполнение итерационных вставок; в основном потому, что вам не нужно делать какие-либо повороты. - person Anthony; 17.12.2012