Universite Libre de BruxellesFaculte des SciencesDepartement d’Informatique

Arbres binaires de rechercheoptimaux et quasi-optimaux

Memoire presente par Gabriel Kalyonen vue de l’obtention du grade deLicencie en Informatique.

Annee academique 2005-2006.

Table des matieres

1 Introduction 5

I Fondements et definitions 7

2 Arbres binaires et complexite 82.1 Arbres binaires . . . . . . . . . . . . . . . . . . . . . . . . . . 8

2.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . 82.1.2 Profondeur d’un nœud . . . . . . . . . . . . . . . . . . 92.1.3 Hauteur d’un nœud . . . . . . . . . . . . . . . . . . . . 92.1.4 Rotations . . . . . . . . . . . . . . . . . . . . . . . . . 9

2.2 Arbres binaires de recherche . . . . . . . . . . . . . . . . . . . 112.2.1 Modele . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2.2 Classes d’arbres binaires de recherche . . . . . . . . . . 13

2.3 Performances asymptotiques . . . . . . . . . . . . . . . . . . . 142.3.1 Notation O(.) . . . . . . . . . . . . . . . . . . . . . . . 152.3.2 Notation !(.) . . . . . . . . . . . . . . . . . . . . . . . 152.3.3 Notation "(.) . . . . . . . . . . . . . . . . . . . . . . . 152.3.4 Lien entre les notations asymptotiques . . . . . . . . . 15

2.4 Complexite . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.4.1 Complexite au pire cas . . . . . . . . . . . . . . . . . . 162.4.2 Complexite moyenne . . . . . . . . . . . . . . . . . . . 162.4.3 Complexite amortie . . . . . . . . . . . . . . . . . . . . 17

2.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Proprietes des arbres binaires de recherche 193.1 Relations entre les proprietes . . . . . . . . . . . . . . . . . . . 193.2 Static finger . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.3 Optimalite statique . . . . . . . . . . . . . . . . . . . . . . . . 213.4 Working set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.5 Dynamic finger . . . . . . . . . . . . . . . . . . . . . . . . . . 22

1

3.6 Unifiee . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233.7 Optimalite dynamique . . . . . . . . . . . . . . . . . . . . . . 243.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

II Arbres binaires de recherche particuliers 26

4 Arbres Binaires de Recherche Optimaux 274.1 Generalites . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.2 Algorithme exhaustif . . . . . . . . . . . . . . . . . . . . . . . 294.3 Algorithme de Knuth . . . . . . . . . . . . . . . . . . . . . . . 294.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

5 Arbres binaires de recherche equilibres 325.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325.2 Arbres rouges-noirs . . . . . . . . . . . . . . . . . . . . . . . . 32

5.2.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 335.2.2 Recherche . . . . . . . . . . . . . . . . . . . . . . . . . 335.2.3 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . 335.2.4 Successeur . . . . . . . . . . . . . . . . . . . . . . . . . 345.2.5 Predecesseur . . . . . . . . . . . . . . . . . . . . . . . . 355.2.6 Analyse des performances . . . . . . . . . . . . . . . . 35

5.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

6 Arbres binaires de recherche auto-ajustables 386.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386.2 Splay trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

6.2.1 Splaying . . . . . . . . . . . . . . . . . . . . . . . . . . 396.2.2 Recherche . . . . . . . . . . . . . . . . . . . . . . . . . 396.2.3 Insertion . . . . . . . . . . . . . . . . . . . . . . . . . . 396.2.4 Suppression . . . . . . . . . . . . . . . . . . . . . . . . 396.2.5 Analyse des performances . . . . . . . . . . . . . . . . 40

6.3 Comparaisons . . . . . . . . . . . . . . . . . . . . . . . . . . . 446.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

III Optimalite dynamique 46

7 Bornes inferieures sur le cout des arbres binaires de recherche 477.1 Modele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477.2 La borne inferieure de couverture de rectangle . . . . . . . . . 487.3 Applications de la borne inferieure de couverture de rectangle 53

2

7.3.1 La borne inferieure d’entrelacement . . . . . . . . . . . 547.3.2 La seconde borne de Wilber . . . . . . . . . . . . . . . 56

7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

8 Tango 608.1 Structures de donnees . . . . . . . . . . . . . . . . . . . . . . 608.2 Algorithme de l’arbre de reference . . . . . . . . . . . . . . . . 618.3 Arbres auxiliaires . . . . . . . . . . . . . . . . . . . . . . . . . 66

8.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 668.3.2 Concatenation . . . . . . . . . . . . . . . . . . . . . . . 678.3.3 Eclatement . . . . . . . . . . . . . . . . . . . . . . . . 678.3.4 Cutting . . . . . . . . . . . . . . . . . . . . . . . . . . 698.3.5 Joining . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

8.4 Algorithme Tango . . . . . . . . . . . . . . . . . . . . . . . . . 758.5 Analyse des performances . . . . . . . . . . . . . . . . . . . . 778.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

9 Multi-splay tree 829.1 Structures de donnees . . . . . . . . . . . . . . . . . . . . . . 829.2 Algorithmes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

9.2.1 Algorithme de l’arbre de reference . . . . . . . . . . . . 839.2.2 Algorithme multi-splay tree . . . . . . . . . . . . . . . 83

9.3 Analyse des performances . . . . . . . . . . . . . . . . . . . . 899.3.1 Fonction potentiel . . . . . . . . . . . . . . . . . . . . . 909.3.2 Access Lemma Generalise . . . . . . . . . . . . . . . . 909.3.3 Multi-Splay Access Lemma . . . . . . . . . . . . . . . . 919.3.4 Proprietes . . . . . . . . . . . . . . . . . . . . . . . . . 98

9.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

10 Optimalite de recherche dynamique 10210.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10210.2 Interet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10210.3 Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10310.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

11 Experimentations 10911.1 Jeux de tests . . . . . . . . . . . . . . . . . . . . . . . . . . . 10911.2 Distribution aleatoire . . . . . . . . . . . . . . . . . . . . . . . 11011.3 Distribution working set . . . . . . . . . . . . . . . . . . . . . 11111.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

3

12 Conclusion 114

13 Annexe 11613.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . 116

13.1.1 Multi-splay trees . . . . . . . . . . . . . . . . . . . . . 11613.1.2 Splay trees . . . . . . . . . . . . . . . . . . . . . . . . . 13713.1.3 Arbres rouges-noirs . . . . . . . . . . . . . . . . . . . . 148

13.2 Jeux de tests . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

4

Chapitre 1

Introduction

Lorsque nous recherchons un element dans un ensemble, nous pouvonse#ectuer deux types de recherche : une recherche lineaire et une recherche di-chotomique. La recherche lineaire consiste a examiner un a un les elements del’ensemble, ce qui ne donne pas des performances interessantes. La recherchedichotomique consiste a eliminer a chaque etape la moitie des elements del’ensemble. Cette methode donne des resultats interessants, car la recherchese fait en temps logarithmique et non plus en temps lineaire.

Les arbres binaires de recherche sont une application de la recherche di-chotomique. Ce type de structure organise les elements sous forme d’arbrepour tenter d’eliminer a chaque etape de la recherche le plus d’elementspossibles (dans le meilleur des cas la moitie des elements sont elimines) demaniere a localiser le plus rapidement possible un element.

Depuis que ce type de structure a ete developpe dans les annees 1960, ily a eu enormement de travaux realises sur le sujet. En general, le but de cestravaux etait d’essayer de developper une structure qui atteigne l’optimalitedynamique, c’est-a-dire qui donne le meilleur cout de recherche et cela quelleque soit la sequence d’elements a rechercher.

Ce memoire consiste en un travail de recherche bibliographique et lebut est de presenter les principaux travaux realises dans le domaine desarbres binaires de recherche et de l’optimalite dynamique, ainsi que les prin-cipales etapes franchies dans ces domaines. Cela va en general consister apresenter des structures et a analyser leurs performances. La presentation deces resultats se fera de maniere plus detaillee et plus didactique que dansles articles dans lesquels ils sont presentes. Le second objectif de ce memoireest d’implementer quelques structures de donnees pour verifier si en pratiquenous obtenons des resultats aussi interessants qu’en theorie. En e#et, il sepeut que pour des structures trop complexes les resultats obtenus en pratiquesoient moins bons que ceux auxquels nous aurions pu nous attendre a avoir

5

par la theorie. Ceci s’explique notamment par le fait que dans les analysesdes couts d’une structure, nous omettrons les constantes multiplicatives etles termes d’ordre inferieur.

Dans les chapitres 2 et 3, nous allons definir un certain nombre de no-tions. En fait, dans le chapitre 2, nous allons definir des notions de basedans le domaine des arbres binaires de recherche et dans le chapitre 3, nousallons definir des proprietes permettant de caracteriser le cout d’executiond’une sequence d’acces dans un arbre binaire de recherche. Parmi ces pro-prietes, nous pouvons notamment citer l’optimalite statique et l’optimalitedynamique.

Dans le chapitre 4, nous allons etudier les arbres binaires de rechercheoptimaux. Cette structure se base sur une connaissance prealable de la dis-tribution des cles a acceder pour atteindre l’optimalite statique.

Dans les chapitres 5 et 6, nous allons presenter deux categories d’arbresbinaires de recherche : les arbres binaires de recherche equilibres et les arbresbinaires de recherche auto-ajustables. Chacune de ces categories sera illustreepar une structure de donnees : les arbres rouges-noirs pour la premiere et lessplay trees pour la seconde. Nous detaillerons les algorithmes de ces structureset nous analyserons leurs performances.

Dans le chapitre 7, nous presenterons trois bornes inferieures sur le coutd’execution d’une sequence d’acces dans un arbre binaire de recherche. Unede ces trois bornes est la borne inferieure d’entrelacement. Celle-ci est a labase de la structure Tango etudiee dans le chapitre 8. Cette structure presenteun grand interet, parce qu’elle approche l’optimalite dynamique a un facteurlog(log n) pres.

Dans le chapitre 9, nous etudierons la structure des multi-splay trees,qui approche egalement l’optimalite dynamique a un facteur log(log n)pres. Cette structure presente comme principal interet d’etre plus facile aimplementer que Tango.

A l’heure actuelle, aucune structure de donnees n’atteint l’optimalite dy-namique, mais nous presenterons dans le chapitre 10 un cas particulier oucette propriete est atteinte. Nous montrerons dans ce chapitre, que nous pou-vons atteindre l’optimalite dynamique en changeant le modele de cout et enpermettant a la structure d’e#ectuer un nombre quelconque d’operations dereorganisation entre chaque acces sans que cela soit comptabilise dans le coutd’execution.

Pour analyser les performances en pratique des structures etudiees, nousen avons implemente certaines pour y executer des jeux de tests. Dans lechapitre 11, nous fournirons les resultats des jeux de tests executes, ainsi queles conclusions que nous pouvons en tirer. L’implementation des structures,accompagnee d’explications, est fournie en annexe.

6

Premiere partie

Fondements et definitions

7

Chapitre 2

Arbres binaires et complexite

Dans ce chapitre, nous allons definir toute une serie de notions de basedans le domaine des arbres binaires de recherche et dans le domaine de lacomplexite. Ces rappels seront utiles au lecteur de maniere a poser ces no-tions, qui seront sans cesse utilisees.

2.1 Arbres binaires

Dans cette section, nous allons donner la definition d’un arbre binaire,ainsi que de la terminologie associee a ce type de structure.

2.1.1 Definitions

Cette section est basee sur les notes d’un cours dispense par Olivier Mar-kowitch [Mar02].

Un arbre est une structure de donnees permettant de stocker un ensembled’elements et il consiste en une collection de nœuds et d’aretes (on utiliseraaussi le terme arc pour designer une arete). Un nœud permet de stockerun element de cet ensemble et une arete (arc) est un lien entre deux nœuds.L’organisation de l’arbre est telle que deux nœuds quelconques de l’arbre sontrelies entre eux par un chemin unique. Un chemin est une suite de nœudsdistincts dans laquelle deux nœuds successifs sont relies par une arete. Unnœud peut posseder des fils. Un nœud y est le fils d’une nœud x si y se situeen-dessous de x dans l’arbre et s’il est relie a ce nœud par une arete. Unnœud x possede egalement un pere ; il s’agit du nœud ayant x comme fils.Les nœuds qui n’ont pas de fils sont appeles des feuilles. Le nœud au sommetde l’arbre est appele la racine et il ne possede pas de pere.

8

Un arbre binaire est un arbre, ou chaque nœud possede au plus deux filsappeles fils gauche et fils droit.

Les ancetres d’un nœud x sont les nœuds qui appartiennent au cheminreliant la racine de l’arbre a x.

Les descendants d’un nœud x sont les nœuds qui ont x comme ancetre.Le sous-arbre d’un nœud x dans un arbre A est la partie de A contenant

x, ainsi que ses descendants. Le sous-arbre gauche d’un nœud x est le sous-arbre du fils gauche de x. Le sous-arbre droit d’un nœud x est le sous-arbredu fils droit de x. Un sous-arbre est vide s’il ne contient pas d’elements ; parexemple si x n’a pas de fils droit, alors le sous-arbre droit de x est vide.

2.1.2 Profondeur d’un nœud

Cette section est basee sur les notes d’un cours dispense par Olivier Mar-kowitch [Mar02].

La profondeur d’un nœud x, notee d(x), est le nombre d’arcs sur le cheminallant de la racine de l’arbre au nœud x plus 1. De maniere plus formelle :

1. d(x) = 1 si x est la racine de l’arbre

2. d(x) = 1 + d(parent) sinon

ou parent est le nœud pere de x.

2.1.3 Hauteur d’un nœud

Cette section est basee sur les notes d’un cours dispense par Olivier Mar-kowitch [Mar02].

La hauteur d’un nœud x, notee h(x), est le nombre d’arcs sur le cheminallant de x a la feuille la plus profonde du sous-arbre de x. De maniere plusformelle :

1. h(x) = 0 si x est feuille

2. h(x) = 1 + max{h(fg), h(fd)} sinon

ou fg et fd sont, respectivement, les fils gauche et droit de x.

2.1.4 Rotations

Il existe trois types de rotations possibles sur les arbres binaires :

1. une rotation simple

2. une rotation double

3. une rotation zig-zig

9

Fig. 2.1 – Rotation simple entre x et y .

2.1.4.1 Rotation simple

Cette operation a ete decrite pour la premiere fois dans l’articled’Adel’son-Vel’skii et Landis [AVL62].

Une rotation simple entre un nœud x et un nœud y (avec d(x) > d(y),ou d(x) est la profondeur de x et d(y) est la profondeur de y) consiste apermuter la profondeur de x et de y comme decrit a la figure 2.1.

Une rotation simple est dite droite si x est le fils gauche de y et elle ditegauche si x est le fils droit de y. La rotation a la figure 2.1 correspond a unerotation droite. La rotation gauche est deduite de maniere symetrique parrapport a la rotation droite.

2.1.4.2 Rotation double

Une rotation double entre un nœud x, un nœud y et un nœud z (avecd(x) > d(y) > d(z)) consiste a e#ectuer une rotation simple entre x et y,puis une rotation simple entre x et z (cfr figure 2.2).

Pour pouvoir e#ectuer une rotation double, il faut que x soit un fils droit(respectivement fils gauche) et y soit un fils gauche (respectivement fils droit).

10

Fig. 2.2 – Rotation double entre x, y et z.

2.1.4.3 Rotation zig-zig

Cette operation a ete decrite pour la premiere fois dans l’article de Sleatoret Tarjan [ST85].

Une rotation zig-zig entre un nœud x, un nœud y et un nœud z (avecd(x) > d(y) > d(z)) consiste a permuter la profondeur de x et de z commedecrit a la figure 2.3.

Pour pouvoir e#ectuer une rotation zig-zig, il faut que x et y soient tousdeux des fils gauches ou des fils droits.

2.2 Arbres binaires de recherche

Le point principal dans cette section consiste a definir le modele desarbres binaires de recherche, qui sera etudie. Il faut noter, qu’il existe plu-sieurs modeles d’arbres binaires de recherche. En general, ces variantes sontequivalentes (a un facteur constant pres) en terme de performances au modeledecrit ci-dessous.

11

Fig. 2.3 – Rotation zig-zig entre x, y et z.

2.2.1 Modele

Nous considerons le modele defini par Demaine, Harmon, Iacono et Pa-trascu [DHIP04]. Ils ont defini ce modele en se basant sur celui de Wilber[Wil89], qui correspond egalement a celui utilise par Sleator et Tarjan [ST85].

Un ABR(Arbre Binaire de Recherche) est un arbre binaire qui maintientun ensemble de cles selon une regle precise : pour chaque nœud x de l’arbre,la cle de x est plus grande que toutes les cles contenues dans le sous-arbregauche de x et elle est plus petite que toutes les cles contenues dans le sous-arbre droit de x.

Dans cette definition, nous considerons qu’un ABR ne supporte qu’uneseule operation : la recherche d’un element. Cette recherche se fait sur un en-semble statique de n cles. Nous considerons seulement des recherches reussies,appelees acces. Nous supposons egalement, sans nuire a la generalite, quechaque cle d’un ABR prend une valeur unique dans l’ensemble {1, 2, . . . , n}.

Un ABR est utilise pour servir une sequence d’acces, qui consiste en unesuite de cles X = x1, x2, . . . , xm. L’algorithme d’acces de l’ABR permet, enfait, de servir chaque acces xi de cette sequence. Pour acceder a un nœud xi,l’algorithme d’acces ne peut utiliser qu’un seul pointeur P durant le parcoursde l’arbre. Au debut de l’acces, ce pointeur est initialise a la racine de l’arbre.

12

L’algorithme d’acces peut, ensuite, realiser les operations de cout unitairesuivantes :

1. deplacer le pointeur P vers son fils gauche

2. deplacer le pointeur P vers son fils droit

3. deplacer le pointeur P vers son pere

4. e#ectuer une rotation simple entre le pointeur P et son pere

L’algorithme d’acces realise une sequence des operations ci-dessus jusqu’ace que le pointeur P atteigne le nœud xi.

Le cout d’acces au nœud xi est le nombre d’operations de cout unitairerealisees pour l’atteindre. Des lors, le cout exige par un ABR pour executerune sequence X = x1, x2, . . . , xm vaut

!mi=1 cout(xi).

Nous designerons ce modele par le terme modele dynamique.Comme autre modele pour les arbres binaires de recherche, nous pouvons

citer le modele standard. Ce modele est defini dans les articles [DSW05] et[BCK03] et il sera aborde dans le chapitre 10.

2.2.2 Classes d’arbres binaires de recherche

Il existe deux grandes classes d’ABR, basees sur la maniere de choisirl’operation de cout unitaire suivante a realiser lors d’un acces xi :

1. les ABR online

2. les ABR o!ine

2.2.2.1 ABR online

Un ABR online [DHIP04] est une structure de donnees ABR dans laquellechaque nœud peut contenir des donnees supplementaires. Lors de chaqueoperation de cout unitaire, les donnees contenues dans le nœud pointe parle pointeur P peuvent etre modifiees. Les donnees contenues dans les nœudspermettent, en general, de garder de l’information sur les cles deja accedees,de maniere a ameliorer le cout d’acces aux cles devant encore etre accedees.

Lors d’un acces, l’algorithme d’acces choisit l’operation de cout uni-taire suivante a realiser en fonction de la cle a acceder et des informationssupplementaires contenues dans le nœud pointe par le pointeur P .

La quantite d’informations supplementaires contenues dans un nœud doitetre la plus petite possible de maniere a avoir une incidence negligeable sur letemps d’execution du programme. En e#et, si cette quantite est trop grande,la mise a jour de ces informations apres une operation risque de couter cher.

13

Comme exemples d’ABR online, nous pouvons citer : les arbres rouges-noirs (qui necessitent un bit de couleur par nœud), les arbres AVL (quinecessitent un compteur par nœud) et les splay trees (qui ne necessitentpas d’informations supplementaires).

2.2.2.2 ABR o!ine

Un ABR o$ine est une structure de donnees ABR, qui a une connaissanceprealable de la sequence X a executer. En fait, il s’agit d’une structure uto-pique, qui avant meme de servir X, connaıt deja les nœuds qui devront etreaccedes dans cette sequence. De par cette connaissance, une telle structuren’a pas besoin de garder des informations supplementaires dans ses nœuds.

Lors d’un acces xi, le choix de l’operation de cout unitaire suivante arealiser est base sur la connaissance de toute la sequence X. La di#erenceentre un ABR online et un ABR o$ine est que, pour choisir l’operation decout unitaire suivante a realiser lors d’un acces xi, ce dernier peut se basersur les acces qui suivent xi dans la sequence X.

2.3 Performances asymptotiques

Cette section est basee sur l’ouvrage de Flajolet et Sedgewick [FS98].Pour caracteriser l’e%cacite d’un algorithme, nous etudions ses perfor-

mances asymptotiques. Ceci consiste a etudier la facon dont varie le tempsd’execution d’un algorithme quand la taille de l’entree tend vers l’infini.

Plusieurs raisons justifient l’usage des methodes asymptotiques :

1. les performances asymptotiques d’un algorithme sont plus faciles a cal-culer que son temps d’execution exact.

2. calculer le temps d’execution exact d’un algorithme est en general in-utile. En e#et, pour des entrees su%samment grandes, les e#ets desconstantes multiplicatives et des termes d’ordre inferieur dans le tempsd’execution exact sont negligeables.

3. les methodes asymptotiques fournissent de bons criteres de comparai-son entre les algorithmes. En e#et, un algorithme, qui est asymptoti-quement meilleur qu’un autre, est plus e%cace que ce dernier pour desentrees su%samment longues.

Ci-dessous suivent trois notations asymptotiques permettant de decrirele temps d’execution asymptotique d’un algorithme.

14

2.3.1 Notation O(.)

Soit N la taille de l’entree d’un algorithme. Nous disons que le tempsd’execution T (N) d’un algorithme est en O(g(N)) (dit grand o de g de N )s’il existe des constantes positives c1 et n0 telles que :

!n " n0 , 0 # T (n) # c1.g(n) (2.1)

Nous constatons, que pour n su%samment grand, T (n) est bornesuperieurement par c1 · g(n). Intuitivement, la notation O(.) sert a majo-rer la fonction T (N).

2.3.2 Notation !(.)

Soit N la taille de l’entree d’un algorithme. Nous disons que le tempsd’execution T (N) d’un algorithme est en !(g(N)) (dit grand omega de g deN ) s’il existe des constantes positives c1 et n0 telles que :

!n " n0 , 0 # c1.g(n) # T (n) (2.2)

Nous constatons, que pour n su%samment grand, T (n) est borneinferieurement par c1 · g(n). Intuitivement, la notation !(.) sert a minorer lafonction T (N).

2.3.3 Notation "(.)

Soit N la taille de l’entree d’un algorithme. Nous disons que le tempsd’execution T (N) d’un algorithme est en "(g(N)) (dit grand theta de g deN ) s’il existe des constantes positives c1, c2 et n0 telles que :

!n " n0 , 0 # c1.g(n) # T (n) # c2.g(n) (2.3)

Nous constatons, que pour n su%samment grand, T (n) est borneinferieurement par c1 · g(n) et superieurement par c2 · g(n). Intuitivement,la notation "(.) fournit une valeur approchee de la fonction T (N).

2.3.4 Lien entre les notations asymptotiques

Une fois les trois definitions ci-dessus presentees, il est assez aise d’etablirun lien entre elles. Ce lien est explicite par le theoreme suivant.

Theoreme 1. Pour deux fonctions quelconques g(n) et f(n), nous avons quef(n) = "(g(n)) si et seulement si f(n) = O(g(n)) et f(n) = !(g(n)).

15

Ce theoreme peut facilement etre demontre en prouvant d’abord l’im-plication du theoreme dans un sens, puis en prouvant son implication dansl’autre sens et cela en se basant a chaque fois sur la definition de O(.), "(.)et !(.)

2.4 Complexite

Cette section est basee sur l’ouvrage de Jean Cardinal [Car04] et l’articlede Tarjan [Tar85].

Il existe principalement trois manieres d’analyser la complexite d’unestructure :

1. e#ectuer une analyse au pire cas

2. e#ectuer une analyse amortie

3. e#ectuer une analyse du cas moyen

Dans cette section, nous allons definir ces trois analyses et developper demaniere plus precise l’analyse amortie.

2.4.1 Complexite au pire cas

L’analyse au pire cas consiste a caracteriser la complexite d’une operationdans le pire des cas. Ce pire cas peut se produire de maniere repetee ou non.Si ce pire cas peut se produire de maniere repetee, la complexite au pire casdonne une bonne indication des performances en pratique de la structure.Par contre, si ce pire cas ne peut pas se produire souvent, elle ne donnepas une indication concrete sur les performances en pratique. Ceci peut etreillustre par l’exemple suivant : la complexite au pire cas de l’algorithme deKnuth-Morris-Pratt (pour la recherche de motifs) est bien meilleure que lacomplexite au pire cas de l’algorithme de Boyer-Moore, alors qu’en pratiquece deuxieme algorithme est plus e%cace que le premier.

2.4.2 Complexite moyenne

L’analyse de la complexite moyenne est en general delicate. La com-plexite moyenne est calculee sur la base d’une distribution de probabilitessur l’ensemble des entrees de l’algorithme, pour laquelle des hypotheses ontete posees. La source de l’aleatoire vient alors des entrees. Cette complexitedonne des informations assez significatives concernant les performances enpratique si les pire cas sont rares.

16

Il existe une seconde maniere de calculer une complexite moyenne, danslaquelle la source de l’aleatoire ne vient pas des entrees, mais de l’algorithmequi fait des choix aleatoires. La complexite est calculee sur ces choix et onparle alors de complexite moyenne randomisee.

2.4.3 Complexite amortie

2.4.3.1 Definition

La complexite amortie est la complexite au pire cas d’une sequence deM operations divisee par M . La complexite amortie donne des informationssignificatives concernant les performances en pratique d’une structure, touten se basant sur les performances au pire cas. Cette analyse apparaıt, donc,comme un bon intermediaire entre la complexite moyenne et la complexite aupire cas. Elle permet, mieux que les deux analyses precedentes, de concevoirdes structures e%caces en pratique.

Il existe plusieurs methodes pour e#ectuer une analyse amortie d’unestructure.

La methode qui sera developpee dans le point suivant est la methode dupotentiel.

2.4.3.2 Methode du potentiel

La methode du potentiel necessite de definir une fonction potentiel. Cettefonction peut etre comparee a un compte bancaire. Celui-ci ne peut pasdescendre en dessous d’une certaine valeur (par exemple 0). Lorsqu’un achatnecessite un cout moindre que prevu, l’argent restant est remis dans le compteet celui-ci augmente. Par contre, lorsque le cout d’un achat est superieur acelui prevu, il faut aller puiser dans le compte pour payer le reste et celui-cidiminue donc. Cette analogie permet de donner une premiere idee de ce qu’estune fonction potentiel. Une definition plus precise est donnee ci-dessous.

La fonction potentiel est une valeur qui est bornee inferieurement parune constante. Cette borne depend de la structure, mais vaut en general 0.La fonction potentiel va augmenter, lorsque le temps reel pour e#ectuer uneoperation est inferieur a son temps amorti. Et elle va diminuer, si le temps reelpour e#ectuer une operation est superieur a son temps amorti. En d’autrestermes, lorsque le cout e#ectif d’une operation est inferieur a son cout amorti,la fonction potentiel sauvegarde la di#erence entre ces deux couts, et lorsquele cout d’une operation est superieur a son cout amorti, la fonction potentielpuise dans sa reserve pour compenser ce surcout.

17

Pour prouver une complexite amortie CA, il faut etablir l’equation sui-vante, qui utilise une fonction potentiel P :

CA = CE + $P, (2.4)

ou CE est la complexite e#ective de l’operation et $P est la variation dela fonction potentiel entre le debut et la fin de l’operation.

