2. P. Chassaing, How many questions are needed to find out the maximum of a Random Walk An introduction to probability theory and its application

S. Gradshteyn and 1. M. Ryzhik, Table of Integral, Series and Products, p.319, 1980.

H. K. Hwang, A constant arising from the ano1ysis of algorithms for determining the maximum of a random walk, R.S.A, vol.10, pp.333-335, 1997.

S. E. Karatzas and . Shreve, Brownian Motion and Stochastic Calculus, 1988.

7. E. Novak and K. Ritter, Some Complexity Results for Zero Finding for Univariate Functions, Journal of Complexity, vol.9, issue.1, pp.15-40, 1993.
DOI : 10.1006/jcom.1993.1003

8. A. Odlyzko, Search for the maximum of a random walk, R.S.A, vol.6, pp.275-295, 1995.

9. D. Revuz and M. Yor, Continuous Martingales and Brownian Motion, p.10, 1990.

F. Loj, A. V. Spitzer-aho, J. E. Hopcroft, and J. D. Ullman, Principes of Random Walk REFERENCES CHAPITRE II References The design and analysis of computer algorithm, pp.61-352, 1964.

L. Alonso, E. M. Reingold, and R. Schott, The Average-Case Complexity of Determining the Majority, SIAM Journal on Computing, vol.26, issue.1, pp.1-14, 1997.
DOI : 10.1137/S0097539794275914

S. Asmussen, Applied probability and queues, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, 1987.

M. Avriel and D. J. Wilde, Optimal Search for a Maximum with Sequences of Simultaneous Function Evaluations, Management Science, vol.12, issue.9, pp.722-731, 1966.
DOI : 10.1287/mnsc.12.9.722

F. Baccelli and P. Brémaud, Elements of queuing theory. Palm-martingale calculus and stochastic recurrences, Applications of Mathematics, p.26, 1994.

P. Biane, J. Pitman, and M. .. Yor, Probability laws related to the Jacobi theta and Riemann zeta functions, and Brownian excursions, preprint, 1999.

P. 8}-biane and M. Yor, Valeurs principales associées aux temps locaux browniens, Bull. Sci. Maths, vol.111, pp.23-101, 1987.

P. 9}-biane and M. Yor, Quelques précisions sur le méandre brownien, Bull. Sci. Maths, vol.112, pp.101-109, 1988.

B. Lo}-bollobas, Random Graphs, p.12, 1985.

P. N}-carmona, F. Petit, J. Pitman, and M. Yor, On the laws of homogeneous functionals of the Brownian bridge, 1998.

P. Chassaing, Determining the majority: the biased case, The Annals of Applied Probability, vol.7, issue.2, pp.523-544, 1997.
DOI : 10.1214/aoap/1034625343

P. Chassaing, How many questions are needed to find out the maximum of a Random Walk, to appear in Stoch, Proc. and Applns, 1999.

P. Chassaing and J. F. Marckert, Parking functions, empirical processes and the width of rooted labeled trees, 1999.

R. Chapitre, P. Chassaing, J. F. Marckert, and M. Yor, On the harmonie mean of depths of nodes of a random tree

K. L. Chung, Excursions in Brownian motion, Arkiv f??r Matematik, vol.14, issue.1-2, pp.155-177, 1976.
DOI : 10.1007/BF02385832

W. Cunto and J. I. Munro, Average case selection, Journal of the ACM, vol.36, issue.2, pp.270-279, 1989.
DOI : 10.1145/62044.62047

L. Denisov, A Random Walk and a Wiener Process Near a Maximum, Theory of Probability & Its Applications, vol.28, issue.4, pp.821-824, 1983.
DOI : 10.1137/1128082

R. Durrett and D. L. , Functionals of Brownian Meander and Brownian Excursion, The Annals of Probability, vol.5, issue.1, pp.130-135, 1977.
DOI : 10.1214/aop/1176995896

P. Flajolet, Z. C. Gao, A. M. Odlyzko, and B. Richmond, The Distribution of Heights of Binary Trees and Other Simple Trees, Combinatorics, Probability and Computing, vol.30, issue.02, pp.145-156, 1993.
DOI : 10.1016/0377-0427(91)90197-R

