2

m-way 探索木を実装したいのですが、m-way 探索木の実装の基本が必要です。同じことを実装するのに役立つ良いリソースを誰かが提供してくれますか??

4

2 に答える 2

1

ほとんどの m-way 探索ツリーは、(m-1) 個のキーを各ノードにソートされた順序で格納することによって機能します。次に、これらの値は要素を m 領域に分割します。m-2 領域は (m-1) キーの間で囲まれ、左端のキーよりも 1 領域小さく、最大のキーよりも 1 領域大きくなります。たとえば、4 方向ツリーのノードは次のようになります。

       1              3              7
x < 1    1 < x < 3      3 < x < 7     7 < x

検索を実装するには、ツリーのルートから開始し、要素をノードに格納されている各値と比較します。ノードが属するグループに基づいて、ノードが見つかったことを報告するか、適切な子に下ります。

ノードを挿入および削除する方法の背後にある実際のメカニズムは、使用する多元配置ツリーのタイプによって異なります。これは、バイナリ サーチ ツリーの挿入および削除がツリーのタイプ (AVL、スプレイ、赤/黒など) によって異なるのと同じです。良い出発点は、おそらく最も有名な m ウェイツリーであるB ツリーです。有名な CLRS の教科書には、構造に特化した章全体があり、アルゴリズムの詳細については優れたリソースになります。

お役に立てれば！

于 2011-08-19T09:08:02.717 に答える
0

三分木を探してみませんか？三分木はデータ構造に似たトライですが、パトリシア トライやクリビット ツリーと同様に、タイプまたはツリー モデルとして B ツリーを使用します。カートトライも良い出発点です。

于 2011-08-19T09:59:53.850 に答える