BST avec des doublons

Je sais que, BST n'autorise pas les doublons. Par exemple, si j'ai un mot "RABSAB".

L'arbre de recherche Binaire pour le dessus de la chaîne est:

    R
    /\
   A  S
    \
     B

Que si nous voulions inclure les doublons dans l'arbre. Comment l'arbre va changer? J'ai été demandé à cette question dans une interview.

Ils m'ont demandé de dessiner:

un arbre binaire
un déséquilibre de la structure d'Arbre de Recherche Binaires
un arbre de recherche binaire sans doublons
un arbre de recherche binaire avec des doublons

Toute Aide est très appréciée!

PS: Aidez-moi par le dessin de la relative arbres

BST n'a pas de contrainte que les doublons ne sont pas autorisés, vous pouvez garder en double, lire : Stratégie pour les entrées en double dans un arbre de recherche binaire
Je parlais en général. J'ai lu dans le wiki, en général BST habitude de permettre les doublons. Pouvez-vous aider dans l'élaboration de la BST pour la Chaîne?
double possible de Sont des doubles des clés autorisées dans la définition des arbres binaires?, parce que toute bonne réponse à cette question doit examiner comment mettre en œuvre ces techniciennes se chargent

OriginalL'auteur user | 2013-05-24

19

Règle insérer dans un arbre de Recherche binaire sans doublon est:
1. Aller à gauche si l'élément est inférieure à la racine
2. Aller à droite si l'élément est plus grand que la racine.
Et pour permettre des entrées en double, vous devez modifier la règle comme ci-dessous:
1. Aller à gauche si l'élément est inférieure ou égale racine
2. Aller à droite si l'élément est plus grand que la racine.
ou
1. Aller à gauche si l'élément est inférieure à la racine
2. Aller à droite si l'élément est plus grand ou égal à la racine.
ou
1. Aller à gauche si l'élément est inférieure à la racine
2. Aller à droite si l'élément est plus grand que la racine.
3. Augmenter le compte si l'élément est égale à la racine.
De sorte que votre BST pour word "RABSAB", avec des doublons peuvent être:
```
     R
    / \
   A   S
  / \
 A   B
    /
   B
```
Ou,
```
     R
    / \
   A   S
    \
     A
      \
       B
        \
         B
```
ou
```
    R(1)
   /  \
  /    \
 A(2)  S(1)
  \
   \
   B(2)
```
Dans les deux Premiers cas, à la fois de l'insertion et de la recherche devient peu complexe! Vous trouverez ici avec beaucoup d'explications!

Et le troisième cas est un peu plus facile à maintenir.

Tous d'entre eux sont utilisés avec succès pour autoriser les doublons, maintenant le choix est vôtre!

Vous m'avez donnée à tous les scénarios.
vous êtes toujours à gauche dans le double cas?
yoo, frère, beau travail!
lola... 😉 bro!

OriginalL'auteur Sazzadur Rahaman
2

Une option consiste à modifier l'arbre de sorte que l'on branche comprendra les doublons, par exemple, la gauche branches tenir les nœuds qui sont inférieures ou égales à la société mère, sinon ont le droit de branches de tenir les nœuds qui sont supérieures ou égales à la mère

Une autre option est de conserver tous les doublons dans un nœud, de sorte qu'au lieu de
```
class Node {
    Node left, right;
    Object data;
}
```
vous serait plutôt
```
class Node {
    Node left, right;
    List data;
}
```
ou
```
class Node {
    Node left, right;
    Object data;
    int count;
}
```
maintenant le "Liste des données" permettrait d'ajouter les frais généraux hors parcourant la liste, puis en les ajoutant à la liste , en gardant le compteur convient le mieux .

OriginalL'auteur Zim-Zam O'Pootertoot
0

Dans un normal la BST, de l'insertion et de la recherche à la fois se produire sur la base de moins de(>) et supérieur à (<) de la règle.

Vous pourriez essayer d'insertion sur moins égal à (>=) supérieure ou égale à (<=) et essayez d'utiliser la même règle pour la recherche.

Vous pouvez également inclure un tableau dans chaque noeud pour accueillir les éléments en double.

OriginalL'auteur amitdonanand
0

Pour votre entrée RABPAB, Vous pouvez créer un BST en utilisant une LISTE de stocker toutes les valeur égale clés. Tous les d'une valeur égale clés sont placées dans le même niveau à l'aide d'une structure de données capable de stocker.

Le BST va ressembler à quelque chose comme ceci,
```
     R
    / \
A--A   P
    \
  B--B
```
Le code Java pour votre BST stocker des valeurs de type entier pouvait être comme ça,
```
class Node 
{
    Node left, right;
    int data[maxvalue];
}
```
Ici maxvalue est le maximum possible d'une valeur égale clés.

OriginalL'auteur Deepu

Vous devez vous connecter pour publier un commentaire.