Embed Size (px)
Citation preview
Structures de données
IFT-2000
Abder AlikacemAbder Alikacem
Semaine 12
Les arbres rouges et noir
Département d’informatique et de génie logiciel
Édition septembre 2009
6
3 8
4
v
z
Arbre rouge noirArbre 2-3
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é.
Dans un arbre rouge et noir, on peut toujours supposer que la racine est noire. Si elle est rouge, on change sa couleur en noire et toutes les propriétés restent vérifiées.
Arbre rouge et noir : Propriétés
26
17 41
30
3819
14 21
26 28
47
11 16
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. Autrement dit, un arbre ayant n nœuds internes est de hauteur au moins égale à ln(n+1)-1. 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 rouges et noirs sont relativement bien équilibrés. La hauteur d'un arbre rouge et noir est de l'ordre de grandeur de log(n) où n est le nombre d'éléments dans l'arbre. En effet, la hauteur h un arbre rouge et noir ayant n éléments vérifie l'inégalité
h ≤ 2log(n+1).
Arbre rouge et noir : La hauteur
Pour un arbre rouge et noir, on appelle hauteur noire le nombre k de nœuds internes noirs le long d'une branche de la racine à une feuille.
On montre par récurrence sur cette hauteur noire, qu'un arbre de hauteur noire égale à k possède au moins 2k-1 nœuds internes.
Si cette hauteur noire vaut 0, l'arbre est réduit à une seule feuille et il ne possède aucun nœud interne. Si un arbre est de hauteur noire égale à k > 0, alors ses sous-arbres gauche et droit sont au moins de hauteur noire k-1. Par hypothèse de récurrence, ils ont chacun au moins 2k-1-1 nœuds internes et l'arbre a au moins (2k-1-1)+(2k-1-1)+1 = 2k-1 nœuds internes au total. Ceci montre que la hauteur noire k d'un arbre vérifie k ≤ ln(n+1). Puisque la racine peut être supposée noire et qu'une branche ne contient pas deux nœuds rouges consécutifs, la hauteur h de l'arbre vérifie h ≤ 2k. Elle vérifie donc finalement h ≤ 2log(n+1).
Arbre rouge et noir : La hauteur
On montre ainsi que dans un arbre rouge et noir comportant n nœuds, les opérations rechercher, minimum, maximum ont une complexité de l’ordre de log2(n).
Arbre rouge et noir : Complexité
En contrôlant ainsi les manières dont les nœuds sont colorés on garantit que tout chemin menant de la racine à une feuille n’est pas plus de deux fois plus long qu’un autre.
De plus, et on vient de le voir, un arbre rouge et noir comportant n nœuds a donc une hauteur au plus égale à : 2 log2(n+1).
h <= 2 log2(n+1).
Arbre rouge et noir : Exemple
30
85
80 90
60
5540
50 65
15
20
5
10
70
Arbre rouge et noir : Exemple
30
85
80 90
60
5540
50 65
15
20
5
10
70
Arbre rouge et noir : Exemple
30
85
80 90
60
5540
50 65
15
5
10
70
83 95
2 noeuds noirs
4 noeuds noirs
Arbre rouge et noir : Implémentation
template <typename E>class Arbre{public:
//..private:
// classe Noeudclass Noeud{ public:
E data;Noeud *gauche;Noeud *droite;Noeud *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, 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.
Aussi, 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 : Insérer/Sup
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 : Top-Down
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é 3
Arbre rouge et noir : Top-Down
En descendant dans l’arbre, lorsqu’on rencontre un noeud 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 X est rouge. Dans ce cas, il faudra appliquer une rotationCeci fonctionnera parce qu’on est sur que le noeud frère du parent de X ne peut être que noir.Attention: la racine doit toujours demeurer noire
6
3 8
6
3 8
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 : Restructuration
4
6
7z
vw2 4
6
7
z
v
w2
L’oncle de z, le frère de v, est noir
Arbre rouge et noir : Restructuration
Il y a 4 situations de configuration pour une restructuration lorsque la condition 3 est violée
2
4
6
6
2
4
6
4
2
2
6
4
2 6
4
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
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 (x<>racine) 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 (x<>racine) 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 (x<>racine) 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
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 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/garantir la propriété des arbres rougeet noir.
Arbres Rouge-Noir – Suppression
Si le nœud supprimé est rouge, la propriété (3) 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. Ceci signifie qu'il devient noir s'il est rouge et qu'il devient doublement noir s'il est déjà noir. La propriété (3) reste ainsi vérifié mais il y a éventuellement un nœud qui est doublement noir.
Exemple. Suppression de 8 cause la violation de la règle 3.
6
3 8
4
6
3
4
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.
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.
Arbres AA
Implémentation plus simple que les autres
Une condition supplémentaire: le fils de gauche ne peut pas être rouge Soit le niveau d’un noeud défini ainsi:
- 1 si c’est une feuille- niveau du parent si le noeud est
rouge- (1 – niveau du parent) si le noeud est
noir
On construit un arbre équivalent avec cette définition de niveau et on obtient un algorithme plus simple à implémenter.
ARBRE 2-3
Quand un ABR est déséquilibré : s’il se réduit par exemple à une liste linéaire chaînée alors les opérations ont une complexité de l ’ordre de (N).
Pour garantir de bonnes performances une deuxième variante des ABR est les arbres 2-3
ARBRE 2-3 : propriétés
Dans un arbre 2-3 : Chaque nœud interne a exactement 2 ou 3 fils Tout chemin de la racine à une feuille a une longueur
fixe
Un arbre binaire de recherche ordonne totalement les informations qu’il stocke(par clé) :A gauche d ’un nœud : valeurs de clés inférieures ou égales à la clé du nœud.A droite : valeurs de clés supérieures strictement.
ARBRE 2-3 : propriétés
Représentation d ’une suite ordonnée dans un arbre 2-3 :
Les nœuds internes ont pour valeur les clés Les feuilles ont pour valeur les éléments de la suite ordonnée
ARBRE 2-3 : exemple
Relation d ’ordre R :a R b <=> clé(a) R clé(b)
52 7
7 16
5 - 8 12
128
19 -
1916
Représentation d ’une suite ordonnée dans un arbre 2-3 : Un nœud interne a pour valeur
la clé de l ’élément minimal du deuxième filsla clé de l ’élément minimal du troisième fils
Feuille ont pour valeur les éléments de la suite
ARBRE 2-3 : insertion - cas 1
Cas 1 : insérer x=18Cas où le nœud père de x n ’a que deux feuilles.
52 7
7 16
5 - 8 12
128
19 -
1916
52 7
7 16
5 - 8 12
128
18 19
1816 19
ARBRE 2-3 : insertion - cas 2
Cas 2 : insérer x=10La feuille x est un 4ème fils
52 7
7 16
5 - 8 12
128
18 19
16 18 19
Lorsqu’on insère un 4ème fils dans un nœud N , alors on scinde N en deux.
7
8 -
852
7 16
5 - 18 19
16 18 1910
12 -
12
x=10
ARBRE 2-3 : insertion - cas 2
Lorsqu’on insère un 4ème fils dans un nœud N alors
On scinde N en deux,
Les deux éléments les plus petits restent avec N Les deux plus grands ont pour père un nouveau nœud N1 N1 est inséré parmi les pères de N (on itère l ’insertion)
52 7
7 16
5 - 8 -
8
18 19
16 18 1910
12 -
12
N N1
ARBRE 2-3 : insertion - cas 2
52 7
7 16
5 - 8 -
8
18 19
16 18 1910
12 -
12
52 7
10 -
5 - 8 -
8
18 19
16 18 1910
12 -
12
7 - 16 - (12 -) est un 4ème filsde (7 16).
On scinde(7 16) en deux nœuds
Nouvelle racine 10
ARBRE 2-3 : complexité
Un arbre 2-3 de profondeur k a un nombre de feuilles compris entre 2 k-1 et 3 k-1
La profondeur d ’un arbre 2-3 comprenant N éléments est comprise entre 1+Log 3 (N) et 1+Log 2 (N)
Par rapport aux arbres de recherche, les opérations : RECHERCHER, MINIMUM, MAXIMUM,SUCCESSEUR et PREDECESSEUR sont triviales dans un arbre 2-3
Par rapport aux arbres de recherche, les opérations : INSERER et SUPPRIMER ne sont pas directement supportées dans un arbre 2-3
