Manipulation des clés de doublons dans un arbre AVL

Question

Je veux faire mon soutien à avl-tree clés en double, mais il y a un problème avec le comportement par défaut du binary search tree avec des doublons que la rotation pourrait faire des nœuds avec clé égale sur la gauche et le droit du parent.

Par exemple lors de l'ajout de trois nœuds tout avec la touche A PROVOQUERONT l'arbre pour faire une rotation à quelque chose comme ceci:

   A
  /  \ 
 A    A

Alors obtenir toutes les entrées avec cette clé sera un problème ... et la recherche dans les deux sens n'est pas bon.

La solution que j'ai pensé fait chaque nœud stocke un tableau de doubles donc lors de l'ajout d'un nouvel élément qui existe déjà sera simplement d'ajouter un nouvel élément au tableau, Suppression de l'élément avec la clé supprimera le nœud tout en la trouver tous les éléments avec clé retournera ce tableau.

Y at-il existe d'autres méthodes pour gérer les doublons?

L'élément d'insertion prend une clé et une valeur .. donc je besoin de stocker les valeurs envue de les retourner par la findAll avec une certaine méthode clé.

Answer 1

Une autre approche générale est de faire en interne la partie de la valeur de la clé afin que vous ne vraiment pas les clés en double plus. Vous aurez besoin à la fois la clé et la valeur de toute façon pour supprimer une entrée d'un arbre qui autorise les doublons.

Pour rechercher une clé sans connaître la valeur, alors vous feriez quelque chose comme (pseudo-code):

searchResult = myTree.SearchGreaterOrEqual(Key);
found = (searchResult != null) && (searchResult.Key == Key);

Answer 2

Demandez à chaque noeud contiennent un nombre: ajout de doublons incrémenter le compteur, les prélèvements décrémente le compte à moins qu'il soit 1, auquel cas le nœud entier sera supprimé

.