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.lang.c++.moderated/browse_thread/thread/fa5b8c38bace0ee5/
http://groups.google.fr/group/comp.lang.c++.moderated/browse_thread/thread/13feb73ec4135cf8/

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