10
1 Botanique
Fig. 1.6 Un exemple d’arbre
binaire de taille 3 et de l’arbre
binaire complet associé, qui a
4 feuilles, 3 nœuds internes,
et est de taille 7
combinatoire atomique contenant un objet de taille 1, noté ◦ et appelé « nœud »
de l’arbre, telles que C vérifie l’équation récursive
C = E + (◦ × C × C).
(1.2)
Une telle classe est parfois appelée classe des arbres de Catalan. 5
Une classe combinatoire B est une classe d’arbres binaires complets lorsqu’il
existe deux classes combinatoires atomiques contenant chacune un objet de taille 1,
respectivement notés • et et appelés « nœud interne » et « nœud externe », telles
que B vérifie l’équation récursive
B = + (• × B × B).
(1.3)
Lorsque nous travaillons avec les arbres binaires, nous utilisons la terminologie
classique de sous-arbres gauche et droit, plutôt que de premier et deuxième sousarbre. Notons aussi que l’ensemble des arbres binaires contient l’arbre vide – alors
que ni l’ensemble des arbres planaires ni l’ensemble des arbres binaires complets
ne le contiennent.
Un arbre binaire se complète canoniquement en un arbre binaire complet 6 (en
anglais extended), de sorte qu’il y a une bijection entre les arbres binaires à n nœuds
et les arbres binaires complets à n nœuds internes et (n + 1) feuilles. Cette propriété
se démontre récursivement sur n.
Deux notions de taille sont illustrées dans la figure 1.6 : la taille d’un arbre binaire
(de C) est le nombre total de nœuds ; la taille d’un arbre binaire complet (de B) au
sens de la classe combinatoire est le nombre total de nœuds, c’est-à-dire 2n + 1
lorsqu’il y a n nœuds internes. On dit parfois qu’il est de taille n en ne comptant que
ses nœuds internes.
Remarque 1.12 L’ensemble B des arbres binaires complets est le sous-ensemble
P {0,2} de l’ensemble P des arbres planaires. Comme classe combinatoire, la classe
B des arbres binaires complets est isomorphe à la sous-classe P {0,2} de la classe P
des arbres planaires.
5 Le nom vient d’Eugène Catalan, à qui est associée l’énumération des arbres binaires par les
nombres dits (justement !) « de Catalan ».
6 Ne pas confondre avec ce que les probabilistes ou les algébristes appellent « l’arbre binaire
complet », qui est l’arbre infini dans lequel tout nœud a toujours deux fils.
1 Botanique
Fig. 1.6 Un exemple d’arbre
binaire de taille 3 et de l’arbre
binaire complet associé, qui a
4 feuilles, 3 nœuds internes,
et est de taille 7
combinatoire atomique contenant un objet de taille 1, noté ◦ et appelé « nœud »
de l’arbre, telles que C vérifie l’équation récursive
C = E + (◦ × C × C).
(1.2)
Une telle classe est parfois appelée classe des arbres de Catalan. 5
Une classe combinatoire B est une classe d’arbres binaires complets lorsqu’il
existe deux classes combinatoires atomiques contenant chacune un objet de taille 1,
respectivement notés • et et appelés « nœud interne » et « nœud externe », telles
que B vérifie l’équation récursive
B = + (• × B × B).
(1.3)
Lorsque nous travaillons avec les arbres binaires, nous utilisons la terminologie
classique de sous-arbres gauche et droit, plutôt que de premier et deuxième sousarbre. Notons aussi que l’ensemble des arbres binaires contient l’arbre vide – alors
que ni l’ensemble des arbres planaires ni l’ensemble des arbres binaires complets
ne le contiennent.
Un arbre binaire se complète canoniquement en un arbre binaire complet 6 (en
anglais extended), de sorte qu’il y a une bijection entre les arbres binaires à n nœuds
et les arbres binaires complets à n nœuds internes et (n + 1) feuilles. Cette propriété
se démontre récursivement sur n.
Deux notions de taille sont illustrées dans la figure 1.6 : la taille d’un arbre binaire
(de C) est le nombre total de nœuds ; la taille d’un arbre binaire complet (de B) au
sens de la classe combinatoire est le nombre total de nœuds, c’est-à-dire 2n + 1
lorsqu’il y a n nœuds internes. On dit parfois qu’il est de taille n en ne comptant que
ses nœuds internes.
Remarque 1.12 L’ensemble B des arbres binaires complets est le sous-ensemble
P {0,2} de l’ensemble P des arbres planaires. Comme classe combinatoire, la classe
B des arbres binaires complets est isomorphe à la sous-classe P {0,2} de la classe P
des arbres planaires.
5 Le nom vient d’Eugène Catalan, à qui est associée l’énumération des arbres binaires par les
nombres dits (justement !) « de Catalan ».
6 Ne pas confondre avec ce que les probabilistes ou les algébristes appellent « l’arbre binaire
complet », qui est l’arbre infini dans lequel tout nœud a toujours deux fils.