202
5 Approche probabiliste
Fig. 5.4 Un exemple d’arbre planaire à 7 = n + 1 nœuds et le chemin de Dyck associé par
contour. Le parcours d’arbre est le parcours en profondeur ou parcours préfixe. La fonction de
contour C n est dessinée à droite. Exceptionnellement, l’arbre est dessiné poussant vers le haut, afin
que l’excursion à droite soit naturellement positive
(a) Arbres sous le modèle de Catalan et chemins de Dyck
Un chemin de Dyck de longueur 2n, est une fonction f continue, positive ou
nulle sur [0, 2n] telle que f (0) = f (2n) = 0 et f est affine par morceaux, de pente
+1 ou −1 sur chaque intervalle [k, k + 1], k = 0, . . . , 2n − 1.
Les arbres binaires de taille n sont en bijection avec les arbres planaires de taille
n+1. Et ceux-ci sont en bijection avec les chemins de Dyck, de la manière suivante,
grâce à la fonction de contour : heuristiquement, pour un arbre à n + 1 nœuds
τ n+1 , la fonction de contour C n est l’altitude d’une fourmi qui part de la racine
et visite les nœuds de l’arbre le long des branches, dans l’ordre du parcours en
profondeur. Voir la figure 5.4 où l’arbre pousse vers le haut (!) pour le confort
d’une excursion positive. Formellement, soit F n la fonction de {0, . . . , 2n} dans
l’ensemble des nœuds de l’arbre définie par récurrence par : F n (0) = ε la racine
de l’arbre. Pour k ≥ 0, si le nœud F n (k) a des enfants non encore visités (i.e., pas
dans la liste F n (0), . . . , F n (k − 1)), alors F n (k + 1) est le nœud le plus à gauche
des enfants non visités de F n (k). Si tous les enfants de F n (k) ont été visités, alors
F n (k + 1) est le parent de F n (k), et ce, jusqu’au retour à la racine. Puis la fonction
de contour C n est définie par : ∀k = 0, . . . , 2n,
C n (k) = |F n (k)|,
(comme d’habitude, |F n (k)| désigne la longueur du mot F n (k)) et C n est rendue
continue, affine par morceaux, par interpolation entre les points d’abscisses entières.
Il est alors clair que la hauteur de l’arbre est égale au maximum du chemin de Dyck :
h(τ n ) = max
0≤k≤2n
C n (k).
(b) Convergence des chemins de Dyck vers l’excursion brownienne
Du côté de l’aléa, la loi uniforme sur les arbres de taille n induit la loi uniforme
sur les chemins de Dyck de longueur 2n. Un chemin de Dyck associé à un arbre
5 Approche probabiliste
Fig. 5.4 Un exemple d’arbre planaire à 7 = n + 1 nœuds et le chemin de Dyck associé par
contour. Le parcours d’arbre est le parcours en profondeur ou parcours préfixe. La fonction de
contour C n est dessinée à droite. Exceptionnellement, l’arbre est dessiné poussant vers le haut, afin
que l’excursion à droite soit naturellement positive
(a) Arbres sous le modèle de Catalan et chemins de Dyck
Un chemin de Dyck de longueur 2n, est une fonction f continue, positive ou
nulle sur [0, 2n] telle que f (0) = f (2n) = 0 et f est affine par morceaux, de pente
+1 ou −1 sur chaque intervalle [k, k + 1], k = 0, . . . , 2n − 1.
Les arbres binaires de taille n sont en bijection avec les arbres planaires de taille
n+1. Et ceux-ci sont en bijection avec les chemins de Dyck, de la manière suivante,
grâce à la fonction de contour : heuristiquement, pour un arbre à n + 1 nœuds
τ n+1 , la fonction de contour C n est l’altitude d’une fourmi qui part de la racine
et visite les nœuds de l’arbre le long des branches, dans l’ordre du parcours en
profondeur. Voir la figure 5.4 où l’arbre pousse vers le haut (!) pour le confort
d’une excursion positive. Formellement, soit F n la fonction de {0, . . . , 2n} dans
l’ensemble des nœuds de l’arbre définie par récurrence par : F n (0) = ε la racine
de l’arbre. Pour k ≥ 0, si le nœud F n (k) a des enfants non encore visités (i.e., pas
dans la liste F n (0), . . . , F n (k − 1)), alors F n (k + 1) est le nœud le plus à gauche
des enfants non visités de F n (k). Si tous les enfants de F n (k) ont été visités, alors
F n (k + 1) est le parent de F n (k), et ce, jusqu’au retour à la racine. Puis la fonction
de contour C n est définie par : ∀k = 0, . . . , 2n,
C n (k) = |F n (k)|,
(comme d’habitude, |F n (k)| désigne la longueur du mot F n (k)) et C n est rendue
continue, affine par morceaux, par interpolation entre les points d’abscisses entières.
Il est alors clair que la hauteur de l’arbre est égale au maximum du chemin de Dyck :
h(τ n ) = max
0≤k≤2n
C n (k).
(b) Convergence des chemins de Dyck vers l’excursion brownienne
Du côté de l’aléa, la loi uniforme sur les arbres de taille n induit la loi uniforme
sur les chemins de Dyck de longueur 2n. Un chemin de Dyck associé à un arbre