424
A Rappels algorithmiques
ET : a et b vaut Faux si a est égal à Faux, et b n’est alors pas évalué, et prend la
valeur de b sinon. C’est en fait le and standard, dit paresseux et aussi noté &&, de
langages de programmation tels que C ou Python.
Fonction insérerRacineNonPleine(élément X, ArbreB A)
// Précondition : A est un arbre-B non vide ; sa racine n’est pas pleine ;
X ∈ A.
// Postcondition : Retourne un arbre-B construit à partir de A dans lequel a
été insérée la clé X ; sa racine est toujours le nœud A.
// Utilise : éclater, insérerRacineNonPleine, sauver
// Variable locale : entier j
si A.feuille alors
// Mettre à jour le nombre de clés de A
A.nombreClés = A.nombreClés + 1
j = A.nombreClés
// Insérer X dans A
tant que (j > 1) et (X < A.clés[j]) faire
// Décaler les clés de A pour mettre X à sa place
A.clés[j] = A.clés[j-1]
j = j - 1
// Maintenant j = 1, ou alors j ≥ 2 et X > A.clés[j] ; dans les deux
cas X devient la j -ième clé de A
A.clés[j] = X
sauver(A)
retourner A
sinon
j = A.nombreClés
// Chercher dans quel fils de A continuer la recherche
tant que (j > 1) et (X < A.clés[j]) faire
j = j - 1
// Ici, j = 1, ou bien j ≥ 2 et X > A.clés[j] ; dans les deux cas
l’insertion de X se poursuit dans le j-ème fils de A, qui pourrait être plein
si A.fils[j].nombreClés == 2m − 1 alors
A = éclater(A, j)
si X > A.clés[j] alors
j = j + 1
insérerRacineNonPleine(X, A.fils[j])
retourner A