Equilibrer un arbre binaire... [Algo] - Programmation
Marsh Posté le 10-04-2002 à 15:30:57
bah, j'ai fait ça, mais y'a longtemps, en C..
Je regarderais si j'ai ça ici, mais il se peut que je ne l'aie que chez mes parents, avec mes cours..
Marsh Posté le 10-04-2002 à 15:42:40
regarde toujours ici :
http://www.enseignement.polytechni [...] copie-1.6/
Marsh Posté le 10-04-2002 à 16:01:15
j'avai fait ca en cours c'était chiant je me souviens plus...
Marsh Posté le 10-04-2002 à 16:46:36
vas voir sur le site de Vincent Delaval, étudiant en informatique
(fais une recherche sur son nom). Y'a des cours avec les algos.
Marsh Posté le 10-04-2002 à 17:03:23
mais bon, sinon, tu peuxaussi essayer de faire le tien, à mon avis, ce sera plus formateur...
Le nôtre, il "maintenait" l'arbre équilibré au fur et à mesure qu'on y ajoutait des valeurs.
Marsh Posté le 10-04-2002 à 19:05:38
il y a des methodes plus ou moins rapides.
La plus simple a concevoir c'est celle-ci:
tu as une liste ordonnée de tes valeurs.
Le noeud le plus haut c'est la valeur mediane (pas la moyenne
mais la mediane !) de telle sorte qu'il y ait autant de noeuds d'un cote que de l'autre de ton noeud pere (ou pas plus d'un noeud de difference).
et puis ensuite tu procedes d'un cote et de l'autre de maniere identique recursivement et voila, tu as un arbre balance..
LEGREG
Marsh Posté le 10-04-2002 à 19:39:49
merci Legreg j'vait pensé à un truc comme ça, par contre lors de la réalisation j'ai bloqué. Mais bon apparement c'est possible donc faut que je m'y remette.
Marsh Posté le 10-04-2002 à 20:17:58
Rasta Knight a écrit a écrit : merci Legreg j'vait pensé à un truc comme ça, par contre lors de la réalisation j'ai bloqué. Mais bon apparement c'est possible donc faut que je m'y remette. |
moi aussi javé fait ca ya keke tps mais je me rappelle pu de l'algo en tt k c po bien mechant
Marsh Posté le 10-04-2002 à 23:49:32
legreg a écrit a écrit : il y a des methodes plus ou moins rapides. La plus simple a concevoir c'est celle-ci: tu as une liste ordonnée de tes valeurs. Le noeud le plus haut c'est la valeur mediane (pas la moyenne mais la mediane !) de telle sorte qu'il y ait autant de noeuds d'un cote que de l'autre de ton noeud pere (ou pas plus d'un noeud de difference). et puis ensuite tu procedes d'un cote et de l'autre de maniere identique recursivement et voila, tu as un arbre balance.. LEGREG |
houlà, je crois pas que ce soit la bonen méthode : tu perds du temps à chercher la médiane!!
Il me semble qu'il serait plus judicieux de placer les valeurs dans l'arbre les unes après les autres, en trouvant l'algo de placement qui équilibre l'arbre....Je sais que c possible, je l'avais fait, mais j'ai malheureusement pas mes cours ici...Par contre, je dois avoir le code...Je regarde ça demain matin..
Marsh Posté le 10-04-2002 à 23:55:47
gfive a écrit a écrit : houlà, je crois pas que ce soit la bonen méthode : tu perds du temps à chercher la médiane!! Il me semble qu'il serait plus judicieux de placer les valeurs dans l'arbre les unes après les autres, en trouvant l'algo de placement qui équilibre l'arbre....Je sais que c possible, je l'avais fait, mais j'ai malheureusement pas mes cours ici...Par contre, je dois avoir le code...Je regarde ça demain matin.. |
tien on avait fait l'algo de Hepa Sort en DEUG2 mais je c pu komment ca marche c trop loin et je c pu comment ca trie
Marsh Posté le 11-04-2002 à 00:46:09
il y a les 'splay trees' :
http://www.google.com/search?q=splay+trees
http://www.cs.nyu.edu/algvis/java/index.html
"Splay Trees were invented by Sleator and Tarjan. This data structure is essentially a binary tree with special update and access rules. It has the wonderful property to adapt optimally to a sequence of tree operations. "
Marsh Posté le 10-04-2002 à 15:24:21
voilà, je dois écrire une procédure qui prenne en entrée un arbre binaire "en boxon" et en ressorte un autre équilibré. Le problème c'est que je ne vois pas du tout comment faire
Si qqn pouvait ne serait-ce que me mettre sur la voie ça m'arrangerait bien
PS : rien trouver avec Google ou ici
---------------
Le tout c'est d'y croire! DaBZHWDT site : www.setibzh.com