Institut Galilée
Année 2010-2011
Algorithmique et arbres
L2
TD 7
Les arbres rouge noir
Rappel : lorsque nous avons adopté la représention des arbres binaires qui place comme
feuilles des nœuds qui ne contiennent pas d’éléments (les valeurs NULL sont les feuilles les autres
nœuds, contiennent les éléments et ont toujours leurs deux fils), nous avons adapté la notion de
hauteur en excluant ces nouvelles feuilles du décompte (la hauteur d’un arbre est la même qu’on
représente ou non les feuilles NULL).
40
41
20
60
31
61
N
30
N
N
11
N
N
N
N
N
(a)
N
N
(b)
32
33
22
62
23
Publicité
N
12
10
N
N
13
N
N
N
N
N
(c)
N
N
(d)
ROUGE
NOIR
Figure 1: Rouge noir ?
Exercice 1.
Pour chaque arbre de la figure 1, dire s’il s’agit d’un arbre rouge noir. Si non, pourquoi ?
Exercice 2.
Est-il possible de colorier tous les nœuds de l’arbre binaire de recherche de la figure 2 pour en
faire un arbre rouge noir ?
2 1 pt
6 min
3 1 pt
9 min
30
15
40
10
25
N
50
N
N
Publicité
20
N
N
N
N
N
Exercice 3.
Notre but est de montrer que la hauteur d’un arbre rouge noire est logarithmique en son nombre
de nœuds.
1
Rappel. Soit x un nœud d’un arbre rouge noir. On appelle hauteur noire de x, notée Hn(x), le
nombre de nœuds noirs présents dans un chemin descendant de x (sans l’inclure) vers une feuille
de l’arbre.
30
20
40
10
25
35
50
3
15
21
28
32
37
N
N
N
N
N
N
N
N
N
N
Publicité
N
N
N
N
Figure 2: Un exemple d’arbre rouge noir
1. Dans l’arbre rouge noir donné en figure 2, que valent Hn(30), Hn(20), Hn(35), Hn(50) ?
Montrer que, pour un nœud x quelconque dans un arbre rouge noir, le sous-arbre enraciné à x
contient au moins 2Hn(x) − 1 nœuds internes.
En déduire qu’un arbre rouge noir comportant n nœuds internes a une hauteur au plus égale à
2 log(n + 1).
2
Corrigé
Correction de l’exercice 1.
Aucun n’est un rouge noir.
Un arbrerougenoir est un arbre binaire de recherche comportant un champ suppplémentaire
par nœud : sa couleur, qui peut valoir soit ROUGE, soir NOIR.
En outre, un arbre rouge noir satisfait les propriétés suivantes :
1. Chaque nœud est soit rouge, soit noir.
2. Chaque feuille est noire.
3. Si un nœud est rouge, alors ses deux fils sont noirs.
4. Pour chaque nœud de l’arbre, tous les chemins descendants vers des feuilles contiennent
le même nombre de nœuds noirs.
5. La racine est noire.
– Le premier arbre (a) n’a pas sa racine noir.
– Dans le deuxième (b) le chemin vers la troisième feuille contient un seul nœuds noir feuille
exclue, tandis qu’un chemin vers la première en contient 2 feuille exclue.
– Le troisième arbre (c) est très joli avec de belles couleurs mais ce n’est pas un ABR donc
pas un rouge noir (oui je sais c’est vache).
– Le quatrième (d) a un nœud rouge dont un fils est rouge.
Correction de l’exercice 2.
Oui.
30
15
40
10
25
Publicité
N
50
N
N
20
N
N
N
N
N
Figure 3: Coloriage corrigé
Correction de l’exercice 3.
1. Réponses :
Hn(30) = 3
Hn(20) = 3
Hn(35) = 2
Hn(50) = 1
2. On peut prouver cette proposition par induction sur la hauteur de x.
Si la hauteur de x est 0, x est une feuille et le sous-arbre enraciné à x contient 0 nœud
interne, c’est-à-dire 2Hn(x) − 1 = 20 − 1.
3
Soit x un nœud de hauteur h(x) > 0. Ce nœud a deux fils, g et d. Dans ce cas, Hn(g) ≥
Hn(x) − 1 et Hn(d) ≥ Hn(x) − 1. De plus, la hauteur de g et de d est inférieure à la hauteur
de x, donc, en appliquant l’hypothèse d’induction à g et d, les sous-arbres enracinés à g et
d possèdent chacun au moins 2Hn(g) − 1 ≥ 2Hn(x)−1 − 1 et 2Hn(d) − 1 ≥ 2Hn(x)−1 − 1 nœuds
internes. Il s’ensuit que le sous-arbre enraciné à x possède au moins 2(2Hn(x)−1 − 1) + 1 =
2Hn(x) − 1 nœuds internes.
3. Soit h la hauteur de l’arbre D’après la propriété 3, au moins la moitié des nœuds d’un
chemin simple reliant la racine de l’arbre à une feuille doivent être noirs (preuve facile par
l’absurde). En conséquence, la hauteur noire de la racine vaut au moins h/2, donc
d’où
n ≥ 2h/2 − 1,
h ≤ 2 log(n + 1).
4