4.4 Arbres équilibrés
165
En inversant ces deux relations, nous obtenons un encadrement de la hauteur. Un
calcul parallèle peut bien sûr être fait pour les arbres-B optimistes. D’où le théorème
suivant.
Théorème 4.25
i) Le nombre n de clés pouvant être stockées dans un arbre-B prudent de
paramètre m et de hauteur h est tel que
2 m
h
− 1 ≤ n ≤ (2m)
h+1
− 1.
ii) Soit τ un arbre-B prudent de paramètre m et contenant n clés ; sa hauteur h(τ )
vérifie
log 2m (n + 1) − 1 ≤ h(τ ) ≤ log m
n + 1
2
.
iii) Le nombre n de clés pouvant être stockées dans un arbre-B optimiste de
paramètre m et de hauteur h est tel que
2 (m + 1)
h
− 1 ≤ n ≤ (2m + 1)
h+1
− 1.
iv) Soit τ un arbre-B optimiste de paramètre m et contenant n clés ; sa hauteur h(τ )
vérifie
log 2m+1 (n + 1) − 1 ≤ h(τ ) ≤ log m+1
n + 1
2
.
Remarque 4.26 En posant m = 1 et en regardant les arbres-B optimistes,
nous retrouvons bien les encadrements relatifs aux arbres 2–3 donnés dans le
théorème 4.19.
Nombre d’arbres-B de hauteur fixée
Comme nous venons de le faire pour les arbres 2–3, nous cherchons ici à dénombrer
les arbres-B de hauteur donnée h. Les calculs que nous avons faits pour les arbres
2–3 (cf. la preuve de la proposition 4.20) se transposent sans difficulté au cas des
arbres-B, et nous les détaillons ci-dessous pour la version optimiste – rappelons
qu’un arbre 2–3 est un arbre-B optimiste de paramètre 1.
Pour un tel arbre de paramètre m, le nombre maximal de clés dans un nœud est
égal à 2m. La racine a entre 1 et 2m clés et donc entre 2 et 2m + 1 enfants, et les
autres nœuds entre m et 2m clés et entre m + 1 et 2m + 1 enfants. Pour tenir compte
de la différence entre la racine et les autres nœuds, nous définissons b h comme le
nombre d’arbres-B de hauteur h, et c h comme le nombre de sous-arbres (stricts) de
hauteur h. Nous avons alors b 0 = 2m : un arbre de hauteur nulle a un seul nœud,
165
En inversant ces deux relations, nous obtenons un encadrement de la hauteur. Un
calcul parallèle peut bien sûr être fait pour les arbres-B optimistes. D’où le théorème
suivant.
Théorème 4.25
i) Le nombre n de clés pouvant être stockées dans un arbre-B prudent de
paramètre m et de hauteur h est tel que
2 m
h
− 1 ≤ n ≤ (2m)
h+1
− 1.
ii) Soit τ un arbre-B prudent de paramètre m et contenant n clés ; sa hauteur h(τ )
vérifie
log 2m (n + 1) − 1 ≤ h(τ ) ≤ log m
n + 1
2
.
iii) Le nombre n de clés pouvant être stockées dans un arbre-B optimiste de
paramètre m et de hauteur h est tel que
2 (m + 1)
h
− 1 ≤ n ≤ (2m + 1)
h+1
− 1.
iv) Soit τ un arbre-B optimiste de paramètre m et contenant n clés ; sa hauteur h(τ )
vérifie
log 2m+1 (n + 1) − 1 ≤ h(τ ) ≤ log m+1
n + 1
2
.
Remarque 4.26 En posant m = 1 et en regardant les arbres-B optimistes,
nous retrouvons bien les encadrements relatifs aux arbres 2–3 donnés dans le
théorème 4.19.
Nombre d’arbres-B de hauteur fixée
Comme nous venons de le faire pour les arbres 2–3, nous cherchons ici à dénombrer
les arbres-B de hauteur donnée h. Les calculs que nous avons faits pour les arbres
2–3 (cf. la preuve de la proposition 4.20) se transposent sans difficulté au cas des
arbres-B, et nous les détaillons ci-dessous pour la version optimiste – rappelons
qu’un arbre 2–3 est un arbre-B optimiste de paramètre 1.
Pour un tel arbre de paramètre m, le nombre maximal de clés dans un nœud est
égal à 2m. La racine a entre 1 et 2m clés et donc entre 2 et 2m + 1 enfants, et les
autres nœuds entre m et 2m clés et entre m + 1 et 2m + 1 enfants. Pour tenir compte
de la différence entre la racine et les autres nœuds, nous définissons b h comme le
nombre d’arbres-B de hauteur h, et c h comme le nombre de sous-arbres (stricts) de
hauteur h. Nous avons alors b 0 = 2m : un arbre de hauteur nulle a un seul nœud,