大規模コレクションからAVLツリーを構築するための効率的なアルゴリズム

Question

私はプログラム中にソートされていないコレクション（後でアイテムを挿入/削除するために使用される）で何度か構築する大きいAVL Treeを持っています。

各アイテムに簡単な挿入を使用するよりも優れたアルゴリズムはありますか？最初にコレクションを並べ替えて別の方法でビルドする方が効率的でしょうか？

私のアプリケーションのプロファイリングでは、このAVLビルがホットスポットの場所であることがわかります。

Answer 1

データが便利にメモリに収まる場合は、クイックソートを最初に実行し、それからツリーを構築する方が通常の挿入をすべて実行するよりも高速になると思います。

ツリーをアレイから構築するには、ツリーを3つの部分に分割する再帰的な方法で操作します。中間要素、左側部分、右側部分。両方の部分が同じサイズ（+ -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; 
}