Effizienter Algorithmus zum Erstellen eines AVL-Baumes aus einer großen Sammlung

Question

Ich habe eine große AVL Tree, die ich während des Programms aus einer unsortierten Sammlung (wird später zum Einfügen/Entfernen von Elementen verwendet werden).

Gibt es einen besseren Algorithmus als den einfachen Einsatz für jedes Element? Ist es effizienter, die Sammlung zuerst zu sortieren und dann zu versuchen, sie anders aufzubauen?

Profiling meiner Anwendung sagt mir, dass diese AVL-Gebäude ist ein Hotspot-Standort.

Answer 1

Wenn die Daten bequem in den Speicher passen, würde ich tatsächlich erwarten, dass zuerst ein Quicksort ausgeführt wird und der Baum daraus schneller aufgebaut wird als alle regulären Einfügungen.

Um den Baum aus einem Array zu erstellen, rekursiv arbeiten und den Baum in drei Teile aufteilen: ein mittleres Element, der linke Teil und der rechte Teil; Beide Teile müssen die gleiche Größe (+ -1) haben und dann Bäume aus diesen Teilen bilden. Dies garantiert, dass der resultierende Baum nahezu ausgeglichen ist (er wird perfekt ausgeglichen sein, wenn die Anzahl der Elemente 2^n-1 ist). Die Erstellung des Baums sollte die Höhe des Baumes zurückgeben, damit Sie das Gleichgewicht bequem in jeden Knoten einfügen können.

bearbeiten: Unter der Annahme, Ian Piumarta der tree.h, ich glaube, dieser Algorithmus den Trick tun sollten:

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