4.4 Arbres équilibrés
159
Fig. 4.13 Les deux formes d’arbres 2–3 de hauteur h = 3 (les feuilles sont donc à profondeur 3)
et avec les nombres minimal et maximal de nœuds
Fig. 4.14 Les 12 arbres 2–3 de recherche (marqués) de hauteur 1. Nous indiquons par des • les
clés présentes dans chaque nœud
Théorème 4.19
i) Le nombre n de clés pouvant être stockées dans un arbre 2–3 de hauteur h est
tel que
2
h+1
− 1 ≤ n ≤ 3
h+1
− 1.
ii) Soit τ un arbre 2–3 contenant n clés ; sa hauteur h(τ ) vérifie
log 3 (n + 1) ≤ h(τ ) + 1 ≤ log 2 (n + 1).
Nombre d’arbres 2–3 de hauteur fixée
Nous allons maintenant compter le nombre d’arbres 2–3 de hauteur donnée, en
suivant une approche due à Reingold [220] (figure 4.14).
159
Fig. 4.13 Les deux formes d’arbres 2–3 de hauteur h = 3 (les feuilles sont donc à profondeur 3)
et avec les nombres minimal et maximal de nœuds
Fig. 4.14 Les 12 arbres 2–3 de recherche (marqués) de hauteur 1. Nous indiquons par des • les
clés présentes dans chaque nœud
Théorème 4.19
i) Le nombre n de clés pouvant être stockées dans un arbre 2–3 de hauteur h est
tel que
2
h+1
− 1 ≤ n ≤ 3
h+1
− 1.
ii) Soit τ un arbre 2–3 contenant n clés ; sa hauteur h(τ ) vérifie
log 3 (n + 1) ≤ h(τ ) + 1 ≤ log 2 (n + 1).
Nombre d’arbres 2–3 de hauteur fixée
Nous allons maintenant compter le nombre d’arbres 2–3 de hauteur donnée, en
suivant une approche due à Reingold [220] (figure 4.14).