Pour etablir l’equation ci-dessus, il faut prouver, qu’a la ieme (! 1 # i #M) operation d’une sequence de M operations, l’egalite suivante est verifiee :

CA = CE(i) + $P (i), (2.5)

ou CE(i) est le cout e#ectif de la ieme operation et $P (i) est la variationde potentiel a la ieme etape, c’est-a-dire la di#erence entre le potentiel apresla ieme etape (= P (i)) et le potentiel avant la ieme etape (= P (i% 1)). Cetteequation peut etre reecrite de la maniere suivante :

CA = CE(i) + P (i) % P (i % 1) (2.6)

2.5 Conclusion

Dans ce chapitre, nous avons d’abord defini la notion d’arbre binaire,ainsi que la terminologie associee a ce type de structure. Ensuite, nous avonsdefini le modele dynamique des arbres binaires de recherche. Et finalement,nous avons presente plusieurs outils (les performances asymptotiques et lesdi#erents types de complexite) permettant de caracteriser les performancesd’une structure ABR et permettant de comparer les performances de tellesstructures.

18

Chapitre 3

Proprietes des arbres binairesde recherche

Dans ce chapitre, nous allons presenter plusieurs proprietes caracterisantle cout d’execution d’une sequence d’acces dans des ABR. Ces proprietes sontegalement valables pour certaines structures qui ne sont pas des ABR.

3.1 Relations entre les proprietes

Nous allons decrire dans ce chapitre six proprietes :

1. Static Finger

2. Optimalite Statique

3. Working Set

4. Dynamic Finger

5. Unifiee

6. Optimalite Dynamique

La figure 3.1 illustre la relation d’implication entre ces proprietes. Lapropriete static finger est la plus faible de toutes, car elle est une consequencede toutes les autres proprietes. De plus, les proprietes working set et dynamicfinger sont independantes.

Les definitions des proprietes ci-dessus sont basees sur deux articles deIacono [Iac01] et [Iac05].

3.2 Static finger

Considerons un ensemble de n cles {1, 2, . . . , n}, une sequence d’accesX = x1, x2, . . . , xm et un nœud specifique f , appele le finger, appartenant a

19

Fig. 3.1 – Relation d’implication entre les proprietes.

l’ensemble {1, 2, . . . , n}. Une structure a la propriete static finger si le couttotal pour executer la sequence X vaut :

O

"m#

i=1

log (1 + |xi % f |)$

(3.1)

L’expression |xi%f | est la distance dans l’ordre symetrique entre le fingerf et le nœud xi. En d’autres termes, la distance |xi % f | est le nombred’elements situes entre xi et f dans la sequence triee des nœuds plus 1. Unefois fixe, le finger reste le meme durant toute l’execution de la sequence X.

Les Finger Search Trees [BLM+03] possedent cette propriete, mais cettestructure ne repond pas a la definition du modele dynamique des ABR (cfrpoint 2.2.1), car son operation de recherche peut debuter a partir d’une feuillequelconque de l’arbre. Les splay trees [ST85] possedent egalement cette pro-priete.

De l’equation (3.1), nous constatons que plus la distance entre le finger fet le nœud xi est petite, plus le cout sera petit et inversement.

Par consequent, pour une structure ayant la propriete static finger, lecout total pour executer une sequence X sera determine par la distance dansl’ordre symetrique entre le finger f et chaque nœud de la sequence X aexecuter.

20

3.3 Optimalite statique

Considerons un ensemble de n cles {1, 2, . . . , n} et une sequence d’accesX = x1, x2, . . . , xm. Une structure a la propriete d’optimalite statique, si elleexecute X avec un cout de :

O

"n#

i=1

f (i) · log

%m

f (i)

&$

, (3.2)

ou f (i) est le nombre d’acces a i dans la sequence X.Supposons que nous ayons une variable aleatoire discrete qui puisse

prendre n valeurs ( {1, 2, . . . , n} ), l’entropie de cette variable est la quantite :

H = %n#

i=1

pi · log (pi) =n#

i=1

pi · log

%1

pi

&, (3.3)

ou pi est la probabilite que la variable aleatoire soit egale a i.Prenons l’equation (3.2) et reecrivons-la de la maniere suivante :

O

"

m ·n#

i=1

f(i)

m· log

%m

f(i)

&$

(3.4)

En posant pi = f(i)/m , nous obtenons :

O

"

m ·n#

i=1

pi · log

%1

pi

&$

= O(m · H) (3.5)

Une structure, qui atteint l’optimalite statique, execute donc la sequenceX avec un cout egal a O(m ·H). De plus, elle execute un acces avec un coutamorti O(H).

Les Arbres Binaires de Recherche Optimaux [Knu73] et les splay trees[ST85] sont deux structures ABR ayant cette propriete d’optimalite statique.Ces deux structures feront l’objet d’explications plus detaillees, respective-ment, dans les chapitres 4 et 6.

3.4 Working set

Considerons un ensemble de n cles {1, 2, . . . , n} et une sequence d’accesX = x1, x2, . . . , xm.

Soit l(i, x) egal a j si xj est le dernier acces a x dans la sequence x1, x2, . . . ,xi!1. Si x n’est pas accede dans cette sequence, alors l(i, x) vaut 1. Nousdefinissons w(i, x) comme etant le nombre d’elements distincts accedes dans

21

la sequence xl(i,x)+1, xl(i,x)+2, . . . , xi. Des lors, w(i, xi) est le nombre d’elementsdistincts accedes dans la sequence xl(i,xi)+1, xl(i,xi)+2, . . . , xi. Il s’agit donc dunombre d’elements distincts accedes entre l’acces xi et le precedent acces acet element. Notons w(i, xi) par w(xi).

Une structure a la propriete working set, si elle execute une sequenced’acces X avec un cout :

O

"m#

i=1

log (w (xi))

$

(3.6)

De cette propriete, nous deduisons que plus il y a d’elements di#erentsaccedes entre deux acces successifs d’un nœud xi, plus le cout d’acces a cenœud xi sera eleve et inversement.

De plus, nous constatons que, si les acces d’une sequence X ne se fontque sur un sous-ensemble de k elements parmi les n, la complexite d’un accesa une cle xi de cette sequence sera d’au plus O(log k), car w(xi) ne pourrajamais etre superieur a k.

Par consequent, pour une structure ayant la propriete working set, le couttotal pour executer une sequence X depend de deux criteres :

1. le nombre de cles di#erentes dans la sequence X.

2. le nombre d’elements di#erents accedes entre deux acces successifsd’une meme cle dans la sequence X.

Plus la premiere quantite sera petite, plus elle aura d’importance dans lecout d’execution de la sequence X.

En fait, cette propriete est basee sur la localite temporelle : plus la localitetemporelle entre deux acces successifs d’une meme cle est petite (c’est-a-direque le temps ecoule entre ces deux acces est petit), plus le cout d’acces a cenœud est petit et inversement.

La Working Set Data Structure proposee par Iacono [Iac01] atteint unpire cas de O(log(w(xi))) pour un acces xi. Cependant, cette structure nerepond pas a la definition du modele dynamique des ABR, car elle utilise despointeurs et des files additionnels. Les splay trees [ST85] possedent egalementcette propriete.

3.5 Dynamic finger

Considerons un ensemble de n cles {1, 2, . . . , n} et une sequence d’accesX = x1, x2, . . . , xm. Une structure a la propriete dynamic finger si le couttotal pour executer la sequence X vaut :

22

O

"m!1#

i=1

log (1 + |xi+1 % xi|)$

(3.7)

Cette propriete est analogue a la propriete static finger. La di#erenceetant que pour cette derniere, le finger f est fixe, tandis que pour la proprietedynamic finger, le finger est le dernier element accede.

Les Level-Linked Trees [BT80] possedent cette propriete, mais cette struc-ture ne repond pas a la definition du modele dynamique des ABR, car elleutilise des pointeurs additionnels. Les level-linked trees atteignent un pire casde O(log (1 + |xi+1 % xi|)) pour un acces. Les splay trees [ST85] possedentegalement la propriete dynamic finger.

De l’equation (3.7), nous deduisons que l’acces a un nœud est d’autantplus rapide que la distance entre l’element auquel on doit acceder et le dernierelement auquel on a accede est petite.

En fait, cette propriete est basee sur la localite spatiale : plus la distanceentre deux acces adjacents est petite, plus le cout d’acces au nœud est petitet inversement.

Par consequent, pour une structure ayant la propriete dynamic finger,le cout total pour executer une sequence X sera determine par la distanceentre les acces adjacents de la sequence. Plus la distance entre les accesadjacents de la sequence sera grande, plus le cout pour executer X seragrand et inversement.

3.6 Unifiee

Considerons un ensemble de n cles {1, 2, . . . , n} et une sequence d’accesX = x1, x2, . . . , xm. Une structure a la propriete unifiee si elle execute Xavec un cout :

O

"m#

i=1

minj"X

(log (w(i, j) + |xi % j| + 1))

$

(3.8)

L’Unified Structure [Iac01] possede cette propriete, mais elle ne repondpas a la definition du modele dynamique des ABR. Les splay trees [ST85] sontconjectures avoir la propriete unifiee. A l’heure actuelle, il n’existe aucunestructure ABR qui atteigne cette borne.

Une structure ayant cette propriete executera une sequence avec un coutfaible si les acces sont proches en terme de distance a des elements accedesrecemment et inversement. Cette propriete est donc basee sur la localitetemporelle et la localite spatiale des acces.

23

La propriete unifiee implique la propriete working set et la propriete dyna-mic finger. L’interet de la propriete unifiee est d’unifier les proprietes workingset et dynamic finger ; ces deux proprietes etant independantes, car aucunedes deux n’implique l’autre.

3.7 Optimalite dynamique

Considerons une sequence quelconque d’acces X = x1, x2, . . . , xm. Cer-tains ABR peuvent l’executer de maniere optimale. Notons par OPT (X) cecout minimal pour executer X. Ce cout OPT (X) est le cout de l’ABR o$inele plus rapide qui puisse executer X. En e#et, dans le modele ABR o$ine,il n’y a aucune contrainte dans l’algorithme d’acces sur la maniere de choisirla prochaine operation de cout unitaire a realiser. Et en particulier, ce choixpeut dependre des futurs acces a servir dans la sequence.

Une structure de donnees ABR a la propriete d’optimalite dynamique, sielle execute une quelconque sequence d’acces X avec un cout O(OPT (X)).

On dit qu’une structure de donnees A est !% competitive (ou a un tauxde competitivite de !) si pour toute sequence X :

COUTA(X) # ! · OPT (X), (3.9)

ou COUTA(X) est le cout necessaire a la structure A pour executer X.La conjecture d’optimalite dynamique, enoncee par Sleator et Tarjan

[ST85], a%rme que les splay trees sont O(1) % competitifs. Cependant, au-cune demonstration n’est venue etayer cette conjecture.

Jusqu’il y a peu, le meilleur taux de competitivite etait le taux trivial deO(log(n)), atteint par exemple par les arbres rouges-noirs. Ce n’est qu’en2004, que ce taux a pu etre ameliore par une structure de donnees ap-pelee Tango [DHIP04]. Cette structure atteint un taux de competitivite deO(log(log n)). Par apres, une autre structure de donnees, les Multi-SplayTrees ([SW04] et [DSW06]), a ete developpee sur base de Tango pour at-teindre egalement un taux de competitivite de O(log(log n)). Ces deux struc-tures seront detaillees dans les chapitres 8 et 9.

La propriete d’optimalite dynamique a une signification profonde :connaıtre le futur ne permet d’ameliorer le temps d’execution d’une sequenced’acces que d’un facteur constant. En e#et, si nous parvenons a developperun ABR online, qui atteint l’optimalite dynamique, cela signifierait que noussommes parvenus a creer une structure, qui en se basant sur le passe de lasequence d’acces X a executer, donne des resultats equivalents, a un facteurconstant pres, a la meilleure structure de donnees o$ine, qui se base sur la

24

connaissance du futur pour executer de maniere optimale la sequence d’accesX.

3.8 Conclusion

Dans ce chapitre, nous avons defini toute une serie de proprietes permet-tant de caracteriser le cout d’execution d’une sequence d’acces dans un ABR.La propriete la plus forte etant bien evidemment l’optimalite dynamique.

De plus, nous avons presente la relation d’implication entre ces proprietesde maniere a specifier celles qui sont les plus fortes et celles qui sont les plusfaibles.

25

Deuxieme partie

Arbres binaires de rechercheparticuliers

26

Chapitre 4

Arbres Binaires de RechercheOptimaux

La redaction de ce chapitre est basee sur l’ouvrage de Knuth [Knu73].La structure des ABRO (= Arbres Binaires de Recherche Optimaux) a

ete developpee par Knuth [Knu73]. Le but de cette structure est d’atteindrel’optimalite statique et elle necessite pour cela de connaıtre la distributiondes cles a acceder.

Pour rappel, une structure a la propriete d’optimalite statique (cfr point3.3), si elle execute une sequence d’acces X = x1, x2, . . . , xm sur un arbre den cles {1, 2, . . . , n} avec un cout de :

O

"n#

i=1

f (i) · log

%m

f (i)

&$, (4.1)

ou f (i) est le nombre d’acces a i dans la sequence X.

4.1 Generalites

Pour construire l’ABRO d’un ensemble de nœuds P = {p1, p2, ... , pn},nous disposons, en plus de ces nœuds, de leur frequence relative d’acces. Pourtenir compte des recherches infructueuses, nous avons egalement besoin d’unensemble de nœuds externes Q = {q0, q1, q2, ... , qn}. Ces nœuds externesrepresentent les pointeurs nuls des nœuds de l’arbre. Chaque nœud de Qrepresente un intervalle de nœuds pour lesquels la recherche est infructueuse :q0 represente l’intervalle (%&, p1), qi represente l’intervalle (pi, pi+1) (! 0 <i < n) et qn represente l’intervalle (pn,&). Les nœuds de Q sont accompagnesde leur frequence relative d’acces.

27

Fig. 4.1 – Arbre dont le cout de recherche est de 2.2

Le cout d’une recherche dans l’arbre T construit sur les cles de P estdonne par la quantite :

c(T ) =

"#

1#j#n

f(pj) · profondeur(pj)

$+

"#

0#j#n

f(qj) · (profondeur(qj) % 1)

$,

ou f(pj) est la frequence relative d’acces au nœud pj et ou f(qj) est lafrequence relative d’acces au nœud externe qj , c’est-a-dire la probabilite quela cle recherchee appartienne a l’intervalle (qj, qj+1). La notion de profondeurest definie au point 2.1.2.

Considerons l’arbre T de la figure 4.1 et l’assignation de frequences sui-vante : f(p1) = 0.15, f(p2) = 0.1, f(p3) = 0.25, f(q0) = 0.05, f(q1) = 0.2,f(q2) = 0.15, f(q3) = 0.1. Le cout d’une recherche dans l’arbre T est lesuivant :

c(T ) = (0.15) · 3 + (0.1) · 2 + (0.25) · 1 + (0.05) · 3+(0.2) · 3 + (0.15) · 2 + (0.1) · 1

= 2.2

Pour determiner l’ABRO de P , il su%t de trouver l’arbre T , dont le coutde recherche c(T ) est le minimum parmi les couts de recherche de tous lesarbres possibles. A noter qu’il peut exister plusieurs arbres, dont le cout derecherche est minimal.

28

4.2 Algorithme exhaustif

Pour determiner l’ABRO de l’ensemble P de nœuds, il su%t de construiretous les arbres possibles sur P , de calculer leur cout de recherche et de retenircelui dont le cout est minimal. Cependant, la complexite d’un tel algorithmeest exponentielle. En e#et, avec n nœuds il est possible de construire Cn+1

(= le (n + 1)eme nombre de Catalan) arbres binaires de recherche. Or,

Cn+1 =

'2nn

(

(n + 1)

' 4n

"1/2 · n3/2

Clairement un tel algorithme pour construire l’ABRO est a exclure.

4.3 Algorithme de Knuth

L’algorithme de Knuth est un algorithme de programmation dynamique.Il se base sur la propriete suivante : tous les sous-arbres d’un ABRO sontoptimaux. En e#et, une amelioration du cout de recherche d’un quelconquesous-arbre d’un ABRO mene a une amelioration du cout de recherche del’ABRO.

L’idee est de considerer le probleme de maniere recursive (cfr figure 4.2).Un ABRO T est constitue d’une racine pk, d’un sous-arbre gauche (qui estun ABRO) et d’un sous-arbre droit (qui est un ABRO). On construit demaniere recursive le sous-arbre gauche et le sous-arbre droit de pk avant deconstruire T .

Pour construire l’ABRO avec l’algorithme de programmation dynamique,nous avons besoin de trois tables :

1. la table C, ou C(i, j) (! 0 # i # j # n) est le cout de l’ABRO sur lesnœuds {pi+1, ... , pj, qi, ... , qj}.

2. la table r, ou r(i, j) (! 0 # i # j # n) est l’indice k de la racine pk del’ABRO sur les nœuds {pi+1, ... , pj , qi, ... , qj}.

3. la table W , ou W (i, j) = f(pi+1) + . . . + f(pj) + f(qi) + . . . + f(qj)(! 0 # i # j # n).

Le remplissage de la table C commence a la ligne 0 et se termine a laligne n. Il est base sur la formule suivante :

29

Fig. 4.2 – ABRO d’un point de vue recursif

C(i, j) =

)0 si i " jW (i, j) + min

i<k#j(C(i, k % 1) + C(k, j)) si i < j (4.2)

L’idee de cette formule est de determiner pour chaque indice k le cout del’arbre construit avec pk comme racine, un ABRO de cout C(i, k%1) commesous-arbre gauche et un ABRO de cout C(k, j) comme sous-arbre droit ; ilfaut retenir celui qui minimise la quantite C(i, k % 1) + C(k, j). Une fois kdetermine (si plusieurs indices donnent un cout minimal, il faut en choisir unarbitrairement), il faut stocker cet indice dans r(i, j). Il faut noter que dansle calcul de C(i, j), il faut rajouter le terme W (i, j). En e#et, lorsque le sous-arbre gauche de cout C(i, k % 1) et le sous-arbre droit de cout C(k, j) sontrattaches a la racine pk, la profondeur de chacun des nœuds dans ces sous-arbres augmente de 1. Ceci implique qu’il faut rajouter dans le cout C(i, j)la frequence de chacun de ces nœuds. Comme il faut egalement rajouter lafrequence de pk, cela revient finalement a rajouter W (i, j) au cout C(i, j).

Il est possible d’optimiser la formule 4.2 en se basant sur l’inegalite sui-vante demontree par Knuth dans [Knu73] :

r(i, j % 1) # r(i, j) # r(i + 1, j) (4.3)

30

La formule devient alors :

C(i, j) =

)0 si i " jW (i, j) + min

r(i,j!1)#r(i,j)#r(i+1,j)(C(i, k % 1) + C(k, j)) si i < j

(4.4)La construction de l’ABRO en utilisant la formule 4.4 necessite un cout en

O(n2) (si n est la taille de l’arbre), alors que la construction avec la formule4.2 necessite un cout en O(n3) [Knu73].

De plus, le cout d’une recherche dans un tel arbre se fait en O(H) [Knu73](ou H est l’entropie).

4.4 Conclusion

Dans cette section, nous avons presente un algorithme de programma-tion dynamique, qui construit avec un cout en O(n2) une structure qui at-teint l’optimalite dynamique. Cette structure est statique et elle requiere laconnaissance de la frequence des nœuds.

En 1979, Bitner [Bit79] a presente et analyse les Arbres Monotones Dy-namiques. Cette structure est un ABR dynamique (un ABR qui permet lesinsertions et les suppressions), qui essaie d’approximer l’ABRO.

31

Chapitre 5

Arbres binaires de rechercheequilibres

Dans ce chapitre, nous allons d’abord definir la notion d’arbre binairede recherche equilibre. Ensuite, nous allons illustrer ce concept par lapresentation des arbres rouges-noirs. Le choix de cette structure plutot qu’uneautre se justifie par le fait qu’elle fait partie des plus connues et des plus ef-ficaces de sa categorie.

5.1 Definition

Un arbre binaire de recherche equilibre est un ABR, qui maintient desinformations supplementaires dans ses nœuds, de maniere a ce qu’il resteequilibre. Le but de cet equilibrage est qu’a tout moment, la hauteur del’arbre soit logarithmique, a un facteur constant pres, en le nombre d’elementsdans l’arbre. Ceci permet d’avoir des operations sur la structure en tempslogarithmique en le nombre d’elements dans l’arbre.

5.2 Arbres rouges-noirs

Dans la litterature, il existe deux manieres de presenter les arbres rouges-noirs : soit de les decrire comme une implementation des arbres 2-3-4 (unedescription de cette structure-ci est presentee dans l’ouvrage [Sed04]), soit deles decrire comme une structure verifiant un certain nombre de conditions,qui permettent d’equilibrer l’arbre. Les deux methodes sont bien evidemmentequivalentes. La premiere methode est plus interessante, car elle permet decomprendre le sens des proprietes imposees aux arbres rouges-noirs. Ellepermet, de plus, de comprendre aisement les algorithmes d’insertion et de

32

suppression des arbres rouges-noirs, ainsi que leur preuve de correction. Ladeuxieme methode permet de presenter la structure de maniere plus breve.Nous utiliserons la deuxieme methode pour presenter la structure. Cette des-cription est basee sur les ouvrages de Jean Cardinal [Car04] et de Sedgewick[Sed04].

5.2.1 Definition

Les arbres rouges-noirs ont deux types d’arcs : les arcs rouges et lesarcs noirs. Un seul bit par nœud x est necessaire comme informationsupplementaire. Ce bit indique si l’arc pointant vers ce nœud x est rougeou noir. Un arbre, pour repondre a la definition d’arbres rouges-noirs, doitverifier les proprietes suivantes :

1. dans un chemin de la racine a une feuille, il n’y a jamais deux arcsrouges successifs

2. le nombre d’arcs noirs dans un chemin de la racine a un sous-arbre videest le meme quel que soit le chemin

3. le bit de couleur de la racine est noir

Ces conditions permettent d’equilibrer l’arbre, comme il le sera demontreplus loin dans ce chapitre, de maniere a ce que les operations sur les arbresrouges-noirs se fassent en temps logarithmique au pire cas en le nombred’elements dans l’arbre.

5.2.2 Recherche

L’algorithme de recherche pour les arbres rouges-noirs est identique al’algorithme d’acces des ABR defini pour le modele dynamique (cfr point2.2.1).

5.2.3 Insertion

L’algorithme d’insertion pour les arbres rouges-noirs est le suivant.En commencant le traitement a la racine, il faut e#ectuer les operations

suivantes :

1. Designons par x le nœud courant. Si x a deux arcs sortants rouges, ilfaut traiter ce nœud de la maniere suivante :

(a) colorier les deux arcs sortants de x en noir

(b) colorier l’arc liant x a p (ou p est le pere de x) en rouge

33

(c) si l’arc liant p a g (ou g est le pere de p ) est rouge, il faut e#ectuerune rotation. Cette rotation est simple (rotation entre p et g) si xet p sont tous deux des fils gauches ou s’ils sont tous deux des filsdroits ; elle est double sinon.

Apres cet eventuel traitement, il faut deplacer le pointeur courant surle fils gauche ou le fils droit de x suivant que la cle a inserer soit,respectivement, plus petite ou plus grande que x.

Cette premiere etape est a iterer tant que le nœud courant ne pointepas sur un sous-arbre vide.

2. A ce niveau, le pointeur courant pointe sur un sous-arbre vide. Il nesu%t, des lors, qu’a inserer le nouveau nœud dans ce sous-arbre videen coloriant son bit de couleur en rouge. Apres cela, si l’arc liant p (oup est le pere du nœud insere) a g (ou g est le pere de p) est rouge, ilfaut e#ectuer une rotation. Cette rotation est simple (rotation entre pet g) si le nœud insere et p sont tous deux des fils gauches ou s’ils sonttous deux des fils droits ; elle est double sinon. Les notions de rotationsimple et de rotation double sont definies au point 2.1.4.

Certains lecteurs pourraient etre sceptiques quant a la correction de cetalgorithme, mais si nous considerons les arbres rouges-noirs comme uneimplementation des arbres 2-3-4, alors cette preuve peut facilement etreetablie. Les utilisateurs interesses par cela peuvent consulter la reference[Car04] ou [Sed04].

5.2.4 Successeur

L’operation successeur pour un nœud x donne l’element, qui suit x dansl’ordre symetrique. L’algorithme suivant permet de determiner le successeurde x.

Supposons que le pointeur courant pointe sur le nœud x (si ce n’est pasle cas, il su%t de realiser une recherche sur cet element). Ensuite, deux cassont a envisager, selon que x ait un fils droit ou non :

1. Si x a un fils droit, note y , il faut se positionner sur le fils droit de xet suivre le chemin des fils gauches a partir de y . Le successeur de xest alors le dernier nœud rencontre sur ce chemin.

2. Si x n’a pas de fils droit, il faut remonter dans l’arbre, tant que xappartient au sous-arbre droit du nœud courant. Le successeur de xest, alors, le premier nœud dans cette remontee, qui contient x dansson sous-arbre gauche. S’il n’existe pas de tel nœud, alors x n’a pas desuccesseur.

34

5.2.5 Predecesseur

L’operation predecesseur pour un nœud x donne l’element, qui precedex dans l’ordre symetrique. L’algorithme suivant permet de determiner lepredecesseur de x.

Supposons que le pointeur courant pointe sur le nœud x (si ce n’est pasle cas, il su%t de realiser une recherche sur cet element). Ensuite, deux cassont a envisager, selon que x ait un fils gauche ou non :

1. Si x a un fils gauche, note y , il faut se positionner sur le fils gauche dex et suivre le chemin des fils droits a partir de y . Le predecesseur dex est alors le dernier nœud rencontre sur ce chemin.

2. Si x n’a pas de fils gauche, il faut remonter dans l’arbre, tant que xappartient au sous-arbre gauche du nœud courant. Le predecesseur dex est, alors, le premier nœud dans cette remontee, qui contient x dansson sous-arbre droit. S’il n’existe pas de tel nœud, alors x n’a pas depredecesseur.

5.2.6 Analyse des performances

Les deux demonstrations presentees dans cette partie sont basees surl’ouvrage de Sedgewick [Sed04]

Lemme 1. Soient un arbre rouge-noir et un nœud x appartenant a cet arbre.Le sous-arbre A de x contient au moins 2bh(x)%1 nœuds (bh(x) est la hauteurnoire de x, c’est-a-dire le nombre de nœuds ayant un bit noir entre x (inclus)et la feuille la plus profonde de x moins 1. On impose que bh(x) " 0).

Demonstration : La demonstration de ce lemme se fait par recurrence surla hauteur de x :

1. Initialisation de la recurrence : Si la hauteur de x vaut 0, alors bh(x)vaut 0. Des lors, le sous-arbre A de x doit contenir au moins 2bh(x)%1 =20 % 1 = 0 nœud. Or, si x a une hauteur de 0, cela signifie que le sous-arbre A consiste en la seule feuille x. Le sous-arbre A contient, donc,un element et le lemme est, alors, verifie.

2. Pas de recurrence : Supposons que le lemme soit vrai pour une hauteurh % 1 et montrons qu’il l’est aussi pour une hauteur h.

Supposons que le nœud x ait une hauteur h et une hauteur noire bh(x).Considerons le pire cas, ou x a deux enfants ; en e#et, on augmenteainsi le nombre d’elements dans le sous-arbre de x. Chaque enfant dex a une hauteur noire qui vaut bh(x) ou bh(x)% 1, selon que son bit de

35

couleur soit respectivement rouge ou noir. Etant donne que la hauteurde chacun de ces enfants vaut h % 1, on peut appliquer l’hypothese derecurrence sur ces nœuds, et ainsi deduire que le sous-arbre de chacunde ces elements contient au moins 2bh(x)!1 % 1 nœuds. Finalement, lesous-arbre de x doit contenir au minimum (2bh(x)!1 % 1) + (2bh(x)!1 %1) + 1 = 2bh(x) % 1 nœuds, ce qui prouve bien le lemme.

!

Theoreme 2. Un arbre rouge-noir T ayant n nœuds a une hauteur au plusegale a 2 · lg(n + 1) + 2.

Demonstration : Supposons que la hauteur de l’arbre rouge-noir T vauth. Etant donne que dans un chemin allant de la racine a un sous-arbre vide ilne peut y avoir deux arcs rouges successifs et que le bit de la racine est noir,il doit y avoir au moins h/2 nœuds ayant un bit noir sur ce chemin. Des lors,bh(y) (ou y est la racine de T ) vaut au moins h/2% 1. Par le lemme 1, nousdeduisons que T contient au moins 2bh(y) % 1 = 2h/2!1 % 1 nœuds. Sachantque T contient exactement n nœuds, nous en deduisons l’inegalite suivante :

n " 2h/2!1 % 1

( n + 1 " 2h/2!1

En prenant le logarithme des deux membres, nous obtenons :

log(n + 1) " h

2% 1

( log(n + 1) + 1 " h

2( 2 · log(n + 1) + 2 " h

!Ainsi, par cette propriete, nous constatons que la hauteur d’un arbre

rouge-noir a n nœuds vaut O(log n), ce qui implique que les operations derecherche, d’insertion, de successeur et de predecesseur se font en O(log n)au pire cas.

5.3 Conclusion

Dans ce chapitre, nous avons detaille la structure des arbres rouges-noirset analyse ses performances. Celle-ci fournit des performances interessantes

36

pour une operation : un cout au pire cas de O(log n). Cependant, cette struc-ture n’atteint pas l’optimalite dynamique, car elle est O(logn)%competitive.

Un inconvenient de cette structure est qu’elle n’est pas capable de s’adap-ter a la sequence d’acces a traiter. Si par exemple une sequence d’accesconsiste a acceder plusieurs fois a un meme nœud et que celui-ci se trouveau bas de l’arbre, la structure e#ectuera chacun des acces a ce nœud avec uncout au pire cas de O(log n), alors qu’en le remontant a la racine, elle auraitpu ameliorer les acces a ce nœud.

37

Chapitre 6

Arbres binaires de rechercheauto-ajustables

Dans ce chapitre, nous allons d’abord definir la notion d’arbre binairede recherche auto-ajustable. Ensuite, nous allons illustrer ce concept par lapresentation des splay trees. Et nous terminerons par une comparaison entreles arbres rouges-noirs et les splay trees.

6.1 Definition

Un arbre binaire de recherche auto-ajustable est un ABR sur lequel nousappliquons une regle apres chaque operation dans le but d’equilibrer l’arbre.En general, le but de cette regle n’est pas d’avoir, a tout moment, une hauteurpour l’arbre qui soit logarithmique en le nombre d’elements. Par contre, nousnous attendons a ce que, pour une sequence su%samment longue, la regleequilibre l’arbre de maniere a avoir une complexite amortie (cfr point 2.4.3)logarithmique en la taille de l’arbre.

6.2 Splay trees

Cette partie contient une presentation des splay trees avec ses principalesoperations et l’analyse de ses performances. Le choix de cette structure auto-ajustable, plutot qu’une autre, se justifie par le fait que cette structure estsans conteste l’une des plus interessantes et l’une des plus impressionnantes,qui ait jamais ete developpee. Elle possede un eventail de proprietes treslarge, bien qu’elle soit definie sur une idee assez simple.

La presentation de cette structure est basee sur l’ouvrage de Jean Cardinal[Car04] et sur l’article de Sleator et Tarjan [ST85].

38

6.2.1 Splaying

L’operation de splaying sur un nœud x consiste a le remonter a la racinepar une serie de rotations. Trois types de rotations peuvent etre employes :

1. la rotation simple (cfr point 2.1.4) : nous l’appliquons si le nœud asplayer n’a pas de grand-pere.

2. la rotation zig-zag : nous l’appliquons si le nœud a splayer est un filsgauche (respectivement fils droit) et que son pere est un fils droit (res-pectivement fils gauche). Cette rotation est en fait une rotation double(cfr point 2.1.4).

3. la rotation zig-zig (cfr point 2.1.4) : nous l’appliquons si le nœud asplayer est un fils gauche (respectivement fils droit) et que son pere estun fils gauche (respectivement fils droit).

6.2.2 Recherche

L’algorithme de recherche dans un splay tree est identique a l’algorithmed’acces des ABR defini pour le modele dynamique (cfr point 2.2.1), hormisqu’apres avoir atteint le nœud desire, il faut e#ectuer un splaying sur cenœud.

6.2.3 Insertion

L’algorithme d’insertion pour les splay trees est le suivant.En commencant le traitement a la racine, il faut e#ectuer les operations

suivantes :

1. Designons par x le nœud courant. Il faut deplacer le pointeur courantsur le fils gauche ou le fils droit de x suivant que la cle a inserer soit,respectivement, plus petite ou plus grande que x.

Cette premiere etape est a iterer tant que le nœud courant ne pointepas sur un sous-arbre vide.

2. A ce niveau, le pointeur courant pointe sur un sous-arbre vide. Il nesu%t, des lors, qu’a inserer le nouveau nœud dans ce sous-arbre videet a e#ectuer un splaying sur ce nœud.

6.2.4 Suppression

L’algorithme de suppression pour les splay trees est le suivant :

1. Rechercher l’element a supprimer en utilisant l’algorithme de recherche.

39

2. Lorsque l’element est repere, il faut le splayer. Par ce splaying, cetelement devient la racine de l’arbre.

3. Enlever la racine de l’arbre. Cette suppression a pour consequence decreer deux sous-arbres Tg et Td (Tg est le sous-arbre gauche de la racineenlevee et Td est son sous-arbre droit).

4. Rechercher le plus grand element de Tg. Pour cela, il faut partir de laracine de l’arbre et suivre le chemin des fils droits. Le dernier nœudrencontre sur ce chemin est l’element maximal de Tg.

5. Realiser un splaying du plus grand element de Tg. Cet element devientalors la racine de Tg et a un sous-arbre droit vide, car il est le plusgrand element de Tg.

6. Fusionner Tg et Td en accrochant Td comme sous-arbre droit de la racinede Tg.

6.2.5 Analyse des performances

L’analyse des performances des splay trees se fera par une analyse amor-tie. Cette analyse necessite donc d’introduire une fonction potentiel (cfr point2.4.3). Le choix de cette fonction est crucial, car de cette fonction dependentles resultats que nous obtiendrons. Si nous utilisons une mauvaise fonctionpotentiel, nous ne parviendrons pas a demontrer les resultats escomptes.

La fonction potentiel utilisee dans cette analyse est celle introduite parSleator et Tarjan [ST85]. Elle est decrite dans le paragraphe ci-dessous.

Supposons que chaque nœud x d’un arbre T ait un poids w$(x) ; il s’agitd’une valeur arbitraire positive, mais fixee. La taille s(x) d’un nœud x est lasomme des poids de tous les nœuds appartenant au sous-arbre de x (w$(x)est inclus dans cette somme). Le rang r(x) d’un nœud x est le logarithme enbase 2 de sa taille. Finalement, le potentiel d’un arbre T est la somme desrangs de tous ses nœuds. En resume :

w$(x) ) R+ , !x ) T

s(x) =!

j"Txw$(j) , ou Tx est le sous-arbre de x.

r(x) = log(s(x)) , par log nous entendons logarithme en base 2.

P (T ) =!

x"T r(x)

En se basant sur cette fonction potentiel, nous pouvons demontrer lelemme suivant, qui est la propriete de base permettant de caracteriser lesperformances amorties des splay trees. Nous nous limiterons pour chaque

40

propriete a l’idee de la demonstration.

6.2.5.1 Access Lemma

Le cout amorti necessaire pour e"ectuer un splaying sur un nœud x dansun arbre de racine t est d’au plus 3(r(t) - r(x)) + 1.

La demonstration de ce lemme est decrite, notamment, dans l’ouvragede Weiss [Wei99]. L’idee de la demonstration, est de calculer le cout d’unerotation simple, d’une rotation zig-zig et d’une rotation zig-zag en se basantsur la fonction potentiel definie ci-dessus et utilisant l’equation fondamentalepour definir une complexite amortie (CA = CE + $P , cfr point 2.4.3). Lesplaying etant une sequence de rotations simple, zig-zig et zig-zag, son coutpeut alors etre calcule a partir du cout de ces rotations.

En partant de cette propriete, il est alors possible de demontrer touteune serie de proprietes sur les splay trees en assignant des poids aux nœudsde l’arbre. Les proprietes, ainsi deduites, sont presentees ci-dessous.

6.2.5.2 Theoreme d’equilibre

Dans un arbre de taille n, le cout total de m operations vaut O(m · log n).La complexite amortie d’une operation vaut alors O(log n).

Pour demontrer ce theoreme, il su%t d’utiliser l’Access Lemma et d’assi-gner un poids de 1/n a chaque nœud de l’arbre. Le theoreme d’equilibre est,donc, atteint en imposant une distribution uniforme sur les cles.

Nous constatons, donc, que si la distribution sur les cles est uniforme,les splay trees ont un cout de recherche amorti egal au cout de recherche aupire cas d’arbres equilibres comme les arbres AVL et les arbres rouges-noirset cela sans utiliser la moindre information de reequilibrage.

6.2.5.3 Theoreme d’optimalite statique

La notion d’optimalite statique est definie au point 3.3 et est rappeleeci-dessous.

Soient un arbre de taille n et une sequence d’acces X = x1, x2, . . . , xm.Le temps d’acces total de cette sequence de m operations vaut :

O

"n#

i=1

f(i) · log

%m

f(i)

&$, (6.1)

41

ou f(i) est la frequence d’acces du nœud i. Des lors, f(i)/m est sa frequencerelative.

Pour demontrer ce theoreme, il su%t d’utiliser l’Access Lemma et d’assi-gner a chaque nœud sa frequence relative. En d’autres termes, pour un nœudxi, son poids w$(xi) vaut f(xi)/m.

Les ABRO [Knu73] (cfr chapitre 4) atteignent la propriete d’optimalitestatique, mais ils requierent pour cela de connaıtre prealablement la frequencede chaque nœud. Les splay trees atteignent l’optimalite statique sans cetteconnaissance prealable de la frequence de chaque nœud.6.2.5.4 Theoreme du static finger

La notion de static finger est definie au point 3.2 et est rappelee ci-dessous.Soient un arbre de taille n, un nœud specifique f appele le finger et une

sequence d’acces X = x1, x2, . . . , xm. Le cout pour traiter cette sequence dem acces vaut :

O

"m#

i=1

log(1 + |xi % f |)$

, (6.2)

ou |xi % f | est la distance dans l’ordre symetrique entre le finger f et lenœud xi. Donc, |xi % f | est le nombre d’elements situes entre xi et f dansla sequence triee des nœuds de l’arbre.

Pour demontrer ce theoreme, il su%t d’utiliser l’Access Lemma et d’assi-gner a chaque nœud xi de l’arbre un poids w$(xi) egal a 1

(1+|xi!f |)2 .Il est important de noter que le finger f est un nœud quelconque de

l’arbre, mais une fois choisi, ce finger doit rester le meme durant toutel’execution de la sequence d’acces. Ce qui est le plus remarquable est queles splay trees atteignent la propriete static finger pour un quelconque fingerpossible. En e#et, il su%t d’utiliser ce finger dans l’assignation des poidsaux nœuds.

6.2.5.5 Theoreme du working set

La notion de working set est definie au point 3.4 et est rappelee ci-dessous.Soient un arbre de taille n et une sequence d’acces X = x1, x2, . . . , xm.

Le cout pour traiter cette sequence de m acces vaut :

O

"m#

i=1

log(w(xi))

$, (6.3)

42

ou w(xi) est le nombre d’elements distincts entre l’acces xi et le precedentacces a cet element.

L’assignation des poids pour ce theoreme est plus compliquee, car il fautmodifier le poids des nœuds durant l’execution de la sequence.

6.2.5.6 Theoreme du dynamic finger

La notion de dynamic finger est definie au point 3.5 et est rappelee ci-dessous.

Soient un arbre de taille n et une sequence X = x1, x2, . . . , xm. Le coutpour traiter cette sequence de m acces vaut :

O

"m!1#

j=1

log (|xj+1 % xj | + 1)

$

(6.4)

En 1985, epoque de la publication de l’article de Sleator et Tarjan [ST85], ce theoreme n’avait pas pu etre demontre. Ce n’est qu’en 1995, que Cole[Col00] y est parvenu, mais la demonstration de ce theoreme reste tres com-plexe.

Le splay tree est la seule structure ayant cette propriete et repondanta la definition du modele dynamique des ABR (cfr point 2.2.1), mais lademonstration de cette propriete est complexe. Un probleme interessant(propose par Stefan Langerman) serait d’elaborer une structure relativementsimple et ayant la propriete dynamic finger avec une demonstration de cettepropriete plus simple que celle des splay trees.

6.2.5.7 Theoreme du scanning

Soient un arbre de taille n et une sequence d’acces X = 1, 2, . . . , n. Lecout pour traiter ces n acces vaut :

O(n) (6.5)

Ce theoreme est en fait un corollaire du theoreme dynamic finger. Ene#et, comme les nœuds sont accedes par ordre croissant sur les cles, nousavons que |xj+1 % xj | = 1 (! j ) [1, n% 1]). Et par consequent, la complexitepour traiter X vaut O(n).

43

6.2.5.8 Conjecture d’unifiee

La notion d’unifiee est definie au point 3.6 et est rappelee ci-dessous.Soient un arbre de taille n et une sequence d’acces X = x1, x2, . . . , xm.

Le cout pour traiter cette sequence de m acces vaut :

O

"m#

i=1

minj"X

(log (w(i, j) + |xi % j| + 1))

$(6.6)

Cette propriete n’a pas encore pu etre demontree pour les splay trees etelle reste donc une conjecture.

6.2.5.9 Conjecture d’optimalite dynamique

La notion d’optimalite dynamique est definie au point 3.7 et est rappeleeci-dessous.

Soient un arbre de taille n et une sequence d’acces X. Le cout pourexecuter cette sequence vaut :

O(OPT (X)) (6.7)

Si cette conjecture est demontree, cela signifierait que les splay treespeuvent executer n’importe quelle sequence d’acces avec un cout optimalet cela, par une simple regle de rearrangement et sans garder la moindreinformation supplementaire. Ce serait comme si les splay trees etaient ca-pables de prevoir la sequence a executer, de maniere a pouvoir s’y adapteret l’executer de maniere optimale.

Cette propriete n’est malheureusement pas encore demontree pour lessplay trees. Et a l’heure actuelle, cette structure est l’une des rares a encorepouvoir pretendre atteindre l’optimalite dynamique.

6.3 Comparaisons

Nous allons comparer les arbres rouges-noirs et les splay trees. Ces com-paraisons sont en general valables pour les ABR equilibres et les ABR auto-ajustables.

Pour le temps d’execution au pire cas, les arbres rouges-noirs presententdes performances plus interessantes que les splay trees. Les splay trees four-nissent des performances interessantes sur de longues sequences d’acces, alors

44

que les arbres rouges-noirs ont pour but de fournir des resultats interessantssur une seule operation. L’inconvenient des splay trees est que les operationsde reorganisation peuvent etre nombreuses, et ainsi couter cher. Quant auxarbres rouges-noirs, les operations de reequilibrage restent limitees, et nenuisent donc pas aux performances.

Au niveau de l’espace memoire, les arbres rouges-noirs necessitent de sto-cker un bit de couleur, alors que les splay trees n’ont pas besoin d’informa-tions supplementaires. Les arbres rouges-noirs necessitent donc plus d’espacememoire, mais ce surplus reste limite (n bits pour un arbre de taille n).

En ce qui concerne les proprietes atteintes par les structures, nous avonsque les splay trees ont un eventail tres large de proprietes, ce qui n’est pasdu tout le cas pour les arbres rouges-noirs. Nous remarquons, notammentgrace a ces proprietes, que les splay trees ont la capacite de s’adapter a unesequence d’acces. Ceci est du au fait que les splay trees gardent pres dela racine les nœuds frequemment accedes. Les arbres rouges-noirs n’ont pascette capacite de s’adapter a une sequence d’acces, ce qui peut influer sur letemps d’execution de la sequence. Supposons par exemple, qu’une sequenced’acces consiste a acceder plusieurs fois a un meme nœud x situe dans le basde l’arbre. Les arbres rouges-noirs e#ectueront chacun des acces a x avec uncout O(log n), alors que pour les splay trees, le premier acces a x se fera avecun cout egal a la profondeur de x et les acces suivants a x se feront en tempsconstant.

6.4 Conclusion

Si la distribution sur les cles est uniforme (theoreme d’equilibre), la re-cherche pour les splay trees se fait avec une complexite amortie en O(log n).Mais pour une distribution qui n’est pas uniforme (theoreme d’optimalitestatique, theoreme du static finger et theoreme du working set), les resultatsobtenus pour la recherche sont meilleurs que celui obtenu pour la distribu-tion uniforme. On peut comprendre cela de maniere intuitive. Si la distri-bution n’est pas uniforme, certains elements seront accedes plus souvent qued’autres. Les elements souvent accedes auront tendance a se situer en haut del’arbre, alors que les elements moins frequemment accedes se situeront dansle bas de l’arbre. Et comme les elements du haut sont plus souvent accedes,on aura plus d’acces a faible cout, ce qui aura pour consequence d’ameliorerle cout total de l’execution de la sequence d’acces.

45

Troisieme partie

Optimalite dynamique

46

Chapitre 7

Bornes inferieures sur le coutdes arbres binaires de recherche

Ce chapitre est consacre au probleme de borner inferieurement le coutd’execution d’une sequence d’acces par un ABR. L’interet d’avoir de tellesbornes est double. D’une part, il est possible de developper de nouvellesstructures a partir d’une borne inferieure (cela a par exemple ete le cas pour lastructure Tango que nous etudierons dans le chapitre 8). D’autre part, il seraitpossible de prouver l’optimalite dynamique grace a une borne inferieure. Ene#et, si nous parvenons a demontrer que, pour un ABR, le cout d’executiond’une quelconque sequence d’acces est egal a la borne inferieure, alors nousen deduirons immediatement que la structure est optimale dynamiquement.

Dans ce chapitre, nous allons presenter trois bornes inferieures sur letemps d’execution d’une sequence d’acces : La Borne Inferieure de Couver-ture de Rectangle, La Borne Inferieure d’Entrelacement et La Seconde Bornede Wilber. Les deux dernieres bornes seront en fait derivees de la premiere.

Ce chapitre est base sur l’article de Derryberry, Sleator et Wang [DSW05],sur l’article de Wilber [Wil89] et sur l’article de Demaine, Harmon, Iaconoet Patrascu [DHIP04].

7.1 Modele

Pour prouver la borne inferieure de couverture de rectangle, nous devonspasser au modele standard. La di#erence entre ce modele et le modele dyna-mique (cfr point 2.2.1) est que le nœud a acceder doit d’abord etre ramenea la racine par une serie de rotations. Ensuite, seulement, l’acces au nœudse fait a la racine. Apres l’acces au nœud, l’algorithme peut e#ectuer desrotations pour ameliorer le cout des futurs acces.

47

Le cout d’acces est defini comme le nombre de rotations plus 1. Commeune rotation est inversible, le cout dans le modele standard vaut au plus deuxfois celui dans le modele dynamique.

Par consequent, si nous parvenons a determiner une borne inferieure surle cout d’execution d’une sequence d’acces dans le modele standard, alors ilsu%t de prendre cette borne et de la diviser par deux pour obtenir une bornedans le modele dynamique.

7.2 La borne inferieure de couverture de rec-tangle

Considerons une sequence d’acces comme un ensemble de points dansl’espace a deux dimensions, ou la coordonnee x correspond au temps etla coordonnee y correspond a l’espace des cles. Pour une sequence X =x1, x2, . . . , xm, chaque acces xi correspond au point (i, xi). Notons P l’en-semble des points generes a partir de X.

Une boıte est un rectangle, dont deux coins opposes sont des points deP . Nous considerons deux types de boıtes : les boıtes hautes et les boıtesbasses. Une boıte est haute si ses coins inferieur gauche et superieur droitsont dans P . Et une boıte est basse si ses coins superieur gauche et inferieurdroit sont dans P . Chaque boıte contient un diviseur, qui consiste en uneligne horizontale traversant la boıte d’une extremite a l’autre. L’ordonneedu diviseur est choisie de maniere arbitraire, mais elle doit cependant etredi#erente de l’ordonnee de tous les points de P et elle doit etre compriseentre l’ordonnee minimale et l’ordonnee maximale de la boıte.

Deux boıtes sont dites en conflit si elles sont toutes deux des boıtes hautesou des boıtes basses et si leur intersection contient une partie ou l’entieretedes deux diviseurs.

Pour illustrer ces definitions, considerons le schema de la fi-gure 7.1 representant les points correspondant a la sequence X =3(x1), 5(x2), 1(x3), 7(x4), 10(x5), 2(x6). Trois boıtes sont illustrees sur ceschema (les diviseurs sont representes en pointilles). Les boıtes A et B sonthautes, tandis que la boıte C est basse. De plus, les boıtes A et B sont enconflit, alors que les boıtes B et C ne le sont pas.

Avant d’enoncer et de demontrer la borne inferieure de couverture de rec-tangle, nous prouvons le lemme qui suit. Nous notons par LCA(x, y) l’ancetrecommun le plus bas des nœuds x et y. Les demonstrations du lemme 2 et dutheoreme qui suit ce lemme sont basees sur l’article [DSW05]. La contribu-tion personnelle dans ces deux demonstrations a consiste a aller plus dans le

48

Fig. 7.1 – Representation graphique de la sequence X = 3, 5, 1, 7, 10, 2.

49

detail en eclaircissant certains points de la demonstration.

Lemme 2. Soient a et b deux nœuds distincts dans un ABR T avec a < b.Soient p et c deux nœuds de T avec p parent de c. Si une rotation est e"ectueesur les nœuds c et p et qu’elle implique que LCA(a, b) change, alors les quatreproprietes suivantes sont verifiees :

1. a # c # b

2. a # p # b

3. LCA(a, b) = p avant la rotation

4. LCA(a, b) = c apres la rotation

Demonstration : Considerons une permutation & des cles de T , ou cescles sont triees par ordre croissant de profondeur. Les cas d’egalite pour desnœuds ayant la meme profondeur sont geres arbitrairement. On impose unecontrainte : les nœuds p et c doivent etre adjacents (p precede alors c, caril a une profondeur plus petite que celle de c). Comme les nœuds sont triespar ordre croissant de profondeur, l’arbre obtenu en inserant de manieresuccessive les cles de & a partir d’un arbre vide est T . Notons que LCA(a, b)est le nœud le moins profond ayant une valeur comprise entre a et b, cartous les autres nœuds ayant une valeur comprise entre a et b appartiennentau sous-arbre de LCA(a, b). Par consequent, LCA(a, b) est le premier nœuddans & ayant une valeur comprise entre a et b.

Si nous permutons les nœuds p et c dans &, l’arbre obtenu a partir decette sequence est celui que nous obtenons en e#ectuant une rotation sur cet p dans T , et cela parce que la permutation de p et c dans & implique quele nœud c est insere avant p.

La sequence & est donc une autre maniere de representer une rotationsur p et c, ainsi que LCA(a, b).

Supposons que nous realisons une rotation sur p et c, et que cela aitcomme consequence que LCA(a, b) change. Cela signifie, qu’au niveau de&, le fait de permuter p et c implique que le premier nœud dans & ayantune valeur entre a et b change. Nous en deduisons alors que les nœuds pet c appartiennent a l’intervalle [a, b], car sinon la permutation de p et cdans & n’aurait pas modifie le premier element de & appartenant a [a, b]. Deplus, comme le premier element de & appartenant a [a, b] est modifie par lapermutation de p et c, nous en deduisons que LCA(a, b) etait egal a p avantla rotation et que LCA(a, b) vaut c apres la rotation.

!

50

Theoreme 3 (Theoreme de la borne inferieure de couverture derectangle). Soient une sequence d’acces X = x1, x2, . . . , xm et un ensembleP de points correspondant a X. Soit B un ensemble de boıtes pour P, qui prisesdeux a deux, ne sont pas en conflit. Le nombre de rotations necessaires a unABR (repondant a la definition du modele standard) pour traiter X vaut aumoins |B|.

Demonstration : Nous allons associer a chaque boıte Bk de B une rotationRk realisee par l’ABR pour traiter X. A deux boıtes ne sera pas associeela meme rotation, ce qui permettra de deduire que le nombre de rotationse#ectuees par l’ABR pour traiter X vaut au moins le nombre de boıtes dansB.

Considerons une boıte haute Bk. Disons que le point (i, xi) est son coininferieur gauche et que le point (j, xj) est son coin superieur droit. Apresl’acces xi, nous avons que ce nœud devient la racine de l’arbre. De meme,apres l’acces xj , nous avons que ce nœud-ci devient la racine de l’arbre. L’in-tervalle de temps couvert par la boıte vaut [i, j]. Au debut de cet intervalle,LCA(xi, xj) vaut xi, car ce nœud est la racine de l’arbre et a la fin de l’in-tervalle, LCA(xi, xj) vaut xj , car ce nœud-ci est la racine de l’arbre. Parconsequent, durant l’intervalle [i, j], nous avons que LCA(xi, xj) a du passerd’une valeur inferieure au diviseur de Bk a une valeur superieure au divi-seur de Bk. La rotation Rk associee a Bk est la premiere, qui implique queLCA(xi, xj) traverse le diviseur de Bk de bas en haut.

Par le lemme 2, si LCA(xi, xj) change a cause d’une rotation, alors cetterotation est appliquee sur deux elements p et c appartenant a l’intervalle[xi, xj ]. Les points correspondant a ces deux cles ont donc une ordonneecomprise entre xi et xj . La rotation Rk est representee par une ligne verticaletraversant le diviseur de la boıte Bk (cfr figure 7.2).

Une rotation Rk ne peut pas etre associee a deux boıtes hautes di#erentes.En e#et, supposons que Rk soit associee a deux boıtes di#erentes Bl et Bk.Des lors, Rk doit traverser le diviseur de Bl et de Bk. L’intersection de Bl etde Bk doit contenir Rk et par consequent les diviseurs de Bl et de Bk. Or,cela implique que Bl et Bk soient en conflit, ce qui est impossible car cesdeux boıtes appartiennent a B et ne sont par definition pas en conflit.

De maniere analogue, nous pouvons montrer qu’une rotation Rk ne peutpas etre associee a deux boıtes basses di#erentes.

Une rotation Rk ne peut pas etre associee a une boıte basse et a une boıtehaute. Nous prouvons ceci en montrant que la rotation associee a une boıtehaute est une rotation gauche et la rotation associee a une boıte basse estune rotation droite. En e#et, considerons la boıte haute Bk et la rotation Rk

51

Fig. 7.2 – Rotation Rk representee par une fleche.

52

c

p

p

c

Fig. 7.3 – Avant la rotation on a que p est le parent de c et que p < c

qui y est associee et qui porte sur p et c (avec p parent de c). Comme cetterotation entre p et c implique que LCA(xi, xj) passe d’une valeur inferieureau diviseur de Bk a une valeur superieure au diviseur de Bk, alors nous avonsque p < c par le lemme 2, car LCA(xi, xj) = p avant la rotation Rk etLCA(xi, xj) = c apres cette rotation. Et comme p est le pere de c, alors larotation entre p et c est une rotation gauche (cfr figure 7.3). Nous pouvonsmontrer de maniere analogue que la rotation associee a une boıte basse estune rotation droite.

En conclusion, nous avons montre qu’une rotation ne peut pas etre as-sociee a deux boıtes di#erentes, ce qui prouve bien la borne inferieure decouverture de rectangle.

!

7.3 Applications de la borne inferieure decouverture de rectangle

Dans cette section, nous allons deriver deux bornes a partir de la borneinferieure de couverture de rectangle :

1. la borne inferieure d’entrelacement. Cette borne a ete developpee parDemaine, Harmon, Iacono et Patrascu [DHIP04].

2. la seconde borne de Wilber. Cette borne a ete developpee par Wilber[Wil89]

Les demonstrations dans cette section sont basees sur l’article [DSW05].La contribution personnelle a consiste a detailler les demonstrations en yeclaircissant certains points.

53

7.3.1 La borne inferieure d’entrelacement

Soient un ensemble de n cles {1, 2, . . . , n} et une sequence d’acces X =x1, x2, . . . , xm. La region gauche d’un nœud xi correspond a xi plus son sous-arbre gauche et la region droite de xi correspond a son sous-arbre droit.

Nous definissons ci-dessous la borne inferieure d’entrelacement en expli-quant la maniere de la calculer.

Le calcul de la borne inferieure d’entrelacement necessite de maintenirun arbre parfait P sur les cles {1, 2, . . . , n}. Pour calculer l’entrelacementIB(X, y) d’un nœud y , il faut etiqueter chaque acces xi de X par left si xi

appartient a la region gauche de y ou par right si xi appartient a la regiondroite de y ; si xi n’appartient a aucune des deux regions, il faut l’exclurede la sequence etiquetee. IB(X, y) correspond alors au nombre d’alternancesentre les labels left et right dans la sequence etiquetee creee.

La borne inferieure d’entrelacement IB(X) de la sequence X corresponda la somme des entrelacements IB(X, y) de chaque nœud y dans P . Nousavons donc :

IB(X) =#

y"P

IB(X, y) (7.1)

Theoreme 4 (Theoreme de la borne inferieure d’entrelacement).Soient un ensemble de n cles {1, 2, . . . , n} et une sequence d’acces X =x1, x2, . . . , xm. Dans le modele standard, nous avons la borne inferieure sui-vante sur le cout optimal OPT(X) de l’algorithme o!ine pour traiter X :

OPT (X) " IB(X) + m (7.2)

Demonstration : Pour prouver ce theoreme, il faut montrer que nouspouvons placer une boıte haute pour chaque alternance left-right et une boıtebasse pour chaque alternance right-left, de sorte que les boıtes prises deux adeux ne sont pas en conflit. Comme les boıtes hautes et les boıtes basses nepeuvent pas etre en conflit, il su%t de demontrer que deux boıtes hautes nepeuvent pas etre en conflit et que deux boıtes basses ne peuvent pas etre enconflit.

Supposons que pour un nœud v, il y ait une alternance left-right dans lasequence etiquetee au temps r. La boıte haute, correspondant a cette alter-nance, est construite de la maniere suivante. Soit xl le dernier acces ayantlieu dans le sous-arbre gauche de v strictement avant le temps r. Disonsque cet acces ait eu lieu au temps l (l < r). Et soit xr l’acces ayant pro-voque l’alternance left-right au temps r. Nous creons la boıte correspondanta cette alternance avec (l, xl) comme coin inferieur gauche, (r, xr) comme coin

54

superieur droit et v % # comme diviseur (avec # tres petit). Nous denotonscette boıte par le triplet ((l, xl), (r, xr), v % #).

Considerons deux boıtes hautes : B = ((l, xl), (r, xr), v % #) et B$ =((l$, x$

l), (r$, x$

r), v$ % #). Quatre cas sont a envisager :

1. si v = v$, alors les boıtes B et B$ ne peuvent pas se chevaucher, car lesintervalles [l, r] et [l$, r$] sont soit disjoints, soit adjacents. Et donc, lesboıtes ne peuvent pas etre en conflit.

2. si v n’est pas un ancetre de v$ et si v$ n’est pas un ancetre de v, alors l’es-pace des cles [xl, xr] correspondant a l’espace des ordonnees de la boıteB et l’espace de cles [x$

l, x$r] correspondant a l’espace des ordonnees de

la boıte B$ sont disjoints. Ces deux boıtes ne peuvent donc pas etre enconflit.

3. si v$ est un ancetre de v et si v < v$, alors v appartient au sous-arbregauche de v$. Et donc, tous les elements dans l’espace des cles [xl, xr]de B sont strictement plus petits que v$. De plus, comme B est uneboıte haute, nous avons que xl < xr. Tout ceci nous permet de deduireque xl < xr # v$ % 1 < v$ % #. Ainsi, B ne peut pas contenir le diviseurde B$ et les boıtes B et B$ ne peuvent donc pas etre en conflit.

4. si v$ est un ancetre de v et si v > v$, alors v appartient au sous-arbredroit de v$. Et donc, tous les elements dans l’espace des cles [xl, xr] deB sont strictement plus grands que v$. De plus, comme B est une boıtehaute, nous avons que xl < xr. Tout ceci nous permet de deduire quexr > xl " v$ + 1 > v$ % #. Ainsi, B ne peut pas contenir le diviseur deB$ et les boıtes B et B$ ne peuvent donc pas etre en conflit.

Les cas ou v est un ancetre de v$ sont similaires au cas 3 et 4. Et les casou B et B$ sont des boıtes basses sont analogues aux quatre cas ci-dessus.

Nous avons donc prouve que dans tous les cas possibles B et B$ ne peuventpas etre en conflit.

Par consequent, nous avons prouve que IB(X) est une borne inferieure surle nombre de rotations necessaires a un algorithme pour traiter une sequenceX = x1, x2, . . . , xm. Comme le cout d’un algorithme pour traiter la sequenceX vaut le nombre de rotations e#ectuees plus m (un cout de 1 est necessairepour acceder au nœud ramene a la racine), alors nous pouvons rajouter m ala borne inferieure IB(X). Finalement, nous avons que :

OPT (X) " IB(X) + m (7.3)

!Corollaire 1. Soient un ensemble de n cles {1, 2, . . . , n} et une sequenced’acces X = x1, x2, . . . , xm. Dans le modele dynamique, nous avons la borne

55

inferieure suivante sur le cout optimal OPT(X) de l’algorithme o!ine pourtraiter X :

OPT (X) " 1

2· (IB(X) + m) (7.4)

7.3.2 La seconde borne de Wilber

Soient un ensemble de n cles {1, 2, . . . , n} et une sequence d’acces X =x1, x2, . . . , xm.

De maniere informelle, nous pouvons definir cette borne de la manieresuivante. Pour chaque acces xi de X, nous commencons la traversee de lasequence a partir de xi!1 en reculant jusqu’a x1. Nous gardons a chaqueetape une trace des deux acces les plus proches de xi ; l’un devant etre pluspetit que xi et l’autre plus grand que xi. La seconde borne de Wilber pourun acces xi est le nombre de fois qu’un record de proximite s’est produitsur un cote di#erent du dernier record. La seconde borne de Wilber pour lasequence X est egale a la somme des secondes bornes de Wilber de chaqueacces de X.

De maniere formelle, pour determiner la seconde borne de Wilber pourl’acces xi, il faut trouver la sous-sequence de taille maximale constitueed’acces traversants xc1 , . . . , xcK(i)+1

(K(i) est alors egal a la seconde bornede Wilber pour l’acces xi) (si nous prenons deux acces adjacents de cettesequence, alors ils representent une amelioration du record de proximite,mais sur des cotes di#erents par rapport a xi) et une sous-sequence d’accesinterieurs xb1 , . . . , xbK(i)

telles que :

1. Pour s’assurer que les acces traversants et les acces interieurs reculentdans le temps, il faut que :

cj+1 < bj # cj # c1 = i % 1 (7.5)

2. Pour s’assurer que deux acces traversants successifs se trouvent surdeux cotes di#erents de xi, il faut que !j ) [1, K(i)] :

(xcj+1 % xi) · (xcj % xi) # 0 (7.6)

3. bj est defini comme suit !j ) [1, K(i)] :

Sj =*k | (cj+1 < k < i) * ((xcj % xi) · (xk % xi) > 0)

+

bj = mink"Sj

|xk % xi|

Si le minimum est atteint pour plusieurs k ) Sj, alors par convention,nous prenons celui dont la valeur est la plus petite. Cette definition de

56

bj assure que xbj est l’element de l’ensemble M (M est l’ensemble deselements de X qui ont un indice dans l’intervalle (cj+1, i)) qui est leplus proche de xi et qui se trouve du meme cote que xcj .

4. Pour s’assurer que xcj+2(!j ) [1, K(i) % 1]) est un nouveau record, ilfaut que :

|xcj+2 % xi| < |xbj % xi| (7.7)

Tous les elements qui appartiennent a l’ensemble M (M est l’ensembledes elements de X qui ont un indice dans l’intervalle (cj+1, i)) et quisont du meme cote que xcj+2 (par rapport a xi) sont plus eloignes dexi que l’est xcj+2 .

La seconde borne de Wilber pour la sequence X est egale a :

m#

i=1

K(i) (7.8)

Pour illustrer cette definition, prenons la sequence X =7(x1), 15(x2), 1(x3), 2(x4), 5(x5), 20(x6), 23(x7), 10(x8). La seconde bornede Wilber pour l’acces 10 vaut 3, car il s’agit du nombre de fois qu’un recordde proximite est ameliore sur un cote di#erent par rapport a 10 (cfr figure7.4).

Calculons cette borne en utilisant la definition formelle. Nous calculonsdonc la valeur de K(8). Pour cela, prenons les valeurs suivantes pour lesindices des acces traversants :

1. c1 = 7 (donc xc1 = 23)

2. c2 = 5 (donc xc2 = 5)

3. c3 = 2 (donc xc3 = 15)

4. c4 = 1 (donc xc4 = xcK(8)+1= 7)

Nous pouvons alors calculer la valeur de Sj (pour j = 1, 2, 3 et 4) definiea la propriete 3 pour en deduire que :

1. b1 = 6 (donc xb1 = 20), car S1 = {6, 7}2. b2 = 5 (donc xb2 = 5), car S2 = {3, 4, 5}3. b3 = 2 (donc xb3 = 15), car S3 = {2, 6, 7}

Les sous-sequences d’acces traversants 23, 5, 15, 7 et d’acces internes20, 5, 15 verifient les quatre proprietes et sont maximales. Nous avons doncque la seconde borne de Wilber pour l’acces 10 vaut 3, car K(8) = 3.

57

Fig. 7.4 – La seconde borne de Wilber pour l’acces 10 vaut 3.

58

Theoreme 5 (Theoreme de la seconde borne de Wilber). Soient unensemble de n cles {1, 2, . . . , n} et une sequence d’acces X = x1, x2, . . . , xm.Le nombre de rotations necessaires dans le modele standard pour traiter lasequence X vaut au moins

!mi=1 K(i). Et donc,

OPT (X) " m +m#

i=1

K(i) (7.9)

Ce theoreme n’est pas demontre ici, mais une demonstration est dispo-nible dans l’article [DSW05].

7.4 Conclusion

Dans ce chapitre, nous avons presente trois bornes inferieures sur le tempsd’execution d’une sequence d’acces. La premiere borne, la borne inferieurede couverture de rectangle, nous a permis d’en deriver deux autres : la borneinferieure d’entrelacement et la seconde borne de Wilber. La borne inferieured’entrelacement sera utilisee pour elaborer une structure ABR dans le cha-pitre suivant. Cette borne est en fait une simplification de la Premiere Bornede Wilber [Wil89]. Et la seconde borne de Wilber est utilisee dans un conceptparticulier appele Key-Independent Optimality [Iac05].

Un probleme [DSW05] concernant la borne inferieure de couverture derectangle est de savoir si cette borne est egale a l’optimalite dynamique (aun facteur constant pres).

Un autre probleme [DSW05] concernant cette borne est de savoir si ellepeut etre calculee en temps polynomial, car la valeur de cette borne est egalea |B|, c’est-a-dire au nombre de boıtes qui prises deux a deux ne sont pas enconflit, mais ce nombre depend de la maniere dont on place les diviseurs desboıtes.

59

Chapitre 8

Tango

Tango est une structure de donnees, qui atteint un taux de competitivitede O(log(log n)). Il s’agit de la premiere structure de donnees, qui a ameliorele taux de competitivite trivial de O(log n). Elle a ete elaboree en 2004 parDemaine, Harmon, Iacono et Patrascu [DHIP04] et constitue une tres grandeavancee dans le domaine de l’optimalite dynamique.

Dans ce chapitre, nous commencerons par presenter Tango selon unepremiere approche, qui ne verifie pas la definition du modele dynamiquedes ABR (cfr point 2.2.1). Cette approche est necessaire pour comprendreles fondements du veritable algorithme. Ensuite, nous montrerons commentrealiser cet algorithme avec une structure ABR. Et pour finir, nous analyse-rons les performances de Tango.

8.1 Structures de donnees

Les sections presentant l’algorithme Tango sont basees sur l’article[DHIP04]. Cet article presente les grandes lignes de l’algorithme. La contri-bution personnelle a ete de presenter cet algorithme en detaillant tous lessous-algorithmes qui le constituent.

Supposons que nous ayons un ensemble {1, 2, . . . , n} de n cles et unesequence X = x1, x2, . . . , xm.

Nous notons par Ti l’etat de Tango apres avoir e#ectue les accesx1, x2, . . . , xi. A cote de cette structure, nous maintenons egalement un arbreparfait P , appele arbre de reference, construit sur les memes cles que cellesde T . Chaque nœud de l’arbre P contient une information supplementaire :son fils prefere. Le fils prefere d’un nœud x est son fils gauche si le dernieracces dans le sous-arbre de x dans P a eu lieu dans le sous-arbre gauche dex ou s’il consistait a atteindre x. Le fils prefere de x est son fils droit si le

60

dernier acces dans le sous-arbre de x dans P a eu lieu dans le sous-arbre droitde x. Dans le cas ou aucun acces n’a eu lieu dans le sous-arbre de x, alors xn’a pas de fils prefere.

L’arbre P est fixe durant toute l’execution de la sequence X ; seul le filsprefere des nœuds peut changer. Ainsi, l’etat Pi de l’arbre P au temps i (l’etatde P apres avoir execute les acces x1, x2, . . . , xi) est seulement determine parla sequence d’acces.

8.2 Algorithme de l’arbre de reference

L’etat Ti de Tango est determine a partir de l’etat Pi en appliquant l’al-gorithme suivant :

1. Suivre le fils prefere de la racine, puis le fils prefere de ce fils, et ainside suite jusqu’a atteindre une feuille. Nous obtenons, alors, un cheminallant de la racine a une feuille, qu’on appelle le chemin prefere.

2. Compresser ce chemin en un arbre auxiliaire R. A ce stade-ci, nouspouvons nous contenter d’admettre qu’un arbre auxiliaire est un arbrerouge-noir. Des informations supplementaires seront fournies plus loindans ce chapitre sur les arbres auxiliaires.

3. Supprimer ce chemin prefere de Pi. Cela a pour consequence de parti-tionner cet arbre en plusieurs pieces.

4. Proceder de maniere recursive sur chacune de ces pieces. Nous obtenons,alors, un arbre auxiliaire pour chaque piece. Il ne reste des lors qu’aaccrocher chacun de ces arbres obtenus a l’arbre auxiliaire R, tout enrespectant l’ordre ABR sur les nœuds de l’arbre. Pour rappel, l’ordreABR signifie que, pour chaque nœud x de l’arbre, les elements dans lesous-arbre gauche de x sont plus petits que x et les elements dans lesous-arbre droit de x sont plus grands que x.

Nous deduisons de cette construction, que l’arbre Ti est un arbre d’arbresauxiliaires, dans lequel l’ordre ABR est verifie.

Nous allons illustrer l’algorithme presente ci-dessus avec un exemple.Supposons que nous ayons l’arbre Pi de la figure 8.1 et que nous desironsconstruire l’arbre Ti.

Le chemin prefere de l’arbre de la figure 8.1 est constitue des nœuds3, 1 et 2. Il faut, alors, compresser ce chemin en un arbre auxiliaire. L’ar-ticle [DHIP04] ne precise pas comment compresser ce chemin. Nous allons ,alors, choisir de realiser cette compression en inserant, a l’aide de l’algorithmed’insertion des arbres rouges-noirs (cfr point 5.2.3), de maniere successive lesnœuds du chemin prefere en partant d’un arbre vide et en commencant les

61

3

2

1

0 6

5

4

= fils préféré

= fils non préféré

Fig. 8.1 – Arbre Pi.

insertions avec le nœud racine. Ainsi, pour compresser le chemin prefere dela figure 8.1, il su%t d’e#ectuer l’operation d’insertion sur les nœuds 3, 1 et2. Le resultat de ces operations donne l’arbre auxiliaire de la figure 8.2, quenous designons par Ri

Maintenant, que le chemin prefere de Pi est compresse, il faut le supprimerde l’arbre Pi. Ceci partitionne Pi en deux pieces (P 1

i et P 2i ) presentees a la

figure 8.3. Et il ne reste qu’a e#ectuer les memes operations sur chaque piece.Nous traitons, d’abord, la piece P 1

i constituee du nœud 0. Sa transforma-tion en arbre auxiliaire est triviale et consiste en le nœud 0. Nous designonscet arbre auxiliaire par R1

i .Nous traitons, maintenant, la derniere piece P 2

i constituee des nœuds 4,5 et 6. Le chemin prefere de cet arbre est constitue des nœuds 5 et 6. Lacompression de ce chemin, notee R3, est donnee a la figure 8.4.

Apres cette compression, il faut retirer le chemin prefere de P 2i , ce qui

donne une unique piece consistant en le nœud 4.La transformation de cette piece en arbre auxiliaire est triviale. Nous

designons par R4 cet arbre auxiliaire.Maintenant, il faut rassembler chaque arbre auxiliaire obtenu. On com-

mence par placer R4 comme fils gauche de la racine de R3, pour obtenirl’arbre auxiliaire relatif a P 2

i . L’agencement de R3 et R4 est realise de lasorte, de maniere a respecter l’ordre ABR. Ce nouvel arbre auxiliaire estrepresente a la figure 8.5 et est note R2

i .A present, il ne reste plus qu’a attacher R1

i et R2i a Ri pour obtenir l’arbre

auxiliaire Ti correspondant a Pi. L’arbre R1i est place comme fils gauche du

62

2

1 3

= arc rouge

= arc noir

= l’isroot bit est activé

= l’isroot bit est désactivé

Fig. 8.2 – Arbre Ri correspondant a la compression du chemin prefere 3, 1,2

0 6

5

4

Fig. 8.3 – A gauche, l’arbre P 1i et a droite, l’arbre P 2

i .

63

5

6

Fig. 8.4 – Arbre R3 correspondant a la compression du chemin prefere 5, 6

5

4 6

Fig. 8.5 – Arbre R2i obtenu en attachant R4 a R3.

64

2

1 3

5

4 6

0

Fig. 8.6 – Arbre Ti obtenu en attachant R1i et R2

i a Ri.

nœud 1 de Ri et l’arbre R2i est place comme fils droit du nœud 3 de Ri, de

maniere a verifier l’ordre ABR. L’arbre resultant Ti est presente a la figure8.6 et correspond a la transformation de Pi par l’algorithme Tango.

Il existe deux principaux inconvenients avec cette premiere approche deTango :

1. la transformation de Pi en Ti est fort couteuse en temps d’execution,ce qui nuit aux performances de l’algorithme.

2. cette approche ne verifie pas la definition du modele ABR, car deuxarbres sont utilises par l’algorithme.

Cependant, cette premiere approche permet d’avoir une idee globale desprincipes de l’algorithme Tango et aidera a la comprehension du veritable

65

algorithme.

8.3 Arbres auxiliaires

Avant de presenter l’algorithme Tango, nous avons besoin de definir lesarbres auxiliaires, ainsi que quatre operations supportees par cette structure :

1. la concatenation (cet algorithme provient de l’article [Sah05])

2. l’eclatement (cet algorithme provient de l’article [Sah05])

3. le cutting (cet algorithme provient de l’article [DHIP04])

4. le joining (cet algorithme provient de l’article [DHIP04])

Les deux premieres operations sont definies pour etre utilisees par lesdeux dernieres.

8.3.1 Definition

Un arbre auxiliaire est une structure, qui contient un sous-chemin d’unchemin allant de la racine a une feuille de P (les nœuds de ce sous-cheminsont relies par des aretes fils prefere dans P ). Les nœuds d’un arbre auxiliairesont organises en fonction de la valeur de leur cle. Chaque nœud x d’un arbreauxiliaire contient des informations supplementaires :

1. la profondeur du nœud x dans l’arbre parfait P . Cette donnee est fixedurant toute l’execution d’une sequence et est comprise dans l’intervalle[0, log(n + 1)). Cette information sera designee par le terme prof.

2. la profondeur maximale dans P des nœuds appartenant au sous-arbrede x dans T . Cette information sera designee par le terme profondeur-Max.

3. la profondeur minimale dans P des nœuds appartenant au sous-arbre dex dans T . Cette information sera designee par le terme profondeurMin.

4. un bit, nomme isroot, pour indiquer si x est la racine de l’arbre auxi-liaire, auquel il appartient. Tango etant un arbre d’arbres auxiliaires,il arrivera, donc, qu’une feuille d’un arbre auxiliaire ait comme fils laracine d’un autre arbre auxiliaire. L’isroot bit permet, donc, d’indiquers’il y a eu un passage d’un arbre auxiliaire a un autre.

Il est important de noter qu’un arbre auxiliaire est implemente commeun arbre rouge-noir.

66

8.3.2 Concatenation

Cette operation porte sur un arbre D tel que la racine est x, le sous-arbregauche A de x est un arbre rouge-noir et le sous-arbre droit B de x est unarbre rouge-noir ; l’arbre D n’etant pas necessairement un arbre rouge-noir.Le but de la concatenation est de construire a partir de A, B et x un arbrerouge-noir. Pour realiser cette operation de maniere e%cace, il est necessaireque chaque nœud x de l’arbre stocke une information supplementaire : sahauteur noire bh(x) (pour rappel bh(x) est le nombre de nœuds ayant un bitnoir entre x (inclus) et la feuille la plus profonde de x moins 1).

L’operation de concatenation se realise par l’algorithme suivant :

1. Si la hauteur noire de la racine de A est egale a la hauteur noire dela racine de B, nous construisons l’arbre rouge-noir C avec x commeracine, A comme sous-arbre gauche de x et B comme sous-arbre droitde x. On colorie les arcs liant x a A et x a B en noir. La hauteur noirede x est alors definie comme la hauteur noire de la racine de A plus 1.

2. Si la hauteur noire de la racine de A est plus grande que la hauteurnoire de la racine de B, il faut suivre le chemin des fils droits de Ajusqu’au premier nœud y ayant une hauteur noire egale a celle de laracine de B. Il faut remarquer que la hauteur noire du pere p de y doitetre egale a bh(B) % 1 (ou bh(B) correspond a la hauteur noire de laracine de B), car sinon il aurait ete le premier nœud sur le chemin desfils droits a avoir une hauteur noire egale a bh(B). Designons par Yle sous-arbre de y. Nous retirons Y de l’arbre A pour placer le nœudx a la place de Y . Pour que le nœud x ait une hauteur noire egale abh(B)%1, nous colorions l’arc entre x et p en rouge. Si l’arc entre g (lepere de p) et p est rouge, alors il faut e#ectuer une rotation simple entreg et p. Cette rotation laisse x sans fils, car il n’en avait pas avant larotation entre g et p (cfr figure 8.7). Ensuite, il faut attacher Y commefils gauche de x en coloriant l’arc en noir et l’arbre B comme fils droitde x en coloriant l’arc en noir.

3. Si la hauteur noire de la racine de A est plus petite que la hauteur noirede la racine de B, nous procedons de maniere symetrique au cas 2 surl’arbre B.

8.3.3 Eclatement

L’operation d’eclatement porte sur un arbre auxiliaire C et sur un nœudx de cet arbre. Elle reorganise C, de maniere a ramener x a la racine de

67

Fig. 8.7 – Rotation simple sur les nœuds g et p.

l’arbre avec comme sous-arbre gauche de x un arbre rouge-noir, note A, etcomme sous-arbre droit de x un arbre rouge-noir, note B.

Pour realiser l’eclatement, il faut d’abord construire les arbres A et B apartir de C avec l’algorithme suivant. Au debut les arbres A et B sont vides.

1. Rechercher le nœud x dans C. Lorsque x est localise, il faut rajouterdans A le sous-arbre gauche de x et dans B le sous-arbre droit de x.

2. Ensuite, il faut remonter le chemin de x a la racine et realiser l’etape,qui suit, jusqu’a ce que la racine soit atteinte.

3. Soit p le nœud courant. Deux cas doivent etre envisages, selon que x sesitue dans le sous-arbre gauche ou dans le sous-arbre droit de p :

(a) si x est dans le sous-arbre gauche de p, alors le sous-arbre droitde p contient des nœuds ayant des valeurs plus grandes que cellede x. Ces nœuds doivent, donc, se situer dans l’arbre B. Des lors,nous e#ectuons une concatenation avec B, p et le sous-arbre droitde p. Cette concatenation donne un arbre rouge-noir, qui devientB.

(b) si x est dans le sous-arbre droit de p, alors le sous-arbre gauche dep contient des nœuds ayant des valeurs plus petites que celle de x.Ces nœuds doivent, donc, se situer dans l’arbre A. Des lors, nouse#ectuons une concatenation avec A, p et le sous-arbre gauche dep. Cette concatenation donne un arbre rouge-noir, qui devient A.

68

4. Lorsque tous les elements sur le chemin de la remontee sont traites, nousobtenons que A forme un arbre rouge-noir avec des elements ayant desvaleurs plus petites que celle de x et que B forme un arbre rouge-noiravec des elements ayant des valeurs plus grandes que celle de x. Unefois A et B crees, il su%t d’attacher A comme sous-arbre gauche de xavec un arc noir et B comme sous-arbre droit de x avec un arc noir.

Bien que cela ne soit pas trivialement verifiable, la complexite de cetteoperation est logarithmique en le nombre d’elements dans l’arbre [Sah05].

8.3.4 Cutting

Le cutting a une profondeur d sur un arbre auxiliaire coupe cet arbre endeux arbres auxiliaires. L’un stockant les nœuds, dont l’information prof estplus petite que d. L’autre stockant les nœuds, dont l’information prof estplus grande que d.

Un arbre auxiliaire A stocke un sous-chemin C d’un chemin allant dela racine a une feuille de P . Par consequent, l’operation de cutting a uneprofondeur d sur l’arbre A consiste, au niveau de l’arbre P , a scinder C endeux parties. La premiere partie part du debut du chemin C jusqu’au nœudde profondeur d % 1 et la seconde partie part du nœud de profondeur djusqu’a la fin du chemin C. Ces deux parties correspondent aux deux arbresauxiliaires crees par le cutting.

Les nœuds d’un arbre auxiliaire A, qui ont une information prof plusgrande que d, forment un intervalle I dans l’espace des cles de cet arbre.Ceci est du au fait que les nœuds de cet arbre auxiliaire appartiennent aun meme sous-chemin d’un chemin allant de la racine a une feuille dans P .L’operation de cutting se base sur cette propriete.

Pour realiser un cutting a une profondeur d, il faut d’abord determiner leselements minimal et maximal de l’intervalle I. Il faut, donc, trouver l’elementminimal de A ayant une profondeur plus grande que d (ou egale a d) etl’element maximal de A ayant une profondeur plus grande que d (ou egale ad). Nous designerons, respectivement, ces elements par l et r.

Le nœud l est l’element de l’arbre A le plus a gauche et ayant une profon-deur plus grande que d. Determiner l peut se faire par l’algorithme suivant :

1. Commencer le traitement a la racine de A.

2. Analyser l’information prof du nœud courant x :

(a) Si l’information prof est superieure a d, alors il faut analyser l’in-formation profondeurMax du fils gauche de x :

69

i. Si l’information profondeurMax du fils gauche de x est plusgrande que d, alors il existe dans le sous-arbre du fils gauchede x un nœud plus petit que le nœud courant x et ayantune information prof plus grande que d. Des lors, il faut sedeplacer sur le fils gauche de x et recommencer l’etape 2.

ii. Si l’information profondeurMax du fils gauche de x est stric-tement plus petite que d, alors il n’existe pas de nœud pluspetit que x et ayant une information prof plus grande que d.Le nœud x correspond, alors, a l et l’algorithme est arrete.

(b) Si l’information prof est strictement plus petite que d, alors il fautanalyser l’information profondeurMax des fils de x :

i. Si l’information profondeurMax du fils gauche de x est plusgrande que d, alors il faut se deplacer sur le fils gauche de x,car le nœud l se situe dans le sous-arbre gauche de x.

ii. Si l’information profondeurMax du fils droit de x est plusgrande que d, alors il faut se positionner sur le fils droit de x,car le nœud l se situe dans le sous-arbre droit de x.

iii. Si l’information profondeurMax du fils gauche et du fils droitde x est plus grande que d, alors il faut se positionner sur lefils gauche de x, plutot que le fils droit. En e#et, comme lesous-arbre gauche de x contient des cles plus petites que cellesdu sous-arbre droit de x, on est certain que l se situe dans lesous-arbre gauche de x, et non pas dans le sous-arbre droit dex.

Cet algorithme n’est correct que s’il existe un nœud l dans l’arbre auxi-liaire A. Pour traiter le cas, ou il n’existe pas un tel nœud dans A, il su%td’examiner l’information profondeurMax de la racine de A. Si cette informa-tion est strictement plus petite que d, alors il n’existe pas de nœud l dansA. Par contre, si elle est plus grande que d, le nœud l existe et l’algorithmeci-dessus peut etre applique.

Quant au nœud r, il s’agit de l’element de A le plus a droite et ayant uneprofondeur plus grande que d. Determiner r se fait de maniere symetrique al’algorithme pour determiner l.

Une fois l et r determines, il faut determiner le predecesseur l$ de l et lesuccesseur r$ de r en appliquant, respectivement, les algorithmes predecesseur(cfr point 5.2.5) et successeur (cfr point 5.2.4) des arbres rouges-noirs.

Etant donne que les nœuds qui ont une information prof superieure ad forment un intervalle I dans l’espace des cles de A, nous allons utiliser

70

cette propriete pour e#ectuer le cutting. En e#et, l’intervalle I correspond a[l, r] ou de maniere equivalente a (l$, r$). Il ne reste, des lors, qu’a isoler leselements de cet intervalle dans un sous-arbre, de maniere a pouvoir, ensuite,les separer du reste de l’arbre. L’algorithme, qui suit, se base sur ce principepour e#ectuer le cutting (voir figure 8.8) :

1. E#ectuer un eclatement sur A en l$ . De par cette operation, l$ devientla racine de l’arbre, ce qui a pour consequence que les elements dusous-arbre gauche de l$ ont des cles appartenant a l’intervalle (%&, l$)et que les elements du sous-arbre droit de l$ ont des cles appartenanta l’intervalle (l$,&). Notons par B et C, respectivement, le sous-arbregauche de l$ et le sous-arbre droit de l$ .

2. E#ectuer sur C un eclatement en r$. Cette operation fait de r$ la racinedu sous-arbre C. Des lors, le sous-arbre gauche de r$, note D, contientdes cles appartenant a l’intervalle (l$, r$) et le sous-arbre droit de r$,note E, contient des cles dans l’intervalle (r$,&). Ainsi, par les deuxeclatements sur l$ et r$, on est parvenu a isoler les nœuds, dont l’infor-mation prof est superieure a d, dans un sous-arbre de A. Ce sous-arbreetant D.

3. Activer l’isroot bit de la racine D. Cette operation separe, de manieree#ective, le sous-arbre D du reste de l’arbre A et fait de D unarbre auxiliaire. La partie restante de A, obtenue apres avoir enleveD, sera dorenavant designee par A$. Une operation d’eclatement oude concatenation sur A$ ne portera que sur les nœuds de cet arbreauxiliaire ; elle n’a#ectera pas les nœuds de l’arbre auxiliaire D. Acette etape-ci, D contient les nœuds de A, dont l’information profest superieure a d et A$ contient les nœuds de A, dont l’informationprof est inferieure a d. Cependant, le fait d’avoir ainsi separe de r$

son sous-arbre gauche D a pour consequence, que le sous-arbre de r$

n’est plus forcement un arbre rouge-noir, ce qui implique que l’arbreA$, egalement, n’en est plus forcement un. Les deux operations, quisuivent, ont pour but de transformer A$ en un arbre rouge-noir, et parla meme occasion en un arbre auxiliaire.

4. E#ectuer une concatenation sur r$. Le nœud r$ n’ayant pas de sous-arbre gauche, l’operation de concatenation forme un arbre rouge-noir apartir du nœud r$ et des nœuds dans le sous-arbre droit de r$. Notonspar C $ cet arbre rouge-noir, ainsi, cree.

5. E#ectuer une concatenation sur l$ . Cette operation cree un arbre rouge-noir a partir de tous les nœuds de A$. Ainsi, par ces deux concatenationssuccessives, l’arbre A$ a ete reordonne, de maniere a devenir un arbre

71

repondant a la definition d’arbre auxiliaire. Il est important de noterque deux concatenations sont necessaires pour transformer A$ en unarbre auxiliaire. En e#et, on pourrait penser a e#ectuer qu’une seuleconcatenation (portant sur l$), de maniere a transformer A$ en un arbreauxiliaire. Mais cette solution aurait ete erronee, car la concatenationsur un nœud necessite que le sous-arbre gauche et le sous-arbre droitde ce nœud soient des arbres rouges-noirs. Or, le sous-arbre droit de l$,c’est-a-dire le sous-arbre de r$, n’est plus forcement un arbre rouge-noir,apres que son sous-arbre gauche D lui ait ete retire. D’ou la necessite,d’abord, de transformer le sous-arbre de r$ en arbre rouge-noir, avantde realiser la meme operation sur le sous-arbre de l$.

Deux cas particuliers sont a gerer :

1. le nœud l$ n’existe pas (l n’a pas de predecesseur dans son arbre auxi-liaire) : il ne faut alors realiser des etapes ci-dessus que les etapes 2, 3et 4.

2. le nœud r$ n’existe pas (r n’a pas de successeur dans son arbre auxi-liaire) : il ne faut alors realiser des etapes ci-dessus que les etapes 1, 3et 5.

8.3.5 Joining

L’operation de joining porte sur deux arbres auxiliaires A et B, et consistea les reunir pour n’en former qu’un seul. Une precondition a cette operationconsiste, au niveau de l’arbre parfait P , a ce que les deux chemins, qui corres-pondent aux arbres A et B, forment un sous-chemin continu C1 d’un cheminallant de la racine a une feuille de P s’ils sont reunis. Par consequent, lejoining sur A et B consiste a reunir les chemins, qu’ils stockent, pour formerle chemin C1, qui sera stocke dans un nouvel arbre auxiliaire C. Du fait, quele chemin A1, stocke par A, est adjacent au chemin B1, stocke par B, nousen deduisons deux proprietes :

1. un des deux arbres A et B est tel que l’information prof de chacun deses nœuds est plus grande que celle de tous les nœuds de l’autre arbre.

2. l’espace des cles de l’arbre, ayant les informations prof plus grandes,forme un intervalle dans l’espace des cles de l’arbre ayant les informa-tions prof plus petites.

Une seconde precondition est necessaire pour cette operation : l’arbre,ayant les informations prof plus grandes, est attache a un nœud du secondarbre.

L’algorithme du joining se base sur tout ceci et est decrit ci-dessous.

72

Fig. 8.8 – Realisation d’un cutting avec des eclatements et desconcatenations.

73

D’abord, il faut determiner lequel des arbres A et B stocke les nœudsayant les informations prof plus grandes. Pour cela, il su%t de comparerl’information prof de la racine de A et de la racine de B, et de determinerlaquelle est la plus grande. Supposons, quitte a renommer les arbres, que Bstocke les nœuds ayant les informations prof plus grandes.

Ensuite, il faut rechercher les nœuds l$ et r$ (posons l$ < r$ ) de A entrelesquels l’espace de cles de B est compris. La recherche de ces elements sefait par l’algorithme suivant :

1. Rechercher dans A la cle de la racine de B. Etant donne que la racinede B est le fils d’un nœud p de A, cette operation permet d’atteindrece nœud p.

2. Si la racine de B est le fils gauche de p, alors ce nœud-ci correspond ar$ et comme l$ est le predecesseur de r$ dans A, ce nœud l$ peut etredetermine en appliquant l’algorithme predecesseur (cfr point 5.2.5) surr$. Ainsi, nous sommes parvenus a identifier l$ et r$ dans ce premier cas.

3. Par contre, si la racine de B est le fils droit de p, alors ce nœud-cicorrespond a l$ et comme r$ est le successeur de l$ dans A, ce nœudr$ peut etre determine en appliquant l’algorithme successeur (cfr point5.2.4) sur l$. Ainsi, nous sommes parvenus a identifier l$ et r$ dans cesecond cas.

Une fois l$ et r$ determines, il faut appliquer l’algorithme, qui suit, demaniere a realiser le joining (voir figure 8.9) :

1. E#ectuer sur A un eclatement en l$ . Ceci ramene l$ a la racine del’arbre. Notons par, respectivement, A$ et C le sous-arbre gauche et lesous-arbre droit de l$. Les cles de A$ appartiennent a l’intervalle (%&, l$)et les cles de C appartiennent a l’intervalle (l$,&)

2. E#ectuer sur C un eclatement en r$. Par cette operation, r$ devient laracine du sous-arbre C. Comme les nœuds l$ et r$ sont adjacents, alorsr$ est le plus petit element de C. Des lors, etant ramene a la racinede C par le second eclatement, r$ contient dans son sous-arbre droit,note E, tous les elements de C. Comme r$ ne contient aucun elementde C dans son sous-arbre gauche, on est, alors, certain de n’avoir dansle sous-arbre gauche de r$ que l’arbre auxiliaire B.

3. Desactiver l’isroot bit de la racine de B. Cette operation reunit demaniere e#ective l’arbre A et l’arbre B. L’arbre resultant de cettereunification sera designe par Z. Le fait de rajouter, ainsi, l’arbre B apour consequence que le sous-arbre de r$ n’est plus forcement un arbrerouge-noir, ce qui implique que Z, egalement, n’en est plus forcement

74

un. Les deux operations, qui suivent, ont pour but de resoudre ceprobleme.

4. E#ectuer une concatenation sur r$. Cette operation de concatenationrearrange le sous-arbre de r$, de maniere a le transformer en un arbrerouge-noir. Notons par C $ l’arbre resultant de cette concatenation.

5. E#ectuer une concatenation sur l$. Cette operation rearrange l’arbreZ pour le transformer en un arbre rouge-noir. Ainsi, Z est un arbreauxiliaire, qui contient les elements de A et B. Il s’agit, donc, de l’arbreresultant du joining de A et B.

8.4 Algorithme Tango

Dans la premiere approche, l’etat Ti de l’arbre Tango T est construit apartir de l’etat Pi de l’arbre parfait P . Cependant, cette maniere de procederposait plusieurs inconvenients. L’algorithme Tango se base sur les fondementsde la premiere approche, mais il construit di#eremment l’arbre Ti, de sorte aresoudre les problemes de la premiere approche. En fait, l’etat Ti est construita partir de l’etat Ti!1 et du prochain acces xi de la sequence X.

Il faut remarquer que l’acces au nœud xi, au niveau de l’arbre parfait P ,change necessairement les fils preferes, de maniere a avoir un chemin prefereallant de la racine de P a xi et ne change pas d’autres fils preferes. Parconvention, nous decidons que pour un nœud accede son fils gauche doitdevenir son fils prefere. Par consequent, les seuls nœuds, dont les fils preferespeuvent changer a cause de l’acces a xi, sont ceux se trouvant sur le cheminmenant de la racine de P a xi (ainsi que le fils droit de xi).

Au niveau de l’arbre Tango T , il est possible, lors de la recherche de xi,de determiner les nœuds, dont les fils preferes changent, car un changementde fils prefere (excepte pour le changement de fils prefere de xi) correspondau passage entre deux arbres auxiliaires (disons de A a B). En e#et, commeun arbre auxiliaire stocke un chemin prefere, alors le point de passage entredeux arbres auxiliaires correspond a choisir le fils non prefere d’un des nœudsde A, car si on avait choisi son fils prefere, on serait reste dans le meme arbreauxiliaire.

En se basant sur cette constatation, il est inutile de construire Ti a partirde Pi. Il su%t de partir de Ti!1, de rechercher le nœud xi dans cet arbre et dechanger durant cette recherche le fils prefere des nœuds, pour lesquels l’accesa xi provoque un changement de fils prefere. L’algorithme suivant se base surcette idee pour construire l’etat Ti a partir de Ti!1 et de xi :

1. Commencer la recherche de xi a la racine de Ti!1.

75

Fig. 8.9 – Realisation d’un joining avec des eclatements et desconcatenations. 76

2. Se deplacer vers le sous-arbre gauche ou le sous-arbre droit du nœudcourant x selon que xi soit, respectivement, plus petit ou plus grandque x. Une fois le deplacement e#ectue, disons sur le nœud y , il fautanalyser l’isroot bit de ce nœud :

(a) Si l’isroot bit est desactive, cela signifie que x et y appartiennentau meme arbre auxiliaire. Des lors, l’acces a xi ne modifie pas a ceniveau un fils prefere et aucun traitement additionnel n’est alorsnecessaire.

(b) Si l’isroot bit est active, cela signifie qu’on est passe d’un arbreauxiliaire a un autre (disons de A a B). Des lors, l’acces a xi

modifie le fils prefere d’un nœud z de A. Il faut alors e#ectuerle traitement qui suit pour changer le fils prefere de z . Notonsd’abord que le nouveau fils prefere de z est le nœud de B ayantla plus petite information prof :

i. E#ectuer sur l’arbre auxiliaire A contenant x un cutting a uneprofondeur d egale a l’information profondeurMin de y , demaniere a faire du fils prefere de z son fils non prefere

ii. E#ectuer un joining entre l’arbre auxiliaire A et l’arbre auxi-liaire B, de maniere a ce que z ait son nouveau fils prefere.

L’etape 2 doit etre reiteree tant que le nœud xi n’est pas atteint.

3. Lorsque le nœud xi est atteint, il faut encore faire de son fils gauche sonfils prefere. Pour cela, il faut e#ectuer un cutting sur l’arbre auxiliairecontenant xi a une profondeur d egale a la profondeur de xi plus 1. En-suite, il faut rechercher le nœud p. Ce nœud est atteint en recherchantle predecesseur de xi, mais en s’arretant sur le premier nœud dont l’is-root bit est active. Ce nœud p est en fait la racine de l’arbre auxiliairecontenant le fils gauche de xi dans P . En e#et, le predecesseur de xi

appartient au sous-arbre du fils gauche de xi dans P , ce qui impliquequ’en recherchant dans T le predecesseur de xi, nous devons obligatoi-rement passer par l’arbre auxiliaire contenant le fils gauche de xi dansP . Et finalement, il faut e#ectuer un joining entre l’arbre auxiliairecontenant xi et l’arbre auxiliaire contenant p .

8.5 Analyse des performances

Cette section est basee sur l’article [DHIP04]. La contribution personnellea ete de detailler les demonstrations des lemmes et des theoremes enonces.

77

Soient un arbre Tango T construit sur les cles {1, 2, . . . , n} et une sequenced’acces X = x1, x2, . . . , xm.

L’analyse des performances de Tango se base sur la borne inferieure d’en-trelacement (cfr point 7.3.1) et nous avons besoin de definir la notion quisuit.

La borne d’entrelacement IBi(X) d’un acces xi est la borne inferieured’entrelacement de la sequence x1, x2, . . . , xi, a laquelle on soustrait la borneinferieure d’entrelacement de la sequence x1, x2, . . . , xi!1. Par consequent,IBi(X) est le nombre d’alternances left-right et right-left introduites en pluspar l’acces xi.

Durant l’analyse des performances de Tango, nous ne tiendrons pascompte des changements de fils preferes qui font du fils gauche de chaquenœud accede son fils prefere. Pour une sequence de m acces, nous omet-trons donc m changements de fils preferes. Cependant, ceci n’est pasproblematique, car nous pouvons nous rendre compte que ces m changementsde fils preferes n’influent pas sur les performances de Tango.

Lemme 3. Supposons que durant un acces xi, il y ait k nœuds, dont le filsprefere change (de gauche a droite ou de droite a gauche) dans P. Ce nombrek est egal a la borne d’entrelacement IBi(X) de l’acces xi.

Demonstration : Considerons que les elements x1, x2, . . . , xi!1 aient eteaccedes et que le prochain element a acceder soit xi.

Pour demontrer ce lemme, il su%t de prouver l’equivalence suivante :l’acces xi change le fils prefere d’un nœud x si et seulement si l’acces xi

induit une alternance left-right ou right-left supplementaire dans la sequenceetiquetee de x sur les cles x1, x2, . . . , xi par rapport a la sequence etiqueteede x sur les cles x1, x2, . . . , xi!1 (entre d’autres termes IBi(X) augmente).Ceci se fait en deux etapes :

1. Lors d’un acces xi, le fils prefere du nœud x passe de gauche a droitesi et seulement si le dernier acces dans le sous-arbre de x etait dans saregion gauche et que xi se situe dans la region droite de x. Ce dernierevenement correspond exactement au cas ou une alternance left-rightsupplementaire est induite par l’acces xi dans la sequence etiquetee dex sur les cles x1, x2, . . . , xi par rapport a la sequence etiquetee de x surles cles x1, x2, . . . , xi!1.

2. Lors d’un acces xi, le fils prefere du nœud x passe de droite a gauchesi et seulement si le dernier acces dans le sous-arbre de x etait dans saregion droite et que xi se situe dans la region gauche de x. Ce dernierevenement correspond exactement au cas ou une alternance right-left

78

supplementaire est induite par l’acces xi dans la sequence etiquetee dex sur les cles x1, x2, . . . , xi par rapport a la sequence etiquetee de x surles cles x1, x2, . . . , xi!1.

Ces deux cas permettent de demontrer l’equivalence citee ci-dessus et parconsequent le lemme.

!Lemme 4. Soit k le nombre de nœuds, dont les fils preferes changent durantun acces xi. Le cout d’acces a xi vaut O ((k + 1) · (1 + log(log n))).

Demonstration : Le cout d’acces au nœud xi consiste, d’une part, au coutpour rechercher xi dans l’arbre, et d’autre part, au cout pour rearranger lastructure, de maniere a la faire passer de l’etat Ti!1 a l’etat Ti.

Nous analysons d’abord le cout pour rechercher xi. Pour rappel, si durantla recherche de xi, on passe d’un arbre auxiliaire a un autre(disons de A aB), cela signifie que l’acces xi change le fils prefere d’un des nœuds de l’arbreauxiliaire A. Etant donne que la recherche de xi induit k changements de filspreferes, cela signifie que k + 1 arbres auxiliaires devront etre visites pour larecherche de xi. Un arbre auxiliaire contient au plus log(n) elements, car ilstocke un sous-chemin d’un chemin allant de la racine a une feuille dans P .Par consequent, le cout d’une recherche dans un arbre auxiliaire necessite uncout au pire cas de O(log(log n)). Pour etre plus precis, la complexite vautO (max {1, log(log n)}). Ceci permet de tenir compte du cas, ou log(log n) estnegatif, car la recherche se fait, alors, en temps constant. Dans la notationO(.), l’expression O (max {1, log(log n)}) est equivalente a O(1 + log(log n)).En e#et, dans la notation O(.), en presence d’une somme, on prend le termemaximal de cette somme. Finalement, comme la recherche de xi visite k + 1arbres auxiliaires, le cout pour la realiser vaut O ((k + 1) · (1 + log(log n))).

Maintenant que le cout de la recherche est analyse, nous nous occuponsdu cout necessaire pour transformer Ti!1 en Ti. Quand nous passons d’unarbre auxiliaire a un autre, il faut e#ectuer un cutting et un joining. Commeces operations portent chacune sur au plus log(n) elements, elles necessitentchacune un cout de O(1 + log(log n)).

Comme nous visitons k+1 arbres auxiliaires, nous avons alors k passagesentre des arbres auxiliaires, ce qui implique d’e#ectuer k cuttings et k joiningspour lesquels nous payons un cout de O(k · (1 + log(log n))).

En conclusion, le cout de l’acces a xi (= recherche de xi + reorganisationde l’arbre) vaut O (max {(k + 1) · (1 + log(log n)) , k · (1 + log(log n))}).En simplifiant ce resultat, nous obtenons finalementO ((k + 1) · (1 + log(log n))).

!

79

Corollaire 2. Soient un arbre constitue des cles {1, 2, . . . , n} etune sequence X = x1, x2, . . . , xm. Le cout pour servir X vautO ((K + m) · (1 + log(log n))), ou K est le nombre de changements de filspreferes durant l’execution de la sequence X.

Theoreme 6. Soient un arbre constitue des cles {1, 2, . . . , n} et une sequenceX = x1, x2, . . . , xm. Le cout pour servir X avec l’algorithme Tango vautO ((OPT (X) + n) · (1 + log(log n))).

Demonstration : Pour demontrer ce resultat, nous allons utiliser le co-rollaire 2. En fait, nous allons compter le nombre de changements de filspreferes durant l’execution de la sequence X pour remplacer le terme Kdans le corollaire 2 par ce nombre.

Par le lemme 3, nous avons que IB(X) ( car!m

i=1 IBi(X) = IB(X)) estle nombre de fois qu’un fils prefere change de gauche a droite ou de droitea gauche lors de l’execution de la sequence X. Cependant, il y a egalementau plus n initialisations de fils preferes (une initialisation d’un fils prefereconsiste a choisir pour un nœud son fils gauche ou son fils droit commefils prefere, alors qu’il n’avait pas encore de fils prefere). Par consequent, lenombre total de changements de fils preferes durant l’execution de la sequenceX vaut IB(X) + n. En combinant ceci avec le corollaire 2, nous obtenonsque le cout pour servir X vaut :

O ((IB(X) + n + m) · (1 + log(log n))) (8.1)

Dans le chapitre 7, nous avons demontre le resultat, qui suit :

OPT (X) " 1

2· (IB(X) + m) (8.2)

En utilisant ce resultat, nous deduisons que le cout pour servir X vautO((2·OPT (X)%m+n+m)·(1+log(log n))). En simplifiant ce resultat, nousobtenons finalement, que le cout pour servir la sequence X avec l’algorithmeTango vaut :

O ((OPT (X) + n) · (1 + log(log n))) (8.3)

!

Corollaire 3. Lorsque m = !(n), le temps d’execution de Tango pour servirla sequence X vaut O(OPT (X) · (1 + log(log n))).

80

Demonstration : Si la sequence d’acces X est constituee de plus de n cles,on a que OPT (X) = !(n). Par consequent, en se basant sur le theoremeprecedent (theoreme 6), on a que le cout pour servir X avec l’algorithmeTango vaut :

O (OPT (X) · (1 + log(log n))) (8.4)

!Si nous avions tenu compte des changements de fils preferes, qui font

du fils gauche de chaque nœud accede son fils prefere, alors il aurait fallurajouter le terme m ·(1+log(log n)) au resultat de l’equation 8.4. Cependant,ce terme peut etre neglige, car OPT (X) # m. Et donc le fait d’omettre ceschangements de fils preferes n’est pas problematique.

Theoreme 7. Le cout au pire cas pour la recherche d’un nœud xi vautO ((log n) · (1 + log(log n))).

Demonstration : Comme l’arbre P est un arbre parfait, sa hauteur estegale a log n. Par consequent, le nombre maximal de nœuds, dont les filspreferes peuvent changer a cause de l’acces xi vaut log n. Des lors, par lelemme 4, le cout au pire cas de l’acces xi vaut O ((log n) · (1 + log(log n))).

!

8.6 Conclusion

Dans ce chapitre, nous avons presente une structure, qui atteint un tauxde competitivite de O(log(log n)). Ce taux est atteint au prix d’un algorithmeassez complique et lourd a implementer. De plus, les nombreuses operationsnecessaires pour realiser l’algorithme pourraient porter prejudice a ses per-formances en pratique.

Notons qu’en utilisant la borne inferieure d’entrelacement, nous ne pou-vons pas ameliorer le taux de O(log(log n)). En e#et, chaque arbre auxiliairecontient au pire cas O(logn) elements. Et donc quelle que soit la manieredont sont organises les arbres auxiliaires, chaque arbre doit avoir une profon-deur de !(log(log n)), ce qui se traduit par un cout d’acces de !(log(log n))dans chaque arbre auxiliaire.

81

Chapitre 9

Multi-splay tree

Le multi-splay tree est une structure de donnees qui est basee sur Tangoet qui atteint un taux de competitivite de O(log(log n)). Elle a ete elaboree en2004 par Sleator et Wang [SW04]. Le principal avantage des multi-splay treespar rapport a Tango est que l’algorithme des multi-splay trees est moins com-plique et plus simple a implementer, ce qui peut favoriser les performancesen pratique de la structure, car l’implementation peut etre plus facilementoptimisee.

Dans ce chapitre, nous allons d’abord presenter l’algorithme des multi-splay trees et ensuite, nous allons proceder a l’analyse amortie des perfor-mances de cette structure.

9.1 Structures de donnees

Les sections presentant l’algorithme des multi-splay trees sont basees surles articles [SW04] et [DSW06]. La contribution personnelle a ete de detaillerle plus possible l’algorithme et d’essayer de le presenter de la maniere la plusclaire possible.

Nous disposons comme pour Tango d’un arbre de reference P (cfr point8.1), auquel est lie un arbre T , qui est ici appele un multi-splay tree. Ladi#erence est que le multi-splay tree est un arbre de splay trees et non pasun arbre d’arbres rouges-noirs.

Chaque nœud x dans T possede plusieurs informations :

1. sa profondeur dans P , denotee par prof. Cette valeur est constante.

2. la profondeur minimale dans P de tous les nœuds appartenant au splaysubtree de x. Le splay subtree de x est l’ensemble des nœuds apparte-nant au meme splay tree que x et qui ont x comme ancetre (a noterque x y est inclus). Cette information est denotee par mindepth.

82

3. l’isroot bit qui indique si l’arete reliant x a son pere est solide ou discon-tinue. Deux nœuds relies par une arete solide appartiennent au memesplay tree et deux nœuds relies par une arete discontinue appartiennenta des splay trees di#erents

9.2 Algorithmes

Nous allons d’abord expliquer l’algorithme du point de vue de l’arbre dereference P et, ensuite, nous allons expliquer comment le realiser au niveaude T .

9.2.1 Algorithme de l’arbre de reference

L’algorithme d’acces a un nœud xi est le suivant :

1. localiser le nœud xi, en commencant la recherche a la racine de P .

2. suivre le chemin allant de xi a la racine, en changeant les fils preferesadequats, de maniere a ce que xi fasse partie du meme chemin prefereque celui de la racine de P .

Cet algorithme est identique a celui de Tango (cfr point 8.2), hormis queles changements de fils preferes se font en remontant de xi a la racine. Cecifacilite, en fait, l’algorithme dans T .

9.2.2 Algorithme multi-splay tree

Pour realiser l’algorithme ci-dessus sans utiliser l’arbre de reference, nousallons nous baser sur l’acces xi et sur l’arbre Ti!1 (l’arbre T avant l’acces xi)pour le transformer de maniere a tenir compte des modifications causees parl’acces xi.

L’idee de l’algorithme est donc la meme que celle de Tango. Cependant,les changements de fils preferes devront se faire di#eremment puisque unmulti-splay tree est constitue de splay trees et non pas d’arbres rouges-noirs.Les changements de fils preferes peuvent etre realises dans un multi-splaytree de maniere plus souple par rapport a Tango, car un splay tree n’imposepas de conditions sur sa structure, contrairement aux arbres rouges-noirs (cfrpoint 5.2.1).

L’algorithme d’acces au nœud xi est le suivant :

1. localiser le nœud xi, en commencant la recherche a la racine de T .

83

2. suivre le chemin menant de xi a la racine de T . Pour chaque nœud x,rencontre durant la remontee, il faut analyser son isroot bit. Si ce bitest active, cela signifie que le passage de x a son pere p correspond aupassage d’un splay tree a un autre. Il faut alors e#ectuer un switch (unchangement de fils prefere). Ce switch doit porter sur le nœud y dusplay tree, auquel p appartient, et dont l’information prof est egale al’information mindepth de x moins 1. Si nous nous basons sur l’arbreparfait P , nous constatons que dans P ce nœud y est l’ancetre desnœuds appartenant au splay tree de x. De ce fait, le splay tree, auquelx appartient, doit etre un descendant de y dans T (voir figure 9.1). Etdonc, le nœud y doit se situer sur le chemin menant de p a la racinedu splay tree de p. Le nœud y peut donc etre determine en suivantce chemin. Une fois y trouve, il faut e#ectuer un switch sur ce nœud,c’est-a-dire changer son fils prefere. Ce changement de fils prefere de y ,au niveau de l’arbre T , consiste a reunir le splay tree, auquel appartienty et le splay tree auquel appartient x, pour n’en faire plus qu’un seulsplay tree.

3. une fois les switches e#ectues et la racine atteinte, il faut splayer lenœud xi pour le ramener a la racine de T . Pour cela, on peut utili-ser l’algorithme usuel de splaying (cfr point 6.2.1), car apres tous lesswitches, xi appartient au meme splay tree que celui de la racine de T .

Nous allons, maintenant, expliquer comment realiser l’operation deswitch. En fait, il y a deux switches a considerer : le switch gauche-droiteet le switch droite-gauche, selon qu’il faille, respectivement, changer le filsprefere de gauche a droite ou de droite a gauche. Nous allons detailler l’algo-rithme du switch gauche-droite. L’autre switch peut etre deduit de maniereanalogue.

Considerons un switch sur y . Nous definissons alors quatre ensembles :

1. L, qui est l’ensemble des nœuds dans le sous-arbre gauche de y dans Pappartenant au meme chemin prefere que celui du fils gauche de y.

2. R, qui est l’ensemble des nœuds dans le sous-arbre droit de y dans Pappartenant au meme chemin prefere que celui du fils droit de y.

3. U , qui est l’ensemble des nœuds au-dessus de y dans P appartenant aumeme chemin prefere que celui de y.

4. S = L + R + {y} + U .

Si nous considerons les elements de S par ordre croissant, nous avons queles cles de L forment un sous-intervalle dans l’intervalle des cles de S. Etidem pour R. De plus, il n’y a que le nœud y qui se situe entre l’intervallede L et l’intervalle de R.

84

Fig. 9.1 – Le splay tree auquel x appartient doit etre un descendant de y.Dans ce cas, le nœud x est plus petit que y.

85

Le splay tree A dans T , qui contient y est constitue des nœuds L+U+{y}.Apres le switch, il doit etre constitue des nœuds R + U + {y}. Il faut doncretirer L de A et y rajouter R. Cela peut se faire par l’algorithme suivant(voir figure 9.2) :

1. splayer le nœud y pour qu’il devienne la racine de A.

2. determiner z . Le nœud z est le plus grand nœud, qui a une informationprof plus petite que celle de y et qui est plus petit que y.

3. splayer le nœud z , jusqu’a ce qu’il devienne le fils gauche de y . Des lors,le sous-arbre droit de z est constitue de nœuds ayant une valeur dansl’intervalle (z, y) et ayant une information prof plus grande que cellede y. En e#et, comme z est le plus grand nœud ayant une informationprof plus petite que celle de y , nous en deduisons que les nœuds dansle sous-arbre droit de z ont une information prof plus grande que cellede y . Comme l’ensemble L est constitue de nœuds ayant une valeurplus petite que celle de y et ayant une information prof plus grande quecelle de y , nous en deduisons que le sous-arbre droit de z corresponda L.

4. activer l’isroot bit de la racine du sous-arbre droit de z pour le separerde A. Cette operation retire de maniere e#ective L de A. De cettemaniere, le fils gauche de y dans P devient son fils non prefere.

5. Determiner x. Le nœud x est le plus petit nœud, qui a une informationprof plus petite que celle de y et qui est plus grand que y.

6. splayer le nœud x, jusqu’a ce qu’il devienne le fils droit de y . Des lors,le sous-arbre gauche de x est constitue de nœuds ayant une valeur dansl’intervalle (y, x) et ayant une information prof plus grande que celle dey. En e#et, comme x est le plus petit nœud ayant une information profplus petite que celle de y , nous en deduisons que les nœuds dans lesous-arbre gauche de x ont une information prof plus grande que cellede y . Comme l’ensemble R est constitue de nœuds ayant une valeurplus grande que celle de y et ayant une profondeur plus grande quecelle de y , nous en deduisons que le sous-arbre gauche de x corresponda R.

7. desactiver l’isroot bit de la racine du sous-arbre gauche de x, de manierea l’incorporer dans A. De cette maniere, le fils droit de y dans P devientson fils prefere.

La souplesse des multi-splay trees par rapport a Tango est illustree dansles etapes 3 et 7 de l’algorithme ci-dessus. Nous pouvons activer ou desactiverun isroot bit, c’est-a-dire retirer un sous-arbre d’un splay tree ou attacher un

86

Fig. 9.2 – Les etapes d’un switch gauche-droite sur le nœud y.

87

sous-arbre a un splay tree sans devoir reorganiser le splay tree, car apres detelles operations l’arbre reste toujours un splay tree. Pour Tango, apres detelles operations il faut reorganiser les arbres rouges-noirs (cfr points 8.3.4 et8.3.5) pour qu’ils repondent a nouveau a la definition d’arbres rouges-noirs.

Deux cas particuliers doivent etre consideres :

1. le nœud z n’existe pas. Dans ce cas, il n’existe pas de nœuds, qui soientplus petits que y et qui aient une information prof plus petite quecelle de y . Le sous-arbre gauche de y est alors constitue exclusivementde nœuds ayant une information prof plus grande que celle de y . Ilcorrespond donc a L.

2. le nœud x n’existe pas. Dans ce cas, il n’existe pas de nœuds, qui soientplus grands que y et qui aient une information prof plus petite quecelle de y . Le sous-arbre droit de y est alors constitue exclusivementde nœuds ayant une information prof plus grande que celle de y . Ilcorrespond donc a R.

Il ne reste plus qu’a detailler les etapes 2 et 5 de l’algorithme precedent,c’est-a-dire comment determiner z et x. Nous allons presenter l’algorithmepour determiner z ; celui pour x peut etre deduit par symetrie.

Pour determiner z , il faut trouver le plus grand nœud, qui a une infor-mation prof plus petite que celle de y et qui est plus petit que y , sachantque y a deja ete ramene a la racine de A (etape 1 de l’algorithme precedent).L’algorithme est alors le suivant :

1. commencer le traitement sur le fils gauche de y , pour ne considererque des nœuds plus petits que y.

2. analyser l’information prof du nœud courant x :

(a) si l’information prof de x est plus petite que l’information prof dey , alors il faut analyser l’information mindepth du fils droit de x :

i. si l’information mindepth du fils droit de x est plus petiteque l’information prof de y , alors il existe dans le sous-arbredroit de x un nœud qui est plus grand que x et qui a uneinformation prof plus petite que celle de y . Des lors, x n’estpas z et il faut, par consequent, se deplacer sur le fils droit dex et recommencer l’etape 2.

ii. si l’information mindepth du fils droit de x est plus grande quel’information prof de y , alors il n’existe aucun nœud dans lesous-arbre droit de x, qui ait une information prof plus petiteque celle de y . Par consequent, x est le nœud z.

88

(b) si l’information prof de x est plus grande que l’information profde y , alors il faut analyser l’information mindepth des fils de x :

i. si l’information mindepth du fils droit de x est plus petite quel’information prof de y , alors il faut se deplacer sur le filsdroit de x et recommencer l’etape 2.

ii. si l’information mindepth du fils gauche de x est plus petiteque l’information prof de y , alors il faut se deplacer sur lefils gauche de x et recommencer l’etape 2.

iii. si l’information mindepth du fils gauche et du fils droit de xest plus petite que l’information prof de y , alors il faut sedeplacer sur le fils droit de x plutot que le fils gauche, car lesous-arbre du fils droit de x a des cles plus grandes que cellesdu sous-arbre du fils gauche de x. Nous sommes donc certainsque z se situera dans le sous-arbre droit de x et non pas dans lesous-arbre gauche de x. Ensuite, il faut recommencer l’etape2.

Cet algorithme n’est correct que si le nœud z existe dans A. Pour traiterle cas ou z n’existe pas, il su%t d’examiner l’information mindepth du filsgauche de y . Si cette information est plus grande que l’information prof dey , alors il n’existe aucun nœud plus petit que y et ayant une informationprof plus petite que celle de y . Dans ce cas, le nœud z n’existe donc pas.Par contre, si l’information mindepth du fils gauche de y est plus petite quel’information prof de y , alors il existe un nœud plus petit que y et ayant uneinformation prof plus petite que celle de y . Dans ce cas, le nœud z existe etl’algorithme ci-dessus peut etre applique.

Le dernier point a eclaircir est la maniere de determiner le type de switch(gauche-droite ou droite-gauche) qu’il faut appliquer a un nœud pour lequelcette operation doit etre realisee. Supposons que nous passons du splay treeA au splay tree B et qu’il faut e#ectuer un switch sur le nœud y de B. Si laracine de A a une valeur qui est plus grande que celle de y , alors les elementsde A appartiennent au sous-arbre droit de y dans P (car ils sont plus grandsque y). Le switch a e#ectuer est alors un switch gauche-droite. Par contre, sila valeur de la racine de A est plus petite que celle de y , alors il faut e#ectuerun switch droite-gauche.

9.3 Analyse des performances

Dans cette section, nous allons demontrer que les multi-splay trees at-teignent un taux de competitivite de O(log(log n)), ainsi qu’une complexite

89

amortie de O(log n) pour l’operation de recherche. Nous allons egalementmontrer que la complexite au pire cas d’une recherche vaut O((log n)2).Cette section est basee sur les articles [SW04] et [DSW06]. La contribu-tion personnelle a ete de detailler les demonstrations et de justifier dans lesdemonstrations des points qui ne l’avaient pas ete.

9.3.1 Fonction potentiel

La fonction potentiel utilisee pour analyser les multi-splay trees est lasuivante.

Soit T le multi-splay tree. Nous assignons a chaque nœud x de T un poidsarbitraire positif, note w(x). Pour un nœud x, nous definissons sa taille s(x)comme la somme des poids de tous les nœuds appartenant au splay subtreede x (tous les nœuds appartenant au meme splay tree que celui de x et ayantx comme ancetre). Le rang r(x) d’un nœud x vaut log(s(x)). Finalement,nous definissons le potentiel d’un arbre T comme la somme des rangs de tousses nœuds.

En resume :

w(x) ) R+ , !x ) T

s(x) =!

a"Txw(a) , ou Tx est le splay subtree de x

r(x) = log(s(x))

P (T ) =!

a"T r(a)

Il est possible de donner une autre definition equivalente pour le poten-tiel d’un multi-splay tree. Pour cela, il faut considerer la fonction potentieldefinie par Sleator et Tarjan [ST85] pour un simple splay tree (cfr point6.2.5). Comme un multi-splay tree est une collection de splay trees, il su%tde calculer le potentiel de chacun de ces splay trees et de sommer ces poten-tiels pour obtenir le potentiel de T . En comparant ces deux definitions depotentiel pour T , nous pouvons constater qu’elles sont equivalentes.

9.3.2 Access Lemma Generalise

Soit un nœud x, la complexite pour splayer ce nœud jus-qu’a un ancetre a appartenant au meme splay tree est d’au plus3(r(a) % r(x)) + 1 = O(log(s(a)/s(x))).

90

La demonstration de l’Access Lemma Generalise decoule immediatementde la demonstration de l’Access Lemma pour les splay trees (cfr point 6.2.5),parce que cette demonstration-ci ne necessite pas que le nœud a splayer soitremonte a la racine.

La di#erence entre l’Access Lemma et l’Access Lemma Generalise est que,pour ce dernier, le splaying peut s’arreter a un quelconque ancetre a de x.

9.3.3 Multi-Splay Access Lemma

Soit P un arbre de reference de racine t constitue de n nœuds et f "2 un multiplicateur. Considerons une assignation de poids, qui attribue achaque nœud x de P un poids positif w(x) et qui satisfait les deux conditionssuivantes :

1) w(x) " maxv"d(x,P )

w(v) (9.1)

2) f · w(x) " maxt"p(x,P )

