Bonjour.

Auriez-vous sous la main un lien vers un site décrivant les règles formelles
de transformation d'une arbre AVL ?
http://fr.wikipedia.org/wiki/Arbre_AVL

Je cherche à à valider mes algorithmes pour une implémentation particulière.

J'ai déjà trouvé plein de tutos très jolis sur les principes, et même des
pseudo-règles supposant une vision humaine de l'arbre, formulées à base de
"on voit que...".
Un algorithme, ça ne "voit" pas, ça applique des règles formelles.

Ce qui m'intéresse, ce sont donc les règles de décision qui s'appliquent
formellement et itérativement, en fonction du côté d'origine, du rôle d'un
noeud et de sa balance courante, lors de la remontée pour rebalançage, après
insertion ou suppression d'un noeud.
Et également les conséquences formelles de chaque type de rotation au niveau
de la balance des noeuds impliqués.

Ces choses-là, j'en ai trouvé beaucoup moins, et avec des contradictions et
un niveau de crédibilité variable.
Auriez-vous une référence fiable ?

Merci.

--{ Patrick 'Zener' Brunet a plopé ceci: }--

> Ces choses-là, j'en ai trouvé beaucoup moins, et avec des contradictions et
> un niveau de crédibilité variable.
> Auriez-vous une référence fiable ?
>
Je ne sais pas si ça va beaucoup faire avancer, mais j'ai un
bouquin de Leendert Ammeraal "programs & data structures in C"
qui traite de ces choses-là. Hélas il est assez ancien, et
probablement épuisé, et je ne l'ai pas sous la main pour vérifier
le contenu exact pour ce sujet. Mais bon, c'est une piste...

Bonjour.

"Thierry B." <tth> a écrit dans le message de news:
c4o1l5-ei9.ln1...
> --{ Patrick 'Zener' Brunet a plopé ceci: }--
>
> > Ces choses-là, j'en ai trouvé beaucoup moins, et avec des
> > contradictions et un niveau de crédibilité variable.
> > Auriez-vous une référence fiable ?
> >
> Je ne sais pas si ça va beaucoup faire avancer, mais j'ai un
> bouquin de Leendert Ammeraal "programs & data structures
> in C" qui traite de ces choses-là. Hélas il est assez ancien, et
> probablement épuisé, et je ne l'ai pas sous la main pour vérifier
> le contenu exact pour ce sujet. Mais bon, c'est une piste...
>

Entre temps, j'ai trouvé cette page:
http://www.cmcrossroads.com/bradapp/.../AvlTrees.html

L'auteur y détaille bien sa conception, et fait apparaître les règles en
question.

Evidemment, cela inclut des choix de conception.
Par exemple: partir de valeurs de balance à +2 ou -2 laisse penser qu'il les
mettrait à jour pour déséquilibrer l'arbre, avant de les corriger par les
rotations...
Moi j'ai choisi de me fonder sur l'état d'équilibre précédent et les
paramètres de l'opération qui vient d'être réalisée.

De même, son implémentation fait que la balance se déplace avec les noeuds,
alors que pour les besoins très particuliers de mon implémentation, la
balance est calculée pour des niveaux fixes... Mais ça c'était attendu.

Donc à une transposition près, je dois trouver là de quoi vérifier les
règles que j'ai implémentées.
Sous réserve bien sûr que, malgré un engagement et un niveau de compétence
visibles, cette personne n'ait pas tout de même laissé un trou de conception
lui échapper :-)

Merci,

Bonjour,

La bibliothèque d'arbres AVL de Caml a été certifiée avec Coq.
Autrement dit les transformations qu'elle fait ont été prouvées
correctes et maintiennent les invariants requis.

Vous aurez plus d'informations sur la page suivante :
http://www.lri.fr/~filliatr/fsets/index.en.html

Cela dit, moi je me contenterais de recopier le code Caml et de
comprendre ce qu'il fait à partir de là.

Diego Olivier

Bonsoir.

<dofernandezpons> a écrit dans le message de news:
27992328-0ae7-4a7c-a7da-0441b5a3156a...
>La bibliothèque d'arbres AVL de Caml a été certifiée avec Coq.
> Autrement dit les transformations qu'elle fait ont été prouvées
> correctes et maintiennent les invariants requis.
>
> Vous aurez plus d'informations sur la page suivante :
> [..]

> Cela dit, moi je me contenterais de recopier le code Caml et
> de comprendre ce qu'il fait à partir de là.

Merci pour ce lien.

Mais vous avez raison, j'aurais dû préciser:
Mon but n'est pas de modifier un peu un code validé pour pouvoir mettre mon
nom dessus :-)