URL : https://hal.archives-ouvertes.fr/inria-00076989

P. Flajolet and A. Odlyzko, The average height of binary trees and other simple trees, Journal of Computer and System Sciences, vol.25, issue.2, pp.171-213, 1982.
DOI : 10.1016/0022-0000(82)90004-6

URL : https://hal.archives-ouvertes.fr/inria-00076505

P. Flajolet and B. Salvy, Euler Sums and Contour Integral Representations, Experimental Mathematics, vol.25, issue.1, pp.1-15, 1998.
DOI : 10.1016/0022-314X(87)90012-6

URL : https://hal.archives-ouvertes.fr/inria-00073780

P. Flajolet, P. Poblete, and A. Viola, On the Analysis of Linear Probing Hashing, Algorithmica, vol.22, issue.4, 1998.
DOI : 10.1007/PL00009236

URL : https://hal.archives-ouvertes.fr/inria-00073424

R. Grübel and U. Rosier, Asymptotic distribution theory for Hoare's selection algorithm, Advances in Applied Probability, vol.3, issue.01, pp.252-269, 1996.
DOI : 10.1016/0022-0000(84)90009-6

B. Hajek, Locating the maximum of a simple random sequence by sequential search, IEEE Transactions on Information Theory, vol.33, issue.6, pp.877-88, 1987.
DOI : 10.1109/TIT.1987.1057378

H. K. Hwang, A constant arising from the analysis of algorithms for determining the maximum of a random walk, Random Structures and Algorithms, vol.10, issue.3, pp.333-335, 1997.
DOI : 10.1002/(SICI)1098-2418(199705)10:3<333::AID-RSA3>3.0.CO;2-X

M. Y. Kao, J. H. Reif, and S. R. Tate, Searching in an Unknown Environment: An Optimal Randomized Algorithm for the Cow-Path Problem, 4th ACM-SlAM Symp. Diserete Math, pp.441-447, 1993.
DOI : 10.1006/inco.1996.0092

D. P. Kennedy, The distribution of the maximum Brownian excursion, Journal of Applied Probability, vol.13, issue.02, pp.371-376, 1976.
DOI : 10.1007/BF00535106

F. B. Knight, On the random walk and Brownian motion, Transactions of the American Mathematical Society, vol.103, issue.2, pp.218-228, 1962.
DOI : 10.1090/S0002-9947-1962-0139211-2

F. B. Knight, Brownian local times and taboo processes, Transactions of the American Mathematical Society, vol.143, pp.173-185, 1969.
DOI : 10.1090/S0002-9947-1969-0253424-7

D. E. Knuth, The art of computer programming: sorting and searching, 1997.

N. H. Kuiper, Tests concering random points on a circle, Indag. Math, vol.22, pp.38-47, 1960.

D. Lépingle, Une remarque sur les lois de certains temps d'atteinte, Sém. Pro. XV, Uni. Str, Lect. Notes Math, vol.80, issue.850, pp.669-670, 1979.

G. Louchard, Kac's formula, levy's local time and brownian excursion, Journal of Applied Probability, vol.1, issue.03, pp.479-499, 1984.
DOI : 10.1214/aop/1176993927

G. Louchard, C. Kenyon, and R. Schott, Data Structures' Maxima, SIAM Journal on Computing, vol.26, issue.4, pp.1006-1042, 1997.
DOI : 10.1137/S0097539791196603

URL : https://hal.archives-ouvertes.fr/inria-00075166

J. F. Marckert, An average case quasi-optimal algorithm for the search of zeros of a random walk, 1997.

A. M. Odlyzko, Search for the maximum of a random walk, Random Structures and Aigorithms, pp.275-295, 1995.

J. W. Pitman, M. À. Yor, P. A. Meyer, and J. Neveu, Quelques identités en loi pour les processus de Bessel Hommage, Paris: Soc. Math. Fr., Astérisque, vol.236, pp.249-276, 1996.

J. W. Pitman and M. Yor, Path decomposition of a Brownian bridge related to the ratio of its maximum and amplitude, Prépub, 1998.

L. Plaskota, Noisy information and computational complexity, 1996.
DOI : 10.1017/CBO9780511600814

