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