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

Question

私は、ソートされていないコレクションからプログラム中にいくつかの回を構築する大規模な AVL木を持っています（後で項目を削除/挿入するために使用されます）。

各項目の簡単な挿入を使用するよりも任意のより良いアルゴリズムがありますか？それは最初のコレクションを並べ替えた後、違っそれを構築しようとする方が効率的でしょうか？

私のアプリケーションのプロファイリングは、この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;
}