A Rappels algorithmiques
423
La fonction qui éclate un nœud non racine est donnée ci-dessous. Elle est très
proche de celle éclatant la racine ; la différence principale est que le nœud à éclater
est toujours fils d’un nœud non plein.
Fonction éclater(ArbreB A, entier i)
// Précondition : A est racine d’un arbre-B non plein, et non réduit à une
feuille ; son i-ème fils est plein (il a 2m − 1 clés).
// Postcondition : Retourne un arbre-B construit à partir de A en remplaçant
le i-ème fils de A par deux nœuds ; ni la hauteur ni l’ensemble de clés
n’ont été modifiés.
// Utilise : nouveau, sauver
// Variables locales : ArbreB T, ArbreB B, élément Y, entier j
B = A.fils[i]
T = nouveau()
A.feuille = B.feuille
T.nombreClés = m − 1
// Transférer les m − 1 dernières clés de B vers T
pour j de 1 à m − 1 faire
T.clés[j] = B.clés[j+m]
// Si nécessaire, transférer les m derniers fils de B vers T
si non B.feuille alors
pour j de 1 à m faire
T.fils[j] = B.fils[j+m]
// Le nouveau nœud T est maintenant créé et a m − 1 clés
// La clé Y va être transférée du nœud B au nœud A
Y = B.clés[m]
// Le nombre de clés de B est mis à jour
B.nombreClés = m − 1
// Le nœud A va recevoir une clé supplémentaire
// Il faut d’abord décaler les clés plus grandes que Y
pour j de A.nombreClés à i faire
A.clés[j+1] = A.clés[j]
// On peut maintenant ajouter la clé Y dans le nœud A
A.clés[i] = Y
pour j de A.nombreClés + 1 à i + 1 faire
A.fils[j+1] = A.fils[j]
A.fils[i+1] = T
A.nombreClés = A.nombreClés + 1
sauver(A, B, T)
retourner A
Nous pouvons maintenant donner la fonction inserérRacineNonPleine. Conformément aux usages usuels des langages de programmation, nous rappelons que
l’opérateur et, utilisé dans le pseudo-code donné ici, diffère de l’opérateur logique
423
La fonction qui éclate un nœud non racine est donnée ci-dessous. Elle est très
proche de celle éclatant la racine ; la différence principale est que le nœud à éclater
est toujours fils d’un nœud non plein.
Fonction éclater(ArbreB A, entier i)
// Précondition : A est racine d’un arbre-B non plein, et non réduit à une
feuille ; son i-ème fils est plein (il a 2m − 1 clés).
// Postcondition : Retourne un arbre-B construit à partir de A en remplaçant
le i-ème fils de A par deux nœuds ; ni la hauteur ni l’ensemble de clés
n’ont été modifiés.
// Utilise : nouveau, sauver
// Variables locales : ArbreB T, ArbreB B, élément Y, entier j
B = A.fils[i]
T = nouveau()
A.feuille = B.feuille
T.nombreClés = m − 1
// Transférer les m − 1 dernières clés de B vers T
pour j de 1 à m − 1 faire
T.clés[j] = B.clés[j+m]
// Si nécessaire, transférer les m derniers fils de B vers T
si non B.feuille alors
pour j de 1 à m faire
T.fils[j] = B.fils[j+m]
// Le nouveau nœud T est maintenant créé et a m − 1 clés
// La clé Y va être transférée du nœud B au nœud A
Y = B.clés[m]
// Le nombre de clés de B est mis à jour
B.nombreClés = m − 1
// Le nœud A va recevoir une clé supplémentaire
// Il faut d’abord décaler les clés plus grandes que Y
pour j de A.nombreClés à i faire
A.clés[j+1] = A.clés[j]
// On peut maintenant ajouter la clé Y dans le nœud A
A.clés[i] = Y
pour j de A.nombreClés + 1 à i + 1 faire
A.fils[j+1] = A.fils[j]
A.fils[i+1] = T
A.nombreClés = A.nombreClés + 1
sauver(A, B, T)
retourner A
Nous pouvons maintenant donner la fonction inserérRacineNonPleine. Conformément aux usages usuels des langages de programmation, nous rappelons que
l’opérateur et, utilisé dans le pseudo-code donné ici, diffère de l’opérateur logique