68
3 Arbres, algorithmes et données
Fig. 3.5 Un arbre-B de recherche prudent de paramètre m = 2 et contenant 30 clés. Cet arbre
a 4 nœuds internes et 9 feuilles ; 2 nœuds contiennent le nombre minimal (1) de clés et ont deux
enfants, 5 nœuds contiennent 2 clés et ont trois enfants, et 6 nœuds sont pleins : ils contiennent
le nombre maximal (3) de clés et ont quatre enfants. Nous avons omis les 31 feuilles de l’arbre
complété, correspondant aux possibilités d’insertion
Dans un arbre-B prudent (resp. optimiste) de paramètre m, la racine a entre 1 et
2m − 1 (resp. 2m) clés et chaque autre nœud contient entre m − 1 et 2m − 1 (resp.
entre m et 2m) clés.
Comme pour les arbres binaires de recherche et les arbres 2–3, l’arbre est
complété aux feuilles par les possibilités d’insertion, représentées par des . Par
ailleurs, tout comme pour les autres arbres de recherche rencontrés jusqu’à présent,
il existe un marquage canonique des arbres-B (figure 3.5).
Construction algorithmique (insertion aux feuilles) prudente Nous pouvons
voir un arbre-B prudent comme obtenu par une suite d’insertions aux feuilles dans
un arbre initialement vide. La première clé insérée provoque la création d’une feuille
qui est la racine de l’arbre. Les 2m − 1 premières clés vont à la racine, et ensuite
chaque insertion se fait récursivement dans un des sous-arbres de la racine. Lorsque
la feuille concernée par l’insertion contient au plus 2m − 2 clés, il est possible
d’ajouter la nouvelle clé ; si elle contient déjà 2m − 1 clés, elle est pleine, et il
faut alors modifier l’arbre de façon à dégager une possibilité d’insertion de cette
nouvelle clé. Cela ne peut pas se faire simplement en remplaçant une feuille par un
nœud interne et des enfants : ces enfants ne seraient pas au même niveau que les
autres. Il est donc nécessaire de rééquilibrer l’arbre, et cela en transférant une des
clés de la feuille pleine vers son parent – bien évidemment, ceci n’est possible que
si ce dernier nœud n’est pas lui-même plein ! D’où l’algorithme suivant, dit prudent
car il évite d’avoir à insérer une clé dans un nœud plein :
– Lors de la recherche de la feuille où insérer, une branche de l’arbre est
déterminée. L’algorithme procède en descendant de la racine à la feuille le long
de cette branche, et commence par contrôler la racine. Dans cet algorithme, les
nœuds pleins sont traités avant l’insertion proprement dite.
– Si la racine est pleine, elle est éclatée, une nouvelle racine est créée avec une
seule clé qui est la médiane de l’ancienne racine (rappelons-nous qu’un nœud
3 Arbres, algorithmes et données
Fig. 3.5 Un arbre-B de recherche prudent de paramètre m = 2 et contenant 30 clés. Cet arbre
a 4 nœuds internes et 9 feuilles ; 2 nœuds contiennent le nombre minimal (1) de clés et ont deux
enfants, 5 nœuds contiennent 2 clés et ont trois enfants, et 6 nœuds sont pleins : ils contiennent
le nombre maximal (3) de clés et ont quatre enfants. Nous avons omis les 31 feuilles de l’arbre
complété, correspondant aux possibilités d’insertion
Dans un arbre-B prudent (resp. optimiste) de paramètre m, la racine a entre 1 et
2m − 1 (resp. 2m) clés et chaque autre nœud contient entre m − 1 et 2m − 1 (resp.
entre m et 2m) clés.
Comme pour les arbres binaires de recherche et les arbres 2–3, l’arbre est
complété aux feuilles par les possibilités d’insertion, représentées par des . Par
ailleurs, tout comme pour les autres arbres de recherche rencontrés jusqu’à présent,
il existe un marquage canonique des arbres-B (figure 3.5).
Construction algorithmique (insertion aux feuilles) prudente Nous pouvons
voir un arbre-B prudent comme obtenu par une suite d’insertions aux feuilles dans
un arbre initialement vide. La première clé insérée provoque la création d’une feuille
qui est la racine de l’arbre. Les 2m − 1 premières clés vont à la racine, et ensuite
chaque insertion se fait récursivement dans un des sous-arbres de la racine. Lorsque
la feuille concernée par l’insertion contient au plus 2m − 2 clés, il est possible
d’ajouter la nouvelle clé ; si elle contient déjà 2m − 1 clés, elle est pleine, et il
faut alors modifier l’arbre de façon à dégager une possibilité d’insertion de cette
nouvelle clé. Cela ne peut pas se faire simplement en remplaçant une feuille par un
nœud interne et des enfants : ces enfants ne seraient pas au même niveau que les
autres. Il est donc nécessaire de rééquilibrer l’arbre, et cela en transférant une des
clés de la feuille pleine vers son parent – bien évidemment, ceci n’est possible que
si ce dernier nœud n’est pas lui-même plein ! D’où l’algorithme suivant, dit prudent
car il évite d’avoir à insérer une clé dans un nœud plein :
– Lors de la recherche de la feuille où insérer, une branche de l’arbre est
déterminée. L’algorithme procède en descendant de la racine à la feuille le long
de cette branche, et commence par contrôler la racine. Dans cet algorithme, les
nœuds pleins sont traités avant l’insertion proprement dite.
– Si la racine est pleine, elle est éclatée, une nouvelle racine est créée avec une
seule clé qui est la médiane de l’ancienne racine (rappelons-nous qu’un nœud