CM4 : les arbres bicolores « rouges-noirs »

Plan :
• Présentation des arbres rouges-noirs
• Démonstration de l’équilibrage des arbres rouges-noirs
• Principe d’insertion dans un arbre rouge-noir
• Principe de suppression dans un arbre rouge-noir

Eric Gascard Polytech Grenoble ALG - 1

 Définition d’un ABR rouge-noir
• C’est un arbre binaire de recherche (ABR) auquel on associe à chaque
nœud une couleur : ROUGE ou NOIR
• Les fils de chaque feuille sont des sentinelles : nœud sans clé et sans
fils. Les sentinelles sont de couleur NOIR.
• Un arbre rouge-noir vérifie les 2 conditions suivantes
– Condition 1 : si un nœud est rouge, tous ses enfants, s’il en a, sont noirs.
– Condition 2 : il y a le même nombre de nœuds noirs sur tout chemin d’un
nœud x de l’arbre à ses descendants (x inclus) ayant 0 ou 1 enfant.
(on ne comptera pas les sentinelles)

Eric Gascard Polytech Grenoble ALG - 2

 Arbre rouge-noir ?

Eric Gascard Polytech Grenoble ALG - 3

 Hauteur noire
• La hauteur noire hn d’un nœud x (hn(x)) est le nombre unique de
nœuds noirs sur tout chemin du nœud x à un descendant de x ayant 0
ou 1 fils, le nœud x exclu (on ne prend pas en compte les sentinelles).
hn=2

hn=1
hn=1

hn=0 hn=0 hn=0

hn=0 hn=0 hn=0 hn=0 hn=0

hn=0 hn=0

Eric Gascard Polytech Grenoble ALG - 4

 Estimation de hn(x)
• On veut encadrer hn(x) en fonction de la hauteur de x, h(x).
ℎ 𝑥𝑥 −1
Notre but : montrer ≤ ℎ𝑛𝑛(𝑥𝑥) ≤ ℎ(𝑥𝑥)
2
• Proposition 1 : hn(x) ≤ ℎ(𝑥𝑥)
Si on a un arbre RN où tous les nœuds sont noirs, alors hn(x)=h(x).
 c’est le cas où on a le plus de nœuds noirs possibles.
ℎ 𝑥𝑥 −1
• Proposition 2 : ≤ ℎ𝑛𝑛(𝑥𝑥)
2
Etudions le cas où l’on a le plus de nœuds rouges possibles (donc le moins
de noirs possibles) :
x h(x)=nombre de nœuds inséré sous x
h(x) = #ROUGE + #NOIR
or #ROUGE = #NOIR +1
ℎ 𝑥𝑥 −1
donc #NOIR =
2

on étudie qu’un seul chemin car on a la

même propriété sur tous les chemins
(condition 2).

Eric Gascard Polytech Grenoble ALG - 5

 Démonstration hauteur logarithmique (1/3)
Proposition : dans un arbre rouge-noir à n nœuds et de racine r, on a : 𝑛𝑛 ≥ 2ℎ𝑛𝑛(𝑟𝑟) .
 Cela signifie que le nombre de nœuds est exponentiel en hauteur noire, c.à.d la
hauteur noire est logarithmique en nombre de nœuds total.

Preuve pas récurrence : sur la hauteur h de l’arbre RN

• Cas de base : h=0
On est dans le cas où la racine est une feuille, on a bien 1 ≥ 20 = 1
• Cas inductif
on fait l’hypothèse que 𝑛𝑛 ≥ 2ℎ𝑛𝑛(𝑟𝑟) est vérifié pour tous les arbres RN de
hauteur ≤ ℎ.
on considère un arbre RN de hauteur h+1 :
o Cas 1 : si hn(r) de l’arbre de hauteur h+1 est égale à 0 alors n ≥ 20 = 1 est bien
vérifié car l’arbre a au moins 2 nœud (la racine et un fils) comme la hauteur>0

Eric Gascard Polytech Grenoble ALG - 6

 Démonstration hauteur logarithmique (2/3)
o Cas 2 : on suppose hn(r) > 0
 Cela signifie que la racine a exactement 2 fils car sinon on aurait une
violation de la condition 2 :
• La hn(r) ne prend pas en compte r (r exclu), comme hn(r)>0 il y a donc un
nœud NOIR dans un chemin de r à un de ses descendants.
• Si r avait un seul fils, le chemin de r à son autre fils vide comporterait 0 nœud
NOIR, ce qui contredit la Condition 2.
ℎ𝑛𝑛(𝑢𝑢) r h+1 h(r)=h+1
 On a ℎ𝑛𝑛 𝑟𝑟 − 1 ≤ �
