1

長いリストを並べ替えたいので、すべての要素を B ツリーに入れます (各要素の挿入には O(log n) 時間がかかります)。

並べ替えたら、要素を読み返す必要があります。

B ツリー内のすべてのオブジェクトを読み取るのにどのくらいの時間がかかるか知っていますか?

ありがとう！

4

1 に答える 1

1

inorder traversal の変更を使用して、時間 O(n) でソートされた順序で B ツリー内のすべての要素を反復処理できます。これを次のように再帰的に行います。

To list off all elements of tree T in sorted order:
    Let the children of T be C0, C1, C2, ... Cn
    Let the keys of T be K1, K2, ..., Kn

    Output C0
    For i from 1 to n:
       Output Ki
       Recursively list all elements of Ci in order.

各キーが 1 回だけアクセスされるため、これには O(n) の時間がかかります。(楽しい練習として、これを標準的な順序トラバーサルの仕組みと比較してみてください!) ソートされていないデータから B ツリーを構築するには O(n log n) の時間がかかるため、このソート アルゴリズムには O(n log n) の時間がかかります。これは、BST ではなく B ツリーを使用するツリー ソートの変更と考えることができます。

B ツリーがディスク上に格納されている場合、キャッシュのパフォーマンスはあまり高くありません。B+ ツリーを使用することをお勧めします。これは、特にインオーダー トラバーサルと範囲検索を最適化するように設計されています。

お役に立てれば！

于 2013-06-13T18:37:51.170 に答える