A Rappels algorithmiques
421
Fig. A.22 L’arbre-B de la figure A.21, dans lequel a été insérée la clé 63
Fonction insérer(élément X, ArbreB A)
// Précondition : A est un arbre-B ; X ∈ A ; A peut être vide.
// Postcondition : Retourne un arbre-B construit à partir de l’arbre initial,
dans lequel a été insérée la clé X.
// Utilise : éclaterRacine, insérerRacineNonPleine,
insérerPremièreClé
si A == None alors
A = insérerPremièreClé(X)
sinon
si A.nombreClés == 2m − 1 alors
A = éclaterRacine(A)
A = insérerRacineNonPleine(X, A)
retourner A
La fonction insérerPremièreClé est appelée une seule fois, lors de la création
de l’arbre au moment de l’insertion de la première clé.
Fonction insérerPremièreClé(élément X)
// Précondition : aucune
// Postcondition : Retourne un arbre réduit à une feuille et de clé unique X.
// Variable locale : ArbreB A
// Utilise : nouveau
A = nouveau()
A.feuille = Vrai
A.nombreClés = 1
A.clés[1] = X
retourner A
La fonction éclaterRacine est appelée à chaque insertion dans un arbre-B
dont la racine a 2m − 1 clés. Son intérêt, comme celui de la fonction éclater
donnée plus loin, est le suivant : si nous sommes amenés à insérer une clé dans une