Arbres Rouge-Noir - UQAC
l'étude de méthodes exactes, à base d'algorithmes de graphes et de
programmation mathématique; ... Cet enseignement est organisé en cours
magistraux et séances de TD et TP. ...... Concepts, Langages et Architecture Web
avancé. 35.
part of the document
ud de larbre, les chemins de ce nud vers les feuilles (nud sentinel) qui en dépendent ont le même nombre de noeuds noirs.
Par commodité, on remplace les pointeurs null vers des sous-arbres vides par des feuilles sans clés. On les appelle nuds externes. Les nuds internes sont ceux qui ne sont pas externes.
Cet arbre est un arbre rouge et noir
Cet arbre nest pas un arbre rouge et noir
Exercice : Montrer quun arbre ayant n nuds internes possède n+1 noeuds externes.
La première condition est simplement technique et sans grande importance. La seconde condition stipule que les nuds rouges ne sont pas trop nombreux. La dernière condition est une condition d'équilibre. Elle signifie que si on oublie les nuds 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.
Exercice: Montrer que lon ne peut pas avoir deux nuds rouges successifs le long dun chemin dun arbre rouge et noir (ARN).
En contrôlant cette information de couleur dans chaque nud, on garantit quaucun chemin ne peut être deux fois plus long que nimporte quel autre chemin, de sorte que larbre reste équilibré. Même si léquilibrage nest pas parfait, on montre que toutes les opérations de recherche, dinsertion et de suppression sont en O(logn).
3. Hauteur dun arbre rouge et noir
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 d un arbre rouge et noir ayant n éléments vérifie l'inégalité
h d" 2ln(n+1).
Pour un arbre rouge et noir, on appelle hauteur noire le nombre hn(x) de nuds internes noirs le long d'une branche de la racine x à une feuille.
On montre par récurrence sur cette hauteur noire, qu'un arbre de hauteur noire égale à hn(x) possède au moins 2hn(x)-1 nuds internes.
Si la hauteur noire de x est 0, alors x doit être une feuille nulle. Le sous arbre enraciné en x contient nud interne.
Si la hauteur noire de x est >0, alors chacun de ses fils a une hauteur noire égale soit à hn(x) sil est rouge, soit à hn(x)-1 sil est noir. Donc, en appliquant lhypothèse dinduction aux deux sous arbres de x, le sous arbre enraciné en x contient au moins nuds internes.
Soit h la hauteur dun arbre rouge-noir, la moitié au moins des nuds vers une feuille doivent être noirs. Autrement dit, la hauteur noire dun arbre rouge-noir est au moins h/2. Nous pouvons donc écrire :
4. Rotations
Les rotations sont des modifications locales d'un arbre binaire. Elles consistent à échanger un nud avec l'un de ses fils. Dans la rotation droite, un nud devient le fils droit du nud qui était son fils gauche. Dans la rotation gauche, un nud devient le fils gauche du nud qui était son fils droit. Les rotations gauche et droite sont inverses l'une de l'autre. Elle sont illustrées à la figure ci-dessous. Dans les figures, les lettres majuscules comme A, B et C désignent des sous-arbres.
INCLUDEPICTURE "http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/LicenceMathInfo/Programmation/RedBlackTree/rotations.png" \* MERGEFORMATINET
Lopération de rotation est réalisable en temps O(1).
La figure ci-dessous montre comment une rotation permet de rééquilibrer un arbre.
Rééquilibrage dun arbre par une rotation. Une rotation gauche sur le nud de clé 11 de larbre (a) conduit à un arbre (b) mieux équilibré: la hauteur de larbre est passée de 5 à 4.
5. Insertion d'une valeur
L'insertion d'une valeur dans un arbre rouge et noir commence par l'insertion usuelle d'une valeur dans un arbre binaire de recherche. Le nouveau nud devient rouge de telle sorte que la propriété (3) reste vérifiée. Par contre, la propriété (2) n'est plus nécessairement vérifiée. Si le père du nouveau nud est également rouge, la propriété (2) est violée.
Afin de rétablir la propriété (2), l'algorithme effectue des modifications dans l'arbre à l'aide de rotations. Ces modifications ont pour but de rééquilibrer l'arbre.
Soit x le nud et p son père qui sont tous les deux rouges. L'algorithme distingue plusieurs cas.
Cas 0 : le nud père p est la racine de l'arbre
Le nud père devient alors noir. La propriété (2) est maintenant vérifiée et la propriété (3) le reste. C'est le seul cas où la hauteur noire de l'arbre augmente.
INCLUDEPICTURE "http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/LicenceMathInfo/Programmation/RedBlackTree/insertion0.png" \* MERGEFORMATINET
Cas 1 : le frère f de p est rouge
Les nuds p et f deviennent noirs et leur père pp devient rouge. La propriété (3) reste vérifiée mais la propriété ne l'est pas nécessairement. Si le père de pp est aussi rouge. Par contre, l'emplacement des deux nuds rouges consécutifs s'est déplacé vers la racine.
INCLUDEPICTURE "http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/LicenceMathInfo/Programmation/RedBlackTree/insertion1.png" \* MERGEFORMATINET
Cas 2 : le frère f de p est noir
Par symétrie on suppose que p est le fils gauche de son père. L'algorithme distingue à nouveau deux cas suivant que x est le fils gauche ou le fils droit de p.
Cas 2a : x est le fils gauche de p.
L'algorithme effectue une rotation droite entre p et pp. Ensuite le nud p devient noir et le nud pp devient rouge. L'algorithme s'arrête alors puisque les propriétés (2) et (3) sont maintenant vérifiées.
INCLUDEPICTURE "http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/LicenceMathInfo/Programmation/RedBlackTree/insertion2a.png" \* MERGEFORMATINET
Cas 2b : x est le fils droit de p.
L'algorithme effectue une rotation gauche entre x et p de sorte que p devienne le fils gauche de x. On est ramené au cas précédent et l'algorithme effectue une rotation droite entre x et pp. Ensuite le nud x devient noir et le nud pp devient rouge. L'algorithme s'arrête alors puisque les propriétés (2) et (3) sont maintenant vérifiées.
INCLUDEPICTURE "http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/LicenceMathInfo/Programmation/RedBlackTree/insertion2b.png" \* MERGEFORMATINET
Exemple :
INCLUDEPICTURE "http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/fig/rb_tree1a.gif" \* MERGEFORMATINET Arbre de départ
INCLUDEPICTURE "http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/fig/rb_tree_ins1.gif" \* MERGEFORMATINET
Ajout de 4
INCLUDEPICTURE "http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/fig/rb_tree_ins2.gif" \* MERGEFORMATINET
Ce nest plus un abre rouge et noir: Il y a deux noeuds rouges successifs sur le chemin : 11 - 2 - 7 - 5 - 4
Changer de couleurs aux nuds 5,7 et 8
INCLUDEPICTURE "http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/fig/rb_tree_ins2.gif" \* MERGEFORMATINET
INCLUDEPICTURE "http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/fig/rb_tree_ins3.gif" \* MERGEFORMATINET
Prendre x jusquà son grand parent. Le parent de x est toujours rouges. Donc, larbre nest pas rouget noir. Marquer loncle, y.
INCLUDEPICTURE "http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/fig/rb_tree_ins4.gif" \* MERGEFORMATINET
Prendre x en haut et faire une rotation gauche.
INCLUDEPICTURE "http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/fig/rb_tree_ins5.gif" \* MERGEFORMATINET
Pas encore rouge et noir
INCLUDEPICTURE "http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/fig/rb_tree_ins7.gif" \* MERGEFORMATINET
Changer de couleur à 7 et 11 et faire une rotation droite
INCLUDEPICTURE "http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/fig/rb_tree_ins8.gif" \* MERGEFORMATINET
Maintenant, larbre est rouge et noir
Exercice : Construire, dans cet ordre, un arbre rouge et noir, à partir des nuds suivants A, L, G, O, R, I, T, H et M .
6. Suppression d'une valeur
Comme pour l'insertion d'une valeur, la suppression d'une valeur dans un arbre rouge et noir commence par supprimer un nud comme dans un arbre binaire de recherche. Si le nud qui porte la valeur à supprimer possède zéro ou un fils, c'est ce nud qui est supprimé et son éventuel fils prend sa place. Si, au contraire, ce nud possède deux fils, il n'est pas supprimé. La valeur qu'il porte est remplacée par la valeur suivante dans l'ordre et c'est le nud qui portait cette valeur suivante qui est supprimé. Ce nud supprimé est le nud au bout de la branche gauche du sous-arbre droit du nud qui portait la valeur à supprimer. Ce nud n'a pas de fils gauche.
Si le nud supprimé est rouge, la propriété (3) reste vérifiée. Si le nud supprimé est noir, alors sa suppression va diminuer la hauteur noire de certains chemins dans larbre. La propriété est retrouvée en rectifiant les couleurs comme suit :
on considère que le nud qui remplace le nud supprimé porte 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ée mais il y a éventuellement un nud qui est doublement noir.
Afin de supprimer ce nud doublement noir, l'algorithme effectue des modifications dans l'arbre à l'aide de rotation. Soit x le nud doublement noir.
Cas 0 : le nud x est la racine de l'arbre
Le nud x devient simplement noir. La propriété (2) est maintenant vérifiée et la propriété (3) le reste. C'est le seul cas où la hauteur noire de l'arbre diminue.
INCLUDEPICTURE "http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/LicenceMathInfo/Programmation/RedBlackTree/suppression0.png" \* MERGEFORMATINET
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 nuds g et d.
Cas 1a : les deux fils g et d de f sont noirs.
Le nud x devient noir et le nud f devient rouge. Le nud 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 nud doublement noir mais il s'est déplacé vers la racine de l'arbre. C'est ce dernier cas qui représenté à la figure ci-dessous.
INCLUDEPICTURE "http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/LicenceMathInfo/Programmation/RedBlackTree/suppression1a.png" \* MERGEFORMATINET
Cas 1b : le fils droit d de f est rouge.
L'algorithme effectue une rotation droite entre p et f. Le nud f prend la couleur du nud p. Les noeuds x, p et d deviennent noirs et l'algorithme se termine.
INCLUDEPICTURE "http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/LicenceMathInfo/Programmation/RedBlackTree/suppression1b.png" \* MERGEFORMATINET
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 nud g devient noir et le nud f devient rouge. Il n'y a pas deux nuds 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 nud f redevient noir et l'algorithme se termine.
INCLUDEPICTURE "http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/LicenceMathInfo/Programmation/RedBlackTree/suppression1c.png" \* MERGEFORMATINET
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 nud x reste doublement noir mais son frère est maintenant le nud g qui est noir. On est donc ramené au cas 1.
INCLUDEPICTURE "http://www.liafa.jussieu.fr/~carton/Enseignement/Algorithmique/LicenceMathInfo/Programmation/RedBlackTree/suppression2.png" \* MERGEFORMATINET
Exemple : supprimer les nuds A, L, G, O, R, I, T H M de larbre rouge et noir suivant :
Supprimer A
supprimer L
supprimer G
supprimer O
Supprimer R
supprimer I
supprimer T
supprimer H
supprimer M
Exercice : À partir des explications présentées ci-dessus, écrire les fonctions dinsertion et de suppression dans un arbre rouge et noir.
Les files de priorité
Donnons d'abord une vision intuitive d'une file de priorité.
On suppose que des gens se présentent au guichet d'une banque avec un numéro écrit sur un bout de papier représentant leur degré de priorité. Plus ce nombre est élevé, plus ils sont importants et doivent passer rapidement. Bien sûr, il n'y a qu'un seul guichet ouvert, et l'employé(e) de la banque doit traiter rapidement tous ses clients pour que tout le monde garde le sourire. La file des personnes en attente s'appelle une file de priorité. L'employé de banque doit donc savoir faire rapidement les 3 opérations suivantes: trouver un maximum dans la file de priorité, retirer cet élément de la file, savoir ajouter un nouvel élément à la file. Plusieurs solutions sont envisageables. La première consiste à mettre la file dans un tableau et à trier la file de priorité dans l'ordre croissant des priorités. Trouver un maximum et le retirer de la file est alors simple: il suffit de prendre l'élément de droite, et de déplacer vers la gauche la borne droite de la file. Mais l'insertion consiste à faire une passe du tri par insertion pour mettre le nouvel élément à sa place, ce qui peut prendre un temps O(n) où n est la longueur de la file.
Une autre méthode consiste à gérer la file comme une simple file et à rechercher le maximum à chaque fois. L'insertion est rapide, mais la recherche du maximum peut prendre un temps O(n), de même que la suppression.
INCLUDEPICTURE "http://metice.univ-montp3.fr/~miap/MASS/DEUG2/polycopie-1.6/main023.gif" \* MERGEFORMATINET
Figure 4.3 : Représentation en arbre d'un tas
Une méthode élégante consiste à gérer une structure d'ordre partiel grâce à un arbre. La file de n éléments est représentée par un arbre binaire contenant en chaque noeud un élément de la file (comme illustré dans la figure 4.3). L'arbre vérifie deux propriétés importantes: d'une part la valeur de chaque noeud est supérieure ou égale à celle de ses enfants, d'autre part l'arbre est quasi complet, propriété que nous allons décrire brièvement. Si l'on divise l'ensemble des noeuds en lignes suivant leur hauteur, on obtient en général dans un arbre binaire une ligne 0 composée simplement de la racine, puis une ligne 1 contenant au plus deux noeuds, et ainsi de suite (la ligne i contenant au plus 2i noeuds). Dans un arbre quasi complet les lignes, exceptée peut être la dernière, contiennent toutes un nombre maximal de noeuds (soit 2i). De plus les feuilles de la dernière ligne se trouvent toutes à gauche, ainsi tous les noeuds internes sont binaires, excepté le plus à droite de l'avant dernière ligne qui peut ne pas avoir de enfants droit. Les feuilles sont toutes sur la dernière et éventuellement l'avant dernière ligne.
Un tas. à gauche, la vue du tas sous forme darborescence, à droite le tableau qui le supporte.
On peut numéroter cet arbre en largeur d'abord, c'est à dire dans l'ordre donné par les petits numéros figurant au dessus de la figure 4.3. Dans cette numérotation on vérifie que tout noeud i a son père en position i/2, lenfant gauche du noeud i est 2i, lenfant droit 2i + 1.
Ceci permet d'implémenter cet arbre dans un tableau a (voir figure 4.4) où le numéro de chaque noeud donne l'indice de l'élément du tableau contenant sa valeur.
INCLUDEPICTURE "http://metice.univ-montp3.fr/~miap/MASS/DEUG2/polycopie-1.6/main024.gif" \* MERGEFORMATINET
Figure 4.4 : Représentation en tableau d'un tas
L'ajout d'un nouvel élément v à la file consiste à incrémenter n puis à poser a[n] = v. Ceci peut ne plus représenter un tas car la relation a[n/2] EMBED Equation.3 v n'est pas nécessairement satisfaite. Pour obtenir un tas, il faut échanger la valeur contenue au noeud n et celle contenue par son père, remonter au père et réitérer jusqu'à ce que la condition des tas soit vérifiée. Ceci se programme par une simple itération (cf. la figure 4.5).
static void ajouter (int v) {
++nTas;
int i = nTas - 1;
whi le (( i > 1) && ( a[pere (i)] < clé )) {
a[i] = a[pere (i)];
i = pere (i);
}
a[i] = v;
ou plus précisément :
while (i > 0 && a [i/2] a[j])
++j;
if (v >= a[j])
break;
a[i] = a[j]; i = j;
}
a[i] = v;
}
A nouveau, la suppression du premier élément de la file ne prend pas un temps supérieur à la hauteur de l'arbre représentant la file. Donc, pour une file de n éléments, la suppression prend O(log n) opérations. La représentation des files de priorités par des tas permet donc de faire les trois opérations demandées: ajout, retrait, chercher le plus grand en log n opérations.
Ces opérations sur les tas permettent de faire le tri HeapSort. Ce tri possède la bonne propriété d'être toujours en temps n log n.
Lalgorithme de HeapSort se divise en deux phases, la première consiste à construire un tas dans le tableau à trier, la seconde à répéter l'opération de prendre l'élément maximal, le retirer du tas en le mettant à droite du tableau. Il reste à comprendre comment on peut construire un tas à partir d'un tableau quelconque. On remarque d'abord que l'élément de gauche du tableau est à lui seul un tas. Puis on ajoute à ce tas, le deuxième élément avec la procédure Ajouter que nous venons de voir, puis le troisième, .... etc.
A la fin, on obtient bien un tas de N éléments dans le tableau à trier. Le programme est:
static void heapSort () {
int i,v;
nTas = 0;
for (i = 0; i < N; ++i)
ajouter (a[i]);
for (i = N - 1; i >= 0; --i) {
v = maximum();
supprimer();
a[i] = v;
}
}
Sources et références
T.H. Cormen et al. (1990): Algorithms, MacGraw Hill.
John Morris (1998): Notes de cours de data structures and algorithms, University of western Autralia.
L.B. Holder (1999): Notes de cours dalgorithms and data structures, University of Texas at Arlington.
O. Carton (2003): Notes de cours dalgorithmique avancée en master de Bio-Info, Université Paris 7.
PAGE
PAGE 3
