從大集合構建AVL樹的高效算法

Question

我有一個大的AVL Tree，我在程序期間從未分類的集合（它將在稍後用於插入/刪除項目）中構建一些時間。

是否有比在每個項目上使用簡單插入更好的算法？首先對收集進行排序然後嘗試以不同的方式構建它會更有效嗎？

我的應用程序分析告訴我，這個AVL建築是一個熱點地點。

Answer 1

如果數據很方便地適用於內存，我確實希望先做一個快速排序，然後從中建立樹會比做所有常規的插入更快。

要從數組構建樹，以遞歸方式操作，將樹分爲三部分：中間元素，左部分和右部分;兩個部分必須具有相同的大小（+ -1），然後從這些部分形成樹。這保證了所得到的樹幾乎是平衡的（如果元素的數量是2^n-1，它將是完全平衡的）。樹的創建應返回樹的高度，以便您可以方便地將天平放入每個節點。

編輯：假設伊恩Piumarta的tree.h，我相信這個算法應該做的伎倆：

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