J'ai une BST qui a des entrées en double. J'essaie de trouver des entrées en double. Maintenant, il est évident que je peux écrire un algorithme muet qui traverse tout l'arbre, ce qui est facile.
Cependant, je veux écrire un plus efficace. Voici ce que j'ai fait / pensé jusqu'à présent: p>
suppose l'arborescence suivante. P>
if (node == null)
return new NodeBST<Value>(name, value);
if (node.key().compareTo(name) > 0)
node.setLeft(insert(node.left(), name, value));
else
node.setRight(insert(node.right(), name, value));
4 Réponses :
L'arbre que vous montrez suppose (bien, au moins, je suppose ... ;-)) que moins que sont à gauche et plus que sont à droite, ai-je raison?
Il y a donc deux choses que vous devriez envisager:
Votre arbre est faux! La seconde "8" à droite de la tête "10" ne peut pas être là, puisqu'elle est inférieure à 10. Une insertion correcte et un équilibrage correct, mettrait tous les deux très près, sinon juste à la "prochaine" itération de la "gauche 8".
en définissant l'arbre comme "moins que ou égal" à gauche et "plus de plus que" à droite, vous obtiendrez le résultat recherché: tous les "8" seront enchaînés à la gauche de l'autre sur un simple arbre d'insertion.
Oui Oui, je m'excuse pour mon erreur. S'il vous plaît voir Modifier 2. Mon insertion les chaîne à la droite de l'autre. Alors, quand je trouve un duplicata, passez simplement à travers son enfant droit / enfants pour voir tous les doublons?
Tout à fait. De plus, pour la brièveté et la performance, si vous vous attendez à un grand nombre de doublons, extension d'une liste liée de tous les objets de valeur similaires de la première, peut être une bonne idée. Si de grands ensembles de duplicats, vous pouvez commencer une table de hachage pour une feuille contenant des doublons ... tout en fonction du problème particulier que vous essayez de résoudre!
Un algorithme récursif peut résoudre ce problème rapidement. Vous n'avez pas à recueillir sur tout l'arbre, car vous pouvez utiliser la structure de la BST pour chasser les valeurs dont vous avez besoin.
Ce que vous avez dessiné n'est pas strictement une BST, je pourrais me tromper, mais je crois que c'est assez brisé - tous les chiffres de l'arbre à gauche doivent être inférieurs à 10, et inversement.
Je suis désolé, je le sais. J'ai fait une erreur s'il vous plaît voir la modification révisée 2. Merci
Je crois à l'étape 2, il devrait s'agir de la sous-branche de RH selon mon insertion (comme indiqué dans la modification 2 ci-dessus), les doublons sont insérés dans le bon enfant du nœud. Correct?
@Nayefc La première fois que vous arrivez à (2) peut ne pas savoir que tous les doublons ne sont que vers la droite. Cela dépend de la façon dont vous écrivez votre code de recherche.
Oh ouais je sais ça. Je dis simplement que ma méthode d'insertion met des doublons sur le côté droit d'un nœud. (S'il vous plaît voir ci-dessus code + diagramme). Donc, cela ne ferait pas l'étape 2 comme: examinez le SUB-BRANCE RH au lieu de la sous-branche LH?
@Nayefc qui ne change rien. Lorsque vous recherchez, Vous devez soit continuer à rester à gauche pendant que les touches sont égales ou arrêtez au premier match. Si ces derniers, les doublons pourraient être des deux côtés.
Oh, vous donnez l'algorithme de recherche entier. Je l'ai Merci
Je pense que la recherche dépend de votre implémentation, c'est-à-dire si votre partie d'insertion est comme si (élément> = arborescence [i]) insérer rh ou si (élément <= arbre [i]) insérer lh.
@Soumajyoti non ce n'est pas le cas. Lorsque vous rencontrez une correspondance non-feuille, vous devez d'abord aller à la première des premières clés égales. Sinon, vous n'êtes pas dans un arbre binaire.
Cette implémentation utilise une méthode récursive et renvoie une gamme d'entrées en double
Connaissez-vous auparavant quel nombre vous recherchez?
Cela ne vaingait-il pas le but d'une BST?
Ce n'est pas une bonne BST. Vous ne pouvez pas avoir 8 sur la branche droite de la racine 10.
@lynks oui - vous avez donné quel numéro vous souhaitez supprimer.
@John Kugelman Oh c'est vrai! Laissez-moi résoudre ce problème. Pardon
Que voulez-vous: 1) Compte tenu de la clé, trouvez-le et tous les duplicats 2) Trouver tous les nœuds qui ont une clé en double? Une question connexe et plus générique: Stackoverflow.com/questions/300935/...