## 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 if (y.gauche != null) x = y.gauche; else x = y.droit; // x est le fils unique de y ou null si y n'a pas de fils 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; } if (w.gauche.couleur == N && w.gauche.couleur == N) { // 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); w = x.pere.droit; } // 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. --- **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 classDef black fill:#888, stroke:#fff 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 classDef black fill:#888, stroke:#fff 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 classDef black fill:#888, stroke:#fff 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 black fill:#888, stroke:#fff 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 ``` Voici comment se déroule la boucle : ```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.