U. Rosier, A limit theorem for "Quicksort, RAIRO Inform. Thor. Appl, vol.25, issue.1, pp.85-100, 1991.

D. Revuz and M. Yor, Continuous Martingales and Brownian Motion, 1994.

R. Sedgewick and P. Flajolet, An introduction to the analysis of algorithms, 1996.

R. Sitaramachandra-rao, A formula of S, Ramanujan, J. Number Theory, vol.251, pp.1-19, 1987.

L. Smith, Honest bernoulli excursions, Journal of Applied Probability, vol.2, issue.03, pp.464-477, 1988.
DOI : 10.2307/3315033

D. Stoyan, Comparison methods for queues and other stochastic models, Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics, 1983.

F. Spitzer, The Wiener-Hopf equation whose kernel is a probability density, Duke math, J, vol.24, pp.327-343, 1957.

L. Tabics, A Bernoulli excursion and its various applications, Adv. in Appl. Probab, vol.23, issue.3, pp.557-585, 1991.

J. F. Traub, G. W. Wasilkowski, and H. Wozniakowski, Information-based complexity, 1988.

W. Vervaat, A relation between Brownian bridge and Brownian excursion, pp.143-149, 1979.

D. Williams, Path Decomposition and Continuity of Local Time for One-Dimensional Diffusions, I, Proc. London math. Soc., III. Ser, pp.738-768, 1974.
DOI : 10.1112/plms/s3-28.4.738

D. Williams, Diffusions, Markov processes, and martingales, Foundations. Wiley, vol.1, 1979.

S. Yakowitz and E. Lugosi, Random Search in the Presence of Noise, with Application to Machine Learning, SIAM Journal on Scientific and Statistical Computing, vol.11, issue.4, pp.702-712, 1990.
DOI : 10.1137/0911041

M. Yor, Some aspects of Brownian motion. Part II. Some recent martingale problems, Lectures in Mathematics, 1997.

2. D. Aldous, The continuum random tree. III Ann. of Probab, pp.248-289, 1993.

3. D. Aldous, Brownian Excursion Conditioned on Its Local Time, Electronic Communications in Probability, vol.3, issue.0, pp.79-90, 1998.
DOI : 10.1214/ECP.v3-996

4. P. Biane and M. Yor, Valeurs principales associées aux temps locaux browniens, Bull. Sei. Maths, vol.111, pp.23-33, 1987.

5. N. De-bruijn, D. Knuth, and S. Rice, The average height of planted plane trees, Graph Theory and Computing, pp.15-22, 1972.

6. P. Chassaing, How many questions are needed to find out the maximum of a Random Walk, press, Stoch. Proc. and Applns, 1999.

7. T. Cormen, E. Leiserson, and R. L. Rivest, Introduction to Algorithm, 1990.

8. P. Chassaing and J. F. Marckert, Parking functions, empirical processes and the width of rooted labe, 1999.

9. P. Chassaing, J. F. Marckert, and M. Yor, A Stochastically Quasi-Optimal Search Algorithm for the Maximum of the Simple Random Walk, 1999.
URL : https://hal.archives-ouvertes.fr/hal-00104835

1. E. Csàki and A. , A note on the stability of the local time of a wiener process, Stochastic Processes and their Applications, vol.25, pp.203-213, 1987.
DOI : 10.1016/0304-4149(87)90198-0

E. Llj, S. G. Csàki, and . Mohanty, Some joint distributions for conditional random walks, Cano J. Stat, vol.14, pp.19-28, 1986.

1. C. Donati-martin, Some remarks about the identity in law for the Bessel bridge rI ds, 1999.

M. Drmota and B. Gittenberger, On the profile of random trees, Random Structures and Algorithms, vol.10, issue.4, pp.421-466, 1997.
DOI : 10.1002/(SICI)1098-2418(199707)10:4<421::AID-RSA2>3.0.CO;2-W

1. R. Durrett and D. L. Iglehart, Functionals of Brownian Meander and Brownian Excursion, The Annals of Probability, vol.5, issue.1, pp.130-135, 1977.
DOI : 10.1214/aop/1176995896

