Algorithme efficace pour la construction d'un arbre AVL de collection

Question

J'ai un grand href="http://en.wikipedia.org/wiki/AVL_tree" AVL Arbre que je construit quelques fois durant le programme d'une collection non triés (il sera utilisé pour insérer / supprimer des éléments plus tard).

Y at-il meilleur algorithme que l'utilisation simple insert sur chaque article? Sera-ce plus efficace pour trier la collection d'abord et ensuite essayer de le construire autrement?

Le profilage de ma demande me dit que ce bâtiment AVL est un emplacement de point d'accès.

Answer 1

Si les données correspondent facilement dans la mémoire, je fait attendre à ce que faire un premier tri rapide, et la construction de l'arbre de ce serait plus rapide que de faire toutes les insertions régulières.

Pour construire l'arbre à partir d'un réseau, fonctionnent d'une manière récursive, diviser l'arbre en trois parties: un élément central, la partie gauche et la partie droite; les deux parties doivent avoir la même taille (+ -1), forment alors des arbres sur ces parties. Cela garantit que l'arbre résultant est presque équilibré (il sera parfaitement équilibré si le nombre d'éléments est 2 ^ n-1). création d'arbres devrait revenir à la hauteur de l'arbre de sorte que vous pouvez mettre l'équilibre facilement dans chaque nœud.

Modifier : En supposant tree.h , je crois que cet algorithme devrait faire l'affaire:

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