A random tree is defined as an elementary event w of a probability space (W , F, P). The probability P depends on the random model of trees which is analyzed. The main results concerning the GaltonWatson processes are recalled. If for nÎN, Z_{n} is the number of individuals of the Nth generation and m the average number of children generated by an individual, it is shown that the martingale (Z_{n}/m^{n}) plays an important role in the analysis of such processes.
The Catalan trees are seen as a particular case of GaltonWatson process. The height of a Catalan tree with n nodes is of the order C (n)^{1/2} (FlajoletOdlyzko) and the number of external leaves has a limiting distribution (KestenPittel).
The binary search trees are related to a branching random walk, hence to marked trees. The analysis of their height involves large deviations results for this random walk; for a binary search tree with n nodes, it is of the order C log n (Devroye, Biggins).
Z_{0}=1, Z_{n+1}= 

G_{i n}, 
U={Ø}È 

N^{*n} 
w=  {  Ø, 1 , 2, 3, 21, 211, 2111, 2112, 22, 221, 31, 311  }  . 
Finally, if uÎw, T_{u}(w) will denote the subtree containing the elements of w whose prefix is u. In the example of Figure 1,
T_{21}(w)=  {  Ø, 1 , 11, 12  }  . 
P 
æ ç ç è 

Z_{n}<+¥ 
ö ÷ ÷ ø 
=q, 
2n 
n 
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.