9

私はBST、重複を許可しないことを知っています。たとえば、「RABSAB」という単語があるとします。

上記の文字列の二分探索木は次のとおりです。

    R
    /\
   A  S
    \
     B

重複をツリーに含めたい場合はどうでしょうか。木はどう変わる？インタビューでこんな質問をされました。

彼らは私に描くように頼んだ：

  1. 二分木
  2. 不均衡な二分探索木
  3. 重複のない二分探索木
  4. 重複のある二分探索木

どんな助けでも大歓迎です！

PS: 関連する木を描いてください

4

4 に答える 4

20

重複なしで二分探索木に挿入するルールは次のとおりです。

  1. 要素がルートより小さい場合は左に移動
  2. 要素がルートより大きい場合は右に移動します。

重複するエントリを許可するには、次のようにルールを変更する必要があります。

  1. 要素がルート以下の場合は左に移動
  2. 要素がルートより大きい場合は右に移動します。

また

  1. 要素がルートより小さい場合は左に移動
  2. 要素がルートより大きいか等しい場合は右に移動します。

また

  1. 要素がルートより小さい場合は左に移動
  2. 要素がルートより大きい場合は右に移動します。
  3. 要素がルートと等しい場合は、カウントを増やします。

したがって、重複する"RABSAB"BSTという単語は次のようになります。

     R
    / \
   A   S
  / \
 A   B
    /
   B

または、

     R
    / \
   A   S
    \
     A
      \
       B
        \
         B

また

    R(1)
   /  \
  /    \
 A(2)  S(1)
  \
   \
   B(2)

最初の 2 つのケースでは、挿入と検索の両方が少し複雑になります。ここにたくさんの説明があります。

そして 3 番目のケースは、メンテナンスがいくぶん簡単です。

それらのすべてが重複を許可するために正常に使用されています。選択はあなた次第です!

于 2013-05-24T05:16:57.600 に答える
2

1 つのオプションは、1 つの分岐に重複が含まれるようにツリーを変更することです。たとえば、左側の分岐に親以下のノードを保持させたり、右側の分岐に親以上のノードを保持させたりします。

別のオプションは、すべての複製をノードに保存することです。

class Node {
    Node left, right;
    Object data;
}

代わりに

class Node {
    Node left, right;
    List data;
}

また

class Node {
    Node left, right;
    Object data;
    int count;
}
于 2013-05-24T05:01:45.037 に答える
0

入力については、LIST を使用して をRABPAB作成し、BSTすべての等しい値のキーを格納できます。すべての等しい値のキーは、それを格納できるデータ構造を使用して同じレベルに配置されます。

BST は次のようになります。

     R
    / \
A--A   P
    \
  B--B

整数値を格納する BST の Java コードは、次のようになります。

class Node 
{
    Node left, right;
    int data[maxvalue];
}

maxvalue可能な最大の等しい値のキーは次のとおりです。

于 2013-05-24T05:09:53.330 に答える
0

通常の BST では、挿入と検索の両方が未満 (>) およびより大きい (<) ルールに基づいて発生します。

代わりに、より小さい (>=) またはより大きい (<=) に挿入して、検索に同じルールを使用することもできます。

または、重複する要素に対応するために、すべてのノードに配列を含めることもできます。

于 2013-05-24T05:04:34.253 に答える