164
4 Approche combinatoire
4.4.2 Arbres-B
Comme pour les arbres 2–3, nous commençons par donner un encadrement de la
hauteur d’un arbre-B en fonction du nombre de clés qu’il contient ; nous calculerons
ensuite le nombre d’arbres-B de hauteur fixée. À chaque fois, nous ferons les calculs
pour l’une seule des deux variantes (arbres prudents ou optimistes) présentées en
section 3.2.2, l’autre variante se traitant de manière similaire.
Hauteur d’un arbre-B
Un raisonnement similaire à celui que nous avons fait en section 4.4.1 pour les
arbres 2–3, qui sont des arbres-B optimistes pour m = 1, nous conduit à regarder
les arbres-B « extrémaux » pour établir une relation entre le nombre de clés d’un
arbre et sa hauteur. Il y a cependant une différence avec les arbres 2–3 : le nombre
minimal de clés dans un nœud est différent, selon qu’il s’agit de la racine ou d’une
autre nœud.
Calculons d’abord 10 le nombre minimal n min de clés contenues dans un arbre-B
(cf. section 3.2.2) de paramètre m et de hauteur h : cet arbre doit avoir une seule clé
à la racine, et m − 1 clés dans chacun des autres nœuds. Chaque nœud interne a m
enfants, à l’exception de la racine qui en a deux, et le nombre de nœuds à profondeur
(1 ≤ ≤ h) est 2m . Nous obtenons
n min = 1 +
h
2m
(m − 1) = 2 m
h
− 1.
De même, le nombre maximal n max de clés pouvant être stockées dans un arbre
de hauteur h est obtenu lorsque tous les nœuds, y compris la racine, ont 2m − 1
clés. Chaque nœud interne, y compris la racine, a donc 2m enfants, et le nombre de
nœuds à profondeur (0 ≤ ≤ h ) est égal à (2m) ; donc
n max =
h
(2m)
(2m − 1) = (2m)
h+1
− 1.
Nous en déduisons que
2 m
h
− 1 ≤ n ≤ (2m)
h+1
− 1.
10 Nous faisons le calcul ici pour la version prudente.