From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA00262; Mon, 16 Sep 2002 14:51:29 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id OAA00339 for ; Mon, 16 Sep 2002 14:51:28 +0200 (MET DST) Received: from shiva.jussieu.fr (shiva.jussieu.fr [134.157.0.129]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g8GCpR910278 for ; Mon, 16 Sep 2002 14:51:27 +0200 (MET DST) Received: from ibm3.cicrp.jussieu.fr (ibm3.cicrp.jussieu.fr [134.157.15.3]) by shiva.jussieu.fr (8.12.5/jtpda-5.4) with ESMTP id g8GCpQjR038031 for ; Mon, 16 Sep 2002 14:51:27 +0200 (CEST) Received: from ibm1.cicrp.jussieu.fr (ibm1.cicrp.jussieu.fr [134.157.15.1]) by ibm3.cicrp.jussieu.fr (8.8.8/jtpda/mob-V8) with ESMTP id OAA34464 for ; Mon, 16 Sep 2002 14:49:49 +0200 Received: from localhost (fernande@localhost) by ibm1.cicrp.jussieu.fr (8.8.8/jtpda/mob-v8) with SMTP id OAA69674 for ; Mon, 16 Sep 2002 14:49:48 +0200 Date: Mon, 16 Sep 2002 14:49:48 +0200 (DST) From: Diego Olivier Fernandez Pons To: caml-list@inria.fr Subject: [Caml-list] Arbres rouge et noir Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=iso-8859-1 Content-Transfer-Encoding: QUOTED-PRINTABLE X-Antivirus: scanned by sophie at shiva.jussieu.fr Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Bonjour, Vous avez appris puis enseign=E9 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=E9rations ensemblistes ? Eh bien oubliez tout cela et utilisez Baire : le module LayeredRedBlackSet contient d=E9sormais une impl=E9mentation efficace des arbres rouge et noir et en particulier des op=E9rations ensemblistes Avec un peu d'attention on se rend compte que ce module est tout =E0 fait semblable =E0 celui des arbres AVL (AvlSet). En effet, la seule diff=E9rence entre les arbres rouge et noir et les arbres AVL est la fonction de hauteur let height =3D function | E -> 0 | N (l, v, r, h) -> 1 + max (height l) (height r) contre let height =3D function | E -> 0 | N (l, v, r, h) -> 1 + min (height l) (height r) Il en est de m=EAme pour les arbres pond=E9r=E9s (weight balanced) let height =3D function | E -> 0 | N (l, v, r, h) -> 1 + (height l) + (height r) Pour cr=E9er votre propre sch=E9ma de balancement il suffit donc de =20 i) choisir votre fonction de hauteur ii) =E9crire la fonction makeBTree de balancement pour la hauteur minimale : 15 lignes dans les 3 exemples propos=E9s dans Baire=20 (AVL et weight balanced sont semblables, en r=E9alit=E9 il semble y avoir 2 classes selon que la fonction de hauteur est croissante ou strictement croissante) iii) en d=E9duire la fonction makeSTree de balancement pour une diff=E9rence de hauteur quelconque (on peut l'obtenir automatiquement par r=E9p=E9tition de makeSTree mais autant la simplifier un peu) 15 lignes iv) copier-coller le reste du fichier, compiler, ex=E9cuter O=F9 est pass=E9e toute la douleur des arbres rouge et noir ? (les 5 types de rotations diff=E9rentes de chaque c=F4t=E9, les fonctions de suppression des conflits rouges, des surpoids noirs ...) Le formalisme bicolore de Sedgewick et Guibas et aux arbres rouge et noir stratifi=E9s noir la m=EAme chose que l'impl=E9mentation des arbres AV= L en hauteur relative (-1, 0, 1) est =E0 leur impl=E9mentation en hauteur absolue (comme dans la stdlib) : m=EAme causes, m=EAmes effets - une acc=E9l=E9ration des insertions et suppressions - un ralentissement consid=E9rable des op=E9rations sur les ensembles (comment unir deux arbres de hauteurs diff=E9rentes si on ne conna=EEt que la hauteur relative des sous-branches ?)=20 - un accroissement consid=E9rable de la complexit=E9 des fonctions De surcroit, l'impl=E9mentation des arbres en hauteur absolue vous permet d'obtenir =E0 peu d'efforts des arbres relax=E9s (et k-relax=E9s) L'id=E9e est simplement qu'au lieu de rebalancer =E0 chaque op=E9ration d'insertion ou suppression, on peut rebalancer globalement l'arbre =E0 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=E9 est en r=E9alit=E9 let height =3D function | E -> 0 | N (l, v, r, h) ->=20 =09let hl =3D height l and hr =3D height r in =09max (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=E9s mais qui eux sont mal form=E9s (une violation) et de leur appliquer makeSTree deux solutions sont possibles : - marquer les violations lors des insertions relax=E9es (cela suppose un petit changement de repr=E9sentation et sera propos=E9 ult=E9rieurement) - reconstruire tout l'arbre la fonction suivante convient let rebuild =3D function | E -> E | N (l, v, r, _) -> makeSTree (rebuild l) v (rebuild r) Bien s=FBr, nous fournissons une fonction qui ne reconstruit pas l'arbres si cela n'est pas n=E9cessaire v=E9rifiant donc rebuild a =3D=3D a (si a est =E9quilibr=E9)=20 On peut facilement obtenir =E0 partir de la des structures de donn=E9es concurrentes par des m=E9thodes de propagations comme celles utilis=E9es par Boug=E9 et alii (voir r=E9f=E9rences Baire) : il suffit de propager =E0= la fois la hauteur r=E9elle et la hauteur apparente (=3D hauteur relax=E9e) et de reconstruire quand elles diff=E8rent Conclusion : Baire propose deux m=E9canismes d'insertions/suppressions : - r=E9=E9quilibrage =E0 chaque op=E9ration / pas de r=E9equilibrage global - pas de r=E9=E9quilibrage entre les op=E9rations / r=E9=E9quilibrage globa= l Nous esp=E9rons pouvoir proposer une proc=E9dure interm=E9diaire =E0 l'aven= ir Enfin, il nous semble inutile de continuer =E0 torturer des =E9tudiants avec des optimisations compliqu=E9es comme celle de Sedgewick et Guibas. Au lieu, Baire prone la g=E9n=E9ricit=E9 et la r=E9utilisabilit=E9. Baire fournit bien =E9videmment =E0 l'usage des masochistes et tortionnaires une impl=E9mentation 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