Arbres Rouge noir

Démo : INF3105 Structures de données et algorithmesGroupe : 30

Monitrice : Kerlyne FostineCourriel : fostinekerlyne@yahoo.fr

2

Arbres rouge noir - Définition Arbre binaire de recherche dans lequel

chaque nœud a un attribut supplémentaire : sa couleur, qui est soit rouge soit noire.

L’arbre a les propriétés suivantes:1. Chaque noeud est soit rouge soit noir2. La racine est noire3. Si un noeud est rouge, tous ses enfants doivent être

noirs4. À partir de n’importe quel noeud, tous les chemins de

la racine jusqu’à un pointeur NULL doivent avoir le même nombre de noeuds noirs

3

Arbres rouge noir - Exemple

30

85

80 90

60

5540

50 65

15

20

5

10

70

4

Arbres rouge noir - exemple30

85

80 90

60

5540

50 65

15

20

5

10

70

5

Arbres rouge noir – exemple

6

Arbres rouge noir – Contre exemple30

85

80 90

60

5540

50 65

15

5

10

70

83 95

2 noeuds noirs

4 noeuds noirs

7

Arbre rouge noir - Structure Chaque nœud d’un arbre rouge noir doit avoir :

Un pointeur parent Un pointeur gauche Un pointeur droit Un champ couleur Un champ element Un champ clef

Un nœud peut être : Une sentinelle nul qui sert à représenter les feuilles de l’arbre (Pas

de valeur, pas d’élément, de couleur noire, clef de valeur minimum, champs parent, gauche, droite pointent a elle-même)

Une sentinelle racine dont les champs parent et droite pointent a la sentinelle nul, sans element, de couleur noire et avec une clef de valeur maximum, et dont le champ de gauche indique le vrai nœud racine.

8

Arbre rouge noir – Insertion Un noeud inséré est toujours une feuille On peut pas le colorier en noir, puisque cela

violerait la condition 4 On colore le noeud en rouge Si le père est noir, pas de problème Si 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

9

Premier cas : Le frère du noeud parent est noir (on utilise la convention qu’un noeud NULL est noir)

P

X

G

C

Noeud inséré

A B

S

D E

P

X G

CA B S

D E

Rotation simple

10

Deuxième cas: le frère du noeud parent est noir (on utilise la convention qu’un noeud NULL est noir)

P

X

G

C

Noeud inséré

B

S

D E

X

P G

CA B S

D E

Rotation double

11

Exemple – Rotation simple30

60

5540

50 65

15

20

70

5

3

Noeud inséré

10

(NOIR)

(NOIR)

Rotation simple

85

80 90

12

Exemple : Rotation simple (suite)

30

85

80 90

60

5540

50 65

15

20

70

5

3

10

(NOIR)(NOIR)

13

Exemple – Rotation simple (Suite)

30

85

80 90

60

5540

50 65

15

20

70

5

3

10

(NOIR)(NOIR)

14

Exemple – Rotation simple (suite)

30

85

80 90

60

5540

50 65

15

20

70

5

3

10

(NOIR)(NOIR)

15

Exemple - rotation simple (suite)

30

85

80 90

60

5540

50 65

15

20

70

5

3 10

(NOIR)(NOIR)

16

Exemple – Rotation simple (suite)

30

85

80 90

60

5540

50 65

15

20

70

5

3 10

(NOIR)(NOIR)

17

Exemple - Double rotation30

85

80 90

60

5540

50 65

15

20

70

5

8

Noeud inséré

10

(NOIR)

(NOIR)

18

Exemple - Double rotation (Suite)

30

85

80 90

60

5540

50 65

15

20

70

5

8

10

(NOIR)(NOIR)

19

Exemple – Double rotation (Suite)

30

85

80 90

60

5540

50 65

15

20

70

5

8

10

(NOIR)(NOIR)

20

Algorithme d’insertion Insertion(z)Y = racineX = racine.gaucheTant que X != nul Y = X if X.clef > Z.clef X = X.gauche else X = X.droiteZ.Parent = YIf Y = racine OU Y.clef > z.clef Y.gauche = ZElse Y.droite = ZZ.Gauche = nulZ.Droite = nulz.Couleur = RougeajusterInsertion(Z)

21

Algorithme d’insertion (suite) ajusterInsertion(Z)Tant que couleur Z.parent = Rouge if Z.parent = Z.parent.parent.droite Y = Z.parent.parent.gauche if Couleur Y = Rouge Couleur Z.parent = noir Couleur Y = noir Couleur Z.parent.parent = Rouge Z = Z.parent.parent else if Z = X.parent.gauche

Z = Z.parentRotation droite z

Couleur Z.parent = Noir Couleur Z.parent.parent = Rouge Rotation fauche Z.parent.parent

else double rotation droite gaucheCouleur Racine.gauche = Noir

22

Algorithme suppression Suppression(Z)Valeur = Z.elementIf Z.gauche = nul OU Z.droite = nul Y = ZElse Y = Successeur ZIf Y.gauche = nul X = Y.droiteElse X = Y.gaucheX.parent = Y.parentIf Racine = X.parent Racine.gauche = XElse If Y = Y.parent.gauche Y.parent.gauche = X Else Y.parent.droite = X

23

Algorithme suppression (Suite)If Y != Z Y.gauche = Z.gauche Y.droite = X.droite Y.parent = X.parent Z.gauche.parent = Z.droite.parent = Y if Z = Z.parent.gauche Z.parent.gauche = Y else Z.parent.droite = Y If couleur Y = Noir Couleur Y = Couleur Z AjusterSuppression(X) else couleur Y = Couleur Z Liberer ZElse If couleur Y = Noir AjusterSuppression(X) Liberer YRetourner Valeur

24

Algorithme suppression (Suite) AjusterSuppression(Z)Tant que couleur Z = Noir ET Z != racine if Z = Z.parent.droite W = Z.parent.gauche If Couleur W = Rouge Couleur W = Noir

Couleur Z.parent = RougeRotation droite Z.parentW = Z.parent.gauche

If couleur W.droite ET W.gauche = NoirCouleur W = Rouge

Z = Z.parent Else

if Couleur W.gauche = Noir Couleur W.droite = Noir Couleur W = Rouge Rotation gauche W

W = Z.parent.gauche Couleur W = Couleur Z.parent Couleur Z.parent = Noir Couleur W.gauche = Noir Rotation droite Z.parent Z = racine

Else Rotation double droite gaucheCouleur z = noir

25

Références

Structures de données avancées avec la STL

http://www.cours.polymtl.ca/inf1101/Hiver2005/Note/Arbres