1. P. Flajolet and A. Odlyzko, The average height of binary trees and other simple trees, Journal of Computer and System Sciences, vol.25, issue.2, 1982.
DOI : 10.1016/0022-0000(82)90004-6

URL : https://hal.archives-ouvertes.fr/inria-00076505

1. L. Gikhman and A. V. Skorohod, Introduction to the theory of random processes, 1969.

R. Chapitre-iii, Semi-martingales et grossissement d'une jiltration, 17J Th. Jeulin Lecture Notes in Mathematics, vol.833, 1980.

1. D. Kennedy, The distribution of the maximum Brownian excursion, Journal of Applied Probability, vol.13, issue.02, pp.371-376, 1976.
DOI : 10.1007/BF00535106

1. D. Knuth, The Art of Computer Programming, second edition, 1973.

2. J. Le and . Gall, Une approche élémentaire des théorèmes de décomposition de Williams, pp.447-464, 1986.

2. J. Marckert, An average case quasi optimal algorithm for the search of ail the zeros of a random walk, p.44, 1997.

2. A. Odlyzko, Search for the maximum of a random walk, Random Structures & Algorithms, vol.11, issue.2-3, pp.275-295, 1995.
DOI : 10.1007/978-94-011-3436-1

2. A. Renyi and G. Szekeres, On the height of trees, Journal of the Australian Mathematical Society, vol.4, issue.04, pp.497-507, 1967.
DOI : 10.1007/BF02559539

2. D. Revuz and M. Yor, Continuous martingales and Brownian motion, 1990.

2. P. Révész, Random walk in random and non-random environments, 1990.

2. R. Sedgewick, . Ph, and . Flajolet, An introduction to the analysis of algorithms, 1996.

. Takacs, A bernoulli excursion and its various applications, Advances in Applied Probability, vol.19, issue.03, pp.557-585, 1991.
DOI : 10.2307/2322249

L. Takacs, On the distribution of the number of vertices in layers of random trees, Journal of Applied Mathematics and Stochastic Analysis, vol.4, issue.3, pp.175-186, 1991.
DOI : 10.1155/S104895339100014X

2. L. Takacs, On the total heights of random rooted trees, Journal of Applied Probability, vol.174, issue.03, pp.543-556, 1992.
DOI : 10.1214/aop/1176993527

3. L. Takacs, Random walk processes and their various applications, Pro. The. App., Essays to the Mem, of J. Mogyorodi, Math. Appl, vol.80, pp.1-32, 1992.

. Takacs, Limit distributions for queues and random rooted trees, Journal of Applied Mathematics and Stochastic Analysis, vol.6, issue.3, pp.189-216, 1993.
DOI : 10.1155/S1048953393000176

R. Chapitre and . References, The continuum random tree. II: An overview. Stochastic analysis, Proc. Symp, pp.23-70, 1990.

2. D. Aldous, The continuum random tree. III Ann. of Probab, pp.248-289, 1993.

3. D. Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent, The Annals of Probability, vol.25, issue.2, pp.812-854, 1997.
DOI : 10.1214/aop/1024404421

4. D. Aldous, Deterministic and Stochastic Models for Coalescence (Aggregation and Coagulation): A Review of the Mean-Field Theory for Probabilists, Bernoulli, vol.5, issue.1, pp.3-48, 1999.
DOI : 10.2307/3318611

R. Alonso and . Schott, Random generation of trees, 1995.
DOI : 10.1007/978-1-4757-6353-9

. Bellman, A brief introduction to theta functions, 1961.

7. P. Biane and M. Yor, Valeurs principales associées aux temps locaux browniens, Bull. Sci. Maths Ill, pp.23-24, 1987.
DOI : 10.1007/bfb0084151

8. J. Borwein and P. B. Borwein, Pi and the AGM. A study in analytic number theory and computational complexity, 1998.

9. N. De-bruijn, D. E. Knuth, and S. O. Rice, THE AVERAGE HEIGHT OF PLANTED PLANE TREES, pp.15-22, 1972.
DOI : 10.1016/B978-1-4832-3187-7.50007-6

I. A. Cayley, A theorem on trees, Quarterly Journal of Pure and Applied Math, vol.23, pp.376-378, 1889.
DOI : 10.1017/CBO9780511703799.010

