Mon bst doit être en mesure de faire face à des entrées en double. Est-ce que quelqu'un a des stratégies pour ce faire qui ne nécessite pas une quantité excessive de code? J'ai pensé à toujours ajouter des doublons sur la droite, mais cela va gâcher la commande bst. par exemple, que se passe-t-il lorsque le doublon a deux enfants qui, à leur tour, ont deux enfants? insérer le doublon est assez facile, mais que faire avec le nœud qu'il a remplacé?traiter les doublons dans un bst
Répondre
Vous pouvez faire les nœuds de l'arbre de recherche binaire dans les listes chaînées.
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>();
}
Ici, treeNode.items
est toujours une liste non vide, de sorte que item1.compareTo(item2) == 0
pour chaque item1
et item2
dans treeNode.items
.
Pour insérer un élément en double, vous devez rechercher l'objet TreeNode
correspondant et ajouter un nouvel élément au items
.
La logique de recherche d'éléments est presque la même que précédemment, sauf qu'une fois que vous avez trouvé l'objet TreeNode
pertinent, vous devez parcourir la liste chaînée.
Tant que ce n'est pas une auto équilibrage BST, je ne vois pas de problème avec mettre des nœuds égaux soit à gauche ou à droite du nœud est égal à eux.
Modifier (après la remarque de Simonn):
Si le « nœud double » en question a déjà 2 enfants, puis insérez simplement le « nouveau nœud double » à gauche et laisser l'enfant gauche de la " ancien noeud dupliqué "devient l'enfant gauche du" nouveau noeud dupliqué ".
Permettez-moi de clarifier un exemple. L'arbre avant d'insérer un double:
4'
/\
2 5
/\
1 3
Et maintenant l'élément 4''
est inséré:
4'
/\
4'' 5
/
2
/\
1 3
Tant que l'arbre est pas auto équilibre, vous devriez être bien.
Salut, je ne suis pas l'affiche originale de cette question. Pourriez-vous s'il vous plaît élaborer la question si nous avons un auto-ajustement BST? Qu'est-ce qui, selon vous, devrait être la propriété d'un BST autoréglable? Je crois, il doit se réorganiser après qu'un noeud est supprimé. Même dans ce cas, je ne trouve pas question d'ajouter l'élément en double à gauche ou à droite du noeud qui est à dupliquer. – dharam
Je me demande si vous avez réellement besoin de stocker les entrées en double en tant que nœuds séparés? Est-ce que l'ajout d'une variable de compteur à votre Node serait suffisant? De cette façon, si vous traversez l'arbre, vous connaîtrez le nombre d'entrées dupliquées et conserverez l'ordre.
merci pour cette idée. – volk
- 1. Un petit problème avec l'implémentation de BST
- 2. Insert BST en C++
- 3. Comment éviter les doublons?
- 4. Comment éviter les doublons dans une énumération?
- 5. SQL Import ignorer les doublons
- 6. Traiter avec les dates
- 7. Comment trouver des doublons dans MySQL
- 8. Traiter un processus plus long dans WCF
- 9. Additionner des doublons dans Excel
- 10. Comment marquer des doublons dans un groupe donné dans MySQL?
- 11. Lucene AddIndexes (fusionner) - comment éviter les doublons?
- 12. Comment traiter les valeurs NULL dans les comparaisons d'égalité?
- 13. comment éviter les doublons dans une relation has_many: through?
- 14. idiome Rails pour éviter les doublons dans has_many: par
- 15. Afficher tous les doublons, côte à côte, dans MySQL
- 16. Comparer fichier et supprimer les doublons
- 17. Supprimer les doublons dans la liste en utilisant linq
- 18. supprimer les doublons de dictionnaires imbriqués dans la liste
- 19. Obtenir ce modèle BST pour fonctionner
- 20. groupement Xsl doublons problème
- 21. Comment réparer les cas de frange dans la fonction de suppression BST?
- 22. Rendre lucene traiter tous les termes dans un champ comme un seul terme
- 23. Comment traiter les objets de portée nulle dans Spring.NET
- 24. Comment traiter les formulaires mutiples dans ASP .NET
- 25. Traiter les fuseaux horaires en PHP
- 26. Traiter avec le calcul paresseux dans les classes de C
- 27. Combinaison de deux listes et suppression des doublons, sans suppression des doublons dans la liste d'origine
- 28. Comment traiter les caractères spéciaux dans une chaîne
- 29. Comment puis-je supprimer les doublons dans un tableau d'objets en PHP?
- 30. Les lignes qui ressortent dans un fichier, mais ne sont pas des doublons exacts
Je suppose que BST est un arbre de recherche binaire? –