O(log(n)) の複雑さで機能するものが必要で、AVL ツリーについて考えましたが、問題は、一部のキーが繰り返される可能性があることです (たとえば、人のスコア)。ツリーとして実装します。これを行う適切な方法は何ですか？
1 に答える
1
利用可能な多くのオプションがあります。二分探索木のほとんどのフレーバーは、重複した値を持つノードを許可するように簡単に変更できます。これは、バランシング操作が (通常) 純粋にローテーションで構成され、順序を維持するためです。このような場合、通常の BST 挿入を行うだけですが、重複した値が表示されるたびに、任意に左または右に移動して、値が異なるかのように続行します。
スキップリストは、挿入や削除で複雑な構造の更新を行わないため、各キーの複数のコピーをサポートするために更新するのが特に簡単です。
各キーに関連付けられた補助情報がない場合、別のより簡単なオプションは、標準の二分探索ツリーを格納することですが、そのフィールドの論理コピーがいくつ存在するかを示す「カウント」フィールドで各ノードを拡張することです。挿入を行うたびに、キーが存在しない場合はカウント 1 で作成します。キーが既に存在する場合は、既存のノードのカウントをインクリメントします。削除も同様に実装されます。
もちろん、独自のデータ構造をロールバックしたくない場合は、マルチマップまたはマルチセットの適切な実装を見つけてください。選択したプログラミング言語によっては、標準ライブラリでこれらを見つけることさえできます。:-)
于 2015-08-24T23:01:05.733 に答える