. Llj-ph, G. Chassaing, and . Louchard, Phase transition for parking blocks, Brownian excursion and coalescence, 1999.

1. K. Chung, Excursions in Brownian motion, Arkiv f??r Matematik, vol.14, issue.1-2, pp.155-177, 1976.
DOI : 10.1007/BF02385832

1. K. Chung, A cluster of great formulas, Acta Mathematica Academiae Scientiarum Hungaricae, vol.48, issue.1-3, pp.65-67, 1982.
DOI : 10.1007/BF01895215

1. M. Cs6rgô and P. Révész, Strong approximations in probability and statistics. Probability and Mathematical Statistics, 1981.

1. M. Drmota and B. Gittenberger, On the profile of random trees, Random Structures and Algorithms, vol.10, issue.4, pp.421-451, 1997.
DOI : 10.1002/(SICI)1098-2418(199707)10:4<421::AID-RSA2>3.0.CO;2-W

R. T. Durrett, D. L. Iglehart, and D. R. Miller, Weak Convergence to Brownian Meander and Brownian Excursion, The Annals of Probability, vol.5, issue.1, pp.117-129, 1977.
DOI : 10.1214/aop/1176995895

URL : http://doi.org/10.1214/aop/1176995895

P. Flajolet and A. Odlyzko, The average height of binary trees and other simple trees, Journal of Computer and System Sciences, vol.25, issue.2, 1982.
DOI : 10.1016/0022-0000(82)90004-6

URL : https://hal.archives-ouvertes.fr/inria-00076505

P. Flajolet, P. Poblete, and A. Viola, On the Analysis of Linear Probing Hashing, Algorithmica, vol.22, issue.4, pp.490-515, 1998.
DOI : 10.1007/PL00009236

URL : https://hal.archives-ouvertes.fr/inria-00073424

D. Foata and J. Riordan, Mappings of acyclic and parking functions. Aequationes math, VoL, vol.10, pp.10-22, 1974.

J. Françon, Acyclic and parking functions, Journal of Combinatorial Theory, Series A, vol.18, issue.1, pp.27-35, 1975.
DOI : 10.1016/0097-3165(75)90063-1

I. A. Ibragimov and Y. V. Linnik, Independent and stationary sequences of random variables, 1971.

. Th and . Jeulin, Semi-martingales et grossissement d'une filtration, Lecture Notes in Mathematics, vol.833, 1980.

W. D. Kaigh, An Invariance Principle for Random Walk Conditioned by a Late Return to Zero, The Annals of Probability, vol.4, issue.1, pp.115-121, 1976.
DOI : 10.1214/aop/1176996189

D. G. Kendall, Some problems in the theory of queues, J. of the Roy, Stat. Soc. B, vol.13, pp.151-185, 1951.

R. Kemp, On the average stack size of regularly distributed binary trees, Lect. Notes in Comp. Sei. 71, pp.340-355, 1979.
DOI : 10.1007/3-540-09510-1_28

D. P. Kennedy, The distribution of the maximum Brownian excursion, Journal of Applied Probability, vol.13, issue.02, pp.371-376, 1976.
DOI : 10.1007/BF00535106

D. E. Knuth, The art of computer programming, 1997.

D. E. Knuth, The art of computer programming: sorting and searching, 1997.

D. E. Knuth, Linear Probing and Graphs, Algorithmica, vol.22, issue.4, pp.561-568, 1998.
DOI : 10.1007/PL00009240

A. G. Konheim and B. Weiss, An Occupancy Discipline and Applications, SIAM Journal on Applied Mathematics, vol.14, issue.6, pp.1266-1274, 1966.
DOI : 10.1137/0114101

G. Louchard, Kac's formula, levy's local time and brownian excursion, Journal of Applied Probability, vol.1, issue.03, pp.479-499, 1984.
DOI : 10.1214/aop/1176993927

J. W. Moon, Counting labelled trees, Canadian Mathematical Monographs, issue.1, 1970.

