Newer
Older
## Suppression
Tout comme pour l'ajout, on commence par une suppression ABR classique légèrement modifiée :
```java
supprimer(Noeud z) {
if (z.gauche == ☒ || z.droit == ☒)
y = z;
else
y = successeur(z);
// y est le nœud à détacher
x = y.gauche;
else
x = y.droit;
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
x.pere = y.pere; // inconditionnelle
if (y.pere == ☒) { // suppression de la racine
racine = x;
} else {
if (y == y.pere.gauche)
y.pere.gauche = x;
else
y.pere.droite = x;
}
if (y != z) z.cle = y.cle;
if (y.couleur == N) supprimerCorrection(x);
recycler y;
}
```
Les modifications sont :
* On remplace les `null` par `☒`
* L'instruction `x.pere = y.pere` n'est plus dans un `if (x != ☒)`. `x` peut être la sentinelle avec son pointeur `pere` modifié. C'est le seul cas où on utilise autre chose que la `couleur` de la sentinelle et cela pour uniformiser les traitements dans ce cas particulier.
* Si le nœud détaché est noir, on appelle une procédure qui restaure les propriétés RN. Notons que si `y` est rouge, (1) - (5) sont préservés (à vérifier).
Quelles propriétés on a pu « casser » en supprimant un nœud noir ?
1. OK
2. Si `y` était la racine et `x` est rouge
3. OK
4. Si `x` et `y.pere` sont rouges
5. Cette propriété est enfreinte pour tous les ancêtres de `y` : tous les chemins qui passait par `y` se retrouvent avec un nœud noir de moins !
(2) et (4) sont faciles à réparer : il suffit de colorier `x` en noir. Le plus difficile est (5).
```java
supprimerCorrection(Noeud x) {
while (x != racine && x.couleur == N) {
if (x == x.pere.gauche) {
w = x.pere.droit; // le frère de x
if (w.couleur == R) {
// cas 1
w.couleur = N;
x.pere.couleur = R;
rotationGauche(x.pere);
w = x.pere.droit;
}
// cas 2
w.couleur = R;
x = x.pere;
} else {
if (w.droit.couleur == N) {
// cas 3
w.gauche.couleur = N;
w.couleur = R;
rotationDroite(w);
}
// cas 4
w.couleur = x.pere.couleur;
x.pere.couleur = N;
w.droit.couleur = N;
rotationGauche(x.pere);
x = racine;
}
} else {
// idem en miroir, gauche <-> droite
// cas 1', 2', 3', 4'
}
}
x.couleur = N;
}
```
C'est difficile de raisonner dans les termes de hauteurs noires et de démontrer que la procédure restaure (5). C'est pourquoi on va « pousser » la noirceur de `y` vers son fils `x`. Ainsi `x` devient double noir ou rouge-noir, (5) est préservé et on cherche à restaurer (1). Avec cette interprétation la boucle `while` remonte ce noir en trop jusqu'à ce que :
* `x` est un nœud rouge-noir. Dans ce cas on colorie `x` en noir (simple) et (1)-(5) sont restaurés.
* `x` pointe vers la racine. Dans ce cas le noir en trop ne pose pas de problème au niveau de (5) et on peut s'en débarrasser.
* On peut procéder à des rotations et colorations appropriées.
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
---
**Proposition**
* (*) Au début de chaque itération de la boucle `while` :
* la seule propriété violée est (1) : `x` est un nœud double noir
* `x` n'est pas la racine
* son frère `w` n'est pas la sentinelle
* (**) À la fin de la boucle les seules propriétés potentiellement violées sont :
* (2) si `x` est la racine et rouge
* (4) si `x` et sont père sont rouges
Dans les deux cas la dernière instruction répare (1)-(5)
---
Pour démontrer cette proposition on va procéder cas par cas.
**Cas 1** `w` (le frère de `z`) est rouge
```mermaid
graph TD
subgraph 0[Avant]
R1[" "] --- B1((B)) --- A1((A)) & D1((D))
A1 --- a1[/a\] & b1[/b\]
D1 --- C1((C)) & E1((E))
C1 --- c1[/c\] & d1[/d\]
E1 --- e1[/e\] & f1[/f\]
end
x1[x] -.-> A1
w1[w] -.-> D1
subgraph 1[Après]
R2 --- D2((D)) --- B2((B)) & E2((E))
B2 --- A2((A)) & C2((C))
A2 --- a2[/a\] & b2[/b\]
C2 --- c2[/c\] & d2[/d\]
E2 --- e2[/e\] & f2[/f\]
end
x2[x] -.-> A2
w2[w] -.-> C2
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
classDef red fill:#f00, stroke:#fff
classDef invisible fill:#0000, stroke:#0000
classDef pointer stroke-dasharray: 5 5, fill:#0000
classDef black2 fill:#000, stroke:#fff
class A1,A2 black2
class B1,C1,E1,D2,C2,E2 black
class D1,B2 red
class R1,R2 invisible
class x1,w1,x2,w2 pointer
```
* (2) - (5) sont préservées (à vérifier)
* `w` devient noir et cela nous ramène dans un des autres cas.
**Cas 2** `w` est noir et ses deux fils sont noirs
```mermaid
graph TD
subgraph 0[Avant]
R1[" "] --- B1((B)) --- A1((A)) & D1((D))
A1 --- a1[/a\] & b1[/b\]
D1 --- C1((C)) & E1((E))
C1 --- c1[/c\] & d1[/d\]
E1 --- e1[/e\] & f1[/f\]
end
x1[x] -.-> A1
w1[w] -.-> D1
subgraph 1[Après]
R2[" "] --- B2((B)) --- A2((A)) & D2((D))
A2 --- a2[/a\] & b2[/b\]
D2 --- C2((C)) & E2((E))
C2 --- c2[/c\] & d2[/d\]
E2 --- e2[/e\] & f2[/f\]
end
x2[x] -.-> B2
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
220
221
222
223
224
225
226
227
228
229
230
classDef red fill:#f00, stroke:#fff
classDef invisible fill:#0000, stroke:#0000
classDef pointer stroke-dasharray: 5 5, fill:#0000
classDef black2 fill:#000, stroke:#fff
classDef green fill:#cde498
class A1 black2
class C1,D1,E1,A2,C2,E2 black
class D2 red
class B1,B2 green
class R1,R2 invisible
class x1,w1,x2,w2 pointer
```
* Soit on entame une nouvelle itération avec (*) (à vérifier)
* Soit on sort de la boucle avec (**)
**Cas 3** `w` est noir, `w.gauche` est rouge, `w.droit` est noir
```mermaid
graph TD
subgraph 0[Avant]
R1[" "] --- B1((B)) --- A1((A)) & D1((D))
A1 --- a1[/a\] & b1[/b\]
D1 --- C1((C)) & E1((E))
C1 --- c1[/c\] & d1[/d\]
E1 --- e1[/e\] & f1[/f\]
end
x1[x] -.-> A1
w1[w] -.-> D1
subgraph 1[Après]
R2[" "] --- B2((B)) --- A2((A)) & C2((C))
A2 --- a2[/a\] & b2[/b\]
C2 --- c2[/c\] & D2((D))
D2 --- d2[/d\] & E2((E))
E2 --- e2[/e\] & f2[/f\]
end
x2[x] -.-> A2
w2[w] -.-> C2
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
classDef red fill:#f00, stroke:#fff
classDef invisible fill:#0000, stroke:#0000
classDef pointer stroke-dasharray: 5 5, fill:#0000
classDef black2 fill:#000, stroke:#fff
classDef green fill:#cde498
class A1,A2 black2
class D1,E1,C2,E2 black
class C1,D2 red
class B1,B2 green
class R1,R2 invisible
class x1,w1,x2,w2 pointer
```
* (2) - (5) sont préservées (à vérifier)
* `w` ce retrouve avec un fils droit rouge et cela nous amène dans cas 4
**Cas 4** `w` est noir et `w.droit` est rouge
```mermaid
graph TD
subgraph 0[Avant]
R1[" "] --- B1((B)) --- A1((A)) & D1((D))
A1 --- a1[/a\] & b1[/b\]
D1 --- C1((C)) & E1((E))
C1 --- c1[/c\] & d1[/d\]
E1 --- e1[/e\] & f1[/f\]
end
x1[x] -.-> A1
w1[w] -.-> D1
subgraph 1[Après]
R2[" "] --- D2((D)) --- B2((B)) & E2((E))
B2((B)) --- A2((A)) & C2((C))
A2 --- a2[/a\] & b2[/b\]
C2 --- c2[/c\] & d2[/d\]
E2 --- e2[/e\] & f2[/f\]
end
classDef red fill:#f00, stroke:#fff
classDef invisible fill:#0000, stroke:#0000
classDef pointer stroke-dasharray: 5 5, fill:#0000
classDef black2 fill:#000, stroke:#fff
classDef green fill:#cde498
classDef yellow fill:#fff5ad
class A1 black2
class D1,A2,B2,E2 black
class E1 red
class B1,D2 green
class C1,C2 yellow
class R1,R2 invisible
class x1,w1,x2,w2 pointer
```
```mermaid
graph TD
start((*)) --> 1[Cas 1] & 2[Cas 2] & 3[Cas 3] & 4[Cas 4]
1 --> 2 & 3 & 4
2 --> start & stop(("**"))
3 --> 4
4 --> stop
```
(1) - (5) sont restaurées et on sort de la boucle.
**Complexité** Dans cas 2 `x` remonte un niveau dans l'arbre, dans les autres cas la boucle s'arrête. Donc au pire $`O(h) = O(\log n)`$.
**Conclusion** Il est possible de maintenir l'arbre équilibré sans augmenter la complexité des opérations `ajouter()` et `supprimer()`. Ainsi toutes les opérations s'exécutent en temps logarithmique.