ℎ𝑛𝑛(𝑣𝑣) h(u) = h(r)-1
En effet : h h(v) = h(r)-1
Si u (resp. v) est noir hn(u)=hn(r)-1 u v
Si u (resp. v) est rouge hn(u)=hn(r)

Par application de l’hypothèse de récurrence, on a : 𝑛𝑛𝑢𝑢 ≥ 2ℎ𝑛𝑛(𝑢𝑢) , 𝑛𝑛𝑣𝑣 ≥ 2ℎ𝑛𝑛(𝑣𝑣)

𝑛𝑛 ≥ 2 × 2ℎ𝑛𝑛 𝑟𝑟 −1
+ 1 ≥ 2ℎ𝑛𝑛(𝑟𝑟) + 1 ≥ 2ℎ𝑛𝑛(𝑟𝑟) cqfd.

Eric Gascard Polytech Grenoble ALG - 7

 Démonstration hauteur logarithmique (3/3)

• Propriété : la hauteur des arbres rouges-noirs est logarithmique en son

nombre de nœuds.

• Preuve :
ℎ 𝑟𝑟 −1
On sait que 𝑛𝑛 ≥ 2ℎ𝑛𝑛(𝑟𝑟) et ℎ𝑛𝑛 𝑟𝑟 ≥
2
ℎ−1
𝑛𝑛 ≥ 2 2 où h est la hauteur de l’arbre
ℎ−1
𝑙𝑙𝑙𝑙𝑙𝑙2 (𝑛𝑛) ≥  ℎ ≤ 2 × 𝑙𝑙𝑙𝑙𝑙𝑙2 𝑛𝑛 + 1  ℎ = 𝑂𝑂(𝑙𝑙𝑙𝑙𝑙𝑙2 𝑛𝑛 ). cqfd.
2

Eric Gascard Polytech Grenoble ALG - 8

 Insertion dans un arbre rouge-noir (1/6)
Principe de l’insertion dans un arbre rouge-noir :
1) Pour insérer un élément dans un arbre rouge-noir, on exécute
l’algorithme d’insertion d’un arbre binaire de recherche et on colore
en ROUGE la nouvelle feuille s créée.
2) Si on est dans une configuration de deux nœuds ROUGE consécutifs
(non respect Condition 1), on corrige des couleurs des nœuds de
l’arbre, et éventuellement on restructure l’arbre par rotation

Règles de correction de couleurs après coloriage d’un noeud z ROUGE :

• Cas 1 : s est la racine  ne rien faire

• Cas 2 : s n’est pas la racine et son père ps est NOIR  ne rien faire

• Cas 3 : s n’est pas la racine et ps est ROUGE et ps est la racine

 ps devient NOIR (Condition 1 à respecter)
(changer la couleur de la racine ne contredit pas la Condition 2)

Eric Gascard Polytech Grenoble ALG - 9

 Insertion dans un arbre rouge-noir (2/6)
Règles de correction de couleurs après insertion :
• Cas 4 : s n’est pas la racine et ps est ROUGE et ps n’est pas la racine et os
(l’oncle de s) est ROUGE : on doit corriger car contredit la Condition 1.
forcément gps Invertion couleur ps, os, gps on réitère le
est NOIR processus sur gps

Cas 4a

 Conditions 1 maintenant vérifiée pour le sous-arbre gps.

 Condition 2 toujours vérifiée pour tout l’arbre : on a fait descendre un NOIR sur
chaque branche de l’arbre ce qui garantit toujours la condition 2 sur tous les chemins
aux descendants.
 On a remonté l’éventuel problème de 2 ROUGES consécutifs au niveau de gps.

Cas 4b Cas 4c Cas 4d

Eric Gascard Polytech Grenoble ALG - 10
 Insertion dans un arbre rouge-noir (3/6)
Règles de correction de couleurs après insertion :
• Cas 5a : s n’est pas la racine et ps est ROUGE et ps n’est pas la racine et os
(l’oncle de s) est NOIR et s est un nœud externe : on doit corriger car
contredit la Condition 1.

rotation droite sur gps

gps ps
+ invertion couleur ps et gps le processus
s’arrête
ps os Cas 5a s gps

s u os
u

Ici s n’est pas une feuille,

c’est la situation d’un
appel récursif