R. Chapitre-iv-[, 3. A. Nijenhuis, and H. S. Wilf, Combinatorial algorithms, 1975.

3. A. Odlyzko and H. S. Wilf, Bandwidths and profiles of trees, Journal of Combinatorial Theory, Series B, vol.42, issue.3, pp.348-370, 1987.
DOI : 10.1016/0095-8956(87)90052-9

3. R. Otter, The Multiplicative Process, The Annals of Mathematical Statistics, vol.20, issue.2, pp.206-224, 1949.
DOI : 10.1214/aoms/1177730031

URL : http://doi.org/10.1214/aoms/1177730031

V. V. Petrov, Sums of independant random variables, 1975.

J. Pitman, Enumerations of trees and forests related ta bran ching processes and random walks, Microsurveys in Discrete Probability, 1998.

J. Pitman, R. Stanley, and D. C. Berkeley, A polytope related ta empirical distributions, plane trees, parking functions, and the associahedron Linear probing: the probable largest search time grows logarithmically with the number of records, J. AIgorithms, vol.8, issue.2, pp.236-249, 1987.

J. D. Pollard, Convergence of stochastic processes. Springer Series in Statistics, 1984.

4. A. Renyi and &. G. Szekeres, On the height of trees, Journal of the Australian Mathematical Society, vol.4, issue.04, pp.497-507, 1967.
DOI : 10.1007/BF02559539

4. M. Schutzenberger, On an enumeration problem, Journal of Combinatorial Theory, vol.4, issue.3, pp.219-241, 1968.
DOI : 10.1016/S0021-9800(68)80003-1

R. Sedgewick and P. Flajolet, An introduction ta the analysis of algorithms, 1996.

G. R. Shorack and J. A. Wellner, Empirical processes with applications ta statistics, 1986.

L. Smith and . Diaconis, Honest bernoulli excursions, Journal of Applied Probability, vol.2, issue.03, pp.464-477, 1988.
DOI : 10.2307/3315033

4. J. Spencer, Enumerating graphs and Brownian motion, Communications on Pure and Applied Mathematics, vol.50, issue.3, pp.291-294, 1997.
DOI : 10.1002/(SICI)1097-0312(199703)50:3<291::AID-CPA4>3.0.CO;2-6

4. K. Supowit and E. M. Reingold, The complexity of drawing trees ni cely. Acta Inform, pp.377-392, 1982.

L. Tabics, On the total heights of random rooted trees, J. Appl. Probab, vol.29, issue.3, pp.543-556, 1992.

5. L. Takacs, Limit distributions for queues and random rooted trees, Journal of Applied Mathematics and Stochastic Analysis, vol.6, issue.3, pp.189-216, 1993.
DOI : 10.1155/S1048953393000176

R. Ij, J. C. Baeza-yates, G. J. Culberson, and . Rawlins, Searching in the plane, Inf. Comput, vol.106, issue.2, pp.234-252, 1993.

2. R. Bellman, Dynamic programming, 1947.

3. W. Feller, An introduction to probability theory and its applications, 1966.

4. E. Horvitz, Reasoning under varying and uncertain constraints, Seventh National Conference on Artificial Intelligence, pp.11-116, 1988.

5. S. Zilberstein, Optimizing decision quality with contract algorithms, 14 th international joint conference on artificial intelligence 49, pp.1576-1582, 1995.

6. S. Zilberstein, F. Charpillet, and P. Chassaing, Real-Time Problem-Solving with Contract Algorithm, th international joint conference on artificial intelligence, 1999.

7. S. Zilberstein and S. J. , Optimal composition of real-time systems, Artificial Intelligence, vol.82, issue.1-2, pp.181-213, 1996.
DOI : 10.1016/0004-3702(94)00074-3

<. Xo-)-<, 4, 15, 13. Il est clair que la forme de l'arbre ne dépend pas de la valeur des étiquettes, mais seulement de l'ordre des Xi' Supposons que les nombres Xi soient des v.a. uniformes indépendantes sur [0, 1]. Il est facile de voir que la permutation 0-de Sn (le groupe symétrique), telle que XO < xO"(n) suit également la loi uniforme sur Sn. L'ensemble des arbres binaires de recherche est classiquement muni de la loi induite par l'équiprobabilité sur Sn, noeuds internes sont les noeuds de T n . Par exemple Muni de cette loi, les ABR ne sont pas des arbres de G.W.. ? Pour s'en convaincre

