Algoritmo eficiente para la construcción de un árbol AVL de la colección grande

Question

Tengo una gran href="http://en.wikipedia.org/wiki/AVL_tree" AVL Árbol que tengo que edificar algunas veces durante el programa a partir de una colección sin clasificar (que se utiliza para insertar / eliminar elementos más adelante).

¿Hay algún algoritmo mejor que usar la inserción sencilla en cada artículo? Va a ser más eficientes para ordenar la recogida primero y luego tratar de construir de manera diferente?

Perfiles de mi solicitud me dice que este edificio AVL es un punto de conexión.

Answer 1

Si los datos se ajustan convenientemente en la memoria, de hecho me gustaría contar con que hacer una clasificación rápida en primer lugar, y la construcción del árbol del que sería más rápido que hacerlo todas las inserciones regulares.

Para construir el árbol de una matriz, operar de una manera recursiva, dividiendo el árbol en tres partes: un elemento medio, la parte izquierda, y la parte derecha; ambas partes deben tener el mismo tamaño (+ -1), a continuación, formar árboles fuera de estas partes. Eso garantiza que el árbol resultante es casi equilibrado (será perfectamente equilibrado si el número de elementos es 2 ^ n-1). creación del árbol debe devolver la altura del árbol, de modo que usted puede poner el equilibrio convenientemente en cada nodo.

Editar : Asumiendo de Ian Piumarta tree.h creo que este algoritmo debe hacer el truco:

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