#

v"t

w(v) (9.2)

ou p(x, P ) est l’ensemble des chemins dans P allant de x a un descendantde x sans enfant et d(x, P ) est l’ensemble des descendants de x dans P . Lavaleur du multiplicateur f n’est pas constante. Elle peut dependre de n (lenombre d’elements dans l’arbre). Le fait que la valeur de f puisse etre choisiearbitrairement (mais en verifiant les conditions ci-dessus) est interessant, carcela nous laisse une marge de manœuvre plus grande pour determiner desproprietes a partir de l’equation 9.3 et d’une assignation de poids aux nœuds.

Alors le temps d’execution amorti d’une sequence X = x1, x2, . . . , xm

vaut :

O

""m#

i=1

log

%w(t)

w(xi)

&$

+ (log f) · (IB(X) + m)

$

(9.3)

Demonstration : La demonstration est composee de trois etapes :

1. calculer le cout d’un switch

2. calculer le cout d’acces a un element

3. calculer le temps d’execution d’une sequence

Supposons que pour l’acces xj , il y ait k switches qui soient realises sur lesnœuds Y = y1, y2, . . . , yk. L’ordre dans lequel les switches sont e#ectues estyk, . . . , y2, y1. Notons par ti la racine du splay tree contenant yi avant l’accesxj et par tk+1 la racine du splay tree contenant xj .

