Chapitre 4
Approche combinatoire
Dans ce chapitre, nous nous intéressons aux différentes familles d’arbres définies
au chapitre 1, essentiellement pour les dénombrer ; souvent nous obtenons aussi les
premiers moments (espérance et variance) de la distribution de divers paramètres
définis sur ces arbres. Nous étudions d’abord plusieurs types d’arbres planaires : les
arbres binaires en section 4.1 et une généralisation aux familles simples d’arbres en
section 4.2, puis les tas en section 4.3 et les arbres équilibrés : arbres 2–3 et arbres-B,
en section 4.4. Nous terminons par les arbres non planaires en section 4.5.
Pour une classe d’arbres donnée, nous fixons le plus souvent la taille des arbres,
parfois leur hauteur, ce qui définit un sous-ensemble E d’arbres de cette classe. La
première étape est d’évaluer la cardinalité de E ; nous pouvons ensuite envisager
l’étude de la distribution d’un paramètre donné dans le cas où la distribution sur les
arbres de E est uniforme. C’est ce que nous avons défini en section 2.1.1 et appelé
le « modèle de Catalan » sur les arbres, et c’est ce modèle que nous utilisons dans
tout ce chapitre.
Certains arbres (les arbres binaires, planaires et les arbres de Cayley) sous
le modèle de Catalan peuvent être vus comme des arbres de Galton-Watson
conditionnés par leur taille (cf. la section 5.2) ; c’est alors une approche probabiliste
qui permettra de déterminer le comportement asymptotique de la hauteur de ces
arbres, en section 5.2.3.
4.1 Les arbres binaires
Rappelons brièvement ce qui a été vu dans la section 1.1.2 : les arbres binaires,
appelés parfois arbres de Catalan, sont définis soit comme ensemble de mots
sur l’alphabet {0, 1}, soit récursivement comme classe combinatoire : la classe
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_4
121
Approche combinatoire
Dans ce chapitre, nous nous intéressons aux différentes familles d’arbres définies
au chapitre 1, essentiellement pour les dénombrer ; souvent nous obtenons aussi les
premiers moments (espérance et variance) de la distribution de divers paramètres
définis sur ces arbres. Nous étudions d’abord plusieurs types d’arbres planaires : les
arbres binaires en section 4.1 et une généralisation aux familles simples d’arbres en
section 4.2, puis les tas en section 4.3 et les arbres équilibrés : arbres 2–3 et arbres-B,
en section 4.4. Nous terminons par les arbres non planaires en section 4.5.
Pour une classe d’arbres donnée, nous fixons le plus souvent la taille des arbres,
parfois leur hauteur, ce qui définit un sous-ensemble E d’arbres de cette classe. La
première étape est d’évaluer la cardinalité de E ; nous pouvons ensuite envisager
l’étude de la distribution d’un paramètre donné dans le cas où la distribution sur les
arbres de E est uniforme. C’est ce que nous avons défini en section 2.1.1 et appelé
le « modèle de Catalan » sur les arbres, et c’est ce modèle que nous utilisons dans
tout ce chapitre.
Certains arbres (les arbres binaires, planaires et les arbres de Cayley) sous
le modèle de Catalan peuvent être vus comme des arbres de Galton-Watson
conditionnés par leur taille (cf. la section 5.2) ; c’est alors une approche probabiliste
qui permettra de déterminer le comportement asymptotique de la hauteur de ces
arbres, en section 5.2.3.
4.1 Les arbres binaires
Rappelons brièvement ce qui a été vu dans la section 1.1.2 : les arbres binaires,
appelés parfois arbres de Catalan, sont définis soit comme ensemble de mots
sur l’alphabet {0, 1}, soit récursivement comme classe combinatoire : la classe
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_4
121