Eric Gascard Polytech Grenoble ALG - 11

 Insertion dans un arbre rouge-noir (4/6)
Règles de correction de couleurs après insertion :
• Cas 5b : s n’est pas la racine et ps est ROUGE et ps n’est pas la racine et os
(l’oncle de z) est NOIR et s est un nœud externe : on doit corriger car
contredit la Condition 1.

rotation gauche sur gps le processus

+ invertion couleur ps et gps s’arrête
gps ps

Cas 5b
os ps gps s

s w u
u

Eric Gascard Polytech Grenoble ALG - 12

 Insertion dans un arbre rouge-noir (5/6)
Règles de correction de couleurs après insertion :
• Cas 6a : s n’est pas la racine et ps est ROUGE et ps n’est pas la racine
et os (l’oncle de z) est NOIR et s est un nœud interne : on doit corriger
car contredit la Condition 1.

gps rotation gauche-droite s le processus
+ invertion couleur s et gps s’arrête
 ps gps
ps os Cas 6a

os
s u v

u v

Eric Gascard Polytech Grenoble ALG - 13

 Insertion dans un arbre rouge-noir (6/6)
Règles de correction de couleurs après insertion :
• Cas 6b : s n’est pas la racine et ps est ROUGE et ps n’est pas la racine
et os (l’oncle de z) est NOIR et s est un nœud interne : on doit corriger
car contredit la Condition 1.

s le processus
gps rotation droite-gauche
+ invertion couleur s et gps s’arrête
 gps ps
os ps Cas 6b

os v
s u

u v

Eric Gascard Polytech Grenoble ALG - 14

 Exercice d’insertion dans un arbre rouge-noir

• Créer un arbre rouge-noir par insertion successive des clés 18, 98, 51,
10, 62.

Eric Gascard Polytech Grenoble ALG - 15

 Suppression dans un arbre rouge-noir (1/4)
Principe de suppression dans un arbre rouge-noir :
1) On commence par la recherche du nœud z contenant la valeur à
supprimer (via l’algorithme de recherche dans un ABR)
a) Si le nœud z à supprimer est une feuille, on la supprime physiquement
b) Si le nœud z à supprimer est un nœud interne ou la racine, on remplace la
valeur dans le nœud z par la valeur qui lui est immédiatement successeur
dans le nœud s puis on applique l’algorithme de suppression dans un
arbre rouge-noir au nœud s dont on a pris la valeur (récursivité).
2) Si le nœud qu’on supprime physiquement de l’arbre était NOIR, on se
trouve alors en déficit d’un nœud NOIR (•) sur le chemin qui menait à
ce nœud, ce qui contredit la Condition 2 pour les autres chemins issus
de la racine de l’arbre :
 On remédie alors à ce déficit de NOIR par re-coloriage, et éventuellement
on restructure l’arbre par rotation.

Eric Gascard Polytech Grenoble ALG - 16

 Suppression dans un arbre rouge-noir (2/4)
Règles de suppression dans un arbre rouge-noir :
• Cas 1a : z est une feuille et également la racine  retourner l’arbre vide

• Cas 1b : z est une feuille mais pas la racine

Pour indiquer déficit de NOIR

p p p p

z z

Arrêt de la
Suppression nœud suppression Suppression nœud Arrêt de la
mais suppression
réorganisation à
effectuer

Eric Gascard Polytech Grenoble ALG - 17

 Suppression dans un arbre rouge-noir (3/4)
Règles de suppression dans un arbre rouge-noir :
• Cas 2 : z n’a qu’un seul fils

p p p p

z r z r

r r

Arrêt de la
suppression
mais Arrêt de la
Suppression nœud réorganisation à Suppression nœud suppression
effectuer

 raisonnement similaire s’il existe que le fils gauche

Eric Gascard Polytech Grenoble ALG - 18

 Suppression dans un arbre rouge-noir (4/4)
Règles de suppression dans un arbre rouge-noir :
• Cas 3 : z a deux fils
p p

z s Changement de clé

s est la valeur minimale

du sous-arbre droit de z

s s

Suppression nœud Suppression nœud

(appel récursif)

Eric Gascard Polytech Grenoble ALG - 19

 Réorganisation dans un arbre rouge-noir (1/8)
Règles de réorganisation après suppression dans un arbre rouge-noir :
• Cas 1: le nœud n est ROUGE (n racine ou nœud interne)

Changement de couleur
n n

 Pour les tous les cas suivants, le nœud n sera considéré NOIR
