 |
||
| ||
| |||||
| Dernière réponse | |
|---|---|
| Sujet : les arbres binaires | |
| swich | l'hammeral, ok, je le note.
j'espere qu'il est en francais... merci bien :bounce: |
| Aperçu |
|---|
| Vue Rapide de la discussion |
|---|
| swich | l'hammeral, ok, je le note.
j'espere qu'il est en francais... merci bien :bounce: |
| mystereetbouledegomme | L'Hammeral est un "bon" bouquin d'algorithmique. Tu y trouveras tout ce que tu veux sur les arbres et le rebalancement(reequilabrage si tu veux). Tu as pense a l'implementation d'un arbre dans un vecteur? |
| zeltron | Pour les arbres binaires équilibrés c'est un peu plus compliqué je vais juste te donner quelque indications car je n'ai pas le temps et tu pourras réfléchir un peu dessus :
il faut que tu change ta structure d'arbre en {arbre *gauche; arbre *droit; arbre *pere; int coefficient_de_desequilibre} où coefficient_de_desequilibre est la différence entre la hauteur du fils droit et celle du fils gauche par exemple pour un arbre équilibré (en hauteur) ca vaudra donc -1 0 ou 1 Il te faudra utiliser quatre petites fonctions élémentaires: arbre gauche_gauche(arbre a) { if (a != NULL) {arbre temp = a-> droit; a->droit = temp->gauche; temp->gauche=a; a=temp; } return a; } Sur le meme principe tu construits la fonction droit_droit. Ensuite; arbre gauche_droit(arbre a) {a->gauche = gauche_gauche(a->gauche); return droit_droit(a); } Sur le même principe tu construits la fonction droit_gauche. Il te reste plus qu'à insérer tes éléments en utilisant ton coefficient de désiquilibre et tes quattre petites fonctions. Je te conseille sérieusement de faire des schémas pour comprendre ce que font tes 4 fonctions et comment les utiliser. (Après à toi de mater ton cours de Scheme pour implémenter l'algo) [edit]--Message édité par zeltron--[/edit] |
| swich | ok merci bien zetes gentil les gars mais bon, mon pb c'est en scheme...
mais bon merci qd meme ca m'aide. comment peut on construire un arbre binaire equilibre??? |
| BifaceMcLeOD | legreg> Le problème du C, c'est que ce genre de boucle n'est pas super lisible, parce qu'on ne voit pas très bien le ou les endroits où on quitte la boucle. Dans ces cas-là, j'utilise 2 macros toutes simples qui éclaircissent pas mal le code (à mon avis) :
#define forever() for( ; ; ) #define EXIT_WHEN(condition) if (condition) break En les utilisant, le code ci-dessus devient : ajoute(insere, ref racine) { if (racine == null) { racine = nouveau noeud (insere, null, null); } else { courant = racine; forever() { if (courant->valeur > insere) { if (courant->filsgauche == null) { courant->filsgauche = nouveau noeud(insere, null, null); EXIT_WHEN(true); } else { courant = courant->filsgauche; } } else { if (courant->filsdroit == null) { courant->filsdroit = nouveau noeud(insere, null, null); EXIT_WHEN(true); } else { courant = courant->filsdroit; } } } } } Sinon, juste pour le plaisir de critiquer ;) , pour obtenir un code le plus lisible possible, il vaut mieux limiter l'imbrication du code, et factoriser au maximum le code. Je proposerai donc la réécriture du code de legreg suivante : ajoute(insere, ref racine) { if (racine == null) { racine = nouveau noeud (insere, null, null); return; } courant = racine; var pfils_courant; // On déclare une variable de type "pointeur sur le type de courant". forever() { if (courant->valeur > insere) { pfils_courant = &courant->filsgauche; } else { pfils_courant = &courant->filsdroit; } if (*pfils_courant == null) { *pfils_courant = nouveau noeud(insere, null, null); EXIT_WHEN(true); } else { courant = *pfils_courant; } } } [edit]--Message édité par BifaceMcLeOD--[/edit] |
| LeGreg | Une methode toujours efficace c'est de passer par des boucles conditionnelles, ce qui est efficace quel que soit
le compilateur utilise: ajoute(insere, ref racine) { if (racine == null) { racine = nouveau noeud (insere, null, null); } else { courant = racine; while (true) { if (courant->valeur > insere) { if (courant->filsgauche == null) { courant->filsgauche = nouveau noeud(insere, null, null); break; } else { courant = courant->filsgauche; } } else { if (courant->filsdroit == null) { courant->filsdroit = nouveau noeud(insere, null, null); break; } else { courant = courant->filsdroit; } } } } } Legreg |
| LeGreg | exemple recursif non terminal:
compter (n) { if (n>0) return compter(n-1)+1; else return 0; } Le meme en recursif terminal: compter (n, res) { if (n>0) return compter(n-1,res+1); else return res; } et il faut l'initialiser par un compter(n,0); Tu remarqueras que dans le premier cas, il est necessaire de memoriser le contexte d'appel de compter() puisqu'au retour de la fonction il faudra encore effectuer l'operation +1 sur la valeur de retour. Dans le deuxime cas par contre, pas besoin de stocker ce contexte d'appel. en effectuant le calcul pour n avec la premiere methode, tu mets n procedures en attente, tandis qu'avec la deuxieme, chaque procedure passe le bebe a la suivante et ne doit rien attendre. A+ LEGREG |
| swich | ah :(
ben c'est pas cool ca car je comprend pas..., pourtant la recursivite, j'ai pas de pb.. |
| verdoux | L'algo donné est en récursivité terminale. |
| swich | hein ??? |
| verdoux | Elle est pas terminale mais récursivité ? |
| swich | le principe c'est bon j'ai compris, mais c'est pour ce qui est de la construction de l'arbre...
verdoux a resume l'algo en recursif normale, mais bon comme je travaille avec des grosses liste... la recursivite terminale, je crois que c'est ce qu'il y'a de mieux.et c la que ca plante. j'y arrive pas. donc c'est ce que je demandais, une explication pour la recursivite terminale. pff ca fait 1semaine que je suis sur ce pb ca commence a me peter les c@@@@@@s.... |
| verdoux | Si les noeud de ton arbres ont la structure suivante:
- valeur v - référence/pointeur sur noeud gauche rng - référence/pointeur sur noeud gauche rnp alors tu peux utiliser la procédure suivante: ajout( nouvelle valeur nv, référence sur un noeud rn): si (nv > rn-> v) alors si (rn->rnd vide) alors créer une feuille avec la valeur nv et affecter à rn->rnd une réference vers cette feuille sinon ajoute(nv, rn->rnd) sinon .... // la même chose avec le noeud fils gauche |
| swich | ben le principe, c'est bon.
il me faudrait l'algo (pour le construire en normal, c'est bon, mais c'est pour le construire en recursivite terminale, et la j'ai du mal...j'y arrive pas. si qq'un connait, comment faire pour eviteer l'erreur : error : could not grow, sous emacs ??? |
| gizmo | watouwatou >> très douteux comme humour :sweat: Sinon, ddr555 a bien expliqué le bazard, mar swich, tu ne nous as toujours pas expliquer ce que tu veux EXACTEMENT, s'il s'agit du principe, de l'implémentation, de l'algo général, du rebalancement de l'arbre... |
| ddr555 | bon pour résumer, je dirai que c'est uns structure de données destinée à trier les éléments pour accélérer l'insertion et la recherche de données.
dans le cas des binaires, il y a au plus deux fils, et on détermine en fonction d'un ordre de tri le placement dans l'arbre ( généralement, c'est l'ordre > ou < qui est utilisé ). par exemple dans le cas d'un arbre stockant des entiers, on détermine la place dans l'arbre en testant les valeurs dans le noeud courant, si c'est supérieur on cherche dans l'arbre droit, si c'est supérieur on cherche dans l'arbre gauche. donc cela doit donner pour insérer un élément, on cherche d'abord dans la racine. si y'a rien dans la racine, alors on crée l'élément dans la racine. sinon, on teste avec la valeur et si la valeur est supérieure à la valeur de la racine, on regarde si il y a quelquechose dans le fils droit. si y'a rien on crée la valeur dans le fils droit, sinon on reprend le cas de figure racine. si c'est inférieur, on fait le même test que juste au dessus. ceci est un algorithme récursif qui te permettra d'insérer des valeurs dans un arbre binaire de recherche. pour rechercher une valeur, c'est exactement le même algorithme, sauf qu'on insère rien. pour afficher la liste, on affiche d'abord le fils gauche, puis la racine, puis le fils droit. lorsqu'on tombe sur une feuille ( c'est à dire un noeud sans fils ) on affiche la valeur et basta. pour supprimer un élément, c'est un peu plus compliqué, mais si tu as déjà compris le principe de l'arbre binaire, tu trouveras comment supprimer. principal inconvénient des arbres binaires de recherche : tu n'es pas sur d'avoir un arbre bien équilibré ( comme celui que tu as fourni en exemple ). par contre là, pour rééquilibrer l'arbre, c'est nettement plus compliqué. si tu n'as rien compris à ce que je viens de dire, ou que tu ne sais pas comment fonctionnent les pointeurs pour faire un arbre binaire de recherche, n'hésites pas à reposer d'autres questions. |
| wouatouwouatou | ben... voila, c kom dans les camps avec ls juifs ...
Les femmes a gauche et les hommes a droite :D |
| swich | vi c'est ca.
mais bon ca je le savais.... |
| BlackLotus | Alors un arbre binaire en programmation fonctionnel c'est
(la notation) (/G,r,D\) avec G partie Gauche, r racine et D partie Droite G et D sont considéré comme racines de sous-arbres binaires En partant d'une racine, il ne peux y avoir que deux branches dans un arbre binaire. |
| swich | vi arbre binaire de recherche sur des chaine de caractere.
ex : a \ an \ annuel / anne etc [edit]--Message édité par swich--[/edit] |
| nabab | Tu veux dire binaire ?
Arbre binaire de recherche ? |
| gizmo | précise ce que tu veux... |
| swich | qq'un pourrait m'expliquer comment ca marche...
parce que la je capte rien du tout... [edit]--Message édité par swich--[/edit] |
