2

私の bst は、重複したエントリに対処できなければなりません。過剰な量のコードを必要としない、これを行うための戦略を誰かが持っていますか? 一貫して右側に重複を追加することを考えましたが、それでは bst の順序が台無しになります。たとえば、複製に 2 人の子がいて、その子が 2 人の子を持つ場合はどうなりますか? 複製を挿入するのは簡単ですが、置き換えられたノードで何をすればよいのでしょうか?

4

3 に答える 3

3

それが自己平衡 BST でない限り、等しいノードをそれらに等しいノードの左側または右側に配置しても問題はありません。

編集（サイモンの発言後）：

問題の「複製ノード」にすでに 2 つの子がある場合は、単に「新しい複製ノード」を左に挿入し、「古い複製ノード」の左の子を「新しい複製ノード」の左の子にします。

例を挙げて明確にしましょう。複製を挿入する前のツリー:

    4'
   / \
  2   5
 / \
1   3

そして今、要素4''が挿入されます:

      4'
     / \
    4'' 5
   /
  2   
 / \
1   3

木が自己バランスをとっていない限り、問題はありません。

于 2009-10-10T12:37:16.050 に答える
2

二分探索木のノードをリンクされたリストにすることができます。

class Data implements Comparable<Data>
{
   // These are the data elements in your binary search tree
}

class TreeNode
{
  TreeNode left; // elements less than current node, or null
  TreeNode right; // elements greater than current node, or null
  List<Data> items = new LinkedList<Data>();    
}

ここで、treeNode.itemsは常に空でないリストであり、item1.compareTo(item2) == 0for everyitem1およびitem2in treeNode.items.

重複した要素を挿入するには、関連するオブジェクトを見つけてTreeNode、新しい項目を に追加しitemsます。

TreeNode要素を見つけるロジックは、関連するオブジェクトを見つけたら、リンクされたリストをたどる必要があることを除いて、以前とほとんど同じです。

于 2009-10-10T12:17:12.947 に答える
0

重複したエントリを別々のノードとして実際に保存する必要があるのでしょうか。ノードにカウンター変数を追加するだけで十分でしょうか？そうすれば、ツリーをトラバースする場合、重複するエントリの数を把握し、順序を維持できます。

于 2012-06-21T18:26:10.077 に答える