CHAPITRE 7 : SUPPRIMER : EMPRUNTER OU FUSIONNER

La suppression est le morceau difficile. L'insertion n'avait qu'un problème, le nœud plein, et une réponse : le partage. La suppression a plusieurs cas, parce qu'un nœud peut tomber sous le minimum autorisé.

Le problème symétrique

Retirer une clé d'un nœud qui en a t − 1 le fait descendre à t − 2 : la quatrième propriété est violée, l'arbre n'est plus un B-arbre.

Deux réparations sont possibles, et l'ordre dans lequel on les essaie compte.

Première réparation : emprunter au frère

Si un frère immédiat possède plus de t − 1 clés, il peut en céder une. Mais pas directement : la clé ne peut pas sauter d'un nœud à l'autre sans casser la propriété d'ordre. Elle passe par le père.

C'est ce qu'on appelle une rotation :

La clé du père qui sépare les deux frères descend dans le nœud trop pauvre.
La clé extrême du frère (la plus grande s'il est à gauche, la plus petite s'il est à droite) remonte prendre sa place dans le père.
Si les nœuds ne sont pas des feuilles, le fils correspondant suit la clé.

def emprunter_au_frere_droit(parent, i):
    # Le fils i emprunte une cle au fils i+1
    pauvre = parent.fils[i]
    frere  = parent.fils[i+1]

    pauvre.cles.append(parent.cles[i])        # le pere descend
    parent.cles[i] = frere.cles.pop(0)        # le frere remonte

    if not frere.feuille:
        pauvre.fils.append(frere.fils.pop(0))

Le compte est juste : le nœud pauvre gagne une clé et repasse à t − 1, le frère en perd une et reste au-dessus du minimum, le père en garde autant.

Seconde réparation : fusionner

Si aucun frère ne peut prêter, tous sont à exactement t − 1 clés, il faut fusionner.

La clé du père qui sépare les deux frères descend.
Les deux nœuds et cette clé forment un seul nœud.
Le père perd une clé et un fils.

Vérifions la taille du résultat :

(t − 2) + 1 + (t − 1) = 2t − 2 ≤ 2t − 1 ✔

Le nœud fusionné tient donc toujours. C'est encore la borne 2t − 1 qui le garantit.

def fusionner(parent, i):
    # Fusionne les fils i et i+1 avec la cle i du pere
    gauche = parent.fils[i]
    droite = parent.fils[i+1]

    gauche.cles.append(parent.cles.pop(i))    # le pere descend
    gauche.cles.extend(droite.cles)
    gauche.fils.extend(droite.fils)

    parent.fils.pop(i+1)                      # droite disparait

La fusion peut se propager. Le père vient de perdre une clé : s'il était lui-même au minimum, il tombe sous le seuil et doit à son tour emprunter ou fusionner. Le problème peut ainsi remonter jusqu'à la racine.

Et si la racine finit par perdre sa dernière clé, elle disparaît : son unique fils devient la nouvelle racine, et l'arbre perd un niveau. C'est la symétrique exacte de la croissance par le haut.

Supprimer une clé interne

Un dernier cas reste à traiter : que faire quand la clé à supprimer n'est pas dans une feuille, mais dans un nœud interne ? On ne peut pas simplement l'enlever : elle sert de séparateur entre deux sous-arbres.

On procède comme dans un arbre binaire de recherche : on la remplace par une clé voisine, puis on supprime celle-ci, qui est forcément dans une feuille.

Le prédécesseur : la plus grande clé du sous-arbre gauche.
Ou le successeur : la plus petite clé du sous-arbre droit.

def predecesseur(noeud, i):
    # La plus grande cle du sous-arbre gauche de la cle i
    x = noeud.fils[i]
    while not x.feuille:
        x = x.fils[-1]        # toujours le fils le plus a droite
    return x.cles[-1]

On choisit de préférence le côté dont le sous-arbre a des clés en trop, pour éviter de déclencher une fusion.

Récapitulatif des cas

Situation	Action
Clé dans une feuille qui a plus de t − 1 clés	la retirer, c'est tout
Clé dans un nœud interne	la remplacer par son prédécesseur ou successeur, puis supprimer celui-ci
Nœud sous le minimum, un frère a des clés en trop	rotation : emprunter via le père
Nœud sous le minimum, aucun frère ne peut prêter	fusion avec un frère, en absorbant une clé du père
La racine se retrouve vide	elle disparaît, son fils devient racine, l'arbre perd un niveau

