cerhu > comp.* > comp.algorithmes

Francis Moreau (09/06/2010, 21h42)
Bonjour,

Je me demande si les arbres binaires de recherche equilibres faisant
intervenir des rotations, comme l'arbre rouge et noir par exemple,
peuvent contenir des clefs de meme valeur.

Je pense que non puisqu'une rotation dans ce cas pourrait transformer un
arbre binaire de recherche (ABR) de facon a ce qu'il ne respecte plus la
propriete qui faisait de lui un ABR. Ainsi le parcours de cet arbre
pourrait ne plus etre correcte.

Est ce que quelqu'un pourrait confirmer mes propos ou alors les
contredire ?

Merci
Pascal J. Bourguignon (09/06/2010, 23h16)
Francis Moreau <francis.moro> writes:

> Bonjour,
> Je me demande si les arbres binaires de recherche equilibres faisant
> intervenir des rotations, comme l'arbre rouge et noir par exemple,
> peuvent contenir des clefs de meme valeur.
> Je pense que non puisqu'une rotation dans ce cas pourrait transformer un
> arbre binaire de recherche (ABR) de facon a ce qu'il ne respecte plus la
> propriete qui faisait de lui un ABR. Ainsi le parcours de cet arbre
> pourrait ne plus etre correcte.
> Est ce que quelqu'un pourrait confirmer mes propos ou alors les
> contredire ?


Je n'ai pas les algorithmes de balancement sous les yeux pour
confirmer ou infirmer, mais en pratique, on peut ruser.

La ruse serait d'avoir une comparaison de clé plus fine pour l'arbre
que pour l'application.

Soit un ensemble d'objets à mettre dans l'abre: V
et un ensemble de clés: K

Soit une fonction k donnant la clé d'un objet:

k:V --> K
v |-> k

Le problème, c'est que faire si k n'est pas une injection.
C'est à dire si ? v?,v??V², v??v? ? k(v?)=k(v?).

La solution c'est d'utiliser une relation d'ordre r
telle que:

k(v?)<k(v?) ? v? r v?
k(v?)=k(v?)?v??v? ? v? r v? ? v? r v?

Une implementation triviale de r utilise un "wrapper":

Soit une variable globale ? ? 0

La procedure w prend comme argument un objet v et retourne une clé "wrappée":
? ? ?+1
resultat ? wrap(?,k(v))

On peut alors définir la relation r comme:

v? r v? ? ( w(v?) = wrap(??,k?)
? w(v?) = wrap(??,k?)
? ( k?<k?
? (k?=k? ? ??<??)))

On place alors dans l'arbre les élements en utilisant w et r au lieu
de k et <.
Francis Moreau (09/06/2010, 23h22)
pjb (Pascal J. Bourguignon) writes:

> Francis Moreau <francis.moro> writes:
>> Je n'ai pas les algorithmes de balancement sous les yeux pour

> confirmer ou infirmer, mais en pratique, on peut ruser.
> La ruse serait d'avoir une comparaison de clé plus fine pour l'arbre
> que pour l'application.


[...]

Merci pour ta reponse mais je n'essaie pas de trouver une 'ruse' pour
contourner le probleme (je dois admettre que celle que tu presentes ne
me seduit pas :P) mais de savoir si le probleme existe vraiment.
Discussions similaires
[INFO] Tout (ou presque) sur les clefs de produits Microsoft, et script VIEWPK pour afficher ces clefs

Arbres Binaire (ABR), MAP,collection, TAS...

recherche de clefs

statistiques mots clefs du moteur de recherche


Fuseau horaire GMT +2. Il est actuellement 06h24. | Privacy Policy