[Algo] Equilibrer un arbre binaire...

Recherche :

Dernière réponse
Sujet : [Algo] Equilibrer un arbre binaire...
youdontcare	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. "

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

youdontcare

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. "

verdoux

Oui, les arbres AVL, on fait plus ça en 1ere S ?

Dj_Jim

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 :ange:

gfive

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..

Dj_Jim

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

Rasta Knight

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.

LeGreg

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

gfive

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.

hebe	vas voir sur le site de Vincent Delaval, étudiant en informatique (fais une recherche sur son nom). Y'a des cours avec les algos.

j'avai fait ca en cours c'était chiant je me souviens plus...

ethernal

regarde toujours ici :
http://www.enseignement.polytechni [...] copie-1.6/

redant

Fais une recherche sur les arbres AVL

gfive

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..

Rasta Knight

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 :hello:

PS : rien trouver avec Google ou ici :(