CHAPITRE 6 : INSÉRER : L'ÉCLATEMENT DES NŒUDS PLEINS

Insérer dans un arbre binaire est facile : on descend, on accroche une feuille. Dans un B-arbre, c'est interdit : accrocher une feuille allongerait une branche et briserait l'équilibre parfait. Il faut donc une autre idée.

Le problème

Toute insertion commence par une descente jusqu'à la feuille où la clé doit aller. Jusque-là, rien de neuf. Mais ensuite :

On ne peut pas créer une nouvelle feuille : elle serait plus profonde que les autres.
Il faut donc insérer la clé dans une feuille existante.
Et si cette feuille est déjà pleine, 2t − 1 clés, on ne peut rien y mettre.

Tout l'art de l'insertion consiste à résoudre ce dernier cas.

Le partage d'un nœud

L'opération fondamentale s'appelle PARTAGE (ou split). Un nœud plein contient 2t − 1 clés, un nombre impair : il a donc une clé médiane bien définie, avec t − 1 clés de chaque côté.

Le partage procède ainsi :

La clé médiane remonte dans le père.
Les t − 1 clés de gauche forment un nouveau nœud.
Les t − 1 clés de droite en forment un second.
Le père gagne une clé et un fils.

Remarquer que les deux nœuds obtenus ont exactement t − 1 clés : ils respectent tout juste la borne inférieure. C'est pour cela que 2t − 1 est le bon maximum : il garantit qu'un partage produit deux nœuds licites.

def partager(parent, i):
    # Partage le i-eme fils de parent, qui est plein
    t = parent.t
    plein = parent.fils[i]

    gauche = Noeud(t, plein.feuille)
    droite = Noeud(t, plein.feuille)

    gauche.cles = plein.cles[:t-1]        # t-1 cles
    mediane     = plein.cles[t-1]         # celle qui remonte
    droite.cles = plein.cles[t:]          # t-1 cles

    if not plein.feuille:
        gauche.fils = plein.fils[:t]
        droite.fils = plein.fils[t:]

    parent.cles.insert(i, mediane)
    parent.fils[i:i+1] = [gauche, droite]

Deux stratégies

La solution naïve consiste à insérer d'abord, puis à réparer : on descend jusqu'à la feuille, on y met la clé, et si la feuille déborde on la partage, ce qui peut faire déborder le père, et ainsi de suite jusqu'à la racine.

Cela marche, mais exige deux parcours de l'arbre : une descente pour trouver la place, une remontée pour réparer. Soit jusqu'à 2h accès disque.

La bonne solution renverse l'ordre :

On partage les nœuds pleins pendant la descente, avant même de savoir si on en aura besoin.

Ainsi, quand on arrive à la feuille, on a la garantie qu'elle n'est pas pleine : puisqu'on vient de partager tout ce qui l'était sur le chemin. Une seule descente suffit.

Pourquoi l'éclatement préventif est correct. Lorsqu'on partage un nœud plein, son père doit pouvoir accueillir la clé médiane. Or le père a été examiné juste avant sur le chemin de descente, et partagé s'il était plein : il n'est donc jamais plein au moment où son fils remonte une clé.

L'invariant se formule ainsi : on ne descend jamais dans un nœud plein, et le nœud courant n'est jamais plein. Il se maintient de proche en proche depuis la racine, qui est traitée à part.

L'algorithme complet

def inserer(arbre, k):
    racine = arbre.racine

    if racine.plein():                      # cas particulier
        neuve = Noeud(arbre.t, feuille=False)
        neuve.fils = [racine]
        partager(neuve, 0)
        arbre.racine = neuve                # l'arbre gagne un niveau

    _inserer_non_plein(arbre.racine, k)


def _inserer_non_plein(x, k):
    # Precondition : x n'est pas plein
    i = len(x.cles) - 1

    if x.feuille:
        x.cles.append(None)                 # on decale vers la droite
        while i >= 0 and k < x.cles[i]:
            x.cles[i+1] = x.cles[i]
            i -= 1
        x.cles[i+1] = k
        return

    while i >= 0 and k < x.cles[i]:
        i -= 1
    i += 1                                  # indice du fils a suivre

    if x.fils[i].plein():
        partager(x, i)
        if k > x.cles[i]:                   # la mediane a change la donne
            i += 1

    _inserer_non_plein(x.fils[i], k)

Un exemple complet

Partons du B-arbre de degré minimal t = 2 du chapitre 2 : racine J M, feuilles A B D, K, S T W.

Insertion de E. On descend : E < J, donc premier fils. Ce fils est A B D, qui est plein (3 = 2t − 1). On le partage avant d'y entrer : B remonte, il reste A et D.

