binary-search - BSTでの重複の場合はどうなりますか？

Question

二分探索木の重複に関する問題を解決するにはどうすればよいですか？

Answer 1

あなたが何を求めているのかよくわかりません。しかし、それは私が答えを投稿するのを止めることはありません。

通常、BSTでは重複キーは許可されていません。それは物事を非常に簡単にする傾向があり、それは避けやすい状態です。

重複を許可したい場合は、挿入は問題になりません。左側のサブツリーまたは右側のサブツリーのいずれかに貼り付けることができます。

問題は、それがAVLツリーや赤黒木のような自己平衡ツリーである場合、特定の側にある重複を期待できないことです。これは削除の問題のようですが、私はかつて、重複を特別に規定していないAVLツリーを実装したことがあり、まったく問題はありませんでした。

AVLツリーからノードを削除するには、（1）ノードを検索し、（2）そのノードを左側のサブツリーの最大のキーまたは右側のサブツリーの最小のキーに置き換えてから、そのノードを再帰的に削除します。サブツリーがない場合は、これ以上何もする必要はありません。

実際には、重複するノードを削除するということは、ルートに最も近い検索されたキーを持つノードが、別のキーを持つノード、または同じキーを持つノードのいずれかに置き換えられることを意味します。いずれにせよ、順序の制約に違反することはなく、すべてが問題なく進行します。

赤黒木や他の種類のBSTについては知りません。

Answer 2

比較チェック次第です。等しい場合と小さい場合は「小さい」ノードに配置され、そうでない場合は「大きい」ノードに配置されます。これに加えて、もちろんそれらを避けたい場合を除いて、重複の問題はないはずです。その場合、追加の同等性チェックが必要になります。