私はデータ構造を独学している最中で、現在二分探索木に取り組んでいます。同一のデータがある場合、ツリーをどのようにソートするのか興味がありました。たとえば、私のデータが[4,6,2,8,4,5,7,3].
それから私は4になるので、どこに置くの4=4ですか？左か右か？
オプション1
オプション #2
これらのどちらかが正しいですか、それとも両方とも間違っていますか? どちらも間違っている場合は、どのように並べ替える必要があるか教えてください。ありがとう！
通常、バイナリ ツリーではデータの複製は許可されません。カスタム実装を作成すると、要素の数を保存できます。Java の TreeSet は一例です。一意の要素のみが含まれています。
実際、あなたがリストしたケースは、ツリーの構造全体を壊しました。検索操作は今では奇妙に見え、 O(ln n) では実行できませんでした。最悪の場合はO(n)かかるため、このデータ構造のすべての利点が失われます。
これがソートツリーである場合、どちらの方法でも問題なく動作します。最後に、ツリー ウォークを実行してデータをダンプします。
これが検索ツリーの場合は、余分な (冗長な) データが検出されたら削除します。"それが存在します"。これは検索ツリーであると言いましたが、理想的ではありませんが、実際には壊れていません.「4」を検索すると、単にルートノードをキャッチし（この場合）、その下に降りて他のノードを表示することはありません. 「4」。余分な # が周りにあるのは最適ではありません。
どちらの方法を選択しても、最良のケースと最悪のケースの状況があります。左/右の決定についてあまり心配しないでください - 一般的には問題ではありません。既知のデータストリームの詳細をしっかりと把握していれば、その特定のケースに最適な決定を下すことができます。