422
A Rappels algorithmiques
feuille pleine – ce qui nécessite de faire remonter la clé médiane contenue dans
la feuille vers le nœud parent – ou à faire remonter la clé médiane d’un nœud
enfant vers le nœud parent, ce nœud parent ne sera pas plein et nous pourrons
toujours trouver la place d’insérer la clé médiane au niveau précédent. Notons que
la fonction éclaterRacine fait appel à une procédure sauver dont le but est de
recopier en mémoire secondaire le ou les nœuds reçus en argument : les arbres-B
sont utilisés pour stocker de très grandes quantités de données, dans des contextes
où il est impossible de garder tout l’arbre, ou même plus qu’un nombre restreint de
nœuds, en mémoire centrale ; nous indiquons donc explicitement les opérations de
recopie en mémoire secondaire.
Fonction éclaterRacine(ArbreB A)
// Précondition : A est un arbre-B dont la racine a 2m − 1 clés.
// Postcondition : Retourne un arbre-B contenant le même ensemble de clés
que A, obtenu par éclatement de sa racine ; sa hauteur a augmenté de 1 par
rapport à celle de A.
// Utilise : nouveau, sauver
// Variables locales : ArbreB T, ArbreB B, entier j
B = nouveau()
T = nouveau()
// T sera la nouvelle racine, A et B ses fils
T.feuille = Faux
B.feuille = A.feuille
T.nombreClés = 1
B.nombreClés = m − 1
// Transférer la clé médiane de A dans T, qui a donc une seule clé
T.clés[1] = A.clés[m]
// Rattacher A et B à T
T.fils[1] = A
T.fils[2] = B
// Transférer les m − 1 dernières clés de A vers B
pour j de 1 à m − 1 faire
B.clés[j] = A.clés[j+m]
// Si A et B ne sont pas des feuilles, transférer les m derniers fils de A vers B
si non A.feuille alors
pour j de 1 à m faire
B.fils[j] = A.fils[j+m]
A.nombreClés = m-1
// Recopier en mémoire secondaire les trois nœuds
sauver(A, B, T)
retourner T
A Rappels algorithmiques
feuille pleine – ce qui nécessite de faire remonter la clé médiane contenue dans
la feuille vers le nœud parent – ou à faire remonter la clé médiane d’un nœud
enfant vers le nœud parent, ce nœud parent ne sera pas plein et nous pourrons
toujours trouver la place d’insérer la clé médiane au niveau précédent. Notons que
la fonction éclaterRacine fait appel à une procédure sauver dont le but est de
recopier en mémoire secondaire le ou les nœuds reçus en argument : les arbres-B
sont utilisés pour stocker de très grandes quantités de données, dans des contextes
où il est impossible de garder tout l’arbre, ou même plus qu’un nombre restreint de
nœuds, en mémoire centrale ; nous indiquons donc explicitement les opérations de
recopie en mémoire secondaire.
Fonction éclaterRacine(ArbreB A)
// Précondition : A est un arbre-B dont la racine a 2m − 1 clés.
// Postcondition : Retourne un arbre-B contenant le même ensemble de clés
que A, obtenu par éclatement de sa racine ; sa hauteur a augmenté de 1 par
rapport à celle de A.
// Utilise : nouveau, sauver
// Variables locales : ArbreB T, ArbreB B, entier j
B = nouveau()
T = nouveau()
// T sera la nouvelle racine, A et B ses fils
T.feuille = Faux
B.feuille = A.feuille
T.nombreClés = 1
B.nombreClés = m − 1
// Transférer la clé médiane de A dans T, qui a donc une seule clé
T.clés[1] = A.clés[m]
// Rattacher A et B à T
T.fils[1] = A
T.fils[2] = B
// Transférer les m − 1 dernières clés de A vers B
pour j de 1 à m − 1 faire
B.clés[j] = A.clés[j+m]
// Si A et B ne sont pas des feuilles, transférer les m derniers fils de A vers B
si non A.feuille alors
pour j de 1 à m faire
B.fils[j] = A.fils[j+m]
A.nombreClés = m-1
// Recopier en mémoire secondaire les trois nœuds
sauver(A, B, T)
retourner T