Si je me suis lancé dans une implémentation particulière, c'est parce
qu'elle doit satisfaire des contraintes spécifiques (entre autres: des
regroupements de noeuds pour factoriser des données, ca va devoir en
supporter des millions).

Evidemment, j'ai commencé par étudier à fond la théorie des AVL, mais comme
toujours, entre le cas d'école et l'implémentation optimisée de toutes les
variantes, il y a des subtilités à recenser (par exemple: les rotations qui
conservent la hauteur, en mode destruction de noeud critique).

Depuis, j'ai réussi: les rotations et le rebalancement fonctionnent, j'en
suis à l'optimisation des déplacements...

Bonjour,

> Evidemment, j'ai commencé par étudier à fond la théorie des AVL

Il n'y a pas grand chose dans la théorie des arbres AVL. En revanche
je n'ai en tête aucune référence complète sur la question. En effet,
aujourd'hui c'est un sujet qui n'intéresse plus grand monde.

Cela dit, quelques commentaires :

Il y a fondamentalement 2 façons d'implémenter les arbres AVL.
L'implémentation sauvegardant la hauteur relative et celle
sauvegardant la hauteur absolue.
La hauteur relative consiste a mettre un -1, 0 ou 1 sur un noeud selon
le côté où il penche. C'est la version en général expliquée dans les
manuels, par exemple "Elements d'algorithmique"
http://www-igm.univ-mlv.fr/~berstel/.../Elements.html (manuel sur
la toile)

La grande limitation c'est qu'il est extrêmement difficile de faire
des opérations ensemblistes sur les arbres ainsi représentés. Les
seules implémentations non triviales que je connaisse (autrement dit
qui font mieux qu'insérer le plus petit terme par terme dans le plus
grand) construisent localement la hauteur absolue pour faire le
calcul. C'est par exemple le cas de la bibliothèque AVL d'Adrian Hey
en Haskell ([url down])
ou d'une extension des arbres rouge-noirs de la STL (je trouve plus le
papier).

C'est pour cela qu'a été introduite l'implémentation en hauteur
absolue de l'arbre. Cette fois ci on ne dit pas de quel côté il
penche, mais quelle est la longueur de la plus longue branche de
l'arbre. Si on veut calculer de quel côté il penche il faut comparer
la hauteur de la sous branche gauche et la hauteur de la sous branche
droite. Ces implémentations sont en général un peu plus lentes car
elles consomment plus de mémoire et la fonction d'équilibrage est plus
compliquée. C'est l'implémentation choisie par Caml entre autres. Le
papier classique de Stephen Adams http://swiss.csail.mit.edu/~adams/BB/index.html
décrit une variante où on sauvegarde le nombre d'éléments dans l'arbre
au lieu de la longueur du plus long chemin, mais c'est
fondamentalement pareil.

Pour l'implémentation en hauteur absolue à ma connaissance il n'y a
pas de livre.

> mais comme
> toujours, entre le cas d'école et l'implémentation optimisée de toutes les
> variantes, il y a des subtilités à recenser (par exemple: les rotations qui
> conservent la hauteur, en mode destruction de noeud critique).
>
> Depuis, j'ai réussi: les rotations et le rebalancement fonctionnent, j'en
> suis à l'optimisation des déplacements...

Je ne suis pas certain de tout comprendre.


Diego Olivier

Bonjour,


* dofernandezpons in fr.comp.algorithmes:
> [...]
> C'est pour cela qu'a été introduite l'implémentation en hauteur
> absolue de l'arbre. Cette fois ci on ne dit pas de quel côté il
> penche, mais quelle est la longueur de la plus longue branche de
> l'arbre. Si on veut calculer de quel côté il penche il faut comparer
> la hauteur de la sous branche gauche et la hauteur de la sous branche
> droite. Ces implémentations sont en général un peu plus lentes car
> elles consomment plus de mémoire et la fonction d'équilibrage est plus
> compliquée. C'est l'implémentation choisie par Caml entre autres. Le
> papier classique de Stephen Adams
> [..] décrit une variante où
> on sauvegarde le nombre d'éléments dans l'arbre au lieu de la longueur
> du plus long chemin, mais c'est fondamentalement pareil.

> Pour l'implémentation en hauteur absolue à ma connaissance il n'y
> a pas de livre.

Après parcours de pas mal de volumes, j'ai pu la trouver dans :