L. 'étiquette-de-ce, fils" est inférieure à toutes les autres et il yan -1 façons de construire cet arbre; il suffit que tous les autres étiquettes soient rangées par ordre croissant

A. Les and G. W. Sont-en-fait-très-différents-des-arbres-de, Par exemple, la hauteur d'un ABR est de l'ordre de logn contre ,;n pour les arbres de G.W .. On pourra se référer aux livres de Knuth, Sedegewick et Flajolet [43] ainsi qu'aux articles de L. Devroye

. Arbres-et-combinatoire-en-combinatoire, on définit les familles d'arbres simples non pas par une loi de reproduction mais par une équation fonctionnelle

. La-remarque-suivante, issue de Aldous [1], permet de passer d'une définition combinatoire des arbres à une définition probabiliste et réciproquement

D. J. Aldous, The continuum random tree. III, Ann. Probab, pp.248-289, 1993.

D. J. Aldous, Brownian excursions, critical random graphs and the multiplicative coalescent, The Annals of Probability, vol.25, issue.2, pp.812-854, 1997.
DOI : 10.1214/aop/1024404421

S. Asmussen and H. Hering, Branching processes, Progress in Prob. and Stat., Birkhaeuser, 1983.

J. Bertoin and J. Pitman, Path transformations connecting Brownian bridge, excursion and meander, Bull. Sei. Math., II. Ser, vol.118, issue.2, pp.147-166, 1994.

P. Biane, Relations entre pont et excursion du mouvement brownien reel, Probab. Stat, vol.22, pp.1-7, 1986.

P. Billingsley, Convergence of probability measures, 1968.
DOI : 10.1002/9780470316962

P. Billingsley, Probability and measure, Wiley Series in Prob. and math, 1979.

A. N. Borodin and P. Salminen, Handbook of Brownian Motion -Facts and Formulae, 1996.

P. Biane and M. Yor, Valeurs principales associées aux temps locaux browniens, Bull. Sei. Maths, vol.111, pp.23-24, 1987.
DOI : 10.1007/bfb0084151

K. L. Chung, Excursions in Brownian motion, Arkiv f??r Matematik, vol.14, issue.1-2, pp.155-177, 1976.
DOI : 10.1007/BF02385832

T. H. Cormen, E. Leiserson, and R. L. Rivest, Introduction to Algorithm, 1990.

E. Csaki and S. G. Mohanty, Some joint distributions for conditional random walks, Canadian Journal of Statistics, vol.26, issue.1, pp.19-28, 1986.
DOI : 10.2307/3315033

M. Drmota and B. Gittenberger, On the profile of random trees, Random Struet, Algorithms, vol.10, issue.4, pp.421-451, 1997.

L. Devroye, Branching processes in the analysis of the heights of trees, Acta Informatica, vol.24, issue.3, pp.277-298, 1987.
DOI : 10.1007/BF00265991

R. T. Durrett and D. L. Iglehart, Functionals of Brownian Meander and Brownian Excursion, The Annals of Probability, vol.5, issue.1, pp.130-135, 1977.
DOI : 10.1214/aop/1176995896

M. Dwass, A Fluctuation Theorem for Cyclic Random Variables, The Annals of Mathematical Statistics, vol.33, issue.4, pp.1450-1453, 1962.
DOI : 10.1214/aoms/1177704376

M. Dwass, The total progeny in a branching process and a related random walk, Journal of Applied Probability, vol.1, issue.03, pp.682-686, 1969.
DOI : 10.1007/BF00531752

P. Flajolet and A. M. Odlyzko, The average height of binary trees and other simple trees, Journal of Computer and System Sciences, vol.25, issue.2, pp.171-213, 1982.
DOI : 10.1016/0022-0000(82)90004-6

URL : https://hal.archives-ouvertes.fr/inria-00076505

D. Foata and J. Riordan, Mappings of acyclic and parking functions, Aequationes Mathematicae, vol.4, issue.1, pp.10-22, 1974.
DOI : 10.1007/BF01834776

J. Françon, Acyclic and parking functions, Journal of Combinatorial Theory, Series A, vol.18, issue.1, pp.27-35, 1975.
DOI : 10.1016/0097-3165(75)90063-1

