Discussion :

[matt92700]

Bonjour,
Je possède une structure qui contient des elements de type chaine de caractères , je les ai ensuite disposé dans un arbre binaire et je souhaiterai et c'est là qu'est mon prblème trier ces sructures par ordre alphabetique(donc suivant un de ses elements) dans cet arbre. Je sais qu'il faut que j'utilise un algorithme avec de la recursivité mais je n'y arrive pas. Je programmerai ensuite tous ça en langage c.

Merci de m'aider à résoudre ce problème.

[Steki-kun]

Si tu le peux, lorsque tu insères les structures dans l'arbre, insère les "intelligemment", de manière à créer un arbre binaire de recherche : toutes les structures à gauche sont plus 'petite' que la racine, le contraire à droite, et les deux arbres fils sont eux-mêmes des arbres binaires de recherche. Comme ça il est déjà trié après.

Sinon, tu peux toujours créer un nouvel arbre à partir du premier en réinsérant tout le monde après coup de cette manière, et tu libères l'ancien arbre (mais pas les structures hein ). Honnêtement, en comparaison, trier un arbre 'en place' c'est plutôt technique donc tu perdras rien à en refaire un.

[matt92700]

ok merci steki kun tu es toujours le premier ;-) c'est cool

Ok, je crois que je vais créer un deuxième arbre alors car en fait dans ma structure j''ai en plus un identifiant de type entier(dsl de ne pas l'avoir précisé) et dans l'arbre c'est dejà trié par identifiant, et je souhaite ensuite, pouvoir retrier selon un element de type chaine de carctère qui se trouve dans ma structure)

Bref, si j'ai bien compris il me suffit de chercher dans le premier arbre la plus petite chaine de la mettre a la racine de l'autre arbre puis de chercher la deuxième plus petite la mettre a la fin du 2ème arbre etc...et ainsi de suite!

Ok j'y avait pas pensé et c'est vrai que ça m'a l'air beaucoup plus simple comme ça!
car je galèrait franchement pour tout trier sur place!

[Steki-kun]

Bref, si j'ai bien compris il me suffit de chercher dans le premier arbre la plus petite chaine de la mettre a la racine de l'autre arbre puis de chercher la deuxième plus petite la mettre a la fin du 2ème arbre etc...et ainsi de suite!

non ne le crée pas comme ça !!
Tu prends un arbre vide
Tu prends la racine, tu l'insères dans ton arbre vide. Elle devient donc.. racine !
Ensuite, recursivement, tu prends le sous arbre gauche et le sous arbre droit et tu insères les éléments dans ton nouvel arbre, comme ils viennent.

Alors comment insérer un élément donné dans ton nouvel arbre ?
Récursivement, s'il est plus petit que la racine, tu l'insères dans le sous arbre gauche. S'il est plus grand, tu l'insères recursivement dans l'arbre droit. Quand tu arrives au bout d'une branche, tu laisses ton élément ici.

comme ça tu crées ton nouvel arbre par une simple descente à chaque fois, et sans tri sur l'arbre initial, c'est en O(n.ln n) où n est le nombre de structures. Si tu avais trié à chaque fois, tu aurais au minimum O(Somme sur p de 1 à n des pLog p, et c'est beaucoup moins bien !).

bon courage, et au pire, tu peux trouver des implémentations ou des explications avec schéma sur google, c super classique

[Steki-kun]

j'ai oublié de préciser : ton arbre de recherche est optimal s'il est 'bien balancé' donc en gros que la racine est un élément médian pour tout ton ensemble de structures, ni trop petit ni trop gros, et ainsi de suite récursivement dans chaque sous arbre !
Donc si tu as un moyen facile pour les premières insertions de mettre des éléments moyens ou d'éviter au pire les éléments extrémaux, fais le, ca sera un petit plus mais c pas nécessaire

[matt92700]

a oui ok c'est vrai que ce sera plus efficace de faire comme ça ...lol
mais aussii plus dur à faire surtout que j'ai vraiment du mal avec la récursivité.
Enfin, avec tes explications je pense que j'y arriverait.
Par contre j'ai pas bien compris quand tu parle d'eléments extrémaux et moyens tu veut dire de réaliser un arbre parfaitement équilibré c'est ça?

[matt92700]

a non je crois que je vien de capter c'est pour l'efficacité dans le parcours de l'arbre si dans l'arbre je met à la racine la chaine qui se trouve être à peu près la chaine du milieu(au niveau des positions des chaines dans l'odre alphabétique) et bien le parcours sera encore plus efficace?

[Steki-kun]

exactement!
en fait tu n'es pas obligé mais c'est l'idéal ! L'algorithme marche très bien si tu insères les éléments dans un ordre quelconque, mais ensuite si tu veux rechercher un élément, c'est plus rapide dans un arbre équilibré que dans un arbre 'en peigne'.
Donc, en général, on insère dans un ordre quelconque, mais quand on a une manière peu coûteuse de choisir des elements ni trop petits ni trop grands en premier, on le fait

Honnetement, ne t'en occupe pas pour l'instant si l'algorithme récursif te pose problème, attele toi plutôt à celui-ci et tu verras après !

[matt92700]

oups au 2ème coup jai dit une connerie en effet si je fai ça ça ne sera plus trier lol nimporte quoi...


Bref, jte remercie !!!

et jvai essayer de faire ce truc là alors . par contre sur google j'ai trouvé des algorithmes de tri mais c'est seulement sur des tableaux alors ça ne m'interessent pas...
Enfin, bon encore merci ;-)

[Steki-kun]

non les deux sont justes, du moins comme je les comprends moi :
* l'algo de recherche dans ton arbre trié, ensuite, est plus efficace si l'arbre est équilibré (s'il est complet par exemple)
* pour que l'arbre soit quiilbré, il faut qu'il y ait autant d'éléments plus petits et plus grands que la racine, et ce récursivement pour les sous arbres gauche et droit, donc avec des nombres de 0 à 100 par exemple, l'idéal serait de mettre 50 en premier, puis d'insérer 75 ou 25 ou les deux et ainsi de suite

[Steki-kun]

par contre sur google j'ai trouvé des algorithmes de tri mais c'est seulement sur des tableaux alors ça ne m'interessent pas...

ce sont des algos sur les tas, c'set à dire des arbres particuliers. Ces arbres là peuvent être avantageusement décrit par un tableau, et on fait un tri tas Pour ton truc là, cherche plutôt ABR comme arbre binaire de recherche.

Enfin, bon encore merci ;-)

De rien!

[matt92700]

ok d'accord j'ai maintenant bien compris mais par contre si je veut réaliser un affichage il faudra que je parcours l'arbre d'une façon particulière non?

parce que sinon ça sera pas affiché dans l'ordre il faudra que je commence par lélement tout en bas à gauche et que je remonte comme il faut aie aie aie ça se complique je sais pas si jvai y arriver...lol

D' ou la première idée qui m'est venue qui est je te l'accorde beaucoup moins efficace c'est vrai.
Enfin , je vais essayer de faire comme tu m'a dit quand même mais je commence à douter de ma réussite lol

[matt92700]

Et pour STEKI-KUN :

Merci ;-)

[Steki-kun]

c'est très simple pour afficher !!!

C'est un parcours préfixe ! D'abord le sous-arbre droit, puis la racine, puis le sous arbre gauche !

genre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
// Ceci est du pseudo-code (* et ceci est un pseudo-commentaire :) *)
void printTriee(Arbre a) {
 if(a==NULL) return;
 printTriee(a->filsGauche);
 print_noeud(a->noeud); //affiche une structure proprement dite
 printTriee(a->filsDroite);
}

et si tu veux afficher dans le sens décroissant, tu fais un parcours dans l'autre sens avec droit en premier !
Cette fois, faut qu'jy aille, bonne soirée.

[matt92700]

Merci à toi aussi