[Caml-list] Arbres rouge et noir

[Caml-list] Arbres rouge et noir

[Diego Olivier Fernandez Pons]

    Bonjour,

Vous avez appris puis enseigné les arbres rouge et noir dans la
douleur ? Vous avez cru Okasaki sur parole quand il expliquait dans un
article sur Patricia que les arbres rouge et noir ne sauraient servir
dans des applications utilisant des opérations ensemblistes ?

Eh bien oubliez tout cela et utilisez Baire :
le module LayeredRedBlackSet contient désormais une implémentation
efficace des arbres rouge et noir et en particulier des opérations
ensemblistes

Avec un peu d'attention on se rend compte que ce module est tout à
fait semblable à celui des arbres AVL (AvlSet). En effet, la seule
différence entre les arbres rouge et noir et les arbres AVL est la
fonction de hauteur

  let height = function
   | E -> 0
   | N (l, v, r, h) -> 1 + max (height l) (height r)

contre

  let height = function
   | E -> 0
   | N (l, v, r, h) -> 1 + min (height l) (height r)

Il en est de même pour les arbres pondérés (weight balanced)

  let height = function
   | E -> 0
   | N (l, v, r, h) -> 1 + (height l) + (height r)


Pour créer votre propre schéma de balancement il suffit donc de
 
 i) choisir votre fonction de hauteur

 ii) écrire la fonction makeBTree de balancement pour la hauteur
minimale : 15 lignes dans les 3 exemples proposés dans Baire 

(AVL et weight balanced sont semblables, en réalité il semble y avoir
2 classes selon que la fonction de hauteur est croissante ou
strictement croissante)

 iii) en déduire la fonction makeSTree de balancement pour une
différence de hauteur quelconque (on peut l'obtenir automatiquement
par répétition de makeSTree mais autant la simplifier un peu) 15
lignes

 iv) copier-coller le reste du fichier, compiler, exécuter

Où est passée toute la douleur des arbres rouge et noir ? (les 5 types
de rotations différentes de chaque côté, les fonctions de suppression
des conflits rouges, des surpoids noirs ...)

Le formalisme bicolore de Sedgewick et Guibas et aux arbres rouge et
noir stratifiés noir la même chose que l'implémentation des arbres AVL
en hauteur relative (-1, 0, 1) est à leur implémentation en hauteur
absolue (comme dans la stdlib) : même causes, mêmes effets

- une accélération des insertions et suppressions
- un ralentissement considérable des opérations sur les ensembles
(comment unir deux arbres de hauteurs différentes si on ne connaît que
la hauteur relative des sous-branches ?) 
- un accroissement considérable de la complexité des fonctions


De surcroit, l'implémentation des arbres en hauteur absolue vous
permet d'obtenir à peu d'efforts des arbres relaxés (et k-relaxés)

L'idée est simplement qu'au lieu de rebalancer à chaque opération
d'insertion ou suppression, on peut rebalancer globalement l'arbre à
la fin des modifications.

L'examen du cas rouge et noir permet de se rendre compte que la
fonction de hauteur dans le cas relaxé est en réalité

  let height = function
    | E -> 0
    | N (l, v, r, h) -> 
	let hl = height l and hr = height r in
	max (1 + min hl hr) (max hl rh)

Pour reconstruire l'arbre il suffit ensuite de localiser les noeuds
dont les deux sous-arbres sont bien formés mais qui eux sont mal
formés (une violation) et de leur appliquer makeSTree


deux solutions sont possibles :

- marquer les violations lors des insertions relaxées (cela suppose un
petit changement de représentation et sera proposé ultérieurement)

- reconstruire tout l'arbre

 la fonction suivante convient

  let rebuild = function
    | E -> E
    | N (l, v, r, _) -> makeSTree (rebuild l) v (rebuild r)

Bien sûr, nous fournissons une fonction qui ne reconstruit pas
l'arbres si cela n'est pas nécessaire vérifiant donc rebuild a == a
(si a est équilibré) 

On peut facilement obtenir à partir de la des structures de données
concurrentes par des méthodes de propagations comme celles utilisées
par Bougé et alii (voir références Baire) : il suffit de propager à la
fois la hauteur réelle et la hauteur apparente (= hauteur relaxée) et
de reconstruire quand elles diffèrent


Conclusion :

Baire propose deux mécanismes d'insertions/suppressions :
- rééquilibrage à chaque opération / pas de réequilibrage global
- pas de rééquilibrage entre les opérations / rééquilibrage global

Nous espérons pouvoir proposer une procédure intermédiaire à l'avenir

Enfin, il nous semble inutile de continuer à torturer des étudiants
avec des optimisations compliquées comme celle de Sedgewick et Guibas.
Au lieu, Baire prone la généricité et la réutilisabilité.

Baire fournit bien évidemment à l'usage des masochistes et
tortionnaires une implémentation classique des arbres rouge et noirs
dans le module RedBlackSet (5 cas dans les insertions, 18 cas dans les
suppressions, etc.)


        Diego Olivier


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners