Algorithme efficace pour construire un arbre AVL à partir d'une grande collection

Question

J'ai un grand AVL Tree que je construis quelques fois au cours d'un programme à partir d'une collection non triée (il sera utilisé pour insérer/retirer des éléments plus tard).

Existe-t-il un meilleur algorithme que d'utiliser l'insertion simple sur chaque article? Sera-t-il plus efficace de trier la collection en premier et ensuite de la construire différemment? Le profilage de mon application me dit que ce bâtiment AVL est un emplacement de hotspot.

Answer 1

Si les données s'intègrent commodément dans la mémoire, je m'attendrais en effet à faire d'abord un quicksort, et construire l'arbre à partir de ce serait plus rapide que de faire toutes les insertions régulières.

Pour construire l'arbre à partir d'un tableau, opérer de manière récursive, en divisant 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), puis former des arbres à partir de 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). La création d'arbre devrait renvoyer la hauteur de l'arbre de sorte que vous puissiez mettre la balance commodément dans chaque nœud.

Modifier: En supposant Ian Piumarta de 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; 
}