Les clés en double sont-elles autorisées dans la définition des arbres de recherche binaires?

J'essaie de trouver la définition d'un arbre de recherche binaire et je continue à trouver différentes définitions partout.

Certains disent que pour tout sous-arbre donné, la clé enfant gauche est inférieure ou égale à la racine.

Certains disent que pour tout sous-arbre donné, la bonne clé enfant est supérieure ou égale à la racine.

Et mon ancien livre sur les structures de données d'université dit que «chaque élément a une clé et aucun élément n'a la même clé».

Existe-t-il une définition universelle d'un bst? En particulier en ce qui concerne ce qu'il faut faire avec les arbres avec plusieurs instances de la même clé.

EDIT: Peut-être que je n'étais pas clair, les définitions que je vois sont

1) gauche <= racine <droite

2) gauche <racine <= droite

3) gauche <racine <droite, de sorte qu'aucune clé en double n'existe.

De nombreux algorithmes spécifieront que les doublons sont exclus. Par exemple, les exemples d'algorithmes dans le livre Algorithmes du MIT présentent généralement des exemples sans doublons. Il est assez simple d'implémenter des doublons (soit sous forme de liste au nœud, soit dans une direction particulière).

La plupart (que j'ai vu) spécifient les enfants de gauche comme <= et les enfants de droite comme>. En pratique, un BST qui permet aux enfants de droite ou de gauche d'être égaux au nœud racine, nécessitera des étapes de calcul supplémentaires pour terminer une recherche où les nœuds en double sont autorisés.

Il est préférable d'utiliser une liste au niveau du nœud pour stocker les doublons, car l'insertion d'une valeur '=' d'un côté d'un nœud nécessite de réécrire l'arborescence de ce côté pour placer le nœud en tant qu'enfant, ou le nœud est placé en grand -enfant, à un moment donné ci-dessous, ce qui élimine une partie de l'efficacité de la recherche.

Vous devez vous rappeler que la plupart des exemples de classe sont simplifiés pour décrire et présenter le concept. Ils ne valent pas la peine d'être accroupis dans de nombreuses situations du monde réel. Mais la déclaration, "chaque élément a une clé et aucun élément n'a la même clé", n'est pas violée par l'utilisation d'une liste au nœud d'élément.

Alors allez avec ce que dit votre livre sur les structures de données!

Éditer:

La définition universelle d'un arbre de recherche binaire implique le stockage et la recherche d'une clé basée sur la traversée d'une structure de données dans l'une des deux directions. Au sens pragmatique, cela signifie que si la valeur est <>, vous parcourez la structure de données dans l'une des deux «directions». Donc, dans ce sens, les valeurs en double n'ont aucun sens.

Ceci est différent de BSP, ou partition de recherche binaire, mais pas si différent. L'algorithme de recherche a l'une des deux directions pour `` voyager '', ou il est fait (avec succès ou non). Je m'excuse donc que ma réponse initiale n'ait pas abordé le concept de `` définition universelle '', car les doublons sont vraiment distincts sujet (quelque chose que vous traitez après une recherche réussie, pas dans le cadre de la recherche binaire.)

Si votre arbre de recherche binaire est un arbre rouge noir, ou si vous avez l'intention d'effectuer n'importe quel type d'opérations de "rotation d'arbre", les nœuds en double poseront des problèmes. Imaginez que votre règle d'arbre soit la suivante:

gauche <racine <= droite

Imaginez maintenant un arbre simple dont la racine est 5, l'enfant gauche est nul et l'enfant droit est 5. Si vous faites une rotation gauche sur la racine, vous vous retrouvez avec un 5 dans l'enfant gauche et un 5 dans la racine avec l'enfant droit étant nul. Maintenant, quelque chose dans l'arborescence de gauche est égal à la racine, mais votre règle ci-dessus supposait left <root.

J'ai passé des heures à essayer de comprendre pourquoi mes arbres rouges / noirs traversaient parfois dans le désordre, le problème était ce que j'ai décrit ci-dessus. J'espère que quelqu'un lira ceci et se sauvera des heures de débogage à l'avenir!

Les trois définitions sont acceptables et correctes. Ils définissent différentes variantes d'un BST.

Le livre de la structure de données de votre collège n'a pas clarifié que sa définition n'était pas la seule possible.

Certes, autoriser les doublons ajoute de la complexité. Si vous utilisez la définition "gauche <= racine <droite" et que vous avez un arbre comme:

      3
    /   \
  2       4

puis l'ajout d'une clé dupliquée "3" à cet arbre se traduira par:

      3
    /   \
  2       4
    \
     3

Notez que les doublons ne sont pas dans des niveaux contigus.

C'est un gros problème lorsque vous autorisez les doublons dans une représentation BST comme celle ci-dessus: les doublons peuvent être séparés par n'importe quel nombre de niveaux, donc vérifier l'existence d'un doublon n'est pas aussi simple que de simplement vérifier les enfants immédiats d'un nœud.

Une option pour éviter ce problème est de ne pas représenter les doublons de manière structurelle (en tant que nœuds séparés) mais d'utiliser à la place un compteur qui compte le nombre d'occurrences de la clé. L'exemple précédent aurait alors un arbre comme:

      3(1)
    /     \
  2(1)     4(1)

et après insertion de la clé "3" dupliquée, elle deviendra:

      3(2)
    /     \
  2(1)     4(1)

Cela simplifie les opérations de recherche, de suppression et d'insertion, au détriment de quelques octets supplémentaires et d'opérations de comptage.

Dans un BST, toutes les valeurs descendant sur le côté gauche d'un nœud sont inférieures (ou égales, voir plus loin) au nœud lui-même. De même, toutes les valeurs descendant sur le côté droit d'un nœud sont supérieures (ou égales à) la valeur des nœuds ^(a) .

Certains BST peuvent choisir d'autoriser les valeurs en double, d'où le qualificatif «ou égal à» ci-dessus.

L'exemple suivant peut clarifier:

            |
      +--- 14 ---+
      |          |
+--- 13    +--- 22 ---+
|          |          |
1         16    +--- 29 ---+
                |          |
               28         29

Cela montre un BST qui autorise les doublons - vous pouvez voir que pour trouver une valeur, vous commencez au nœud racine et descendez dans le sous-arbre gauche ou droit selon que votre valeur de recherche est inférieure ou supérieure à la valeur du nœud.

Cela peut être fait de manière récursive avec quelque chose comme:

def hasVal (node, srchval):
    if node == NULL:
         return false
    if node.val == srchval:
        return true
    if node.val > srchval:
        return hasVal (node.left, srchval)
    return hasVal (node.right, srchval)

et l'appelant avec:

foundIt = hasVal (rootNode, valToLookFor)

Les doublons ajoutent un peu de complexité car vous devrez peut-être continuer à rechercher une fois que vous avez trouvé votre valeur pour d'autres nœuds de la même valeur.

^(a) Vous pouvez en fait les trier dans la direction opposée si vous le souhaitez à condition d'ajuster la façon dont vous recherchez une clé spécifique. Un BST n'a besoin que de maintenir un ordre trié, qu'il soit croissant ou décroissant n'est pas pertinent.

Dans le livre "Introduction aux algorithmes", troisième édition, de Cormen, Leiserson, Rivest et Stein, un arbre de recherche binaire (BST) est explicitement défini comme autorisant les doublons . Cela peut être vu dans la figure 12.1 et les suivantes (page 287):

"Les clés d'un arbre de recherche binaire sont toujours stockées de manière à satisfaire la propriété d'arbre de recherche binaire: Soit xun nœud dans un arbre de recherche binaire. Si yest un nœud dans le sous-arbre gauche de x, alors y:key <= x:key. Si yest un nœud dans le sous-arbre droit de x, alors y:key >= x:key. "

De plus, un arbre rouge-noir est alors défini à la page 308 comme:

"Un arbre rouge-noir est un arbre de recherche binaire avec un bit supplémentaire de stockage par nœud: sa couleur"

Par conséquent, les arbres rouge-noir définis dans ce livre prennent en charge les doublons.

Toute définition est valide. Tant que vous êtes cohérent dans votre implémentation (mettez toujours les nœuds égaux à droite, mettez-les toujours à gauche, ou ne les autorisez jamais) alors tout va bien. Je pense qu'il est plus courant de ne pas les autoriser, mais c'est toujours un BST s'ils sont autorisés et placés à gauche ou à droite.

En travaillant sur une implémentation d'arbre rouge-noir, j'avais des problèmes pour valider l'arbre avec plusieurs clés jusqu'à ce que je réalise qu'avec la rotation d'insertion rouge-noir, vous devez desserrer la contrainte pour

left <= root <= right

Étant donné qu'aucune documentation que je regardais n'autorisait les clés en double et que je ne voulais pas réécrire les méthodes de rotation pour en tenir compte, j'ai simplement décidé de modifier mes nœuds pour permettre plusieurs valeurs dans le nœud, et aucune clé en double dans l'arbre.

Ces trois choses que vous avez dites sont toutes vraies.

• Les clés sont uniques
• À gauche, les clés sont inférieures à celle-ci
• À droite se trouvent des clés plus grandes que celle-ci

Je suppose que vous pouvez inverser votre arbre et mettre les plus petites touches à droite, mais en réalité, le concept «gauche» et «droite» est juste cela: un concept visuel pour nous aider à penser à une structure de données qui n'a pas vraiment de gauche ou à droite, donc ça n'a pas vraiment d'importance.

1.) gauche <= racine <droite