91

xz

cz cx

yi

Fig. 9.3 – Relation entre x, yi, z , cx et cz dans l’arbre T . Il s’agit de larepresentation de T apres 3 splayings, mais avant l’activation de l’isroot bitde cz et la desactivation de l’isroot bit de cx .

Pour calculer le cout d’un switch yi, il faut d’abord calculer la variationde potentiel du a ce switch. Le switch yi est compose de deux changementsd’isroot bit et d’au plus trois splayings (sur yi, x et z, ou x et z sont lesnœuds comme definis pour l’algorithme des multi-splay trees au point 9.2.2).Les changements d’isroot bit porteront sur le fils droit de z , note cz , etle fils gauche de x, note cx . Ces changements d’isroot bit n’a#ecteront quele potentiel des nœuds yi , x et z . Si nous notons par r(v) et s(v) le ranget la taille d’un nœud v avant les changements d’isroot bit et par r$(v) ets$(v) le rang et la taille du nœud v apres les changements d’isroot bit, nousconstatons les proprietes suivantes (voir figure 9.3) pour les nœuds yi, x etz :

1. s$(z) = s(z) % s(cz), car l’activation de l’isroot bit de cz separe sonsous-arbre du reste du splay tree, ce qui diminue la taille de z de s(cz).Cette egalite sera designee par (A).

