Arbres et processus de branchement

Un arbre est d{\'e}fini comme un {\'e}v{\'e}nement {\'e}l{\'e}mentaire $\omega$ d'un espace de probabilit{\'e} $(\Omega , {\cal F}, \P)$, ${\cal F}$ et $\P$ variant suivant le mod{\`e}le {\'e}tudi{\'e}. Les r{\'e}sultats principaux sur les processus de Galton-Watson sont rappel{\'e}s, notamment la martingale $Z_n/m^n$ (o{\`u} $Z_n$ est le nombre d'individus de la n-i{\`e}me g{\'e}n{\'e}ration et $m$ est la moyenne de la loi de reproduction) ainsi que l'arbre de Galton-Watson ``biais{\'e}''.

Les arbres de Catalan sont vus comme un cas particulier des arbres de Galton-Watson critiques. La hauteur $H_n$ d'un arbre de Catalan {\`a} $n$ n\oe{}uds est en $C \sqrt n$ (cf Flajolet-Odlyzko), le nombre de feuilles finales a une loi limite (cf Kesten-Pittel).

Les arbres binaires de recherche sont reli{\'e}s {\`a} une marche al{\'e}atoire avec branchement, donc {\`a} des arbres marqu{\'e}s\,;~leur hauteur est {\'e}troitement reli{\'e}e aux grandes d{\'e}viations de cette marche\,;~pour un arbre binaire de recherche {\`a} $n$ n\oe{}uds, $H_n$ est en $C \log n$ (cf Devroye, Biggins).