La même précaution qu'à l'insertion

De la même façon qu'on partage les nœuds pleins en descendant, les bonnes implémentations renforcent les nœuds trop pauvres en descendant. Avant d'entrer dans un fils qui n'a que t − 1 clés, on lui fait emprunter ou fusionner.

On garantit ainsi qu'on ne descend jamais dans un nœud au minimum, et une seule traversée suffit, comme pour l'insertion.

Complexité

	Coût
Accès disque	O(h) = O(log_t n)
Temps processeur	O(t · log_t n)

Les trois opérations, rechercher, insérer, supprimer, ont donc exactement le même coût. C'est ce qui fait du B-arbre une structure si régulière : aucune opération n'est le point faible des autres.

À retenir

Supprimer peut faire tomber un nœud sous t − 1 clés : il faut le réparer.
On emprunte d'abord à un frère, par rotation à travers le père.
Si aucun frère ne peut prêter, on fusionne, et cela peut remonter jusqu'à la racine.
Une clé interne se supprime en la remplaçant par son prédécesseur ou son successeur.
L'arbre rétrécit par le haut, quand la racine se vide.

Exercices d'application

Exercice 1

Dans un B-arbre de degré t = 2 dont la racine est M, le fils gauche K et le fils droit S T W, supprimez la clé K. Détaillez.

Voir le corrigeMasquer le corrige

K est dans une feuille qui contient exactement t − 1 = 1 clé. La retirer la laisserait vide, sous le minimum : il faut réparer.

Peut-on emprunter ? Le frère droit S T W a 3 clés, soit plus que le minimum de 1. Oui. On fait donc une rotation gauche.

La clé M du père descend dans le nœud appauvri ;
la plus petite clé du frère, S, remonte prendre la place de M.

avant :        M                apres :        S
              / \                             / \
             K   S T W                       M   T W

Le nœud gauche contient maintenant M (1 clé, le minimum est respecté), le frère en garde 2, et le père en a toujours une. L'arbre est de nouveau valide, et sa hauteur n'a pas changé.

Exercice 2

Même arbre, mais le fils droit ne contient que S. Supprimez K.

Voir le corrigeMasquer le corrige

Le frère droit S n'a qu'une clé, soit exactement le minimum : il ne peut rien prêter. L'emprunt est impossible, il faut fusionner.

La clé M du père descend et soude les deux frères en un seul nœud :

avant :        M                apres :    M S
              / \
             K   S           (K vient d'etre supprimee)

Le nœud fusionné contient M et S, soit 2 clés : conforme, puisque le maximum est 2t − 1 = 3.

Mais le père est maintenant vide. C'était la racine, et elle a perdu son unique clé : elle disparaît. Son fils unique devient la nouvelle racine.

resultat final : une racine unique  M S

L'arbre a perdu un niveau : il est passé de la hauteur 1 à la hauteur 0. C'est exactement l'inverse de la croissance par le haut observée à l'insertion.

Exercice 3

Pourquoi la fusion de deux nœuds minimaux ne risque-t-elle jamais de dépasser la capacité d'un nœud ?

Voir le corrigeMasquer le corrige

Comptons précisément les clés du nœud fusionné.

La fusion intervient après qu'un nœud est tombé à t − 2 clés. On lui adjoint :

la clé séparatrice descendue du père : 1 ;
les clés du frère, qui est au minimum : t − 1.

(t − 2) + 1 + (t − 1) = 2t − 2

Or la capacité maximale d'un nœud est 2t − 1. On a donc 2t − 2 ≤ 2t − 1, avec même une place libre.

Ce n'est pas une coïncidence. Les deux bornes t − 1 et 2t − 1 sont choisies ensemble pour que les deux opérations inverses se referment proprement : le partage d'un nœud de 2t − 1 clés produit deux nœuds de t − 1, et la fusion de deux nœuds minimaux reproduit un nœud qui tient. La structure est cohérente dans les deux sens.

Cherchez avant d'ouvrir le corrige : c'est en butant sur les difficultes que l'on progresse.