2. s$(x) = s(x) + s(cx), car la desactivation de l’isroot bit de cx rajoutele sous-arbre de cx au splay tree de yi, ce qui augmente la taille de xde s(cx). Cette egalite sera designee par (B).

3. s$(yi) = s(yi) + s(cx) % s(cz), car la taille de z diminue de s(cz) et lataille de x augmente de s(cx). Cette egalite sera designee par (C).

92

Pour calculer la variation de potentiel due au switch yi, il est necessairede deduire encore deux resultats :

1. s(x) " w(yi)

2. f " s(cx)/w(yi)

Le premier resultat est deduit de la maniere suivante. Au niveau de P ,nous avons que x et yi appartiennent au meme chemin prefere, car ils fontpartie du meme splay tree. De plus, nous avons que x a une profondeur pluspetite que celle de yi ; ceci est du a la definition de x dans l’algorithme desmulti-splay trees (cfr point 9.2.2). De ceci, nous concluons que x est l’ancetrede yi dans P . Comme x est l’ancetre de yi, nous obtenons de la condition9.1, que w(x) " w(yi). Et comme s(x) " w(x), nous obtenons finalementque s(x) " w(yi).

Le deuxieme resultat est deduit de la maniere suivante. Par l’algorithmedes multi-splay trees, nous avons que les nœuds (en particulier cx ) dans lesous-arbre gauche de x au niveau de T appartiennent au sous-arbre du filsnon prefere de yi dans P . Nous avons donc que yi est l’ancetre de cx dansP . Considerons l’ensemble C des chemins dans P , qui commencent en yi, quipassent par cx et qui se terminent en une feuille. Nous pouvons utiliser lacondition 9.2 pour deduire que, pour un chemin quelconque appartenant aC, la somme des poids des nœuds de ce chemin est plus petite que f ·w(yi).Or, dans T le sous-arbre gauche de x, c’est-a-dire le splay subtree de cx ,contient des nœuds plus grands que yi et ayant des informations prof plusgrandes que celle de yi. Ces nœuds forment donc dans P un sous-chemin d’undes chemins de l’ensemble C. Par consequent, la somme des poids des nœudsdans le splay subtree de cx , qui vaut s(cx), est plus petite que f · w(yi).Nous avons donc deduit que s(cx) # f · w(yi), d’ou f " s(cx)/w(yi).

