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.

[thelvin]

Ouais enfin il faut quand même te rappeler à quoi correspondent les clés, quoi.

[wafiwafi]

Ouais enfin il faut quand même te rappeler à quoi correspondent les clés, quoi.

Finalement, c'est important. Surtout si j'ai un traitement à effectuer sur l'objet correspondant à la clé recherchée, sur les parents ou encore sur les fils. On ne sait jamais!

Merci pour cette discussion qui m'a vraiment éclairé.
Cordialement

[wafiwafi]

Une dernière petite curiosité!

Et si mes objets sont dès le départ mémorisés dans un arbre binaire et non dans une liste. Comment je fais pour construire l'ABR puisque je dois partir d'une liste?
solution à me confirmer: Parcourir l'arbre en infixe par exemple et ressortir sous forme d'une liste de tous les objets sans doublons. Puis utiliser cette liste pour construire l'ABR.
Néanmoins cela nécessite à chaque modification (insertion, suppression) d'effectuer un nouveau parcours avant la mise à jour de l'ABR...

Merci

[thelvin]

Tu pourrais simplement jeter l'ABR de départ et ne garder que celui qui est correctement lié à la liste...

[wafiwafi]

Tu pourrais simplement jeter l'ABR de départ et ne garder que celui qui est correctement lié à la liste...

Le problème c'est que si je choisis une structure arborescence pour mémoriser mes objets, c'est parce que j'ai une certaine hiérarchie à leur attribuer qui n'a rien à voir avec l'hiérarchie d'un ABR.
Il y a le problème de mémorisation suivant une certaine hiérarchie qui dépend du contexte et qui peut ne pas être assujettie à une relation d'ordre, et l'autre face qui est simplement la recherche et donc la nécessite d'un Arbre propre à la recherche.
Cordialement

[dinobogan]

Un arbre implique une relation d'ordre. Si tu stockes tes données dans un arbre, sans passer par une liste comme tu dis, alors tu as obligatoirement une règle de remplissage, donc une relation d'ordre.

L'arbre binaire de recherche est généralement un arbre équilibré. Partant de ton arbre de départ, il suffit d'équilibrer ton arbre pour en faire un arbre binaire de recherche.

Si ton arbre de stockage initial n'a pas la même relation d'ordre que ton arbre binaire de recherche, il faudrait penser à revoir la conception ou alors nous donner un exemple concret

[Népomucène]

Par pure curiosité de ma part :
qu'est-ce qui te pousse à créer toi-même un arbre
plutôt que d'utiliser le système des collections Java :

• interface Comparator
• Collections.sort
• Collections.binarySearch
• ...

[wafiwafi]

J'ai suivi un cours sur la conception et l'implantation des structures de données et j'ai voulu aller au delà d'une vision théorique. Je voulais savoir ce que la communauté java en pense.
C'est donc une démarche personnelle sachant que Java propose humblement ce dont on a besoin.
En tout cas, vos commentaires m'ont largement éclairé sur la question.