binary-tree - AVL ツリー内の重複キーの処理

Question

サポートの重複キーを作成したいavl-treeのですが、with duplicates のデフォルトの動作に問題がありbinary search tree、ローテーションによって同じキーを持つノードが親の左右に配置される可能性があります。

たとえば、すべてキー A を持つ 3 つのノードを追加すると、ツリーは次のように回転します。

   A
  /  \ 
 A    A

したがって、そのキーですべてのエントリを取得することは問題になります...そして、双方向の検索は良くありません。

私が考えた解決策は、各ノードに重複の配列を格納することです。そのため、既に存在する新しいアイテムを追加すると、新しいアイテムが配列に追加され、キーでアイテムを削除するとノード全体が削除され、すべてのアイテムが検索されますwith key はその配列を返します。

重複を処理する他の方法はありますか?

挿入項目はキーと値を受け取ります..したがって、特定のキーメソッドを使用してfindAllで値を返すために、値を保存する必要があります。

score 5 · Accepted Answer

もう 1 つの一般的なアプローチは、内部的に値をキーの一部にすることです。これにより、キーが重複することはなくなります。重複を許可するツリーからエントリを削除するには、とにかくキーと値の両方が必要です。

値を知らずにキーを検索するには、次のようにします (疑似コード):

searchResult = myTree.SearchGreaterOrEqual(Key);
found = (searchResult != null) && (searchResult.Key == Key);

score 3 · Accepted Answer

各ノードにカウントを含めます。重複を追加するとカウントが増加し、削除するとカウントが減少しますが、1 の場合はノード全体が削除されます。

2 に答える 2