420
A Rappels algorithmiques
Fig. A.20 L’arbre-B de la figure A.18, dans lequel ont été insérées les clés 60 et 88 : les deux
feuilles dans lesquelles ces clés ont trouvé place n’étaient pas pleines, et ce sont donc les deux
seuls nœuds modifiés
Fig. A.21 L’arbre-B de la figure A.20, en cours d’insertion de la clé 63 : la troisième feuille de
l’arbre devrait recevoir cette clé, mais elle est pleine et a été éclatée : la clé médiane est remontée
au niveau supérieur, et les deux clés 58 et 61 sont maintenant dans des feuilles non pleines ; la
quatrième feuille de cet arbre pourra bien recevoir la clé 63 à insérer
L’appel à l’algorithme d’insertion se fait par la fonction insérer, qui
gère le cas où l’arbre est initialement vide (insertion de la première clé),
et l’éclatement éventuel de la racine, avec appel à la fonction (récursive)
insérerRacineNonPleine, qui traite le cas d’une insertion dans un arbre non
vide et dont la racine n’est pas pleine. Ces deux fonctions utilisent celle éclatant
un nœud plein, éclater, et deux fonctions auxiliaires insérerPremièreClé et
éclaterRacine, que nous donnons plus loin (figure A.22).