Algoritmo eficiente para a construção de uma árvore AVL de grande coleção

Question

Eu tenho um grande AVL Árvore que eu construir algumas vezes durante o programa a partir de uma coleção não ordenada (que será utilizado para inserir / remover os itens mais tarde).

Há qualquer algoritmo melhor do que usar a inserção simples em cada item? Será que vai ser mais eficiente para classificar a coleção primeiro e depois tentar construí-lo de forma diferente?

Profiling da minha candidatura diz-me que este edifício AVL é um local de acesso.

Answer 1

Se os dados se encaixam convenientemente na memória, eu seria realmente esperar que fazendo um quicksort primeiro, e construir a árvore de que seria mais rápido do que fazer todas as inserções regulares.

Para construir a árvore de uma matriz, operar de forma recursiva, dividindo a árvore em três partes: um elemento do meio, a parte esquerda e parte direita; ambas as peças devem ter o mesmo tamanho (+ -1), em seguida, formar árvores para fora dessas partes. Que garante que a árvore resultante é quase equilibradas (que será perfeitamente equilibrado se o número de elementos é 2 ^ n-1). criação árvore deve retornar a altura da árvore de modo que você pode colocar o equilíbrio convenientemente em cada nó.

Editar : Supondo de Ian Piumarta tree.h , eu acredito que este algoritmo deve fazer o truque:

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;
}