1.1 Arbres non marqués
11
En revanche, les arbres binaires de C, s’ils sont des arbres préfixes, ne sont pas
des arbres planaires, au sens des définitions 1.1 et 1.8 : en effet, dans le cadre des
arbres planaires on ne peut distinguer d’enfant gauche et d’enfant droit quand il y a
un seul enfant, alors que les arbres binaires et sont distincts. Il serait possible de
voir les arbres binaires comme des arbres planaires marqués : chaque nœud serait
marqué par une étiquette « gauche » ou « droit ».
1.1.3 Bijection entre les arbres planaires et les arbres binaires
Les arbres planaires sont en bijection avec les arbres binaires par la bijection
« fille aînée–sœur cadette » (appelée aussi lemme de correspondance naturelle
ou correspondance par rotation), que nous détaillons maintenant. Certains auteurs
désignent d’ailleurs par « arbres de Catalan » ce que nous avons appelé « arbres
planaires », ces deux ensembles étant en bijection.
Nous présentons un exemple de transformation d’arbre planaire en arbre binaire
dans les figures 1.7, 1.8, 1.9, et 1.10. Pour faciliter la compréhension, nous avons
indiqué le numérotage canonique des nœuds, mais la bijection est indépendante de
l’existence de ces numéros.
Définissons formellement la transformation – appelons-la φ – qui fait passer
d’un arbre planaire τ ou de l’arbre vide à un arbre binaire φ(τ ). Elle est définie
récursivement comme suit.
Fig. 1.7 Un arbre planaire à 14 nœuds
Fig. 1.8 Le même arbre, avec les liens « fille aînée » en bleu et « sœur cadette » en vert
11
En revanche, les arbres binaires de C, s’ils sont des arbres préfixes, ne sont pas
des arbres planaires, au sens des définitions 1.1 et 1.8 : en effet, dans le cadre des
arbres planaires on ne peut distinguer d’enfant gauche et d’enfant droit quand il y a
un seul enfant, alors que les arbres binaires et sont distincts. Il serait possible de
voir les arbres binaires comme des arbres planaires marqués : chaque nœud serait
marqué par une étiquette « gauche » ou « droit ».
1.1.3 Bijection entre les arbres planaires et les arbres binaires
Les arbres planaires sont en bijection avec les arbres binaires par la bijection
« fille aînée–sœur cadette » (appelée aussi lemme de correspondance naturelle
ou correspondance par rotation), que nous détaillons maintenant. Certains auteurs
désignent d’ailleurs par « arbres de Catalan » ce que nous avons appelé « arbres
planaires », ces deux ensembles étant en bijection.
Nous présentons un exemple de transformation d’arbre planaire en arbre binaire
dans les figures 1.7, 1.8, 1.9, et 1.10. Pour faciliter la compréhension, nous avons
indiqué le numérotage canonique des nœuds, mais la bijection est indépendante de
l’existence de ces numéros.
Définissons formellement la transformation – appelons-la φ – qui fait passer
d’un arbre planaire τ ou de l’arbre vide à un arbre binaire φ(τ ). Elle est définie
récursivement comme suit.
Fig. 1.7 Un arbre planaire à 14 nœuds
Fig. 1.8 Le même arbre, avec les liens « fille aînée » en bleu et « sœur cadette » en vert