2.) gauche <racine <= droite

3.) gauche <racine <droite, de sorte qu'aucune clé en double n'existe.

Je devrais peut-être aller chercher mes livres d'algorithmes, mais au sommet de ma tête (3) se trouve la forme canonique.

(1) ou (2) ne surviennent que lorsque vous commencez à autoriser les nœuds en double et que vous mettez des nœuds en double dans l'arborescence elle-même (plutôt que le nœud contenant une liste).

Dupliquer les clés • Que se passe-t-il s'il y a plus d'un élément de données avec la même clé? - Cela pose un léger problème dans les arbres rouge-noir. - Il est important que les nœuds avec la même clé soient répartis des deux côtés des autres nœuds avec la même clé. - Autrement dit, si les clés arrivent dans l'ordre 50, 50, 50, • vous voulez que le deuxième 50 aille à droite du premier, et le troisième 50 pour aller à gauche du premier. • Sinon, l'arbre se déséquilibre. • Cela pourrait être géré par une sorte de processus de randomisation dans l'algorithme d'insertion. - Cependant, le processus de recherche devient alors plus compliqué si tous les éléments avec la même clé doivent être trouvés. • Il est plus simple d'interdire les articles avec la même clé. - Dans cette discussion, nous supposerons que les doublons ne sont pas autorisés

