8

について理論的な質問がありBalanced BSTます。

通常のから、ノードPerfect Balanced Treeを持つビルドをしたいと思います。私が考えることができる最も簡単な解決策は、ソートされた配列を再帰的にサブ配列に分割し、そこから構築することです。2^k - 1unbalanced BSTArray/Linked listPerfect Balanced BST

ただし、ツリーサイズが非常に大きい場合はArray/List、同じサイズで作成する必要があるため、この方法では大量のメモリが消費されます。

もう1つのオプションは、AVL回転関数を使用して、要素ごとに挿入し、ツリーバランス係数（左右のサブツリーの3つの高さ）に応じた回転でツリーのバランスをとることです。

私の質問は、私は私の仮定について正しいですか？BST不均衡から完璧を作成する他の方法はありますBSTか？

4

3 に答える 3

2

AVL と同様のツリーは完全にバランスが取れているわけではないため、このコンテキストでどのように役立つかはわかりません。

leftandrightポインターの代わりにforwardandポインターを使用して、ツリー ノードから双方向リンク リストを作成できbackwardます。そのリストを並べ替え、下から上に再帰的にツリーを構築し、リストを左から右に消費します。

サイズ 1 のツリーを構築するのは簡単です。リストから一番左のノードを削除するだけです。

サイズ のツリーを構築できる場合は、サイズNのツリーも構築できます。サイズ のツリーを2N+1構築Nし、単一のノードを切り離してから、サイズ の別のツリーを構築しますN。1 つのノードが大きなツリーのルートになり、2 つの小さなツリーが左右のサブツリーになります。リストはソートされているため、ツリーは自動的に有効な検索ツリーになります。

これは、サイズ以外にも簡単に変更2^k-1できます。

O(N)更新: 検索ツリーから開始しているため、ソートされたリストを時間とO(log N)空間で (おそらく少し工夫すれば空間でも) 直接構築し、時間と(または) 空間O(1)でもツリーをボトムアップで構築できます。 .O(N)O(log N)O(1)

于 2012-12-24T14:54:04.710 に答える
0

メモリに制約がある場合は、AVL ツリーで O(log n) 時間で実行できる分割操作と結合操作を使用できます。スペースは一定だと思います。

順序の統計も維持できた場合は、中央値で分割し、LHS と RHS を完全にして結合することができます。

疑似コード (再帰バージョンの場合) は次のようになります。

void MakePerfect (AVLTree tree) {

    Tree left, right;
    Data median;

    SplitOnMedian(tree, &left, &median, &right);
    left = MakePerfect(left);
    right = MakePerfect(right);
    return Join(left, median, right);
}

これは O(n) 時間と O(log n) 空間で実装できると思います。

于 2012-12-24T23:45:59.173 に答える