traiter les doublons dans un bst

Question

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é?

Answer 1

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.

Answer 2

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.

Answer 3

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.