On peut créer une liste chaînée pour chaque nœud de l'arborescence qui contient des clés en double et stocker des données dans la liste.

Je veux juste ajouter quelques informations à ce que @Robert Paulson a répondu.

Supposons que ce nœud contienne des clés et des données. Ainsi, les nœuds avec la même clé peuvent contenir des données différentes.
(La recherche doit donc trouver tous les nœuds avec la même clé)

1) gauche <= cur <droite

2) gauche <cur <= droite

3) gauche <= cur <= droite

4) left <cur <right && cur contiennent des nœuds frères avec la même clé.

5) left <cur <right, de sorte qu'aucune clé en double n'existe.

1) & 2) fonctionne très bien si l'arbre n'a pas de fonctions liées à la rotation pour éviter l'asymétrie.
Mais cette forme ne fonctionne pas avec l' arbre AVL ou l' arbre rouge-noir , car la rotation cassera le principal.
Et même si search () trouve le nœud avec la clé, il doit traverser jusqu'au nœud feuille pour les nœuds avec la clé en double.
Rendre la complexité du temps pour la recherche = thêta (logN)

3) fonctionnera bien avec n'importe quelle forme de BST avec des fonctions liées à la rotation.
Mais la recherche prendra O (n) , ruinant le but de l'utilisation de BST.
Disons que nous avons l'arbre comme ci-dessous, avec 3) principal.

         12
       /    \
     10     20
    /  \    /
   9   11  12 
      /      \
    10       12

Si nous recherchons (12) sur cet arbre, même si nous en avons trouvé 12 à la racine, nous devons continuer à rechercher les enfants à gauche et à droite pour rechercher la clé en double.
Cela prend du temps O (n) comme je l'ai dit.

4) est mon préféré. Disons que frère signifie le nœud avec la même clé.
Nous pouvons changer l'arbre ci-dessus en ci-dessous.

         12 - 12 - 12
       /    \
10 - 10     20
    /  \    /
   9   11  12

Désormais, toute recherche prendra O (logN) car nous n'avons pas à parcourir les enfants pour la clé dupliquée.
Et ce principe fonctionne également bien avec l' arbre AVL ou RB .

La relation d'ordre des éléments <= est un ordre total, donc la relation doit être réflexive, mais généralement un arbre de recherche binaire (aka BST) est un arbre sans doublons.

Sinon, s'il y a des doublons, vous devez exécuter deux fois ou plus la même fonction de suppression!