En se basant sur ces constatations, nous pouvons calculer la variation depotentiel du au switch yi :

93

$P = (r$(x) % r(x)) + (r$(yi) % r(yi)) + (r$(z) % r(z)) ,

car un switch modifie le potentiel des nœuds yi, x et z

< (r$(x) % r(x)) + (r$(yi) % r(yi)) , car r$(z) % r(z) < 0

= log

%s$(x)

s(x)

&+ log

%s$(yi)

s(yi)

&, car log(A) % log(B) = log(A/B)

= log

%s(x) + s(cx)

s(x)

&+ log

%s(yi) + s(cx) % s(cz)

s(yi)

&,

par les egalites (A) et (B)

< log

%s(x) + s(cx)

s(x)

&+ log

%s(yi) + s(cx)

s(yi)

&

= log

%1 +

s(cx)

s(x)

&+ log

%1 +

s(cx)

s(yi)

&

# log

%1 +

s(cx)

w(yi)

&+ log

%1 +

s(cx)

s(yi)

&, car s(x) " w(yi)

# log

%1 +

s(cx)

w(yi)

&+ log

%1 +

s(cx)

w(yi)

&,

car s(yi) " w(yi) par definition de s(yi)

= 2 · log

%1 +

s(cx)

w(yi)

&

# 2 · log (1 + f) , car f " s(cx)

w(yi)

= O(log f)

Nous avons donc deduit que $P < O(log f).Le calcul de la complexite amortie pour le switch de yi se base sur

l’equation suivante : CAswitch = CEswitch + $P (cfr point 2.4.3), c’est-a-direque la complexite amortie du switch est egale a la complexite e#ective duswitch plus la variation de potentiel due a l’operation. La complexite e#ectivedu switch est egale au cout pour splayer yi, x et z . Comme les changementsd’isroot bit se font en temps constant, leur cout peut etre neglige . Avant decalculer la complexite amortie du switch de yi, il est utile de prouver les troisresultats suivants :

1. w(x) " w(yi) (ce resultat sera designe par (D))

2. w(z) " w(yi) (ce resultat sera designe par (E))

3. w(yi) " s(ti+1)/f (ce resultat sera designe par (F ))

94

Le premier resultat a deja ete prouve pour le calcul de $P .Le deuxieme resultat peut etre prouve de maniere similaire.Le troisieme resultat est prouve de la maniere suivante. Pour rappel, lors

d’un acces xj , il y a k switches qui sont e#ectues sur les nœuds y1, y2, . . . , yk

dans l’ordre yk, . . . , y2, y1. Et tj represente la racine du splay tree contenantyj. Comme nous e#ectuons un switch sur yi+1 suivi d’un switch sur yi, celasignifie que nous sommes passes du splay tree contenant yi+1 au splay treecontenant yi par une arete discontinue. Au niveau de P , l’ensemble des nœudsdans le splay tree de yi+1 forme un chemin t allant du fils non prefere de yi aune feuille. Or, t est un sous-chemin de d(yi, P ). En se basant sur cela, nouspouvons utiliser la condition 9.2 pour deduire que f · w(yi) "

!v"t w(v).

Comme ti+1 est la racine du splay tree de yi+1, nous avons que!

v"t w(v) =s(ti+1). Finalement, nous obtenons que f · w(yi) " s(ti+1), d’ou w(yi) "s(ti+1)/f . En se basant sur ce resultat, nous pouvons calculer la complexiteamortie d’un switch :

Cout(switch(yi)) = Cout(splay(yi)) + Cout(splay(x)) + Cout(splay(z)) + $P

< O

%log

%s(ti)

s(yi)

&&+ O

%log

%s(ti)

s(x)

&&+ O

%log

%s(ti)

s(z)

&&

+ O(log f) , ou s(ti) est la taille du splay tree de yi

< O

%log

%s(ti)

w(yi)

&&+ O

%log

%s(ti)

w(x)

&&+ O

%log

%s(ti)

w(z)

&&

+ O(log f)

# O

%log

%s(ti)

w(yi)

&&+ O

%log

%s(ti)

w(yi)

&&+ O

%log

%s(ti)

w(yi)

&&

+ O(log f) , par les resultats (D) et (E)

= O

%log

%s(ti)

w(yi)

&&+ O(log f)

# O

%log

%s(ti)

s(ti+1)/f

&&+ O(log f) , par le resultat (F )

= O

%log

%s(ti)

s(ti+1)· f

&&+ O(log f)

= O

%log

%s(ti)

s(ti+1)

&&+ O(log f) + O(log f)

= O

%log

%s(ti)

s(ti+1)

&&+ O(log f)

95

Pour calculer le cout d’acces a un nœud xj , il est necessaire de prouverles deux resultats suivants :

1. s(tk+1) " w(xj) (tk+1 est la racine du splay tree contenant xj) (ceresultat sera designe par (G))

2. f ·w(t) " s(t1) (t est la racine de P ) (ce resultat sera designe par (H))

La preuve du premier resultat decoule immediatement du fait que tk+1

est la racine du splay tree contenant xj .Le deuxieme resultat est prouve de la maniere suivante. Le nœud t1,

qui est la racine du splay tree contenant y1, est egalement la racine de T .Donc, le splay tree de t1 correspond au chemin C dans P allant de t aune feuille en suivant les fils preferes. Par la condition 9.2, nous avons quef · w(t) "

!v"C w(v) (car C ) p(t, P )). Or,

!v"C w(v) = s(t1), ce qui

implique que f · w(t) " s(t1).L’acces au nœud xj consiste a e#ectuer k switches et a splayer xj . Le cout

d’acces a xj est alors calcule comme suit :

96

Cout(Acces(xj)) =k#

i=1

Cout(switch(yi)) + Cout(splay(xj))

=k#

i=1

O

%log

%s(ti)

s(ti+1)

&&+

k#

i=1

O(log f) + O

%log

%s(t1)

s(xj)

&&

= O

%log

%s(t1)

s(tk+1)

&&+

k#

i=1

O(log f) + O

%log

%s(t1)

s(xj)

&&,

la simplification du premier terme decoule du fait que

log(A) + log(B) = log(A · B)

= O

%log

%s(t1)

s(tk+1)

&&+ O(k · log f) + O

%log

%s(t1)

s(xj)

&&

# O

%log

%s(t1)

w(xj)

&&+ O(k · log f) + O

%log

%s(t1)

w(xj)

&&,

par le resultat (G)

# O

%log

%f · w(t)

w(xj)

&&+ O(k · log f) + O

%log

%f · w(t)

s(xj)

&&,

par le resultat (H)

= O

%log

%f · w(t)

w(xj)

&&+ O(k · log f),

= O(log f) + O

%log

%w(t)

w(xj)

&&+ O(k · log f),

= O

%log

%w(t)

w(xj)

&&+ O((k + 1) · (log f)),

Le nombre k de switches e#ectues lors de l’acces xj correspond au nombrede nœuds dans P , dont les fils preferes changent a cause de cet acces. Durantl’analyse des performances de Tango, il a ete demontre que ce nombre k estegal a la borne d’entrelacement IBj(X) de l’acces xj (cfr point 8.5).

Le cout necessaire a un multi-splay tree pour executer une sequence X =x1, x2, . . . , xm vaut :

97

Cout(executer(X)) =m#

i=1

Cout(acces(xi))

=m#

i=1

O

%log

%w(t)

w(xi)

&&+

m#

i=1

O((IBi(X) + 1) · (log f))

=m#

i=1

O

%log

%w(t)

w(xi)

&&+ O

"m#

i=1

(IBi(X) + 1) · (log f)

$

=m#

i=1

O

%log

%w(t)

w(xi)

&&+ O

"(log f) ·

m#

i=1

(IBi(X) + 1)

$

=m#

i=1

O

%log

%w(t)

w(xi)

&&+ O ((log f) · (IB(X) + m)) ,

carm#

i=1

IBi(X) = IB(X)

= O

""m#

i=1

log

%w(t)

w(xi)

&$+ (log f) · (IB(X) + m)

$

!

9.3.4 Proprietes

En se basant sur le multi-splay tree access lemma, il est possible de definirtrois proprietes sur les multi-splay trees.

Theoreme 8. Le multi-splay tree est O(log(log n))-competitif.

Demonstration : Soit P un arbre de reference a n nœuds. La profondeurde P vaut (log n)+1. On pose w(v) = 1 pour tout nœud v de P et on choisitf = 2 · log n.

La condition 9.1 est verifiee, car le poids maximal d’un ensemble quel-conque de nœuds vaut 1.

La condition 9.2 est verifiee, car la longueur maximale d’un chemin vaut(log n) + 1, ce qui est bien inferieur a f .

Avec l’assignation de poids choisie, le multi-splay tree access lemma vaut :

O

""m#

i=1

log

%1

1

&$

+ (log(2 · log n)) · (IB(X) + m)

$

(9.4)

98

