Structures de données IFT-2000 Abder Alikacem Semaine 12 (1 ière partie) Les arbres rouge et noir...

Structures de données

IFT-2000

Abder AlikacemAbder Alikacem

Semaine 12 (1ière partie)

Les arbres rouge et noir

Département d’informatique et de génie logiciel

Édition septembre 2009

6

3 8

4

v

z

Arbre rouge noir Définition Propriétés Complexité Opération d’ajout Opération de suppression

Plan

Un arbre rouge et noir est un arbre binaire de recherche comprenant une donnée supplémentaire par nœud définissant sa couleur : rouge ou noir.

Arbre rouge et noir

En contrôlant les manières dont sont colorés les nœuds on garantit que tout chemin menant de la racine à une feuille n ’est pas plus de deux fois plus long qu’un autre.

Ainsi, un arbre rouge et noir est un arbre binaire de recherche approximativement équilibré.

Dans un arbre rouge et noir :

Chaque nœud est soit rouge, soit noir (condition #1).

La racine est noire (condition #2). Si un nœud est rouge alors ses deux nœuds fils sont noirs

(condition #3). Chaque chemin reliant un nœud à une feuille descendante a le même

nombre de nœuds noirs (condition #4).

Arbre rouge et noir : Propriétés

26

17 41

30

3819

14 21

26 28

47

11 16

On utilise également la convention qui dit qu’un noeud NULL est noir.

La troisième condition stipule que les nœuds rouges ne sont pas trop nombreux. La quatrième condition est une condition d'équilibre. Elle signifie que s'il on oublie les nœuds rouges d'un arbre on obtient un arbre binaire parfaitement équilibré.

Arbre rouge et noir : Propriétés

Comme la racine est noire et il ne peut y avoir plus de deux noeuds rouges consécutifs, la longueur de tout chemin de la racine à une feuille ne peut être supérieure à 2 fois le nombre de noeuds noirs dans ce chemin. Un arbre binaire complet de hauteur h possède au plus

1 + 2 + … + 2h = 2h+1-1 nœuds internes. La hauteur minimale d'un arbre à n nœuds internes est atteinte

lorsque l'arbre est parfaitement équilibré et que feuilles sont toutes sur un ou deux niveaux: log(n+1)-1 ≤ h.

Les arbres rouge et noir sont relativement bien équilibrés:

h ≤ 2log(n+1).

Arbre rouge et noir : Implémentation

template <typename E>class Arbre{public:

//..private:

// classe Noeudclass Noeud{ public:

E data;Noeud *gauche;Noeud *droite;Nœud *parent;bool is_red;

Noeud( const E&d ) {…}

};// Les membres donnéesNoeud * racine; //racine de l'arbre

};

Arbre rouge et noir : Opérations

Par rapport aux arbres de recherche (i.e. arbres AVL), les opérations : RECHERCHER, MINIMUM, MAXIMUM, SUCCESSEUR et PREDECESSEUR sont inchangées dans un arbre rouge et noir

Par rapport aux arbres de recherche, les opérations INSERER et SUPPRIMER ne sont pas directement supportées dans un arbre rouge et noir

Dans un arbre rouge et noir :

Les opérations INSERER et SUPPRIMER modifient l ’arbre.

Ainsi, pour garantir les propriétés des arbres rouge et noir, il faut changer les couleurs de certains nœuds et changer aussi les chaînages par pointeurs. On modifie ces chaînages par rotations.

Arbre rouge et noir : Insertion

Un noeud inséré est toujours une feuilleOn peut pas le colorier en noir, puisque cela violerait la condition 4On colore le noeud en rougeSi le père est noir, pas de problèmeSi le père est rouge, on viole la condition 3. Dans ce cas, on ajuste l’arbre, par le biais de changements de couleurs et de rotations

6

3 8

6

3 8

4

Exemple. Insertion de 4: violation de la condition 3

Arbre rouge et noir : La condition 3

Cas 2: w est noir Restructuration: changer

4 de place

Soit z le fils de parent v et de frère w

4

6

7z

vw2

z

v

Cas 1: w est rouge Recoloriage: situation

d’overflow

4

6

7z

v2

w

Arbre rouge et noir : Recoloriage

4

6

7z

v2

w4

6

7z

v2

w

L’oncle de z, le frère de v, est rouge

La violation de la condition 3 peut être propagée au grand parent u

uu

Arbre rouge et noir : Restructuration

4

6

7z

vw2 4

67

z

v

w 2

L’oncle de z, le frère de v, est noir

Il y a 4 situations de configuration pour une restructuration lorsque la condition 3 est violée

2

46

6

24

6

42

2

64

2 6

4

On insère un nœud 4 que l ’on colore au départ en rouge

11

2 14

5

1 7

8

15

4

4

Couleur (x) <- rougeTant que (xracine) et (p[x] est rouge) faire si (p[x] = gauche p[p[x]]) alors

y <- droit p[p[x]]si (couleur (y) = rouge) alors //cas 1

couleur (p[x] )<- noircouleur (y) <- noir couleur (p[p[x]] )<- rouge

5

87

x<- p[p[x]] //on itère le traitement

… // traitement symétrique à droiteFin tant quecouleur (racine) <- noir

5

7

8

4

x

Arbre rouge et noir : INSERER - cas 1(père de x et oncle de x sont rouges)

Arbre rouge et noir : INSERER - cas 2(x est fils droit et oncle droit noir)

Couleur (x) <- rougeTant que (xracine) et (p[x] est rouge) faire si (p[x] = gauche p[p[x]]) alors

y <- droit p[p[x]] //oncle droit si (couleur (y) = rouge) alors // cas

1 (diapo précédente) sinon // cas 2

si (x=droit(p[x] )) alorsx

11

7 14

5

8 152

1

4On fait une rotation pour amenerla situation au cas 3

x <- p[x] // x =2Rotation gauche (x)

x

5

7

8

4

x

2

1

14

14

2

Arbre rouge et noir : INSERER - cas 2(x est fils droit et oncle droit noir)

7

Couleur (x) <- rougeTant que (xracine) et (p[x] est rouge) faire si (p[x] = gauche p[p[x]]) alors

y <- droit p[p[x]] //oncle droit si (couleur (y) = rouge) alors // cas

1 (avant dernière diapo) sinon // cas 2

si (x=droit(p[x] )) alorsx

11

7 14

5

8 152

1

4

5

7

8

4

x

2

1

On fait une rotation pour amenerla situation au cas 3 et nouveau x

Cas 2 : frère du père de x est noir et x est un fils droit

Arbre rouge et noir : INSERER - cas 3(x est un fils gauche et oncle droit

noir)

Couleur (x) <- rougeTant que ... faire ... sinon si (x=droit(p[x] )) alors

// cas 2 ...Sinon // cas 3couleur (p[x] ) <- noircouleur (p[p[x]]) <- rouge Rotation droite (p[p[x]]))fsi

x

11

7 14

5

8 152

1

4

7

11

11

7

145 8

15

2

1

4Cas 3 : frère du père de x est noiret x est un fils gauche On a bien un arbre rouge noir

Arbre rouge et noir : Top-Down

6

3 8

6

3 8

Pour éviter de devoir propager vers le haut l’algorithme de rotation, on peut utiliser une approche top-downIdée: garantir que, lorsqu’on arrive au point d’insertion, qu’il ne s’agisse pas d’un noeud rougeOn pourra donc ajouter tout simplement un noeud rouge, sans risque de violer la propriété 3En descendant dans l’arbre, lorsqu’on rencontre un nœud qui a deux fils rouges, on colore ce noeud rouge et noir ses deux fils:

Ainsi, le nombre de noeuds noirs dans un chemin demeure inchangéPar contre, on peut se retrouver avec deux noeuds rouges consécutifs, si le parent de 6 est rouge. Dans ce cas, il faudra appliquer une rotation.

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

10

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

10

85

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

10

85

15

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

8510

Rotation double

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

8510

Ajustement durant le parcours

Attention: la racine ne changepas de couleur

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

8510

70

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

8510

70

20

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

7010

20 85

Rotation simple

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

7010

20 85

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

7010

20 85

Ajustement durant le parcours

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

7010

20 85

60

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

7010

20 85

60

30

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

7010

30 85

6020

Rotation double

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

7010

30 85

6020

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

7010

30 85

6020

Ajustement durant le parcours

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15

7010

30 85

6020

50

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

1570

10

30

856020

50

Rotation double

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

1570

10

30

856020

50

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

1570

10

30

856020

50

Ajustement durant le parcours

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

1570

10

30

856020

50 65

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15 70

10

30

856020

50 65 80

Remarque: ces noeuds n’ont pas étémodifiés parce qu’il ne sont pas dans lechemin parcouru

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15 70

10

30

856020

50 65 80 90

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15 70

10

30

856020

50 65 80 90

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15 70

10

30

856020

50 65 80 90

Ajustement durant le parcours

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15 70

10

30

856020

50 65 80 90

40

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15 70

10

30

856020

50 65 80 90

40

5

Arbres Rouge-Noir – Exemple détaillé

10 85 15 70 20 60 30 50 65 80 90 40 5 55

15 70

10

30

856020

50 65 80 90

40

5

55

Arbres Rouge-Noir – Suppression

La suppression commence par une recherche classique du nœud à supprimer, puis on enchaîne sur la réalisation de la suppression.

La suppression du nœud consiste par remplacer par le plus petit élément de son sous-arbre droit, s’il a deux fils, et en le supprimant effectivement, s’il n’a qu’un seul fils (comme pour les arbres AVL). Par la suite, il faut vérifier la propriété des arbres rouge et noir.

• Si le nœud supprimé est rouge, la propriété (4) reste vérifiée. Si le nœud supprimé est noir, alors sa suppression va diminuer la hauteur noire de certains chemins dans l’arbre.

• Le nœud qui remplacera le nœud supprimé doit porter une couleur noire en plus: il devient noir s'il est rouge et qu'il devient doublement noir s'il est déjà noir. La propriété (4) reste ainsi vérifié mais il y a éventuellement un nœud qui est doublement noir.

Arbres Rouge-Noir – Suppression

Afin de supprimer ce nœud doublement noir, l'algorithme effectue des modifications dans l'arbre à l'aide de rotation.

Soit x le nœud doublement noir.

Cas 0 : le nœud x est la racine de l'arbre Le nœud x devient simplement noir. La propriété (2) est maintenant vérifiée et la propriété (4) le reste. C'est le seul cas où la hauteur noire de l'arbre diminue (l’inverse, lorsqu’on change en noir la couleur de la racine, c’est le seul cas ou la hauteur noire augmente).

Arbres Rouge-Noir – Suppression

Cas 1 : le frère f de x est noir. Par symétrie, on suppose que x est le fils gauche de son père p et que f est donc le fils droit de p. Soient g et d les fils gauche et droit de f. L'algorithme distingue à nouveau trois cas suivant les couleurs des nœuds g et d.

Cas 1a : les deux fils g et d de f sont noirs. Le nœud x devient noir et le nœud f devient rouge. Le nœud p porte une couleur noire en plus. Il devient noir s'il est rouge et il devient doublement noir s'il est déjà noir. Dans ce dernier cas, il reste encore un nœud doublement noir mais il s'est déplacé vers la racine de l'arbre. C'est ce dernier cas qui représenté à la figure suivante.

d

Arbres Rouge-Noir – Suppression

Cas 1b : le fils droit d de f est rouge. L'algorithme effectue une rotation droite entre p et f. Le nœud f prend la couleur du nœud p. Les noeuds x, p et d deviennent noirs et l'algorithme se termine.

Arbres Rouge-Noir – Suppression

Cas 1c : le fils droit d est noir et le fils gauche g est rouge. L'algorithme effectue une rotation gauche entre f et g. Le nœud g devient noir et le nœud f devient rouge. Il n'y a pas deux nœuds rouges consécutifs puisque la racine du sous-arbre D est noire. On est ramené au cas précédent puisque maintenant, le frère de x est g qui est noir et les deux fils de g sont noir et rouge. L'algorithme effectue alors une rotation entre p et g. Le nœud f redevient noir et l'algorithme se termine.

Arbres Rouge-Noir – Suppression

Cas 2 : le frère f de x est rouge. Par symétrie, on suppose que x est le fils gauche de son père p et que f est donc le fils droit de p. Puisque f est rouge, le père p de f ainsi que ses deux fils g et d sont noirs. L'algorithme effectue alors une rotation gauche entre p et f. Ensuite p devient rouge et f devient noir. Le nœud x reste doublement noir mais son frère est maintenant le nœud g qui est noir. On est donc ramené au cas 1.

Structures de donnéesIFT-2000

Abder AlikacemAbder Alikacem

Semaine 12 (2ième partie)

Les B-arbres

Département d’informatique et de génie logiciel

Édition septembre 2009

! +

Plan

Les arbres BDéfinitionNotions de structures de données externesOpérations d’ajout Opérations d’enlèvement

Arbre-B d’ordre m

définition : la racine a au moins 2 enfants à moins que ce ne soit une feuilleaucun nœud n’a plus de m enfants tous les nœuds, sauf la racine et les feuilles, ont au moins m/2

enfants toutes les feuilles apparaissent au même niveau tout nœud qui a k enfants a k-1 éléments

3  6   8  10 12p0 p1 p2 p3 p4

e1 e2 e3 e4

8 15   

 3  6     9 12    16  20   

Arbres-B : recherche

p0 si x < e1

pi si ei < x < ei+1

pm-1 si em-1 < x

3  6  8 10  p0 p1 p2 p3 p4

e1 e2 e3 e4

Arbre-B d’ordre m

Outils pour la gestion d’un fichier binaireNœud typique & en-tête du fichier index (B-arbre)La mécanique de la construction d’un B-ArbreLa procédure de la subdivision d’un nœud

3  6   8  10 p0 p1 p2 p3 p4

e1 e2 e3 e4

struct BTPAGE{

short keycount; /* Le compteur de clefs. Indique quand le noeud est plein.

*/

struct uneCle key [MAXKEYS]; /* Le tableau des clef. */

short CHILD[MAXKEYS+1]; /* Le tableau qui contiendra les fils pointés */

};

Structure typique d’un arbre-B

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

Ajout dans un arbre-B d’ordre 5

20

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

Ajout dans un arbre-B d’ordre 5

20 40

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

Ajout dans un arbre-B d’ordre 5

10 20 40

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 15 20 30 40

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 15 20 30 40

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20   

10  15 30  40   

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20   

10  15 30  35 40   

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20   

7 10  15 30  35 40   

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20   

7 10  15 26 30  35 40   

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20   

7 10  15 18 26 30  35 40   

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20   

7 10 15 18 22 26 30  35 40   

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20   

7 10 15 18 22 26 30  35 40   

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20 30   

7 10 15 18 35 40   22 26  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

20 30   

5 7 10  15 18 35 40   22 26  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

     20 30   

35 40    5 7 10  15 18 22 26  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30   

35 40    5 7 22 26  15 18  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30   

35 40 42    5 7 22 26  15 18  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30   

35 40 42    5 7 22 26  13 15 18  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30   

35 40 42 46    5 7 22 26  13 15 18  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30   

35 40 42 46    5 7 22 26 27  13 15 18  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30   

35 40 42 46    5 7 8 22 26 27  13 15 18  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30   

32 35 40 42 46    5 7 8 22 26 27  13 15 18  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30   

32 35 40 42 46    5 7 8 22 26 27  13 15 18  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40   

32 35 42 46    5 7 8 22 26 27  13 15 18  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40   

32 35 38 42 46    5 7 8 22 26 27  13 15 18  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40   

32 35 38 42 46    5 7 8 22 24 26 27  13 15 18  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40   

32 35 38 42 45 46    5 7 8 22 24 26 27  13 15 18  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40   

5 7 8 22 24 25 26 27  32 35 3813 15 18   42 45 46   

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40   

5 7 8 22 24 25 26 27   32 35 3813 15 18   42 45 46   

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 30 40   

5 7 8 22 24 25 26 27   32 35 3813 15 18   42 45 46   

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 25 30 40   

5 7 8 22 24   32 35 3813 15 18   42 45 46   

26 27  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 25 30 40   

5 7 8 22 24   32 35 3813 15 18   42 45 46   

26 27  

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20 25   

5 7 8 22 24   32 35 3813 15 18   42 45 46   

26 27  

30 40   

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20   

5 7 8 22 24   32 35 3813 15 18   42 45 46   

26 27  

25

30 40   

Ajout dans un arbre-B d’ordre 5

+: 20,40,10,30,15,35,7,26,18,22,5,42,13,46,27,8,32,38,24,45,25

10 20   

5 7 8 22 24   32 35 3813 15 18   42 45 46   

26 27  

25

30 40   

Ajout dans un arbre-B d’ordre 5

Arbres-B

Implantation

• Un B-arbre est une structure de données externe.• On parle de fichier index• Il s’agit d’un fichier binaire (ou structuré)

Les fichiers binaires

Principe

- un fichier est une séquence d'octets non interprétés

Interprétation des données binaires

- à la charge du programmeur - une séquence de n octets peut s'interpréter comme: un entier, un tableau, un enregistrement, ... Les outils

• Déclaration d’un pointeur de fichier• Ouverture et fermeture• Les différents modes d’ouverture• Lecture et écriture• Principe du numéro d’ordre relatif (rrn)• Accès direct..

Les fichiers binaires

#include <fstream>#include <iostream>

//3 classes:ifstream: pour lire dans des fichiersofstream: pour écrire dans des fichiersfstream: pour lire et écrire dans des fichiers

fstream f;f.open("toto.txt", ios::binary|ios::in|ios::out);

mode d'ouverture: ios::in // ouverture en lectureios::out // ouverture en écritureios::app // ajout en fin de fichierios::ate // se position à la finios:: binary // mode binaireios::trunc // tronque le fichier à 0

fstream

Accès direct avec fseekg()

f.seekg (rrn*sizeof(Personne), ios_base::beg)

déplacement par rapport à origine

ios_base::begdébut de f

ios_base::curposition courante

Ios_base::endfin de f

struct Personne {

int age; char nom[40];

};

Personne p; fstream f;…

• Ecriture dans le fichier f.open(nomFich, ios::binary|ios::in|ios::out)

f.write (reinterpret_cast<char*>&p, sizeof(Personne));• Lecture du fichier

f.read (reinterpret_cast<char*>&p, sizeof(Personne));

• f.tellg(); //retourne Position courante du pointeur dans le fichier, en nombre d'octets

• Accès direct pour lire ou écrire:

Arbre-B d’ordre m

Exemple et algorithme d’insertion détaillé (B-arbre d’ordre 3)

I, K, A, Z, M, B, W, L, C, J, O

3  6  8 10 p0 p1 p2 p3 p4

e1 e2 e3 e4

struct BTPAGE{

short keycount; /* Le compteur de clefs. Indique quand le noeud est plein.

*/

struct uneCle key [MAXKEYS]; /* Le tableau des clef. */

short CHILD[MAXKEYS+1]; /* Le tableau qui contiendra les fils pointés */

};

Structure typique d’un arbre-B

/* --------------------------------------------------------*//*

**** Driver.cpp ****

Le "pilote" pour la création et la manipulation d’arbres-B.Crée ou ouvre un fichier arbre-B.

Obtient la clef suivante et appelle la fonction insert pour l'insérer dans l'arbre. Au besoin, driver peut créer une nouvelle racine pour l'arbre.*/

Ajout dans un B-arbre

File StructuresMichael J. Folk and all.

Ajout dans un B-arbre

template <typename T>void BTree:: driver(){ ……

/* ouverture du fichier index*/if btOpen() root = getRoot();else { btfd.open("btree.dat", ios::binary|ios::out|

ios::in);key = getClef(); /*première clé*/root = createRoot(key, NIL, NIL);

}

key = getClef(); /*une clé à insérer*/do{ promoted = insert(root, key, &promoRrn, &promoKey); if (promoted) root = bt.createRoot(promoKey, root,

promoRrn);key = getClef();

} while( /*il y a une clé*/ );

}

/* **** insert.cpp ****

Contient la méthode insert() qui insère une clef dans un arbre-B. S'appelle de manière récursive tant que le bas de l'arbre n'est pas atteint. Alors, insert() insère une clef dans une feuille de l ’arbre. Si le noeud est plein,

- appelle split() pour scinder le noeud- promouvoit la clef du milieu et le rrn du nouveau nœudet essaie d’insérer la clé promue lors de ses remontées

d’appel*//*

insert()Arguments:rrn: Le rrn de la page dans laquelle on fait l'insertion*promoRchild: Le fils promu vers le prochain niveaukey: La clef à être insérée*promoKey: La clef promue vers le prochain niveau

*/

bool BTree:: insert (short rrn, T key, short *promoRchild, clef *promoKey){ ….

if (rrn == NIL) { *promoKey = key;

*promoRchild = NIL; return (true);

}btread(rrn, &page);found = searchNode(key, page, &pos);if (found) {

printf("Erreur: clé dupliquée);return (false);

}promoted = insert(page.child[pos], key, &pBrrn, &pBkey);if (!promoted) return (false); if (page.keycount < MAXKEYS)

{insInPage( pBkey, pBrrn, &page); btWrite(rrn, page); return (false);

}else { split( pBkey, pBrrn, &page, promoKey, promoRchild,

&newPage);btwrite(rrn, page);btwrite(*promoRchild, newPage); return (true);

}}

8 15   

3  6    9 12    16 20   

Arbres-B : recherche

p0 si x < e1

pi si ei < x < ei+1

pm-1 si em-1 < x

3  6  8 10  p0 p1 p2 p3 p4

e1 e2 e3 e4

/* RRN_FichPrin est le numéro du bloc dans le fichier de données (FichPrin) où se trouve toutes les données de l'enregistrement trouvé. Chaque clé est accompagnée par l'adresse où se trouve la donnée correspondante dans un autre fichier que le fichier index B-Arbre.*/

template <typename T>bool BTree::searchBTree(int rrn, T key, int *trouvRRN, short *trouvPos) { short pos; Bool found; BTPAGE page;

if (rrn == NIL) { return false; } else { btread(rrn,&page); /*lecture d'un noeud (une page) dans le fichier B-Arbre*/ found = searchNode(key, page, &pos); /*recherche dans la page lue */ if (found) { *trouvRRN = page.key[pos].RRN_FichPrin; return true; } else { return(search(page.child[pos],key,trouvRRN,trouvPos)); }

} }

3 6  8  10  

Enlèvement dans un arbre-B

-: 25,24,22,20

10 20   

5 7 8 22 24   32 35 3813 15 18   42 45 46   

26 27  

25

30 40   

-: 25,24,22,20

10 20   

5 7 8 22 24   32 35 3813 15 18   42 45 46   

26 27  

25

30 40   

x

Enlèvement dans un arbre-B

-: 25,24,22,20

10 20   

5 7 8 22 24   32 35 3813 15 18   42 45 46   

26 27  

25

30 40   

x

Enlèvement dans un arbre-B

-: 25,24,22,20

10 20   

5 7 8 22   32 35 3813 15 18   42 45 46   

26 27  

24

30 40   

Enlèvement dans un arbre-B

-: 25,24,22,20

10 20   

5 7 8 22   32 35 3813 15 18   42 45 46   

26 27  

24

30 40   

Enlèvement dans un arbre-B

Enlèvement dans un arbre-B

-: 25,24,22,20

10 20   

5 7 8 22   32 35 3813 15 18   42 45 46   

26 27  

24

30 40   

x

Enlèvement dans un arbre-B

-: 25,24,22,20

10 20   

5 7 8 22   32 35 3813 15 18   42 45 46   

26 27  

24

30 40   

x

-: 25,24,22,20

10 20   

5 7 8 32 35 3813 15 18   42 45 46   

26 27  

22

30 40   

Enlèvement dans un arbre-B

-: 25,24,22,20

10 20   

5 7 8 32 35 3813 15 18   42 45 46   

26 27  

22

30 40   

Enlèvement dans un arbre-B

Enlèvement dans un arbre-B

-: 25,24,22,20

10 18   

5 7 8 32 35 3813 15   42 45 46   

26 27  

22

30 40   

20

Enlèvement dans un arbre-B

-: 25,24,22,20

10 18   

5 7 8 32 35 3813 15   42 45 46   

26 27  

22

30 40   

20

x

-: 25,24,22,20

10 18   

5 7 8 32 35 3813 15   42 45 46   

26 27  

22

30 40   

20

x

Enlèvement dans un arbre-B

Enlèvement dans un arbre-B

-: 25,24,22,20

10 18   

5 7 8 32 35 3813 15   42 45 46   

26 27  

20

30 40   

-: 25,24,22,20

10 18   

5 7 8 32 35 3813 15   42 45 46   

26 27  

20

30 40   

Enlèvement dans un arbre-B

18

-: 25,24,22,20

10 15   

5 7 8 32 35 3813   42 45 46   

26 27  

20

30 40   

Enlèvement dans un arbre-B

18

-: 25,24,22,20

10 15   

5 7 8 32 35 3813   42 45 46   

26 27  

20

30 40   

x

Enlèvement dans un arbre-B

18

-: 25,24,22,20

10 15   

5 7 8 32 35 3813   42 45 46   

26 27  

20

30 40   

x

Enlèvement dans un arbre-B

-: 25,24,22,20

10 15   

5 7 8 32 35 3813   42 45 46   

26 27  

18

30 40   

Enlèvement dans un arbre-B

Enlèvement dans un arbre-B

-: 25,24,22,20

10 15   

5 7 8 32 35 3813   42 45 46   

26 27  

18

30 40   

Enlèvement dans un arbre-B

-: 25,24,22,20

10   

5 7 8 32 35 3813 15   42 45 46   

26 27  

18

30 40   

-: 25,24,22,20

10   

5 7 8 32 35 3813 15   42 45 46   

26 27  

18

30 40   

Enlèvement dans un arbre-B

-: 25,24,22,20

10   

5 7 8 32 35 3813 15   42 45 46   

26 27  

18

30 40   

Enlèvement dans un arbre-B

-: 25,24,22,20

10 18   

5 7 8 32 35 3813 15   42 45 46   

26 27  

30 40   

Enlèvement dans un arbre-B

-: 25,24,22,20

10 18   

5 7 8 32 35 3813 15   42 45 46   

26 27  

30 40   +

Enlèvement dans un arbre-B

-: 25,24,22,20

10 18 30 40   

5 7 8 32 35 3813 15   42 45 46   

26 27  

Enlèvement dans un arbre-B

Les arbres-B+

Définitions:• c ’est un B-arbre• + duplications des clés• + chaînage de toutes les feuilles

Insérer 65

65

Exemple

Construction d’un arbre-B+

Insérer 25

25 65

Insérer 50

25 50 65

Insérer 30

25 30 50 65

Insérer 85

85

85

25 30 50 65

25 30 50 65

50

25 30 50 65 85

Insérer 75

50

25 30 50 65 75 85

Insérer 80 50

25 30 50 65 7585

80

50

25 30 50 65 75 80 85

50

25 30 50 65 75 80 85

50 75

25 30 50 65 75 80 85