. Th and . Jeulin, Semi-martingales et grossissement d'une filtration, Lecture Notes in Mathematics, vol.833, 1980.

T. E. Harris, The theory of branching processes, 1963.
DOI : 10.1007/978-3-642-51866-9

S. E. Karatzas and . Shreve, Brownian motion and stochastic calculus, 1988.

R. Kemp, On the stack size of regularly distributed binary trees, Proceedings, 6th ICALP Conf, 1979.

D. P. Kennedy, The Galton-Watson process conditioned on the total progeny, Journal of Applied Probability, vol.13, issue.04, pp.800-806, 1975.
DOI : 10.1017/S0001867800037629

D. E. Knuth, The art of computer programming, 1968.

J. F. Le and . Gall, Une approche élémentaire des théorèmes de décomposition de Williams, Sém. Prob. XX, pp.447-464, 1986.

J. F. Le, Y. Gall, and . Le, Branching processes in Lévy processes : The exploration process, 1996.

G. Louchard, Kac's formula, levy's local time and brownian excursion, Journal of Applied Probability, vol.1, issue.03, pp.479-499, 1984.
DOI : 10.1214/aop/1176993927

G. Louchard, The brownian excursion area: a numerical analysis, Computers & Mathematics with Applications, vol.10, issue.6, pp.413-417, 1984.
DOI : 10.1016/0898-1221(84)90071-3

G. Louchard, Erratum: The Brownian excursion area : a numerical analysis, Comput. Math. Appl, p.375, 1986.

J. W. Moon, Counting labelled trees, Canadian Mathematical Monographs, issue.1, 1970.

R. Otter, The Multiplicative Process, The Annals of Mathematical Statistics, vol.20, issue.2, pp.206-224, 1949.
DOI : 10.1214/aoms/1177730031

D. Pollard, Convergence of stochastic processes, 1984.
DOI : 10.1007/978-1-4612-5254-2

A. Renyi and G. Szekeres, On the height of trees, Journal of the Australian Mathematical Society, vol.4, issue.04, pp.497-507, 1967.
DOI : 10.1007/BF02559539

P. Révész, Random walk in random and non-random environments, 1990.

D. Revuz and M. Yor, Continuous martingales and Brownian motion, pp.9-10, 1990.

J. Riordan, The Enumeration of Trees by Height and Diameter, IBM Journal of Research and Development, vol.4, issue.5, pp.473-478, 1960.
DOI : 10.1147/rd.45.0473

R. Sedgewick, . Ph, and . Flajolet, An introduction to the analysis of algorithms, 1996.

M. P. Schutzenberger, On an enumeration problem, Journal of Combinatorial Theory, vol.4, issue.3, pp.219-241, 1968.
DOI : 10.1016/S0021-9800(68)80003-1

J. Spencer, Enumerating graphs and Brownian motion, Communications on Pure and Applied Mathematics, vol.50, issue.3, pp.291-294, 1997.
DOI : 10.1002/(SICI)1097-0312(199703)50:3<291::AID-CPA4>3.0.CO;2-6

F. Spitzer, Principes of Random Walk, p.6, 1964.

L. Tabics, A Bernoulli excursion and its various applications, Adv. App!. Prob, vol.23, pp.557-585, 1991.

L. Takacs, Random walk processes and their various applications, Probability theory and applications, Essays to the Mem, of J. Mogyorodi, Math. App!, vol.80, pp.1-32, 1992.

L. Takacs, Limit distributions for queues and random rooted trees, Journal of Applied Mathematics and Stochastic Analysis, vol.6, issue.3, pp.189-216, 1993.
DOI : 10.1155/S1048953393000176

L. Takacs, Brownian local times, Journal of Applied Mathematics and Stochastic Analysis, vol.8, issue.3, pp.209-232, 1995.
DOI : 10.1155/S1048953395000207

W. Vervaat, A Relation between Brownian Bridge and Brownian Excursion, The Annals of Probability, vol.7, issue.1, pp.143-149, 1979.
DOI : 10.1214/aop/1176995155

URL : http://doi.org/10.1214/aop/1176995155