- Rabhi & Lapalme
(http://www.iro.umontreal.ca/~lapalme/AlgoFP/start.html), et l'on peut
voir le code correspondant ici :
http://www.iro.umontreal.ca/~lapalme...er5/AVLTree.hs

- Leiss (http://www.amazon.com/dp/1584886730/), dont j'ai scanné les
pages concernées, ce qui intéressera peut-être l'initiateur du fil :
[url down]

Il ne cite pas précisément ses sources, il y a seulement une liste de
manuels, mais je les ai tous parcourus et aucun ne donne la version
des AVL par hauteur absolue ! Par contre je trouve la présentation
assez claire et la partie analyse est plutôt détaillée (je ne l'ai pas
vérifiée).

Sinon je confirme que les autres livres qui abordent les AVL (j'ai dû en
trouver une petite dizaine en remontant assez loin) utilisent
l'implémentation classique.

* Damien Wyart <damien.wyart> in fr.comp.algorithmes:
> Après parcours de pas mal de volumes, j'ai pu la trouver dans :

> - Rabhi & Lapalme
> ([..]), et l'on peut
> voir le code correspondant ici :
> [..]

En fait c'est un calcul local comme chez Hey, donc on ne peut pas
considérer que c'est une implémentation avec hauteur absolue.

Bonjour.

<dofernandezpons> a écrit dans le message de news:
aaa058d7-b0c0-42fa-94a9-ee396dc31fe5...
> [...]

Merci beaucoup pour ces références.

En fait dans mon projet, j'ai surtout besoin d'une (très) grande capacité
pour un arbre qui soit aussi navigable, et donc mes deux premiers critères
sont l'encombrement par noeud (en tenant compte de la granularité mémoire)
et les performances de la fonction de recherche.
Ceci en plus de l'utilisation de pointeurs spéciaux et diverses autres
contraintes de compatibilité...

J'utilise donc la hauteur relative.

> > mais comme toujours, entre le cas d'école et
> > l'implémentation optimisée de toutes les variantes,
> > il y a des subtilités à recenser (par exemple: les
> > rotations qui conservent la hauteur, en mode
> > destruction de noeud critique).
> >
> Je ne suis pas certain de tout comprendre.

Je faisais référence par exemple à ce cas particulier qui se présente lors
de la destruction uniquement, et qui arrête la remontée... quand on n'oublie
pas de le détecter formellement :-) Sinon, après avoir validé toutes les
rotations et l'algo d'insertion, on court un moment après cette anomalie (la
honte).

A D
/ \ / \
B x => B A
/ \ /
C D C

Mais c'est réglé maintenant.

Bonjour,

"Damien Wyart" <damien.wyart> a écrit dans le message de news:
488ee16d$0$7232$426a34cc...
>* Damien Wyart <damien.wyart> in fr.comp.algorithmes:
>> Après parcours de pas mal de volumes, j'ai pu la trouver dans :
>
>> - Rabhi & Lapalme
>> ([..]), et l'on peut
>> voir le code correspondant ici :
>> [..]
>
> En fait c'est un calcul local comme chez Hey, donc on ne peut pas
> considérer que c'est une implémentation avec hauteur absolue.
>
> --
> DW
une question pour ne pas mourrir idiot... y-a-t-il un avantage stratégique à
employer des AVL trees plutôt que des red/black trees? (c'est quoi la
différence???)
j'avais implémenté il y a un bon moment des red/black trees parce que
c'était plutôt simple et ils permettaient la suppression et l'insertion sans
modifications portant atteinte à d'éventuels itérateurs sur la collection.
et évidemment le temps de recherche/insertion en log2 n

Armel

* "Armel" <armelasselin> in fr.comp.algorithmes:
> une question pour ne pas mourrir idiot... y-a-t-il un avantage
> stratégique à employer des AVL trees plutôt que des red/black trees?
> (c'est quoi la différence???)

Voir par exemple ces discussions très détaillées :

http://groups.google.fr/group/comp.l...b8c38bace0ee5/
http://groups.google.fr/group/comp.l...eb73ec4135cf8/

La bibliothèque GNU avl de Ben Pfaff (pas encore citée dans ce fil, je
crois) a une très bonne doc expliquant pas mal de choses sur ces
structures :

http://www.stanford.edu/~blp/avl/
http://www.stanford.edu/~blp/avl/libavl.html

Les AVL y sont implémentés en hauteur relative.

Bonjour,

----- Original Message -----
From: "Damien Wyart" <damien.wyart>
Newsgroups: fr.comp.algorithmes
Sent: Tuesday, July 29, 2008 3:05 PM
Subject: Re: AVL trees / Red/Black trees?


>* "Armel" <armelasselin> in fr.comp.algorithmes:
>
> Voir par exemple ces discussions très détaillées :
>
> [..]
> [..]
>
> La bibliothèque GNU avl de Ben Pfaff (pas encore citée dans ce fil, je
> crois) a une très bonne doc expliquant pas mal de choses sur ces
> structures :
>
> [..]
> [..]
>
> Les AVL y sont implémentés en hauteur relative.
>> --
> DW
merci pour ces pointeurs: donc grosso modo: complexité similaire,
performance à l'usage similaire (mais l'insertion d'éléments déjà triés est
un cas dégradé pour le RB tree et va un peu plus lentement que l'AVL).

Armel

* Damien Wyart <damien.wyart> in fr.comp.algorithmes:
> Sinon je confirme que les autres livres qui abordent les AVL (j'ai dû
> en trouver une petite dizaine en remontant assez loin) utilisent
> l'implémentation classique.

Hé bien, je viens de tomber sur l'exception qui confirme la règle, mais
pas des moindre : le CLRS 2e édition
([url down]) ! Après vérification attentive, ce
grand classique traite bien les AVL en hauteur absolue, mais sous forme
de problème hors texte principal donc les algorithmes canoniques n'y
sont pas détaillés (ils doivent l'être dans le fascicule pour
enseignants).

Donc la réponse précédente de Diego Olivier a peut-être un peu forcé le
trait sur ce point.

Bonjour,

> une question pour ne pas mourir idiot... y-a-t-il un avantage stratégique à
> employer des AVL trees plutôt que des red/black trees? (c'est quoi la
> différence???)

La différence la plus importante c'est qu'il n'y a pas d'opérations
ensemblistes dans les arbres rouge et noirs. En effet, tout comme les
arbres AVL "locaux", la couleur d'un noeud permet de savoir comment
réequilibrer l'arbre après l'ajout ou la suppression d'un noeud, mais
pas pour unir deux arbres. La seconde différence est qu'il y a 36 000
algorithmes d'équilibrage dans les arbres rouge-noir alors qu'il y en
a qu'un seul dans les AVL.

Contrairement aux AVL il n'y a pas de moyen simple de faire une
version en hauteur absolue, car la "hauteur noire" d'un arbre n'est
pas définie de façon univoque (par exemple un arbre completement
rempli peut être completement noir ou rayé rouge et noir par niveaux).
Les seules solutions pour retomber sur ses pattes sont:
1. restreindre un peu les arbres rouge-noirs (=2-3-4) pour en faire
des arbres 2-3 et se reporter aux algorithmes correspondants (très
proches des AVL hauteur absolue)
2. faire une implémentation avec 2 entiers par noeud correspondant aux
bornes inférieure et supérieure de la hauteur noire. Ca s'appelle les
arbres arbres 1/2 équilibres. Mais là on perd tout l'avantage des
arbres rouge-noirs de n'avoir qu'un bit supplémentaire par noeud.
Encore une fois, les algorithmes ressemblent terriblement aux AVL
hauteur absolue

Voici la référence pour les arbres 1/2 équilibrés (en ce temps on ne
savait pas que c'était équivalent aux rouge-noir donc Olivié dit qu'il
a trouvé une autre classe d'arbres qui partagent les mêmes propriétés
que les rouge noirs)
A new class of balanced search trees: half-balanced binary search
trees
Olivié, Hendrik
1982
R.A.I.R.O. Theoretical Informatics vol:4 pages:417-425

La seconde différence est qu'il existe mille et un algorithmes
d'équilibrage des arbres rouge-noir. Selon l'auteur du code, on va
avoir 5 ou 27 cas différents à considérer. Alors que dans les arbres
AVL il n'est pas difficile de constater que tous les auteurs tombent
sur la même procédure de réequilibrage. C'est encore la faute à la
hauteur noire. Supposons qu'on a un arbre parfait - 1 noeud et qu'on
vient d'ajouter le noeud qu'il faut pour le compléter. On a encore
plein de coloriages différents par exemple tout noir ou a rayures
rouge et noires.

En fin de compte, toutes les approches raisonnables vont avoir une
tête d'arbre AVL en hauteur absolue, et à peu près les mêmes
performances. Ensuite c'est une question goût.

> j'avais implémenté il y a un bon moment des red/black trees
> parce que c'était plutôt simple et ils permettaient la suppression
> et l'insertion sans modifications portant atteinte à d'éventuels
> itérateurs sur la collection.
> et évidemment le temps de recherche/insertion en log2 n

C'est le cas de tous les arbres. J'ai même tendance à penser que
l'implémentation du CLR est plus compliquée que les AVL.


Diego Olivier

Bonjour,

> Après vérification attentive, ce
> grand classique traite bien les AVL en hauteur absolue, mais sous forme
> de problème hors texte principal donc les algorithmes canoniques n'y
> sont pas détaillés (ils doivent l'être dans le fascicule pour
> enseignants).

Ah ben si maintenant il faut lire la réponse aux exercices du
fascicule enseignant du CLR, en faisant une attestation sur l'honneur
qu'on va pas donner les réponses sur internet... ils feraient mieux de
mettre leur implémentation des rouge-noir avec 12 cas dans le
fascicule et les arbres AVL en hauteur absolue dans le texte !


Diego Olivier