AVLツリー内の重複キーの取り扱い

Question

私は私のavl-treeサポート重複キーを作りたいが、回転は同じキーを持つノードは、左と親の右側にも作ることができると重複してbinary search treeのデフォルトの動作に問題があります。

3つのノードを追加するとき、

は、例えばキーAを持つすべてはこのようなものにするために回転を行うには、ツリーの原因となります。

   A
  /  \ 
 A    A

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

私は考えている解決策は、各ノードの格納に重複配列を作っています そう既に存在して新しいアイテムを追加する際に、アレイに新しい項目を追加するだけになり、 その配列を返しますキーを持つすべてのアイテムを見つけながらキーで項目を削除すると、全体のノードを削除します。

重複を処理するための他の方法がありますか？

インサート項目は..キーと値をとるので、私は、特定のキーの方法でのfindAllによってそれらを返すように順序どおりの値を格納する必要があります。

Answer 1

もう一つの一般的なアプローチは、あなたが本当にもう重複したキーを持たないように内部的にキーの値の部分を作ることです。あなたは重複を可能にツリーからエントリを削除するために、とにかく、キーと値の両方が必要になります。

あなたがして（擬似コード）のような何かをするだろう、値を知らなくても、キーを検索するには：

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

Answer 2

各ノードは、カウントが含まれていることがあります：重複の添加は、それが全体のノードが削除される場合には1、いない限り削除は、カウントをデクリメントし、カウントをインクリメントします。

。