3.2 Recherche de clés
69
plein contient un nombre impair de clés) et avec deux fils, et la hauteur de l’arbre
augmente de 1.
– Si la racine n’est pas pleine, elle n’est pas modifiée, et l’algorithme continue le
long de la branche allant de la racine à la feuille d’insertion.
– Dès que le pointeur rencontre un nœud plein, la clé médiane remonte dans le
nœud parent (qui n’est pas plein, car l’algorithme est déjà passé), le nœud plein
est éclaté en deux nœuds, et ses enfants sont répartis entre ces deux nouveaux
nœuds.
– Finalement, l’algorithme parvient dans une feuille, il l’éclate si nécessaire, et
l’insertion a lieu dans une feuille non pleine.
Dans cet algorithme, les nœuds pleins sont traités avant l’insertion proprement dite.
Cet algorithme, que nous appelons pour cette raison prudent, est présenté dans la
section A.3 ; cf. aussi le livre de Cormen et al. [50]. Avec cette méthode, une feuille
pleine donne naissance à deux feuilles contenant chacune m−1 clés, puis la nouvelle
clé est insérée, comme dans la figure 3.6. L’algorithme descend de la racine vers
une feuille de l’arbre, et peut conduire à éclater des nœuds internes pleins, alors que
l’insertion se ferait dans une feuille non pleine. Par exemple, l’insertion de la clé 87
dans l’arbre-B de la figure 3.5 conduit à éclater le troisième fils de la racine, alors
que l’insertion se fait dans une feuille ne contenant qu’une seule clé.
Construction algorithmique (insertion aux feuilles) optimiste Dans une variante
optimiste de cet algorithme, les nœuds pleins sont traités après avoir trouvé la
place d’insertion d’une nouvelle clé. Dans un tel arbre-B optimiste de paramètre m,
les nœuds contiennent maintenant entre m et 2m clés. Imaginons qu’une insertion
concerne une certaine feuille. Si elle n’est pas pleine, l’insertion a lieu. Sinon, c’est
qu’elle contient 2m clés. La clé médiane, parmi ces 2m clés et la nouvelle clé,
remonte dans le nœud parent et la feuille pleine éclate en deux feuilles contenant
chacune m clés. Si le nœud parent est plein, une clé est poussée vers le nœud grandparent, etc., et ceci jusqu’à la racine, si nécessaire. Si la racine est pleine, elle est
éclatée, une nouvelle racine est créée contenant une clé, et la hauteur de l’arbre
augmente de 1.
Cet algorithme procède ainsi de la racine vers les feuilles pour trouver la place
d’insertion, puis en remontant de la feuille vers la racine pour éclater les nœuds
Fig. 3.6 Un exemple d’insertion dans un arbre-B prudent. Ici m = 2, les nœuds contiennent
entre 1 et 3 clés. La clé médiane en rouge remonte dans le nœud parent
69
plein contient un nombre impair de clés) et avec deux fils, et la hauteur de l’arbre
augmente de 1.
– Si la racine n’est pas pleine, elle n’est pas modifiée, et l’algorithme continue le
long de la branche allant de la racine à la feuille d’insertion.
– Dès que le pointeur rencontre un nœud plein, la clé médiane remonte dans le
nœud parent (qui n’est pas plein, car l’algorithme est déjà passé), le nœud plein
est éclaté en deux nœuds, et ses enfants sont répartis entre ces deux nouveaux
nœuds.
– Finalement, l’algorithme parvient dans une feuille, il l’éclate si nécessaire, et
l’insertion a lieu dans une feuille non pleine.
Dans cet algorithme, les nœuds pleins sont traités avant l’insertion proprement dite.
Cet algorithme, que nous appelons pour cette raison prudent, est présenté dans la
section A.3 ; cf. aussi le livre de Cormen et al. [50]. Avec cette méthode, une feuille
pleine donne naissance à deux feuilles contenant chacune m−1 clés, puis la nouvelle
clé est insérée, comme dans la figure 3.6. L’algorithme descend de la racine vers
une feuille de l’arbre, et peut conduire à éclater des nœuds internes pleins, alors que
l’insertion se ferait dans une feuille non pleine. Par exemple, l’insertion de la clé 87
dans l’arbre-B de la figure 3.5 conduit à éclater le troisième fils de la racine, alors
que l’insertion se fait dans une feuille ne contenant qu’une seule clé.
Construction algorithmique (insertion aux feuilles) optimiste Dans une variante
optimiste de cet algorithme, les nœuds pleins sont traités après avoir trouvé la
place d’insertion d’une nouvelle clé. Dans un tel arbre-B optimiste de paramètre m,
les nœuds contiennent maintenant entre m et 2m clés. Imaginons qu’une insertion
concerne une certaine feuille. Si elle n’est pas pleine, l’insertion a lieu. Sinon, c’est
qu’elle contient 2m clés. La clé médiane, parmi ces 2m clés et la nouvelle clé,
remonte dans le nœud parent et la feuille pleine éclate en deux feuilles contenant
chacune m clés. Si le nœud parent est plein, une clé est poussée vers le nœud grandparent, etc., et ceci jusqu’à la racine, si nécessaire. Si la racine est pleine, elle est
éclatée, une nouvelle racine est créée contenant une clé, et la hauteur de l’arbre
augmente de 1.
Cet algorithme procède ainsi de la racine vers les feuilles pour trouver la place
d’insertion, puis en remontant de la feuille vers la racine pour éclater les nœuds
Fig. 3.6 Un exemple d’insertion dans un arbre-B prudent. Ici m = 2, les nœuds contiennent
entre 1 et 3 clés. La clé médiane en rouge remonte dans le nœud parent