• Cas 2: le nœud n est la racine
null null

n n

Eric Gascard Polytech Grenoble ALG - 20

 Réorganisation dans un arbre rouge-noir (2/8)
Règles de réorganisation après suppression dans un arbre rouge-noir :
• Cas 3a : le frère w est ROUGE
Changement
de couleur
forcément rotation gauche sur p
p w
NOIR
Cas 3a
n w p v

u v n u

On s’est ramené au
cas d’un frère NOIR

Eric Gascard Polytech Grenoble ALG - 21

 Réorganisation dans un arbre rouge-noir (3/8)
Règles de réorganisation après suppression dans un arbre rouge-noir :
• Cas 3b : le frère w est ROUGE

Changement
forcément rotation droite sur p de couleur
p w
NOIR
Cas 3b
w n u p

u v v n
On s’est ramené au
cas d’un frère NOIR

Eric Gascard Polytech Grenoble ALG - 22

 Réorganisation dans un arbre rouge-noir (4/8)
Règles de réorganisation après suppression dans un arbre rouge-noir :
• Cas 4a et 4b : le frère w est NOIR et ses fils également NOIR
On a fait
p p remonter vers la
racine la
demande de
n w n w réorganisation
Cas 4a
Changement
u v u v de couleur

p p

w n w n
Cas 4b

u v u v

Eric Gascard Polytech Grenoble ALG - 23

 Réorganisation dans un arbre rouge-noir (5/8)
Règles de réorganisation après suppression dans un arbre rouge-noir :
• Cas 5a : le frère w est NOIR et ses fils ont des couleurs différentes entre
eux et son fils gauche est ROUGE
Le fils droit
p p est maintenant
rouge
rotation droite sur w
n w n c

Cas 5a
c u w
Changement
de couleur
u v v

Forcément NOIR

Eric Gascard Polytech Grenoble ALG - 24

 Réorganisation dans un arbre rouge-noir (6/8)
Règles de réorganisation après suppression dans un arbre rouge-noir :
• Cas 5b : le frère w est NOIR et ses fils ont des couleurs différentes entre
eux et son fils droit est ROUGE

p p

rotation gauche sur w

w n c n

Cas 5b Changement
c w v de couleur

Le fils gauche
est maintenant
u v u
rouge

Eric Gascard Polytech Grenoble ALG - 25

 Réorganisation dans un arbre rouge-noir (7/8)
Règles de réorganisation après suppression dans un arbre rouge-noir :
• Cas 6a : le frère w est NOIR et son fils droit est ROUGE

p w w prend la couleur de p

rotation gauche sur p Changement

de couleur
n w p c
Cas 6a

n Le processus
c u
u s’arrête

Eric Gascard Polytech Grenoble ALG - 26

 Réorganisation dans un arbre rouge-noir (8/8)
Règles de réorganisation après suppression dans un arbre rouge-noir :
• Cas 6b : le frère w est NOIR et son fils gauche est ROUGE

p w w prend la couleur de p

rotation droite sur p Changement

c de couleur
w n p
Cas 6b Le processus
n s’arrête
c u
u

Eric Gascard Polytech Grenoble ALG - 27

 Exercice de suppression dans un arbre rouge-noir

• Supprimer successivement les clés 8, 12, 19, 31, 38, 41 :

38

41
19

12 31

Eric Gascard Polytech Grenoble ALG - 28

 Utilisation des arbres rouges-noirs
• Dans les systèmes de fichiers modernes, comme dans le cas des
systèmes Unix, des arbres rouges-noirs sont utilisés pour organiser les
répertoires et les fichiers.
• Les bases de données utilisent des arbres rouges-noirs pour
implémenter des index afin de faciliter la recherche rapide
d'enregistrements.
• Des bibliothèques standards de langages de programmation utilisent
des arbres rouges-noirs pour la gestion des collections :
– Java : La classe TreeMap et TreeSet de la bibliothèque standard de Java
([Link]) sont basées sur des arbres rouges-noirs.
– C++ : La classe map de la bibliothèque STL (Standard Template Library)
utilise également des arbres rouges-noirs pour gérer les paires clé-valeur.
• Les arbres rouges-noirs peuvent être utilisés dans des systèmes de
planification de tâches ou de gestion d’événements : les arbres rouges-
noirs permettent de maintenir un accès rapide tout en insérant ou
supprimant des événements au fur et à mesure.

Eric Gascard Polytech Grenoble ALG - 29