158
4 Approche combinatoire
4.4 Arbres équilibrés
Dans cette section, nous nous intéressons aux arbres équilibrés (arbres 2–3 et arbresB) d’un point de vue combinatoire. Ces arbres sont marqués, et nous nous posons
des questions telles que dénombrer les arbres avec un nombre donné de clés ou
de nœuds, ou les arbres de hauteur donnée, y compris lorsque les nœuds diffèrent
suivant le nombre de clés qu’ils contiennent. Ce qui importe ici est lié à la simple
existence des clés, i.e., au fait que les arbres soient marqués. Le comportement de
ces arbres, en tant qu’arbres de recherche, sera étudié dans le chapitre 9 en mettant
l’accent sur le fait qu’il y a plusieurs types de feuilles, car les nœuds diffèrent suivant
le nombre de clés qu’ils contiennent.
Nous étudions en section 4.4.1 les arbres 2–3 du point de vue de leur hauteur,
en en donnant un encadrement puis en considérant le nombre d’arbres de hauteur
donnée. La question de dénombrer les arbres 2–3 contenant n clés, sans restriction
sur leur hauteur, est nettement plus complexe et nous ne l’abordons que brièvement
à la fin de cette section. Nous passons ensuite en section 4.4.2 aux arbres–B,
pour lesquels nous donnons également un encadrement de la hauteur et le nombre
d’arbres de hauteur donnée.
4.4.1 Arbres 2–3
Nous donnons d’abord un encadrement de la hauteur h d’un arbre 2–3 en fonction
du nombre n de clés qu’il contient. La hauteur est la profondeur d’une feuille (les
feuilles sont ici toutes à la même profondeur). Rappelons qu’un arbre réduit à sa
racine est de hauteur 0.
Hauteur des arbres 2–3
À hauteur donnée, deux types d’arbres donnent, le premier un nombre de clés
minimal, le second un nombre de clés maximal. Regardons d’abord les arbres 2–
3 de nombre de clés minimal pour une hauteur donnée. Un tel arbre a exactement
une clé dans chaque nœud, et sa forme est celle d’un arbre binaire saturé (cf.
définition 1.26). Un arbre saturé de hauteur h a 2 h+1 − 1 nœuds contenant chacun
une seule clé (figure 4.13).
De même, dans un arbre de hauteur h et dont le nombre de clés est maximal, il y
a 3 nœuds à chaque niveau . Le nombre total de nœuds dans un arbre de hauteur h
est
3 h+1 −1
2
. Chacun des nœuds a deux clés ; le nombre de clés d’un tel arbre est donc
n = 3 h+1 − 1. D’où un encadrement de n en fonction de h puis, en l’inversant, un
nouvel encadrement, cette fois de h en fonction de n. Nous résumons ces résultats
dans le théorème suivant.
4 Approche combinatoire
4.4 Arbres équilibrés
Dans cette section, nous nous intéressons aux arbres équilibrés (arbres 2–3 et arbresB) d’un point de vue combinatoire. Ces arbres sont marqués, et nous nous posons
des questions telles que dénombrer les arbres avec un nombre donné de clés ou
de nœuds, ou les arbres de hauteur donnée, y compris lorsque les nœuds diffèrent
suivant le nombre de clés qu’ils contiennent. Ce qui importe ici est lié à la simple
existence des clés, i.e., au fait que les arbres soient marqués. Le comportement de
ces arbres, en tant qu’arbres de recherche, sera étudié dans le chapitre 9 en mettant
l’accent sur le fait qu’il y a plusieurs types de feuilles, car les nœuds diffèrent suivant
le nombre de clés qu’ils contiennent.
Nous étudions en section 4.4.1 les arbres 2–3 du point de vue de leur hauteur,
en en donnant un encadrement puis en considérant le nombre d’arbres de hauteur
donnée. La question de dénombrer les arbres 2–3 contenant n clés, sans restriction
sur leur hauteur, est nettement plus complexe et nous ne l’abordons que brièvement
à la fin de cette section. Nous passons ensuite en section 4.4.2 aux arbres–B,
pour lesquels nous donnons également un encadrement de la hauteur et le nombre
d’arbres de hauteur donnée.
4.4.1 Arbres 2–3
Nous donnons d’abord un encadrement de la hauteur h d’un arbre 2–3 en fonction
du nombre n de clés qu’il contient. La hauteur est la profondeur d’une feuille (les
feuilles sont ici toutes à la même profondeur). Rappelons qu’un arbre réduit à sa
racine est de hauteur 0.
Hauteur des arbres 2–3
À hauteur donnée, deux types d’arbres donnent, le premier un nombre de clés
minimal, le second un nombre de clés maximal. Regardons d’abord les arbres 2–
3 de nombre de clés minimal pour une hauteur donnée. Un tel arbre a exactement
une clé dans chaque nœud, et sa forme est celle d’un arbre binaire saturé (cf.
définition 1.26). Un arbre saturé de hauteur h a 2 h+1 − 1 nœuds contenant chacun
une seule clé (figure 4.13).
De même, dans un arbre de hauteur h et dont le nombre de clés est maximal, il y
a 3 nœuds à chaque niveau . Le nombre total de nœuds dans un arbre de hauteur h
est
3 h+1 −1
2
. Chacun des nœuds a deux clés ; le nombre de clés d’un tel arbre est donc
n = 3 h+1 − 1. D’où un encadrement de n en fonction de h puis, en l’inversant, un
nouvel encadrement, cette fois de h en fonction de n. Nous résumons ces résultats
dans le théorème suivant.