Bonjour,

"Damien Wyart" <damien.wyart***free.fr> a écrit dans le message de news:
488ee16d$0$7232$426a34cc***news.free.fr...
>* Damien Wyart <damien.wyart***free.fr> in fr.comp.algorithmes:
>> 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
>
> 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

Bonjour,

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


>* "Armel" <armelasselin***hotmail.com> 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.
>
>
> --
> 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