La racine devient B J M. Comme E > B, on descend dans D, qui n'est pas plein : E s'y insère, donnant D E.

Insertion de U. Cette fois la racine B J M est elle-même pleine. On la partage avant tout : J remonte dans une racine toute neuve, et l'arbre gagne un niveau.

On descend ensuite normalement jusqu'à la feuille S T W, qui est pleine : on la partage (T remonte), puis U rejoint U W.

La croissance par le haut

C'est le point à retenir absolument.

Un B-arbre ne grandit jamais par le bas. Sa hauteur n'augmente que d'une seule façon : quand la racine éclate.

Et comme toutes les feuilles descendent alors d'un cran en même temps, l'équilibre parfait est préservé sans aucune rotation. C'est là que les B-arbres se séparent des AVL et des arbres rouge-noir, qui doivent, eux, réorganiser localement leurs liens.

Complexité

	Coût
Accès disque	O(h) = O(log_t n)
Temps processeur	O(t · log_t n)
Partages par insertion	au plus h

Une seule descente, donc le même ordre de grandeur que la recherche. Le partage lui-même est en O(t) : il recopie au plus 2t − 1 clés.

À retenir

On n'ajoute jamais de feuille : on insère dans une feuille existante.
Un nœud plein se partage en deux ; sa clé médiane monte chez le père.
On partage pendant la descente, ce qui garantit une seule traversée.
La hauteur n'augmente que lorsque la racine éclate : l'arbre grandit par le haut.

Exercices d'application

Exercice 1

Dans un B-arbre de degré minimal t = 2 réduit à une seule racine contenant A C, insérez successivement B, puis D, puis E. Donnez l'arbre après chaque insertion.

Voir le corrigeMasquer le corrige

Insertion de B. La racine A C a 2 clés, le maximum est 2t − 1 = 3 : elle n'est pas pleine. B s'insère entre A et C.

racine : A B C

Insertion de D. La racine est maintenant pleine (3 clés). On la partage avant tout : la médiane B remonte dans une nouvelle racine, A et C deviennent deux feuilles. L'arbre passe de hauteur 0 à hauteur 1.

      B
     / \
    A   C

Puis D > B, on descend dans la feuille C, qui n'est pas pleine :

      B
     / \
    A   C D

Insertion de E. La racine B n'est pas pleine. E > B, on va vers C D, qui a 2 clés sur 3 possibles : pas plein non plus. E s'y insère.

      B
     / \
    A   C D E

Exercice 2

Pourquoi le maximum de clés d'un nœud vaut-il 2t − 1 et non 2t ? Que se passerait-il avec 2t ?

Voir le corrigeMasquer le corrige

Parce que 2t − 1 est impair, ce qui donne une clé médiane unique, avec exactement t − 1 clés de part et d'autre.

2t - 1 cles  ->  (t-1) | mediane | (t-1)

Les deux nœuds produits ont t − 1 clés, soit précisément le minimum autorisé. Le partage produit donc toujours deux nœuds licites.

Avec 2t clés, le partage donnerait t clés d'un côté et t − 1 de l'autre après extraction de la médiane, ou bien il faudrait choisir arbitrairement laquelle des deux clés centrales remonte. Les deux moitiés seraient déséquilibrées, et surtout la symétrie du raisonnement serait perdue.

Le choix 2t − 1 n'est donc pas une convention arbitraire : c'est ce qui rend le partage propre. C'est d'ailleurs pour cela que la convention en ordre m privilégie les m pairs.

Exercice 3

Quelle suite d'insertions, à partir d'un arbre vide de degré t = 2, produit le plus grand nombre de partages ? Combien de clés faut-il pour atteindre la hauteur 2 ?

Voir le corrigeMasquer le corrige

Le pire cas est la suite croissante (ou décroissante) : chaque nouvelle clé va toujours dans la feuille la plus à droite, qui se remplit puis éclate le plus souvent possible.

Déroulons avec t = 2, donc 3 clés maximum par nœud :

1,2,3       -> racine pleine : 1 2 3
4           -> partage de la racine, hauteur 1
                     2
                    / \
                   1   3 4
5           ->      2
                    / \
                   1   3 4 5
6           -> la feuille droite est pleine : partage
                     2 4
                    / | \
                   1  3  5 6

En continuant ainsi, la racine atteint 3 clés après l'insertion de 10, et le partage suivant fait passer l'arbre à la hauteur 2. Il faut donc de l'ordre de 11 clés.

Cela confirme la borne du chapitre 4 : pour h = 2 et t = 2, le minimum théorique est 2t² − 1 = 7 clés. Une insertion croissante atteint la hauteur 2 un peu plus tard que ce minimum, parce que les partages laissent des nœuds à moitié remplis.

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