Discussion :

[wafiwafi]

Bonjour,
Je suis entrain de programmer en Java des arbres binaires de recherche pour un usage personnel. Tout marche bien.
Mais, j'ai pensé à un truc : Heureusement que toutes mes clés sont numériques et donc peuvent être liées par une relation d'ordre. Que se passe -t- il si mes clés n'étaient pas numériques mais plutôt alphanumériques (exemple :attribut type chaîne de caractères) ou pire clé composée (plusieurs attributs)?

C'est une simple question de curiosité.

Merci à vous

[thelvin]

Ben, elles peuvent toujours être liées par une relation d'ordre.

[Népomucène]

Oui, tu peux créer une règle pour dire d'un objet qu'il est "avant" ou "après" un autre.
Pour cela, regarde l'interface "Comparable"

[wafiwafi]

Merci à toi.
Je m'attendais à cette réponse puisqu'on peut les trier également. mais je ne savais pas si cela se faisait.
J'ai une petite question et votre avis m’intéresse beaucoup:
J'ai développé une petite application qui permet de partir d'une liste d'objets, j'arrive à construire correctement l'ABR qui y correspond. Cela marche bien. j'arrive à retourner si l'objet se trouve ou pas dans la structure.
La prochaine étape c'est indiquer sa position dans la liste (une longue liste) puisque je ne dispose que de sa position dans l'ABR. Alors quelques conseils ou avis me seront utiles!
En gros, il faut que j'établisse un lien entre la position dans l'arbre et la position y correspondante dans ma liste. ça n'a pas l'air d'être évident.
J'espère que ce que je dis est clair!!
Cordialement

[dinobogan]

Connaissant uniquement la position dans l'arbre, il n'est pas possible de donner l'ancienne position dans la liste ayant servie à créer l'arbre.
En effet, le principe d'un arbre de recherche (si on omet la notion d'équilibrage) est de placer dans le sous arbre gauche ou droit selon la valeur de la donnée à insérer.

Supposons le cas trivial d'une liste à 2 éléments entier : "3" et "5".
Dans ton arbre binaire, la racine contient "3" et son fils droit contient "5".

Maintenant, changeons la liste pour : "5" et "3".
Ton arbre binaire commence par la racine contenant "5", puis le fils gauche contenant "3".

Fils droit la première fois, fils gauche la seconde fois. L'arbre binaire de recherche a été conçu pour connaitre l'existence d'un élément. Il est complètement décorrélé de la liste initiale.

Le seul moyen est d'ajouter un entier dans chaque nœud décrivant la position dans la liste initiale.

[wafiwafi]

Ok, c'est clair et c'est bien ce que je craignais.

Maiiiis même si cela m'ajoute un attribut.

Le seul moyen est d'ajouter un entier dans chaque nœud décrivant la position dans la liste initiale.

super idée.

Merci infiniment à toi.

Cordialement

[wafiwafi]

L'arbre binaire de recherche a été conçu pour connaitre l'existence d'un élément. Il est complètement décorrélé de la liste initiale.

Moi qui construis l'arbre binaire de recherche en y mettant les objets, j'aurais pu n'y mettre que les clés?
ça aurait été beaucoup plus simple.