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

Question

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

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

私のアプリケーションのプロファイリングは、この AVL の建物がホットスポットの場所であることを示しています。

Answer 1

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

配列からツリーを構築するには、ツリーを 3 つの部分 (中央の要素、左側の部分、右側の部分) に分割して再帰的に操作します。両方の部分が同じサイズ (+-1) である必要があり、これらの部分からツリーを形成します。これにより、結果のツリーがほぼバランスが取れていることが保証されます (要素の数が 2^n-1 の場合、完全にバランスが取れています)。ツリーの作成では、各ノードに都合よくバランスをとれるように、ツリーの高さを返す必要があります。

編集: Ian 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;
}