Comme O(log(2 · log n) = O((log 2) + (log(log n))) = O(log(log n)), nousobtenons finalement :

O((log(log n)) · OPT (X)) (9.5)

!

Theoreme 9. Un multi-splay tree de n nœuds a une complexite amortie deO(log n) pour un acces.

Demonstration : Soient P un arbre de reference a n nœuds et unesequence d’acces X = x1, x2, . . . , xm. La profondeur de P vaut (log n) + 1.Soit h(v), la hauteur d’un nœud v (la hauteur d’une feuille vaut 0 ; cfr point2.1.3). On pose w(v) = 2h(v) pour tout nœud v de P et on choisit f = 2 .Notons que le poids de la racine t de P vaut :

w(t) = 2h(t) = 2(log n)+1 = 2log n · 2 = n · 2 = O(n) (9.6)

La condition 9.1 est verifiee, car un descendant a une hauteur plus petiteque celle de son ancetre.

La condition 9.2 est verifiee, car 2i "!i!1

j=0 2j.Avec l’assignation de poids choisie, le multi-splay tree access lemma vaut :

Cout(executer(X)) # O

""m#

i=1

log

%n

w(xi)

&$+ (log 2) · (IB(X) + m)

$

# O

""m#

i=1

log (n)

$+ (IB(X) + m)

$,

car ! 1 # i # m : w(xi) " 1

= O(m · log n + OPT (X))

= O(m · log n) , car OPT (X) # m · log n

!

Theoreme 10. Pour une sequence d’acces X, le cout necessaire a un multi-splay tree pour traiter X vaut :

O(min (log(log n) · OPT (X) , m · log n)) (9.7)

99

Demonstration : Ce resultat decoule des deux theoremes precedents (lestheoremes 8 et 9).

!Nous avons encore deux proprietes concernant les multi-splay trees.

Theoreme 11. Un multi-splay tree de n nœuds a une complexite au pire casde O((log n)2) pour un acces xi.

Demonstration : Comme la hauteur de l’arbre de reference vaut log n,nous avons que le nombre de switches pour un acces xi vaut au pire caslog n. De plus, comme chaque splay tree contient au plus logn elements,nous avons que la complexite au pire cas pour une operation sur un splaytree vaut log n (car la complexite au pire cas d’une operation sur un splaytree est lineaire sur la taille de l’arbre). Ainsi, le cout pour e#ectuer un switchsur un splay tree vaut O(log n) au pire cas, car on e#ectue 3 splayings pourrealiser cette operation. Par consequent, le cout pour acceder au nœud xi

vaut O((log n) · (log n)) = O((logn)2).!

Theoreme 12. Soient un arbre a n nœuds et une sequence X consistant aacceder a ces nœuds dans l’ordre symetrique. Le cout pour traiter X vaut :

O(n) (9.8)

Ce theoreme ne sera pas demontre ici, mais une preuve est disponibledans l’article [DSW06].

9.4 Conclusion

Nous venons de presenter une structure qui atteint un taux decompetitivite de O(log(log n)), mais qui est plus simple que l’algorithmeTango. Nous avons egalement montre qu’un acces se fait avec un cout aupire cas de O((logn)2) et avec un cout amorti de O(log n).

Nous avons egalement constate que cette structure presente des similaritesavec Tango. En fait, le principe fondamental est le meme, a savoir qu’ilfaut e#ectuer des switches apres chaque acces pour changer le fils preferede certains nœuds. Seul di#ere la maniere d’e#ectuer les switches, car unmulti-splay tree est constitue de splay trees et Tango est constitue d’arbresrouges-noirs. Nous avons egalement constate que cette di#erence fournit uneplus grande souplesse aux multi-splay trees.

100

Grace a cette souplesse, il est possible d’etendre cette structure pourqu’elle puisse supporter les operations d’insertion et de suppression tout engardant au taux de competitivite de O(log(log n)).

Comme les multi-splay trees presentent des similitudes avec les splaytrees, nous pouvons nous demander si les multi-splay trees possedentegalement les proprietes d’optimalite statique, de static finger, de wor-king set et de dynamic finger [DSW06]. De par cette similitude, un autreprobleme, que nous pourrions nous poser, serait de savoir si les splay treessont O(log(log n)) % competitifs [DSW06].

Nous avons montre que les multi-splay trees et Tango ont un taux decompetitivite de O(log(log n)), mais il se peut que ces deux structures at-teignent l’optimalite dynamique [DSW06]. Pour prouver cela, il faudrait unborne inferieure sur OPT (X) qui soit meilleure que la borne inferieure d’en-trelacement, mais le grand probleme est que de telles bornes sont rares. Cemanque de bornes inferieures est l’un des principaux obstacles pour avoir unestructure optimale dynamiquement.

101

Chapitre 10

Optimalite de recherchedynamique

La redaction de ce chapitre est basee sur l’article de Blum, Chawla etKalai [BCK03].

Dans cette section, nous allons montrer qu’il existe une structure, quiatteint l’optimalite dynamique, si nous ne tenons pas compte du cout desrotations qu’elle e#ectue apres chaque acces.

10.1 Definition

Dans le modele dynamique (cfr point 2.2.1) des ABR que nousconsiderons, le cout d’acces a un element xi est egal au cout de localisa-tion de xi plus le cout des rotations e#ectuees apres avoir atteint xi. Unestructure a la propriete d’optimalite de recherche dynamique si, pour unequelconque sequence X, le cout necessaire a la localisation des elements deX est egal a O(OPT (X)), ou OPT (X) est le cout d’acces aux elements de Xpour l’algorithme o$ine optimal. En d’autres termes, une structure a l’opti-malite de recherche dynamique si son cout pour traiter une sequence (sanscompter les rotations) est egal au cout de l’algorithme o$ine optimal.

10.2 Interet

Un argument en defaveur de l’existence d’un algorithme online optimalserait le suivant. Pour qu’un algorithme soit optimal, il faut qu’il puissegarder pres de la racine les nœuds qui doivent encore etre accedes. Mais leprobleme d’un algorithme online est qu’il ne peut pas deviner les acces avenir et que par consequent il a trop de nœuds a maintenir pres de la racine.

102

L’interet de la propriete d’optimalite de recherche dynamique est de rejetercet argument, car elle montre qu’il est possible pour une structure online degarder les nœuds a acceder su%samment proches de la racine pour avoir uncout optimal.

10.3 Structure

Ici, le but est de prouver qu’il existe une structure ABR online qui atteintl’optimalite de recherche dynamique. L’elaboration de la structure se fait al’aide de distributions de probabilites sur les sequences d’acces. Nous verronsqu’il est possible de transformer une distribution de probabilites en un arbrebinaire de recherche et un arbre binaire de recherche en une distributionde probabilites. Ces transformations sont telles que les nœuds proches dela racine sont ceux dont la probabilite d’acces est la plus grande. Avant depresenter la structure, il est necessaire de presenter quelques resultats.

Toutes les demonstrations presentees ci-dessous sont basees sur l’ar-ticle [BCK03]. La contribution personnelle a consiste a detailler cesdemonstrations et a justifier dans ces demonstrations des points qui nel’avaient pas ete.

Theoreme 13. Le nombre de sequences d’acces pouvant etre executees avecun cout optimal k est de tout au plus 212k, pour tout k " 0.

Ce theoreme n’est pas demontre ici, mais une preuve peut etre consulteedans [BCK03].

Theoreme 14. Il existe une distribution de probabilites sur les sequencesd’acces, qui assigne une probabilite d’au plus 2!13k a une sequence d’accesdont le cout optimal est k.

Demonstration : On choisit le nombre k dans l’intervalle [1,&] selon ladistribution 1/2k. Ensuite, on choisit une sequence d’acces X parmi toutes lessequences dont le cout optimal est k. Comme il existe au plus 212k sequencesde cout optimal k, la probabilite de choisir X parmi toutes les sequences decout k est de 2!12k. Finalement, la probabilite de choisir X vaut au plus :

1

2k· 1

212k=

1

213k(10.1)

!

Theoreme 15. Un arbre binaire de recherche T peut etre transforme en unedistribution de probabilites p telle que pour tout nœud j appartenant a T :

103

p(j) " 3!profondeur(j) (10.2)

Demonstration : A chaque nœud j de T , on associe une probabilite p(j)qui est egale a la probabilite d’atteindre j si on commence la recherche a laracine. Cette probabilite est determinee de la maniere suivante :

1. Commencer a la racine de l’arbre.

2. Soit x le nœud courant :

(a) Si x a deux fils, alors la probabilite d’aller a gauche vaut 1/3, celled’aller a droite vaut 1/3 et celle de s’arreter vaut egalement 1/3.

(b) Si x a un fils (disons le fils gauche), alors la probabilite d’aller agauche vaut 1/2 et celle de s’arreter vaut egalement 1/2. Le casdu fils droit est similaire.

(c) Si x n’a pas de fils, alors la probabilite de s’arreter vaut 1.

Ce traitement est a iterer jusqu’au nœud j.

La probabilite p(j) correspond donc a la probabilite d’atteindre le nœudj et de s’y arreter.

De cette construction, nous deduisons immediatement que p(j) "3!profondeur(j).

Il ne reste plus qu’a demontrer que!

j"T p(j) = 1, de maniere a verifierque p soit bien une distribution de probabilites. Ceci peut se faire parrecurrence sur la hauteur h(T ) de T :

1. Cas de base : la hauteur de T vaut 0. Dans ce cas, l’arbre est constitued’un seul nœud dont la probabilite associee vaut 1.

2. Cas d’induction : considerons que!

i"T p(i) = 1 pour un arbre T dehauteur i et montrons que c’est egalement le cas pour un arbre dehauteur i + 1.

Soit T un arbre de hauteur i+1 et de racine t. Deux cas sont possibles :soit t a deux fils, soit il n’en a qu’un seul. Traitons le premier cas (ledeuxieme cas peut etre resolu de maniere similaire).

La probabilite de s’arreter en t vaut 1/3, celle d’aller dans le sous-arbregauche de t vaut 1/3 et celle d’aller dans le sous-arbre droit de t vaut1/3. Comme le sous-arbre gauche de t a une hauteur i, nous pouvonsy appliquer l’hypothese d’induction. Mais comme ce sous-arbre est at-tache a la racine de t comme fils gauche, nous avons que la probabilitede chaque nœud du sous-arbre doit etre multipliee par 1/3. On obtientalors que :

104

#

i"SAG(t)

p(i) = 1 · 1

3=

1

3(10.3)

Finalement, nous avons que :

#

i"T

p(i) =

,

-#

i"SAG(t)

p(i)

.

/ +

,

-#

i"SAD(t)

p(i)

.

/ + p(t)

=1

3+

1

3+

1

3= 1

!

Theoreme 16. Pour une distribution de probabilites sur n acces, nous pou-vons creer un arbre binaire de recherche T tel que pour tout nœud a de T :

profondeur(a) # 1 % log(p(a)) (10.4)

Demonstration : La construction de T se fait de maniere recursive.Pour la racine de T , on choisit le premier i tel que

!i!1j=1 p(j) # 1/2 et!n

j=i+1 p(j) # 1/2. Ensuite, on travaille de maniere recursive sur les elementsstrictement plus petits que i pour construire le sous-arbre gauche de i. Pourcela, il faut normaliser p, de maniere a ce que

!i!1j=1 p(j) = 1. Apres cela,

il faut e#ectuer un travail similaire sur les elements strictement plus grandsque i pour construire le sous-arbre droit de i.

De la maniere dont on construit T , nous constatons que pour tout nœudi de T , la somme des probabilites des nœuds appartenant au sous-arbre de iest d’au plus 1/2d!1, ou d est la profondeur de i.

Grace a cette observation, nous pouvons montrer que la profondeur d’unnœud i de probabilite p(i) ne peut pas etre plus grande que % log(p(i)). Ene#et, supposons que le nœud i de profondeur d soit tel que d%1 > % log(p(i))(dans ce cas d est plus grand que % log(p(i))). Nous en deduisons que :

1

2d!1<

1

2! log(p(i))

= 2log(p(i))

= p(i)

105

Et donc, 1/2d!1 < p(i). Nous savons egalement que p(Ti) # 1/2d!1, ou Ti

est le sous-arbre de i. En combinant ces deux resultats, nous obtenons que :

p(Ti) #1

2d!1< p(i) (10.5)

Or, ceci est impossible, car p(Ti) " p(i). En faisant l’hypothese que d%1 >% log(p(i)), nous sommes arrives a une contradiction. On en deduit donc que :

d % 1 # % log(p(i))

d # 1 % log(p(i))

!Theoreme 17. Pour une quelconque distribution de probabilites p sur unesequence d’acces, nous pouvons creer un algorithme online dont le cout pourtraiter la sequence vaut tout au plus m% log(p(x1 x2 . . . xm)) et cela quelle quesoit la sequence x1, x2, . . . , xm. Nous notons par p(x1 x2 . . . xm) la probabilited’avoir x1, x2, . . . , xm comme premier, deuxieme, . . . , meme acces.

Demonstration : Considerons les distributions de probabilitesp1, p2, . . . , pm. Nous definissons la probabilite pi(xj) comme la probabi-lite p d’avoir xj comme ieme acces sachant que x1 etait le premier acces, x2

etait le deuxieme acces, et ainsi de suite jusque xi!1 le (i % 1)eme acces. Laprobabilite pi(xj) est definie en termes de probabilites conditionnelles de lamaniere suivante :

pi(xj) = p(xj |x1 x2 . . . xi!1) (10.6)

ou p(xj |x1 x2 . . . xi!1) est la probabilite d’avoir xj comme ieme acces sa-chant que x1, x2, . . . , xi!1 etaient respectivement le premier, deuxieme, . . . ,(i % 1)eme acces.

Par definition des probabilites conditionnelles, nous avons que :

p(B |A) =p(A , B)

p(A)(10.7)

En se basant sur ce resultat, nous obtenons que :

p(xj |x1 x2 . . . xi!1) =p(xj , (x1 x2 . . . xi!1)

p(x1 x2 . . . xi!1)

=p(x1 x2 . . . xi!1 xj)

p(x1 x2 . . . xi!1)

106

Pour la probabilite p(x1 x2 . . . xi!1 xj), nous n’avons aucune restrictionquant a la valeur que peut prendre le (i + 1)eme, (i + 2)eme, . . . , meme acces.Nous avons donc que :

p(xj |x1 x2 . . . xi!1) =

!xm

bi+1=x1. . .

!xm

bm=x1p(x1 . . . xi!1 xj bi+1 . . . bm)

!xm

bi=x1. . .

!xm

bm=x1p(x1 . . . xi!1 bi . . . bm)

(10.8)

La valeur de pi(xj) peut alors etre calculee algorithmiquement grace auresultat ci-dessus.

Soit le lemme suivant :

p(A1 , A2 , . . . , An) = p(A1) · p(A2 |A1) . . . p(An |A1 , . . . , An!1) (10.9)

En se basant sur ce lemme, nous avons que :

p(x1 x2 . . . xm) = p(x1) · p(x2 |x1) . . . p(xm |x1 . . . xm!1)

= p1(x1) · p2(x2) . . . pm(xm)

=m0

i=1

pi(xi)

L’algorithme online procede de la maniere suivante. Pour le ieme acces,on calcule la distribution de probabilites pi grace a la formule 10.8. Ensuite,on convertit la distribution de probabilites pi en un ABR en utilisant letheoreme 16. De par cette construction, la profondeur d’un acces xi est d’auplus 1 % log(pi(xi)). Le cout des m acces (en ne tenant compte que du coutpour localiser les elements) est d’au plus :

m#

i=1

(1 % log(pi(xi))) = m % log(p(x1 . . . xm)) (10.10)

!

Theoreme 18. Il existe un algorithme online, qui a la propriete d’optimalitede recherche dynamique.

Demonstration : Considerons la distribution de probabilites du theoreme14, qui assigne une probabilite de 2!13k a une sequence d’acces dont le coutoptimal est k. Combinons cette distribution de probabilites avec le theoreme17 pour obtenir un algorithme online, dont le cout d’acces a une sequence

107

X = x1, . . . , xm (en ne tenant compte que du cout pour localiser les elements)est d’au plus :

m % log'2!13·OPT (x1...xm)

(= m + 13 · OPT (x1 . . . xm)

# 14 · OPT (x1 . . . xm),

car m # OPT (x1 . . . xm)

L’algorithme online necessite un cout d’au plus 14 fois le cout optimalpour localiser les elements d’une sequence d’acces. Cet algorithme a donc lapropriete d’optimalite de recherche dynamique.

!

10.4 Conclusion

Dans cette section, nous avons presente une structure qui atteint l’opti-malite de recherche dynamique. L’existence d’une telle structure a un grandinteret, parce qu’il s’agit d’un argument en faveur de l’existence d’une struc-ture atteignant l’optimalite dynamique.

Un probleme ouvert concernant l’optimalite de recherche dynamique[BCK03] serait d’elaborer une structure e%cace, qui puisse atteindre cettepropriete.

108

Chapitre 11

Experimentations

Dans ce chapitre, nous allons executer un certain nombre de jeux de testspour analyser et comparer les performances en pratique des arbres rouges-noirs, des splay trees et des multi-splay trees. Le but est de surtout constatersi les multi-splay trees fournissent des resultats interessants en pratique et sil’algorithme des multi-splay trees, qui est plus complexe que celui des arbresrouges-noirs et des splay trees, ne porte pas prejudice aux performances enpratique des multi-splay trees.

Nous allons d’abord expliquer le type de jeux de tests qui seront executeset ensuite, nous allons presenter les resultats de ces jeux de tests pour essayerd’en tirer des constatations.

11.1 Jeux de tests

Nous avons e#ectue plusieurs tests en considerant des tailles di#erentespour la structure. Nous faisons varier la taille de la structure de 28 a 216

en multipliant a chaque pas la taille de la structure par 2. Pour chaquetaille n, nous faisons varier la taille de la sequence de n a 10 · n par pas delog n. Pour chaque sequence, nous calculons le cout necessaire a la structurepour l’executer en prenant comme modele de cout celui defini par le modeledynamique (cfr point 2.2.1). Nous considerons deux types de distributionpour generer une sequence d’acces :

1. distribution aleatoire

2. distribution working set

109

0

10000

20000

30000

40000

50000

60000

70000

80000

0 500 1000 1500 2000 2500 3000

MST8ST8RB8

Fig. 11.1 – Couts d’un arbre de taille 28 avec une distribution aleatoire

11.2 Distribution aleatoire

Supposons que la taille de l’arbre soit egale a n. Une sequence d’accesest generee en choisissant de maniere aleatoire les elements qui la composentparmi les n elements possibles.

Les resultats de ces tests sont illustres par les graphes des figures 11.1 et11.2 (d’autres graphes sont fournis en annexe). Ces resultats nous permettentde constater que le cout des arbres rouges-noirs est plus petit que celui dessplay trees ; lui-meme plus petit que celui des multi-splay trees. Ceci estverifie sur chacun des graphiques cites ci-dessus. De plus , nous constatons surchaque graphique que la di#erence de cout entre les trois structures s’amplifiea mesure que la taille de la sequence augmente.

Des lors, au vue de ces resultats, on peut penser que les arbres rouges-noirsont un meilleur comportement que les splay trees et que cette structure a unmeilleur comportement que les multi-splay trees pour le type de distributionque nous considerons dans cette section. Le fait que les multi-splay trees aientde moins bonnes performances s’expliquent par la complexite de l’algorithmede cette structure et par le grand nombre d’operations de reorganisationqu’elle necessite.

110

0

5e+06

1e+07

1.5e+07

2e+07

2.5e+07

3e+07

3.5e+07

4e+07

4.5e+07

5e+07

0 100000 200000 300000 400000 500000 600000 700000

MST16ST16RB16

Fig. 11.2 – Couts d’un arbre de taille 216 avec une distribution aleatoire

11.3 Distribution working set

Supposons que la taille de la structure soit egale a n. Une sequence d’accesest generee en choisissant de maniere aleatoire les elements qui la composentparmi un sous-ensemble de l’ensemble {1, . . . , n}. Ce sous-ensemble a unetaille de n/5 et correspond a l’ensemble {n/2 % n/10, . . . , n/2 + n/10}. Lebut est de tirer profit de la propriete working set des splay trees pour analyserson comportement dans ce cas.

Les resultats de ces tests sont illustres par les graphes des figures 11.3 et11.4 (d’autres graphes sont fournis en annexe). Si nous analysons le compor-tement des splay trees, nous remarquons qu’au debut il est similaire a leurcomportement pour le premier type de distribution analyse. Ensuite, le com-portement di#ere , car nous assistons a une diminution du cout d’executiondes sequences d’acces. Cette diminution s’explique par le fait que les splaytrees ont la propriete working set. En e#et, comme nous n’accedons qu’aun sous-ensemble des n elements possibles, nous avons que de plus en plusd’elements de ce sous-ensemble ont tendance a se retrouver pres de la racine,ce qui implique que nous avons de plus en plus d’acces a faible cout. Et celase traduit par une diminution du cout total de la sequence d’acces. Apres laphase de decroissance, nous avons une phase ou le cout augmente, mais de

111

facon legere. Cette augmentation s’explique par le fait que tous les elementsdu sous-ensemble des elements accedes ont ete ramenes pres de la racine,ce qui implique que nous ne pouvons plus esperer une amelioration du coutd’execution des sequences d’acces. Dans cette phase, l’augmentation du coutest legere, car les elements accedes sont proches de la racine, ce qui impliqueque leur cout d’acces est faible.

Le comportement des arbres rouges-noirs di#ere peu de leur compor-tement pour le premier type de distribution analyse, parce que les arbresrouges-noirs n’ont pas la propriete working set et qu’ils ne sont pas capablesde s’adapter a une sequence d’acces.

En ce qui concerne les multi-splay trees, nous constatons que leur compor-tement presente des analogies avec celui des splay trees, ce qui pourrait laissersuggerer que cette structure a la propriete working set. Ceci est a prendreavec precaution, car nous tirons une constatation sur quelques resultats, maisil n’existe aucune preuve qui le demontre. Dans la derniere phase de crois-sance, nous constatons que le cout des multi-splay trees a tendance a croıtreplus vite que celui des splay trees. Ceci s’explique par le fait que l’algorithmedes multi-splay trees exige plus d’operations de reorganisation que celui dessplay trees. Nous pouvons egalement constater que le cout des multi-splaytrees est plus petit que celui des arbres rouges-noirs.

Au debut de chaque graphique les arbres rouges-noirs ont un cout quiest meilleur que celui des splay trees et cette structure a un cout qui estmeilleur que celui des multi-splay trees. Mais de par le type de distributionsur laquelle nous travaillons, la tendance s’inverse rapidement. Les splay treesont alors un cout meilleur que celui des multi-splay trees et ceux-ci ont uncout meilleur que celui des arbres rouges-noirs.

11.4 Conclusion

Les di#erents jeux de tests executes nous ont permis de constater que lesmulti-splay trees sou#rent de la complexite de leur algorithme et du grandnombre d’operations de reorganisation qu’il necessite.

Nous avons egalement obtenu des resultats qui pourraient laisser suggererque les multi-splay trees ont la propriete working set.

Les tests e#ectues sur le deuxieme type de distribution illustrent bien lacapacite des splay trees a s’adapter a une sequence d’acces et a l’incapacitedes arbres rouges-noirs a faire de meme.

112

0

5000

10000

15000

20000

25000

30000

35000

40000

0 500 1000 1500 2000 2500 3000

MST8ST8RB8

Fig. 11.3 – Couts d’un arbre de taille 28 avec une distribution working set

0

2e+06

4e+06

6e+06

8e+06

1e+07

1.2e+07

1.4e+07

1.6e+07

1.8e+07

2e+07

2.2e+07

0 100000 200000 300000 400000 500000 600000 700000

MST16ST16RB16

Fig. 11.4 – Couts d’un arbre de taille 216 avec une distribution working set

113

Chapitre 12

Conclusion

Nous avons etudie comme premiere structure les ABRO et nous avonsdetaille l’algorithme qui permet a cette structure d’atteindre l’optimalite sta-tique en se basant sur la connaissance prealable de la distribution des cles aacceder.

Puis, nous avons etudie les arbres rouges-noirs et les splay trees. En ana-lysant les performances de ces structures, nous avons constate que les arbresrouges-noirs fournissent des resultats interessants sur un acces, alors que lessplay trees ont besoin de sequences d’acces plus grandes pour fournir debonnes performances. Nous avons egalement constate que les arbres rouges-noirs ne sont pas capables de s’adapter aux particularites d’une sequenced’acces, alors que les splay trees y parviennent. C’est cette qualite qui fait laforce des splay trees. Et enfin, nous avons constate que les arbres rouges-noirssont O(log n) % competitifs, alors que les splay trees sont conjectures etreO(1) % competitifs.

Ensuite, nous avons enonce et demontre trois bornes inferieures sur lecout d’execution d’une sequence d’acces dans des ABR. L’interet de tellesbornes est grand, car elles permettent de developper de nouvelles structures.A l’heure actuelle, le principal obstacle pour developper une structure quipuisse atteindre l’optimalite dynamique, est le manque de bornes inferieuresde qualite.

La structure Tango a ete developpee sur base de l’une des trois bornesetudiees : la borne inferieure d’entrelacement. Cette structure est la premierequi ait ameliore le taux trivial de competitivite de O(log n). Cette structureatteint un taux de O(log(log n)). Le probleme avec cette structure est qu’elleest complexe, ce qui fait que son implementation est assez lourde.

Les multi-splay trees sont une structure de donnees ABR. Cette struc-ture est basee sur les memes principes que Tango et elle atteint egalementun taux de competitivite de O(log(log n)). Cette structure est plus simple

114

a implementer que Tango. De plus, elle peut etre etendue pour suppor-ter les operations d’insertion et de suppression tout en gardant le taux decompetitivite de O(log(log n)).

Ensuite, nous avons etudie une structure, qui atteint l’optimalite de re-cherche dynamique. Nous avons egalement montre que l’existence d’une tellestructure est importante, car il s’agit d’un argument en faveur de l’existenced’une structure optimale dynamiquement.

Et enfin, nous avons execute des jeux de tests sur les arbres rouges-noirs,les splay trees et les multi-splay trees. Le but de ces tests etait d’analyser lesperformances en pratique de ces structures. Cela nous a permis de constaterque les arbres rouges-noirs sont performants sur des sequences d’acces, oules nœuds a acceder sont choisis de maniere aleatoire parmi l’ensemble desnœuds de l’arbre. Nous avons egalement remarque que les splay trees sontperformants sur des sequences d’acces, ou les nœuds a acceder sont choisisde maniere aleatoire parmi un sous-ensemble de l’ensemble des nœuds del’arbre. Ceci est du au fait que les splay trees ont la propriete working set.L’analyse des performances des multi-splay trees sur ce type de sequencespeut nous laisser suggerer que cette structure a egalement la propriete wor-king set. Concernant les multi-splay trees, nous avons egalement constate quel’algorithme complexe de cette structure a une incidence sur ses performancesen pratique.

Ce memoire a consiste en un travail de recherche bibliographique et ila consiste a synthetiser les grandes avancees dans le domaine des arbresbinaires de recherche et de l’optimalite dynamique. En general, les articlesetudies presentent les algorithmes et les demonstrations de maniere assezsuccincte. Un objectif de ce memoire a donc ete de presenter ces algorithmeset ces demonstrations de maniere didactique en les decortiquant et en lesdetaillant le plus possible.

115

Chapitre 13

Annexe

13.1 Implementation

De maniere a analyser et comparer les performances en pratique desmulti-splay trees, des splay trees et des arbres rouges-noirs, nous avonsimplemente l’algorithme des multi-splay trees et des splay trees. Pour l’algo-rithme des arbres rouges-noirs, nous avons recupere une implementation surle net [Nie05]. Ces trois implementations sont fournies en annexe.

Le but n’est pas d’avoir une implementation de ces structures qui puissentfaire partie d’une librairie en implementant par exemple un type generiquepour les cles. Le but est de simplement avoir une implementation permettantd’executer des jeux de tests.

13.1.1 Multi-splay trees

Les cles sont des elements de type entier et il faut que la taille de l’arbresoit egale a n = 2k%1 (! k > 1). Les valeurs des cles correspond a l’ensemble{1, . . . , n}.

Pour l’implementation de la structure, nous utilisons deux classes :

1. elem : cette classe represente un nœud de l’arbre, ainsi que ses di#erentschamps.

2. splaytree : cette classe represente le multi-splay tree.

Nous detaillons ci-dessous les points principaux de l’implementation. Desexplications plus detaillees sont fournies en tant que commentaires dans lecode.

L’initialisation de la structure se fait a l’aide de la methode construireP,qui est appelee par le constructeur parametre de la classe splaytree. Dans cettemethode, nous construisons un arbre parfait de n nœuds et nous initialisons

116

le fils prefere de chaque nœud a son fils gauche. Durant cette constructionl’isroot bit du fils gauche et du fils droit de chaque nœud est initialise, res-pectivement, a false et true (car pour chaque nœud, son fils droit est son filsnon prefere). De plus, le champ mindepth de chaque nœud x est initialise asa profondeur dans l’arbre parfait (car tous les nœuds dans le splay subtreede x ont une profondeur plus grande que celle de x).

L’arbre parfait ainsi construit est, en fait, egalement un multi-splay treeet il est utilise comme etat initial de la structure. L’avantage d’une telleconstruction est qu’elle permet d’initialiser la structure avec un cout O(n).

La methode recherche localise d’abord le nœud i passe en parametre etreorganise ensuite la structure de maniere a avoir un chemin prefere allant dela racine du multi-splay tree au nœud passe en parametre. La reorganisationde la structure est e#ectuee dans la boucle principale de la methode. Letraitement de cette boucle est le suivant. Si le nœud courant est la racined’un splay tree, alors il faut rechercher dans le splay tree de son pere le nœudsur lequel e#ectuer un switch. Un fois ce nœud determine, on applique soitun switch droite-gauche (methode switchDG), soit un switch gauche-droite(methode switchGD). Et on recommence la boucle jusqu’a ce que la racinede l’arbre soit atteinte. Et lorsqu’elle est atteinte, on splaye le nœud i pourle ramener a la racine de l’arbre (methode switchracine).

Les methodes switchGD et switchDG ne sont qu’une implementation desalgorithmes decrits dans le chapitre 9 pour e#ectuer un switch.

L’implementation est fournie ci-dessous.

# include <iostream># include <limits.h># include <time.h># include <math.h># include <iomanip># include <stdlib.h># include <unistd.h># include <sys/types.h># include <sys/stat.h># include <fcntl.h>using namespace std ;

class splaytree{

private :class elem{

117

friend class splaytree ;int info ;// cle du noeudint profondeur ;// profondeur du noeud dans

//l’arbre de referenceint mindepth ;// profondeur minimum dans le

//splay subtree du noeudbool isroot ;elem - fg ;elem - fd ;elem - pere ;elem(){}elem(int i, int prof=0 , int mind=1, bool

isr=false, elem - g = NULL, elem - d = NULL, elem - p =NULL) :info(i),profondeur(prof), mindepth(mind), isroot(isr), fg(g), fd(d),pere(p) {}

} ;elem - rac ;// racine du multi-splay treevoid rotationsimple(elem -,bool &) ;void zigzag(elem -,bool &) ;void zigzig(elem -,bool &) ;

void splayingracine(elem -) ;void splayingto(elem -, elem -) ;

elem- construireP(int,int,double,int, bool,elem-) ;

elem - localisation(int) ;elem- determinerZ(elem -) ;elem- determinerX(elem -) ;void switchGD(elem -) ;void switchDG(elem -) ;

void infixe(elem -) ;void destructeur(elem -) ;int min(int a, int b) {if(a < b) return(a) ; else

return(b) ;}

public :splaytree(){rac=NULL ;}splaytree(int) ;elem - recherche(int) ; ;

118

'splaytree() ;} ;

splaytree : :splaytree(int n)//Constructeur parametre du multi-splay tree{

elem - p = construireP((n/2)+1,1,(log(n+1.0)/log(2.0)),0, true,NULL) ;

rac=p ;}

splaytree : :elem- splaytree : :construireP(int taille, int prof, double stop,int biais, bool isroot, elem - parent)// Construit l’etat initial du multi-splay tree{

if(prof <= stop){

elem - p = new elem(taille+biais, prof, prof, isroot,NULL, NULL, parent) ;

// la variable biais contient la valeur de la cle// du pere de p, ce qui permet d’initialiser la cle// de p a la bonne valeurp.fg = construireP(taille/2, prof+1,stop,biais, false, p) ;p.fd = construireP(taille/2, prof+1, stop, taille+biais,

true, p) ;// Construction recursive pour le sous-arbre gauche// et le sous-arbre droit de preturn(p) ;

}else

return(NULL) ;}

void splaytree : :rotationsimple(elem - p, bool & stop)// Cette methode e"ectue une rotation simple. La variable ”stop”//indique a l’appelant si le noeud p est devenu la racine du//splay tree auquel il appartient (stop = true) ou non (stop = false){

elem - q = p.pere ;int a=INT MAX, b=INT MAX ;

119

if(q.isroot)// Dans ce cas, il faut changer l’isroot bit de p et q,//car p devient la racine du splay tree auquel il//appartient et q ne l’est plus{

q.isroot=false ;p.isroot=true ;stop=true ;

}

if(q.pere){

// Mise a jour des pointeurs du pere de q pour// qu’il devienne le pere de pif(q == q.pere.fd)

q.pere.fd = p ;else

q.pere.fg = p ;}// Les operations ci-dessous sont des mises a jour de//pointeurs pour e"ectuer la rotation simplep.pere = q.pere ;q.pere = p ;

if(p == q.fg){

q.fg = p.fd ;if(q.fg)

q.fg.pere = q ;p.fd = q ;

}else{

q.fd = p.fg ;if(q.fd)

q.fd.pere = q ;

p.fg = q ;}

120

// Les operations ci-dessous mettent a jour les champs//”mindepth”, qui changent a cause de la rotationp.mindepth = q.mindepth ;if(q.fg)

a = q.fg.mindepth ;if(q.fd)

b = q.fd.mindepth ;

q.mindepth = min(q.profondeur, min(a,b)) ;

}

void splaytree : :zigzag(elem - p, bool & stop)// Cette methode e"ectue une rotation zig-zag. La variable ”stop”//indique a l’appelant si le noeud p est devenu la racine du splay//tree auquel il appartient (stop = true) ou non (stop = false){

elem - q = p.pere ;elem - z = q.pere ;int a=INT MAX, b=INT MAX ;

if(z.isroot)// Dans ce cas, il faut changer l’isroot bit de p et z,//car p devient la racine du splay tree auquel il//appartient et z ne l’est plus{

// Mise a jour des pointeurs du pere de z pour//qu’il devienne le pere de pz.isroot=false ;p.isroot=true ;stop=true ;

}// Les operations ci-dessous sont des mises a jour de//pointeurs pour e"ectuer la rotation zig-zagp.pere = z.pere ;z.pere = p ;q.pere = p ;

if(p == q.fd)

121

{q.fd = p.fg ;if(q.fd)

q.fd.pere = q ;z.fg = p.fd ;if(z.fg)

z.fg.pere = z ;p.fg = q ;p.fd = z ;

}else{

q.fg = p.fd ;if(q.fg)

q.fg.pere = q ;z.fd = p.fg ;if(z.fd)

z.fd.pere = z ;p.fg = z ;p.fd = q ;

}

if(p.pere){

if(p.pere.fg == z)p.pere.fg = p ;

elsep.pere.fd = p ;

}

// Les operations ci-dessous mettent a jour les champs//”mindepth”, qui changent a cause de la rotation

p.mindepth = z.mindepth ;

if(z.fg)a = z.fg.mindepth ;

if(z.fd)b = z.fd.mindepth ;

122

z.mindepth = min(z.profondeur, min(a,b)) ;

a = INT MAX ;b = INT MAX ;if(q.fg)

a = q.fg.mindepth ;if(q.fd)

b = q.fd.mindepth ;

q.mindepth = min(q.profondeur, min(a,b)) ;

}

void splaytree : :zigzig(elem - p, bool & stop)// Cette methode e"ectue une rotation zig-zig. La variable//”stop” indique a l’appelant si le noeud p est devenu la//racine du splay tree auquel il appartient (stop = true)//ou non (stop = false){

elem - q = p.pere ;elem - z = q.pere ;int a = INT MAX, b = INT MAX ;

if(z.isroot)// Dans ce cas, il faut changer l’isroot bit de p et z,//car p devient la racine du splay tree auquel il//appartient et z ne l’est plus{

// Mise a jour des pointeurs du pere de z pour//qu’il devienne le pere de pz.isroot=false ;p.isroot=true ;stop=true ;

}

// Les operations ci-dessous sont des mises a jour de//pointeurs pour e"ectuer la rotation zig-zigp.pere = z.pere ;q.pere = p ;z.pere = q ;

123

if(p == q.fg){

q.fg = p.fd ;if(q.fg)

q.fg.pere = q ;z.fg = q.fd ;if(z.fg)

z.fg.pere = z ;p.fd = q ;q.fd = z ;

p.mindepth = z.mindepth ;

if(z.fg)a = z.fg.mindepth ;

if(z.fd)b = z.fd.mindepth ;

z.mindepth = min(z.profondeur, min(a,b)) ;

a = INT MAX ;if(q.fg)

a = q.fg.mindepth ;

q.mindepth = min(q.profondeur,min(a,z.mindepth)) ;

}else{

q.fd = p.fg ;if(q.fd)

q.fd.pere = q ;z.fd = q.fg ;if(z.fd)

z.fd.pere = z ;p.fg = q ;q.fg = z ;

124

p.mindepth = z.mindepth ;

if(z.fg)a = z.fg.mindepth ;

if(z.fd)b = z.fd.mindepth ;

z.mindepth = min(z.profondeur, min(a,b)) ;

a = INT MAX ;if(q.fd)

a = q.fd.mindepth ;

q.mindepth = min(q.profondeur,min(a,z.mindepth)) ;

}

if(p.pere){

if(p.pere.fg == z)p.pere.fg = p ;

elsep.pere.fd = p ;

}

}

void splaytree : :splayingracine(elem - p)// Cette methode splaye le noeud p jusqu’a ce qu’il devienne//la racine du multi-splay tree auquel il appartient{

elem - q =p.pere ;bool stop = false ;short int tester=0 ;

// On verifie que le noeud a splayer ne soit pas la//racine du multi-splay treeif( !p.isroot){

while( !stop && q)

125

{if(q.isroot){

rotationsimple(p,stop) ;break ;

}else{

if(p == q.fg)//si p est un fils gauche, on//incremente test de 1

++tester ;else//sinon test est decremente de 1

– –tester ;

if(q == q.pere.fg)//si q est un fils gauche, on//incremente test de 1

++tester ;else//sinon test est decremente de 1

– –tester ;

if(tester)//si test est di"erent de 0, cela//signifie qu’on est remonte par deux//sens di"erents pour aller du//noeud x a son grand-pere. Il faut//donc e"ectuer une rotation zig-zig{

zigzig(p,stop) ;tester=0 ;

}else//sinon on est remonte deux fois par le

//meme sens pour aller du//noeud x a son grand-pere. Il faut//donc e"ectuer une rotation zig-zag{ zigzag(p,stop) ;}

126

q = p.pere ;}

}

if( !p.pere)//si p n’a pas de pere, alors il// est la racine du multi-splay tree

{rac = p ;// on met a jour la racine du multi-splay tree

}}

}

void splaytree : :splayingto(elem - p, elem - arret)// Cette methode splaye le noeud p jusqu’a ce qu’il devienne//le fils du noeud arret{

elem - q =p.pere ;short int test=0 ;bool stop=false ;

while(q != arret){

if(q.pere == arret){

rotationsimple(p,stop) ;break ;

}else{

if(p == q.fg)//si p est un fils gauche, on//incremente test de 1

++test ;else//sinon test est decremente de 1

– –test ;

127

if(q == q.pere.fg)//si q est un fils gauche, on//incremente test de 1

++test ;else//sinon test est decremente de 1

– –test ;

if(test)//si test est di"erent de 0, cela//signifie qu’on est remonte par deux//sens di"erents pour aller du//noeud x a son grand-pere. Il faut//donc e"ectuer une rotation zig-zig{

zigzig(p,stop) ;test=0 ;

}else//sinon on est remonte deux fois par le//meme sens pour aller du//noeud x a son grand-pere. Il faut//donc e"ectuer une rotation zig-zag

zigzag(p,stop) ;

q = p.pere ;}

}}

splaytree : :elem- splaytree : :localisation(int i)// Cette methode localise le noeud i dans le multi-splay tree{

