Arbres Rouge-Noir - UQAC

Les arbres rouges et noirs et les tas 1. Introduction
Même si les arbres AVL et les B-arbres possèdent des propriétés
intéressantes, ils n'en demeurent pas moins que des désavantages
subsistent pour quelques applications. Par exemple, les arbres AVL peuvent
nécessiter plusieurs rotations après une suppression; les B-arbres quant à
eux peuvent nécessiter plusieurs opérations de regroupements ou
d'éclatement après une opération insertion ou de suppression.
La structure de données d'arbre rouge et noir, discutée dans ce chapitre,
ne possède pas ce désavantage car ne nécessitant qu'un temps de O(1) après
une mise à jour pour conserver sa propriété d'arbre équilibré.
2. Définition Un arbre rouge et noir est un arbre binaire de recherche où chaque n?ud est
de couleur rouge ou noire de telle sorte que
1. les feuilles (null) sont noires,
2. les enfants d'un n?ud rouge sont noirs,
3. le nombre de n?uds noirs le long d'une branche de la racine à une
feuille est indépendant de la branche. Autrement dit, pour tout noeud
de l'arbre, les chemins de ce n?ud vers les feuilles (n?ud 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 n?uds externes. Les n?uds
internes sont ceux qui ne sont pas externes.
[pic]
Cet arbre est un arbre rouge et noir
[pic]
Cet arbre n'est pas un arbre rouge et noir
Exercice : Montrer qu'un arbre ayant n n?uds internes possède n+1 noeuds
externes.
La première condition est simplement technique et sans grande importance.
La seconde condition stipule que les n?uds rouges ne sont pas trop
nombreux. La dernière condition est une condition d'équilibre. Elle
signifie que si 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.
Exercice: Montrer que l'on ne peut pas avoir deux n?uds rouges successifs
le long d'un chemin d'un arbre rouge et noir (ARN). En contrôlant cette information de couleur dans chaque n?ud, on garantit
qu'aucun chemin ne peut être deux fois plus long que n'importe quel autre
chemin, de sorte que l'arbre reste équilibré. Même si l'équilibrage n'est
pas parfait, on montre que toutes les opérations de recherche, d'insertion
et de suppression sont en O(logn). 3. Hauteur d'un 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 ? 2ln(n+1).
Pour un arbre rouge et noir, on appelle hauteur noire le nombre hn(x) de
n?uds 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 n?uds internes.
. Si la hauteur noire de x est 0, alors x doit être une feuille
nulle. Le sous arbre enraciné en x contient [pic] n?ud interne. . Si la hauteur noire de x est >0, alors chacun de ses fils a une
hauteur noire égale soit à hn(x) s'il est rouge, soit à hn(x)-1
s'il est noir. Donc, en appliquant l'hypothèse d'induction aux
deux sous arbres de x, le sous arbre enraciné en x contient au
moins [pic]n?uds internes.

Soit h la hauteur d'un arbre rouge-noir, la moitié au moins des n?uds vers
une feuille doivent être noirs. Autrement dit, la hauteur noire d'un arbre
rouge-noir est au moins h/2. Nous pouvons donc écrire :
[pic]
[pic]
[pic] 4. Rotations Les rotations sont des modifications locales d'un arbre binaire. Elles
consistent à échanger un n?ud avec l'un de ses fils. Dans la rotation
droite, un n?ud devient le fils droit du n?ud qui était son fils gauche.
Dans la rotation gauche, un n?ud devient le fils gauche du n?ud 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.
[pic]
L'opération de rotation est réalisable en temps O(1). La figure ci-dessous montre comment une rotation permet de rééquilibrer un
arbre. [pic] Rééquilibrage d'un arbre par une rotation. Une rotation gauche sur le n?ud
de clé 11 de l'arbre (a) conduit à un arbre (b) mieux équilibré: la hauteur
de l'arbre 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 n?ud 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 n?ud 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 n?ud et p son père qui sont tous les deux rouges. L'algorithme
distingue plusieurs cas.
Cas 0 : le n?ud père p est la racine de l'arbre
Le n?ud 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.
[pic]
Cas 1 : le frère f de p est rouge
Les n?uds 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 n?uds rouges consécutifs s'est déplacé vers la
racine.
[pic]
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
n?ud p devient noir et le n?ud pp devient rouge. L'algorithme s'arrête
alors puisque les propriétés (2) et (3) sont maintenant vérifiées.
[pic]
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
n?ud x devient noir et le n?ud pp devient rouge. L'algorithme s'arrête
alors puisque les propriétés (2) et (3) sont maintenant vérifiées.
[pic] Exemple : |[pic] |
Arbre de départ
[pic]
Ajout de 4 [pic] . Ce n'est 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 n?uds 5,7 et 8 [pic]
[pic]
Prendre x jusqu'à son grand parent. Le parent de x est toujours rouges.
Donc, l'arbre n'est pas rouget noir. Marquer l'oncle, y.
[pic]
Prendre x en haut et faire une rotation gauche.
[pic]
Pas encore rouge et noir
[pic]
Changer de couleur à 7 et 11 et faire une rotation droite
[pic]
Maintenant, l'arbre est rouge et noir Exercice : Construire, dans cet ordre, un arbre rouge et noir, à partir
des n?uds 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 n?ud comme dans un arbre
binaire de recherche. Si le n?ud qui porte la valeur à supprimer possède
zéro ou un fils, c'est ce n?ud qui est supprimé et son éventuel fils prend
sa place. Si, au contraire, ce n?ud 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 n?ud qui portait cette valeur suivante qui est
supprimé. Ce n?ud supprimé est le n?ud au bout de la branche gauche du sous-
arbre droit du n?ud qui portait la valeur à supprimer. Ce n?ud n'a pas de
fils gauche.
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. La propriété est retrouvée en rectifiant les
couleurs comme suit :
on considère que le n?ud qui remplace le n?ud 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 n?ud qui est doublement noir.
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é (3) le reste. C'est le seul cas où la hauteur
noire de l'arbre diminue.
[pic] Cas 1 : le frère f de x est noir.
Par symétrie, on suppose que x est le