A Rappels algorithmiques
419
A.3.2 Recherche dans un arbre-B
Fonction chercher(élément X, ArbreB A)
// Précondition : A est un arbre-B.
// Postcondition : Retourne l’arbre vide si X ∈ A, et le nœud contenant X
sinon.
// Variables locales : entier i, entier n, élément Y
// Utilise : chercher
si A == None alors
retourner None
sinon
i = 1
Y = A.clés[1] //première clé du nœud racine
n = A.nombreClés
tant que Y < X et i < n faire
i = i + 1
Y = A.clés[i]
// En ce point i = n ou Y ≥ X (ou les deux à la fois)
si Y == X alors
retourner A
sinon
si Y > X alors
retourner chercher(X, A.fils[i])
sinon
// Ici Y < X et i = n
retourner chercher(X, A.fils[n+1])
A.3.3 Insertion d’une clé
Nous commençons par montrer sur un exemple ce qui se passe lors d’une insertion.
L’arbre initial est celui de la figure A.18, dans lequel nous voulons insérer
successivement les clés 60, 88 et 63.
Les deux premières insertions se font dans des feuilles non pleines, et nous
obtenons l’arbre de la figure A.20. L’insertion suivante, de la clé 63, devrait se faire
dans la troisième feuille de cet arbre, qui est pleine. Il nous faut donc l’éclater et
réarranger l’arbre. Ceci se fait en remontant d’un niveau la clé médiane de la feuille,
ce qui est possible car le parent de la feuille n’est pas plein. Nous obtenons alors
l’arbre de la figure A.21, et il suffit d’insérer la clé dans la feuille adéquate, qui est
maintenant non pleine, pour terminer.