elem - p = rac ;elem - q=NULL ;

if(p)// On verifie que l’arbre ne soit pas vide{

do

128

{q = p ;

if(i == p.info){

return(p) ;}else{

if(i < p.info)p = p.fg ;

elsep = p.fd ;

}}while(p) ;//si on sort du while, c’est que l’element i//n’est pas present dans l’arbre.

}

return(NULL) ;}

splaytree : :elem- splaytree : :recherche(int i)//Cette fonction recherche l’element i et reorganise la structure//pour tenir compte des changements causes par l’acces i.{

elem - p = localisation(i) ;//localisation de ielem - save = p ;

//On verifie que le noeud i ne soit pas la racine du//multi-splay treeif(p){

while(p != rac){

if(p.isroot)// Dans ce cas, un changement de fils//prefere doit etre e"ectue

129

{//recherche du noeud a switcher,//qui sera stocke dans p a la fin//de la boucle whileelem - rac splay bas = p ;p=p.pere ;

while(p.profondeur !=(rac splay bas.mindepth)-1)

{p=p.pere ;

}//apres que le noeud a switcher//ait ete localise, il faut determiner//le type de switch a e"ectuerif(rac splay bas.info > p.info)

switchGD(p) ;else

switchDG(p) ;}else{

p=p.pere ;}

}splayingracine(save) ;// le noeud i est remonte

//jusqu’a la racine}else{

return(NULL) ;}

}

void splaytree : :switchGD(elem - y)// Cette methode e"ectue un switch gauche-droite sur le noeud y{

elem - z = NULL ;elem - x = NULL ;int mingauche = INT MAX, mindroite = INT MAX ;

130

splayingracine(y) ;// on ramene y a la racine du splay tree//auquel il appartient

z = determinerZ(y) ;// on localise le noeud z. Il s’agit du plus grand noeud,//qui a une information prof plus petite que celle//de y et qui est plus petit que y

if(z){

splayingto(z, y) ;// on splaye z jusqu’a ce qu’il devienne le fils//gauche de y

if(z.fd){

// on fait du fils gauche de y dans P//son fils non preferez.fd.isroot = true ;int a = INT MAX ;if(z.fg)

a = z.fg.mindepth ;z.mindepth = min(z.profondeur, a) ;

mingauche = z.mindepth ;}

}else // z n’existe pas{

// on fait du fils gauche de y dans P son fils//non prefereif(y.fg){

y.fg.isroot = true ;}

}

x = determinerX(y) ;// on localise le noeud x. Il s’agit du plus petit noeud,//qui a une information prof plus petite que celle

131

//de y et qui est plus grand que y

if(x){

splayingto(x, y) ;// on splaye x jusqu’a ce qu’il devienne le fils//droit de y

if(x.fg){

// on fait du fils droit de y dans P son//fils preferex.fg.isroot = false ;if(x.fg.mindepth < x.mindepth)

x.mindepth = x.fg.mindepth ;mindroite = x.mindepth ;

}}else // x n’existe pas{

// on fait du fils droit de y dans P son fils prefereif(y.fd){

y.fd.isroot = false ;}

}y.mindepth = min(y.profondeur, min(mingauche,mindroite)) ;

}

void splaytree : :switchDG(elem - y)// Cette methode e"ectue un switch gauche-droite sur le noeud y{

elem - z = NULL ;elem - x = NULL ;int mingauche = INT MAX, mindroite = INT MAX ;

splayingracine(y) ;// on ramene y a la racine du splay tree//auquel il appartient

z = determinerZ(y) ;

132

// on localise le noeud z. Il s’agit du plus grand noeud,//qui a une information prof plus petite que celle//de y et qui est plus petit que y

if(z){

splayingto(z, y) ;// on splaye z jusqu’a ce qu’il devienne le fils//gauche de y

if(z.fd){

// on fait du fils gauche de y dans P son//fils preferez.fd.isroot = false ;

if(z.fd.mindepth < z.mindepth)z.mindepth = z.fd.mindepth ;

mingauche = z.mindepth ;}

}else // z n’existe pas{

// on fait du fils gauche de y dans P son fils//prefereif(y.fg){

y.fg.isroot = false ;}

}

x = determinerX(y) ;// on localise le noeud x. Il s’agit du plus petit noeud,//qui a une information prof plus petite que celle//de y et qui est plus grand que y

if(x){

splayingto(x, y) ;// on splaye x jusqu’a ce qu’il devienne le fils//droit de y

133

if(x.fg){

// on fait du fils droit de y dans P son// fils non preferex.fg.isroot = true ;int a = INT MAX ;if(x.fd)

a = x.fd.mindepth ;x.mindepth = min(x.profondeur, a) ;

mindroite = x.mindepth ;}

}else // x n’existe pas{

// on fait du fils droit de y dans P son fils non//prefereif(y.fd){

y.fd.isroot = true ;}

}y.mindepth = min(y.profondeur, min(mingauche,mindroite)) ;

}

splaytree : :elem- splaytree : :determinerZ(elem - y)// Cette methode renvoie le plus grand noeud, qui a une information//prof plus petite que celle de y et qui est plus petit que y.{

elem - x = y .fg ;

if(x && x.mindepth < y.profondeur){

while(true){

if(x.profondeur < y.profondeur){

if(x.fd && x.fd.mindepth <y.profondeur)

134

x = x.fd ;else

return(x) ;

}else{

if(x.fd && x.fd.mindepth <y.profondeur)

x = x.fd ;else

x = x.fg ;}

}

}else{

return(NULL) ;}

}

splaytree : :elem- splaytree : :determinerX(elem - y)// Cette methode renvoie le plus petit noeud, qui a une information//prof plus petite que celle de y et qui est plus grand que y{

elem - x = y .fd ;

if(x && x.mindepth < y.profondeur){

while(true){

if(x.profondeur < y.profondeur){

if(x.fg && x.fg.mindepth <y.profondeur)

x = x.fg ;else

return(x) ;}else

135

{if(x.fg && x.fg.mindepth <

y.profondeur)x = x.fg ;

elsex = x.fd ;

}}

}else{

return(NULL) ;}

}

splaytree : :'splaytree(){

destructeur(rac) ;}

void splaytree : :destructeur(elem - p){

if(p){

destructeur(p.fg) ;destructeur(p.fd) ;delete p ;

}}

int main(){

return(0) ;

}

136

13.1.2 Splay trees

Les cles sont des elements de type entier. Les valeurs des n cles de l’arbrecorrespondent a l’ensemble {1, . . . , n}.

Pour l’implementation de la structure, nous utilisons deux classes :

1. elem : cette classe represente un nœud de l’arbre.

2. splaytree : cette classe represente le splay tree.

Nous detaillons ci-dessous les points principaux de l’implementation. Desexplications plus detaillees sont fournies en tant que commentaires dans lecode.

L’initialisation de la structure se fait dans le constructeur parametre de laclasse splaytree. Elle consiste a inserer de maniere successive les n elements del’arbre dans l’ordre croissant. Elle fait appel pour cela a la methode insertion.

La methode insertion consiste a inserer l’element passe en parametredans l’arbre. Cette methode n’est qu’une implementation de l’algorithmed’insertion de splay trees decrit dans le chapitre 6.

La methode recherche consiste a localiser l’element passe en parametre.Apres cela, elle invoque la methode splaying pour remonter l’element re-cherche a la racine.

La methode splaying consiste a remonter l’element passe en parametre ala racine. La remontee est e#ectuee dans la boucle principale. Le traitementde cette boucle consiste a determiner le type de rotation qu’il faut e#ectuer(soit une rotation simple, soit une rotation zig-zig, soit une rotation zig-zag)et a invoquer, ensuite, la methode adequate pour l’e#ectuer. La boucle estrecommencee jusqu’a ce que la racine soit atteinte.

L’implementation est fournie ci-dessous.

# include <iostream># include <limits.h># include <time.h># include <math.h># include <iomanip># include <stdlib.h># include <unistd.h># include <sys/types.h># include <sys/stat.h># include <fcntl.h>using namespace std ;

class splaytree

137

{private :

class elem{

friend class splaytree ;int info ;elem - fg ;elem - fd ;elem - pere ;elem(){}elem(int i, elem - g = NULL, elem - d =

NULL, elem - p = NULL) :info(i),fg(g), fd(d), pere(p) {}

} ;elem - rac ;void rotationsimple(elem -) ;void zigzag(elem - ) ;void zigzig(elem - ) ;void splaying(elem - ) ;void destructeur(elem -) ;

public :splaytree(){rac=NULL ;}splaytree(int) ;elem - recherche(int) ;void insertion(int) ;void suppression(int) ;'splaytree() ;

} ;

splaytree : :splaytree(int i)//constructeur du splay tree{

rac=new elem(1) ;

for(int j=2 ; j <= i ; j++){

insertion(j) ;}

138

}

void splaytree : :rotationsimple(elem - p)// si l’element a splayer n’a pas de grand-pere on appelle// cette fonction pour realiser la rotation{

elem - q = p.pere ;p.pere = NULL ;q.pere = p ;

if(p == q.fg){

q.fg = p.fd ;if(q.fg)

q.fg.pere = q ;p.fd = q ;

}else{

q.fd = p.fg ;if(q.fd)

q.fd.pere = q ;

p.fg = q ;}

}

void splaytree : :zigzag(elem - p)//si le noeud a splayer est le fils droit(gauche) d’un fils//gauche(droit), on appelle cette fonction pour//e"ectuer la rotation{

elem - q = p.pere ;elem - z = q.pere ;

p.pere = z.pere ;z.pere = p ;

139

q.pere = p ;

if(p == q.fd){

q.fd = p.fg ;if(q.fd)

q.fd.pere = q ;z.fg = p.fd ;if(z.fg)

z.fg.pere = z ;p.fg = q ;p.fd = z ;

}else{

q.fg = p.fd ;if(q.fg)

q.fg.pere = q ;z.fd = p.fg ;if(z.fd)

z.fd.pere = z ;p.fg = z ;p.fd = q ;

}

if(p.pere){

if(p.pere.fg == z)p.pere.fg = p ;

elsep.pere.fd = p ;

}}

void splaytree : :zigzig(elem - p)// si le noeud a splayer est le fils gauche(droit) d’un//fils gauche(droit), on appelle cette fonction pour//e"ectuer la rotation{

140

elem - q = p.pere ;elem - z = q.pere ;

p.pere = z.pere ;q.pere = p ;z.pere = q ;

if(p == q.fg){

q.fg = p.fd ;if(q.fg)

q.fg.pere = q ;z.fg = q.fd ;if(z.fg)

z.fg.pere = z ;p.fd = q ;q.fd = z ;

}else{

q.fd = p.fg ;if(q.fd)

q.fd.pere = q ;z.fd = q.fg ;if(z.fd)

z.fd.pere = z ;p.fg = q ;q.fg = z ;

}

if(p.pere){

if(p.pere.fg == z)p.pere.fg = p ;

elsep.pere.fd = p ;

}}

141

void splaytree : :splaying(elem - p)//fonction qui realise un splaying sur un noeud. Ce splaying//remontera ce noeud jusqu’a la racine de l’arbre par//une serie de rotations. Cette fonction determinera//le type de rotation a realiser sur le noeud//a chaque etape du splaying{

elem - q =p.pere ;short int test=0 ;

while(q)//si p est la racine, alors son pointeur pere q est nul{

if( !q.pere){

rotationsimple(p) ;break ;

}else{

if(p == q.fg)//si p est un fils gauche, on//incremente test de 1

++test ;else//sinon test est decremente de 1

– –test ;

if(q == q.pere.fg)//si q est un fils gauche, on//incremente test de 1

++test ;else//sinon test est decremente de 1

– –test ;

if(test)//si test est di"erent de 0, cela//signifie qu’on est remonte par deux//sens di"erents pour aller du

142

//noeud x a son grand-pere. Il faut//donc e"ectuer une rotation zig-zig{

zigzig(p) ;test=0 ;

}else//sinon on est remonte deux fois par le//meme sens pour aller du//noeud x a son grand-pere. Il faut//donc e"ectuer une rotation zig-zag

zigzag(p) ;

q = p.pere ;}

}

rac = p ;}

splaytree : :elem- splaytree : :recherche(int i)//Cette fonction recherche un element dans un splay tree. Si//l’element est present dans l’arbre, un pointeur vers le noeud//recherche est renvoye. Sinon le pointeur NULL est renvoye pour//signaler que l’element n’est pas present dans l’arbre{

elem - p = rac ;elem - q=NULL ;

if(p){

do{

q = p ;

if(i == p.info){

splaying(p) ;

143

return(p) ;}else{

if(i < p.info)p = p.fg ;

elsep = p.fd ;

}}while(p) ;//si on sort du while, c’est que l’element n’est//pas dans l’arbre. On realise donc un splaying//sur le dernier element rencontre pendant//la recherche.splaying(q) ;

}

return(NULL) ;}

void splaytree : :insertion(int i)//Cette fonction insere un element dans l’arbre, puis y applique//un splaying{

elem - p = rac ;

if(p){

elem - q = NULL ;

do{

q = p ;if( i <= p.info)

p = p.fg ;else

p = p.fd ;}

144

while(p) ;

if( i <= q.info){

q.fg = new elem(i) ;q.fg.pere = q ;splaying(q.fg) ;

}else{

q.fd = new elem(i) ;q.fd.pere = q ;splaying(q.fd) ;

}

}else

rac = new elem(i) ;

}

void splaytree : :suppression(int i)//Pour supprimer un element, on doit d’abord appeler la//fonction rechercher en passant comme parametre l’element//a supprimer. Cet element devient alors la racine//de l’arbre. Puis, on supprime cette racine et on obtient//deux sous-arbres que l’on doit fusionner. Pour ce faire,//il su#t de prendre le plus grand element dans le sous-arbre//gauche(le fils droit le plus a droite dans le sous-arbre//gauche) et de le remonter jusqu’a la racine (par la fonction//de splaying). La racine du sous-arbre gauche ne possedant plus//de fils droit, il su#t de rattacher la racine du sous-arbre//droit comme fils droit de la racine du sous-arbre gauche.{

elem - p ;if((p = recherche(i))){

splaying(p) ;// l’element a e"acer est devenu la racine//de l’arbre

145

elem- ssarbreG = p.fg ;

if (p.fg){

rac = p.fg ;p.fg.pere= 0 ;

}

elem - ssarbreD = p.fd ;

delete p ;// suppression de la racine de l’arbre

if( ssarbreD && ssarbreG){

ssarbreD.pere= 0 ;elem - q = 0 ;

for( p = rac ; p ; p= p.fd)// recherche du noeud le plus a droite// du sous-arbre gauche{

q = p ;}

if(q){

splaying(q) ;q.fd = ssarbreD ;ssarbreD.pere = q ;

}

}else{

if(ssarbreD){

rac = ssarbreD ;ssarbreD.pere= 0 ;

146

}else{

if( !ssarbreG){

rac = 0 ;

}

}

}

}}

splaytree : :'splaytree(){

destructeur(rac) ;}

void splaytree : :destructeur(elem - p){

if(p){

destructeur(p.fg) ;destructeur(p.fd) ;delete p ;

}}

int main(){

return(0) ;

}

147

13.1.3 Arbres rouges-noirs

L’implementation est fournie ci-dessous.

# include <stdio.h># include <stdlib.h># include <string.h># include <stdarg.h># include <time.h># include <math.h># include <unistd.h># include <sys/types.h># include <sys/stat.h># include <fcntl.h>

/- implementation independent declarations -//- Red-Black tree description -/typedef enum { BLACK, RED } nodeColor ;

typedef struct nodeTag {struct nodeTag -left ; /- left child -/struct nodeTag -right ; /- right child -/struct nodeTag -parent ; /- parent -/nodeColor color ; /- node color (BLACK, RED) -/int key ; /- key used for searching -/

/- user data -/} nodeType ;

#define NIL &sentinel /- all leafs are sentinels -/static nodeType sentinel = { NIL, NIL, 0, BLACK, 0} ;

/- last node found, optimizes find/delete operations -/static nodeType -lastFind ;

static nodeType -root = NIL ; /- root of Red-Black tree -/

static void rotateLeft(nodeType -x) {

/--------------------------- rotate node x to left ---------------------------/

148

nodeType -y = x.right ;

/- establish x->right link -/x.right = y.left ;if (y.left != NIL) y.left.parent = x ;

/- establish y->parent link -/if (y != NIL) y.parent = x.parent ;if (x.parent) {

if (x == x.parent.left)x.parent.left = y ;

elsex.parent.right = y ;

} else {root = y ;

}

/- link x and y -/y.left = x ;if (x != NIL) x.parent = y ;

}

static void rotateRight(nodeType -x) {

/----------------------------- rotate node x to right -----------------------------/

nodeType -y = x.left ;

/- establish x->left link -/x.left = y.right ;if (y.right != NIL) y.right.parent = x ;

/- establish y->parent link -/if (y != NIL) y.parent = x.parent ;if (x.parent) {

149

if (x == x.parent.right)x.parent.right = y ;

elsex.parent.left = y ;

} else {root = y ;

}

/- link x and y -/y.right = x ;if (x != NIL) x.parent = y ;

}

static void insertFixup(nodeType -x) {

/-------------------------------------- maintain Red-Black tree balance -- after inserting node x --------------------------------------/

/- check Red-Black properties -/while (x != root && x.parent.color == RED){

/- we have a violation -/if (x.parent == x.parent.parent.left){

nodeType -y = x.parent.parent.right ;if (y.color == RED){

/- uncle is RED -/x.parent.color = BLACK ;y.color = BLACK ;x.parent.parent.color = RED ;x = x.parent.parent ;

}

150

else{

/- uncle is BLACK -/if (x == x.parent.right){

/- make x a left child -/x = x.parent ;

rotateLeft(x) ;}

/- recolor and rotate -/x.parent.color = BLACK ;x.parent.parent.color = RED ;

rotateRight(x.parent.parent) ;}

}else{

/- mirror image of above code -/nodeType -y = x.parent.parent.left ;if (y.color == RED){

/- uncle is RED -/x.parent.color = BLACK ;y.color = BLACK ;x.parent.parent.color = RED ;x = x.parent.parent ;

}else{

/- uncle is BLACK -/if (x == x.parent.left)

151

{x = x.parent ;

rotateRight(x) ;}

x.parent.color = BLACK ;x.parent.parent.color = RED ;

rotateLeft(x.parent.parent) ;}

}

}

root.color = BLACK ;}

void insert(int key) {nodeType -current, -parent, -x ;

/------------------------------------------------ allocate node for data and insert in tree ------------------------------------------------/

/- find future parent -/current = root ;parent = 0 ;while (current != NIL){

/-if (compEQ(key, current->key))return STATUS DUPLICATE KEY ;-/

parent = current ;current = (key < current.key) ?

current.left : current.right ;}

/- setup new node -/

152

x =(nodeType-) malloc (sizeof(-x)) ;

x.parent = parent ;x.left = NIL ;x.right = NIL ;x.color = RED ;x.key = key ;

/- insert node in tree -/if(parent){

if((key < parent.key))parent.left = x ;

elseparent.right = x ;

}else{

root = x ;}

insertFixup(x) ;lastFind = NULL ;

}

static void deleteFixup(nodeType -x) {

/-------------------------------------- maintain Red-Black tree balance -- after deleting node x --------------------------------------/

while (x != root && x.color == BLACK){

if (x == x.parent.left){

nodeType -w = x.parent.right ;if (w.color == RED)

153

{w.color = BLACK ;x.parent.color = RED ;rotateLeft (x.parent) ;w = x.parent.right ;

}if (w.left.color == BLACK && w.right.color ==

BLACK){

w.color = RED ;x = x.parent ;

}else{

if (w.right.color == BLACK){

w.left.color = BLACK ;w.color = RED ;rotateRight (w) ;w = x.parent.right ;

}

w.color = x.parent.color ;x.parent.color = BLACK ;w.right.color = BLACK ;rotateLeft (x.parent) ;x = root ;

}}else{

nodeType -w = x.parent.left ;if (w.color == RED){

w.color = BLACK ;x.parent.color = RED ;rotateRight (x.parent) ;w = x.parent.left ;

}if (w.right.color == BLACK && w.left.color ==

154

BLACK){

w.color = RED ;x = x.parent ;

}else{

if (w.left.color == BLACK){

w.right.color = BLACK ;w.color = RED ;rotateLeft (w) ;w = x.parent.left ;

}

w.color = x.parent.color ;x.parent.color = BLACK ;w.left.color = BLACK ;rotateRight (x.parent) ;x = root ;

}}

}

x.color = BLACK ;}

void deleter(int key) {nodeType -x, -y, -z ;

/------------------------------ delete node z from tree ------------------------------/

z = root ;while(z != NIL){

if((key == z.key))

155

break ;else

z = (key < z.key) ? z.left : z.right ;

}

/-if (z == NIL) return STATUS KEY NOT FOUND ;-/

if (z.left == NIL || z.right == NIL){

/- y has a NIL node as a child -/y = z ;

}else{

/- find tree successor with a NIL node as a child -/y = z.right ;while (y.left != NIL){

y = y.left ;

}

}

/- x is y’s only child -/if (y.left != NIL)

x = y.left ;else

x = y.right ;

/- remove y from the parent chain -/x.parent = y.parent ;if (y.parent){

if (y == y.parent.left)y.parent.left = x ;

else

156

y.parent.right = x ;

}else

root = x ;

if (y != z){

z.key = y.key ;

}

if (y.color == BLACK)deleteFixup (x) ;

free (y) ;lastFind = NULL ;

}

int find(int key) {

/-------------------------------- find node containing data --------------------------------/

nodeType -current = root ;while(current != NIL){

if((key == current.key)){

lastFind = current ;return 1 ;

}else{

current = (key < current.key) ?current.left : current.right ;

}

157

}

return 0 ;}

void destructeur(nodeType- p){

if(p != NIL){

destructeur(p.left) ;destructeur(p.right) ;free(p) ;

}}

int main(){

return(0) ;}

13.2 Jeux de tests

Nous fournissons ci-dessous le reste des diagrammes des jeux de tests pourmontrer que les resultats obtenus sont bien consistants.

158

0

20000

40000

60000

80000

100000

120000

140000

160000

180000

200000

500 1000 1500 2000 2500 3000 3500 4000 4500 5000 5500

MST9ST9RB9

Fig. 13.1 – Couts d’un arbre de taille 29 avec une distribution aleatoire

0

50000

100000

150000

200000

250000

300000

350000

400000

450000

1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000

MST10ST10RB10

Fig. 13.2 – Couts d’un arbre de taille 210 avec une distribution aleatoire

159

0

100000

200000

300000

400000

500000

600000

700000

800000

900000

1e+06

2000 4000 6000 8000 10000 12000 14000 16000 18000 20000 22000

MST11ST11RB11

Fig. 13.3 – Couts d’un arbre de taille 211 avec une distribution aleatoire

0

500000

1e+06

1.5e+06

2e+06

2.5e+06

0 5000 10000 15000 20000 25000 30000 35000 40000 45000

MST12ST12RB12

Fig. 13.4 – Couts d’un arbre de taille 212 avec une distribution aleatoire

160

0

500000

1e+06

1.5e+06

2e+06

2.5e+06

3e+06

3.5e+06

4e+06

4.5e+06

5e+06

0 10000 20000 30000 40000 50000 60000 70000 80000 90000

MST13ST13RB13

Fig. 13.5 – Couts d’un arbre de taille 213 avec une distribution aleatoire

0

1e+06

2e+06

3e+06

4e+06

5e+06

6e+06

7e+06

8e+06

9e+06

1e+07

1.1e+07

0 20000 40000 60000 80000 100000 120000 140000 160000 180000

MST14ST14RB14

Fig. 13.6 – Couts d’un arbre de taille 214 avec une distribution aleatoire

161

0

5e+06

1e+07

1.5e+07

2e+07

2.5e+07

0 50000 100000 150000 200000 250000 300000 350000

MST15ST15RB15

Fig. 13.7 – Couts d’un arbre de taille 215 avec une distribution aleatoire

0

10000

20000

30000

40000

50000

60000

70000

80000

90000

500 1000 1500 2000 2500 3000 3500 4000 4500 5000 5500

MST9ST9RB9

Fig. 13.8 – Couts d’un arbre de taille 29 avec une distribution working set

162

0

20000

40000

60000

80000

100000

120000

140000

160000

180000

200000

1000 2000 3000 4000 5000 6000 7000 8000 9000 10000 11000

MST10ST10RB10

Fig. 13.9 – Couts d’un arbre de taille 210 avec une distribution working set

0

50000

100000

150000

200000

250000

300000

350000

400000

450000

2000 4000 6000 8000 10000 12000 14000 16000 18000 20000 22000

MST11ST11RB11

Fig. 13.10 – Couts d’un arbre de taille 211 avec une distribution working set

163

0

100000

200000

300000

400000

500000

600000

700000

800000

900000

1e+06

0 5000 10000 15000 20000 25000 30000 35000 40000 45000

MST12ST12RB12

Fig. 13.11 – Couts d’un arbre de taille 212 avec une distribution working set

0

500000

1e+06

1.5e+06

2e+06

2.5e+06

0 10000 20000 30000 40000 50000 60000 70000 80000 90000

MST13ST13RB13

Fig. 13.12 – Couts d’un arbre de taille 213 avec une distribution working set

164

0

500000

1e+06

1.5e+06

2e+06

2.5e+06

3e+06

3.5e+06

4e+06

4.5e+06

0 20000 40000 60000 80000 100000 120000 140000 160000 180000

MST14ST14RB14

Fig. 13.13 – Couts d’un arbre de taille 214 avec une distribution working set

0

1e+06

2e+06

3e+06

4e+06

5e+06

6e+06

7e+06

8e+06

9e+06

1e+07

0 50000 100000 150000 200000 250000 300000 350000

MST15ST15RB15

Fig. 13.14 – Couts d’un arbre de taille 215 avec une distribution working set

165

Bibliographie

[AVL62] George M. Adel’son-Vel’skii and Evgenii M. Landis. An algorithmfor the organisation of information. Soviet Mathematics Doklay,3 :1259–1262, 1962.

[BCK03] Avrim Blum, Shuchi Chawla, and Adam Kalai. Static optimalityand dynamic search optimality in lists and trees. Algorithmica,36(3) :249–260, 2003.

[Bit79] James R. Bitner. Heuristics that dynamically organize data struc-tures. SIAM Journal of Computing, 8 :82–110, 1979.

[BLM+03] Gerth S. Brodal, George Lagogiannis, Christos Makris, Atha-nasios Tsakalidis, and Kostas Tsichlas. Optimal finger searchtrees in the pointer machine. Journal of Computer and SystemSciences, 67(2) :381–418, 2003.

[BT80] Mark R. Brown and Robert E. Tarjan. Design and analysis of adata structure for representing sorted lists. SIAM Journal Com-puter, 9 :594–614, 1980.

[Car04] Jean Cardinal. Structures de l’information. Presses Universitairede Bruxelles, 3eme edition, 2004.

[Col00] Richard Cole. On the dynamic finger conjecture for splay trees.SIAM Journal of Computing, 30 :44–85, 2000.

[DHIP04] Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pa-trascu. Dynamic optimality-almost. In Proceedings of the 45thAnnual IEEE Symposium on Fonudations of Computer Science,pages 484–490, 2004.

[DSW05] Jonathan Derryberry, Daniel D. Sleator, and Chengwen C. Wang.A lower bound framework for binary search trees with rotations.Technical report, Carnegie Mellon University, 2005.

[DSW06] Jonathan Derryberry, Daniel D. Sleator, and Chengwen C. Wang.(log log n)-competitive dynamic binary search trees. pages 374–383, 2006.

166

[FS98] Philippe Flajolet and Robert Sedgewick. Introduction l’analysedes algorithmes. International Thomson publishing, 1998.

[Iac01] John Iacono. Alternatives to splay trees with o(log n) worst-caseaccess times. Symposium on Discrete Algorithms, pages 516–522,2001.

[Iac05] John Iacono. Key-independent optimality. Algorithmica, 42(1) :3–10, 2005.

[Knu73] Donald E. Knuth. Computing Programming, Sorting and Sear-ching, volume 3. Addison-Wesley, 2eme edition, 1973.

[Mar02] Olivier Markowitch. Universite libre de bruxelles, INFO 090 :Algorithmique general 1, 2002. http ://www.markowitch.net.

[Nie05] Tom Niemann, 2005. http ://epaperpress.com/sortsearch/txt/rbt.txt.

[Sah05] Sartaj Sahni. E%cient binary search trees, Universityof Florida, COP 5536 : Advanced Data Structures, 2005.http ://www.cise.ufl.edu/'sahni/cop5536.

[Sed04] Robert Sedgewick. Algorithmes en C++. Pearson Education,2004.

[ST85] Daniel D. Sleator and Robert E. Tarjan. Self-adjusting binarysearch trees. Journal of the ACM, 32 :652–686, 1985.

[SW04] Daniel D. Sleator and Chengwen C. Wang. Dynamic optimaltityand multi-splay trees. Technical report, Carnegie Mellon Univer-sity, 2004.

[Tar85] Robert E. Tarjan. Amortized computational complexity. SIAMJournal on Algebraic and Discrete Methods, 6 :306–318, 1985.

[Wei99] Mark A. Weiss. Data Structures and Algorithm Analysis in Java.Addison-Wesley, 1999.

[Wil89] Robert Wilber. Lower bounds for accessing binary search treeswith rotations. SIAM Journal of Computing, 18 :56–67, 1989.

167