Newer
Older
Les arbres équilibrés sont des ABR pour lesquels $`h = O(\log n)`$. Parmi les différents types d'arbres équilibrés on va s'intéresser aux ARN où chaque nœud possède une couleur.
## Définitions et propriétés
Pour simplifier les définitions et les algorithmes qui suivent, on va considérer les `null` comme des feuilles externes qu'on notera par ☒. Ainsi chaque nœud interne a deux fils.
---
**Définition** Un *arbre rouge-noir (ARN)* est un ABR tel que :
1. Chaque nœud est soit rouge, soit noir.
2. La racine est noire.
4. Si un nœud est rouge, alors ses deux fils sont noirs.
5. Pour chaque nœud, tous les chemins le reliant à des feuilles contiennent le même nombre de nœuds noirs.
À partir de (4) et (5) on voit déjà que l'arbre est « équilibré » dans le sens où pour chaque sous-arbre, la branche la plus longue est au plus deux fois plus longue que la branche la plus courte.
---
**Définition** La *hauteur noire* d'un nœud $`x`$ (on note $`hn(x)`$) est le nombre de nœuds noirs (sans compter $`x`$) sur le chemin de $`x`$ vers une feuille. La hauteur noire d'un arbre est la hauteur noire de sa racine.
---
**Exemple**
```mermaid
graph TD
50((50)) --- 32 & 80
32((32)) --- 26 & 40
80((80)) --- 58 & 92
26((26)) --- 18 & 30
40((40)) --- 36 & 44
58((58)) --- 54 & 74
92((92)) --- s01[ ] & s02[ ]
18((18)) --- 12 & 22
30((30)) --- 28 & s03[ ]
36((36)) --- s04[ ] & 38
44((44)) --- s05[ ] & s06[ ]
54((54)) --- s07[ ] & s08[ ]
74((74)) --- 68 & 76
12((12)) --- 4 & s09[ ]
22((22)) --- s10[ ] & s11[ ]
28((28)) --- s12[ ] & s13[ ]
38((38)) --- s14[ ] & s15[ ]
68((68)) --- s16[ ] & s17[ ]
76((76)) --- s18[ ] & s19[ ]
4((4)) --- s20[ ] & s21[ ]
class 50,80,26,40,92,30,36,44,54,74,s01,s02,12,22,s03,s04,s05,s06,s07,s08,s09,s10,s11,s12,s13,s14,s15,s16,s17,s18,s19,s20,s21 black;
class 32,58,18,28,38,68,76,4 red;
```
En plus d'attributs `cle`, `pere`, `gauche` et `droit` des nœuds d'un ABR, on ajoute un attribut supplémentaire `couleur` (1 bit) qui peut prendre les valeurs `N` ou `R`.
Le fait de remplacer `null` par des nœuds ☒ noirs nous permet de simplifier nos algorithmes en écrivant par exemple
```java
if (x.couleur == N) { ... }
```
au lieu de
```java
if (x == null || x.couleur == N) { ... }
```
De l'autre coté, si on utilise un nœud différent pour chaque feuille, on gaspille de la mémoire. C'est pourquoi on peut remplacer tous les ☒ par un nœud unique, la *sentinelle*.
```mermaid
graph TD
r(( ))
r -.- f1(( )) & f2(( )) & f3(( ))
---
**Proposition** Pour tout nœud $`x`$, le sous-arbre de racine $`x`$ contient au moins $`2^{hn(x)} - 1`$ nœuds internes.
À démontrer par récurrence sur $`h(x)`$, la hauteur du sous-arbre de racine $`x`$.
---
**Proposition** La hauteur d'un ARN ayant $`n`$ nœuds internes est au plus $`2\log_2(n + 1)`$.
---
**Corollaire** Les opérations `rechercher()`, `minimum()`, `maximum()`, `successeur()` et `predecesseur()` s'exécutent en $`O(\log n)`$.
---
## Rotations
Pour ajouter ou supprimer des clés, on va se baser sur les opérations `ajouter()` et supprimer des ABR. Celles-ci ne préservent pas forcement les propriétés (1)-(5). Si certaines de ces propriétés sont violées, on va les réparer en faisant des recoloriages et des *rotations*.
```mermaid
x1((x)) --- a1[/a\] & y1((y))
y1 --- b1[/b\] & c1[/c\]
end
y2((y)) --- x2((x)) & c2[/c\]
x2 --- a[/a\] & b[/b\]
end
* `rotationGauche(x)` : `T1 -> T2`
* `rotationDroite(y)` : `T2 -> T1`
---
**Proposition** Les rotations préservent la propriété des ABR.
---
**Complexité :** $`O(1)`$
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
On commence par l'ajout classique dans un ABR légèrement modifié :
```java
ajouter(Noeud z) {
y = ☒;
x = racine;
while (x != ☒) {
y = x;
x = z.cle < x.cle ? x.gauche : x.droit;
}
z.pere = y;
if (y == ☒) { // arbre vide
racine = z;
} else {
if (z.cle < y.cle)
y.gauche = z;
else
y.droit = z;
}
z.gauche = z.droit = ☒;
z.couleur = R;
ajouterCorrection(z);
}
```
Les modifications sont :
* on remplace les `null` par `☒`
* on colorie le nouveau nœud `z` en rouge
* comme ce coloriage risque de violer certaines propriétés RN, on appelle une procédure qui les restaure.
Avant de donner le pseudo-code de `ajouterCorrection()` voyons quelles propriétés RN risquent d'être violées :
1. OK
2. Si l'arbre était vide `z` devient sa racine. C'est facile à réparer, il suffit de le colorier en noir
3. OK
4. Si le père de `z`, `y` est rouge, cette propriété est violée.
5. OK
Voici comment on répare :
```java
ajouterCorrection(Noeud z) {
while (z.pere.couleur == R) {
if (z.pere == z.pere.pere.gauche) {
// La seule propriété RN violée est (4) : z et z.pere sont rouges
y = z.pere.pere.droit; // l'oncle de z
if (y.couleur == R) {
// cas 1
z.pere.couleur = N;
y.couleur = N;
z.pere.pere.couleur = R;
z = z.pere.pere;
} else {
if (z == z.pere.droit) {
// cas 2
z = z.pere;
rotationGauche(z);
}
// cas 3
z.pere.couleur = N;
z.pere.pere.couleur = R;
rotationDroite(z.pere.pere);
}
} else {
// idem en miroir, gauche <-> droite
// cas 1', 2', 3'
}
}
// La seule propriété (potentiellement) violée est (2)
racine.couleur = N;
}
```
---
**Proposition**
* Au début de chaque itération de la boucle `while` la seule propriété RN violée est (4) : `z` et `z.pere` sont tous les deux rouges.
* À la fin de la boucle, la seule propriété potentiellement violée est (4) et la dernière instruction la répare.
---
Pour démontrer cette proposition, on va regarder ce qui se passe dans les cas 1, 2 et 3. Les cas 1', 2' et 3' sont symétriques.
**Cas 1** `y` (l'oncle de `z`) est rouge.
On analysera le sous-cas où `z` est fils gauche, l'autre cas est symétrique.