This is the second volume in a series of innovative proceedings entirely devoted to the connections between mathematics and computer science. Here mathematics and computer science are directly confronted and joined to tackle intricate problems in computer science with deep and innovative mathematical approaches.

The book serves as an outstanding tool and a main information source for a large public in applied mathematics, discrete mathematics and computer science, including researchers, teachers, graduate students and engineers. It provides an overview of the current questions in computer science and the related modern and powerful mathematical methods. The range of applications is very wide and reaches beyond computer science.

Mathematics and Computer Science III contains invited and contributed papers on combinatorics, random graphs and networks, algorithms analysis and trees, branching processes, constituting the Proceedings of the Third International Colloquium on Mathematics and Computer Science, held in Vienna in September 2004. It addresses a large public in applied mathematics, discrete mathematics and computer science, including researchers, teachers, graduate students and engineers.

Mathematics and Computer Science III contains invited and contributed papers on combinatorics, random graphs and networks, algorithms analysis and trees, branching processes, constituting the Proceedings of the Third International Colloquium on Mathematics and Computer Science, held in Vienna in September 2004. It addresses a large public in applied mathematics, discrete mathematics and computer science, including researchers, teachers, graduate students and engineers.

This is the second volume in a series of innovative proceedings entirely devoted to the connections between mathematics and computer science. Here mathematics and computer science are directly confronted and joined to tackle intricate problems in computer science with deep and innovative mathematical approaches.

The book serves as an outstanding tool and a main information source for a large public in applied mathematics, discrete mathematics and computer science, including researchers, teachers, graduate students and engineers. It provides an overview of the current questions in computer science and the related modern and powerful mathematical methods. The range of applications is very wide and reaches beyond computer science.

This book is based on the proceedings of the Colloquium on Mathematics and Computer Science held in the University of Versailles-St-Quentin on September 18- It contains articles on topics that are relevant both to Mathematics and 20, 2000. to Computer Science. These articles have been selected throughout a rigourous process; each of them has been submitted to two referees at least. This selection process, which took place under the supervision of the scientific committee, en- sures the high level and the originality of the contributions. We thank the invited speakers, the authors, the participants to the collo- quium and, of course, the Scientific Committee whose members were D. Aldous, F. Baccelli, P. Cartier, B. Chauvin, P. Flajolet, J.M. Fourneau, D. Gardy, D. Gouyou- Beauchamps, R. Kenyon, J.F. Le Gall, C. Lemarechal, R. Lyons, A. Mokkadem, A. Rouault and C. Roucairol. We also take this opportunity to thank the University of Versailles-St-Quentin, the University of Paris-Sud (Orsay) and the Centre National de la Recherche Sci- entifique (CNRS), whose financial and material support contributed to the success of the Colloquium.

Cet ouvrage presente les types d'arbres les plus utilises en informatique, sous les angles algorithmique et mathematique. Pour chaque type, nous donnons les algorithmes courants associes et des exemples d'utilisation, directe ou en modelisation, puis nous etudions leurs performances d'un point de vue mathematique. Nos outils sont les mathematiques discretes, les probabilites et la combinatoire analytique, presentes ici simultanement.Le public vise est d'abord celui des etudiants de niveau master scientifique ou en derniere annee d'ecole d'ingenieurs avec un cursus prealable en informatique ou en mathematiques, ou ceux visant une double competence en mathematiques et informatique ; ainsi que toute personne dotee d'un bagage scientifique " minimal " et amenee a utiliser des structures arborescentes liees a des algorithmes, qui souhaiterait avoir une meilleure connaissance de ces structures et une idee des performances des algorithmes associes sans se plonger dans les travaux originaux. This book presents a wide range of tree structures, from both a computer science and a mathematical point of view. For each of these structures we give the algorithms that allow us to visit or update the structure, and discuss their potential uses, either directly (for storing data) or in modelling a variety of situations. We present a mathematical approach to their performances; this is done by the systematic and parallel use of tools from discrete mathematics, probability and analytic combinatorics.The book is intended for graduate students in mathematics or computer science (or both) and in engineering schools. It is also suitable for anyone with a basic level of scientific knowledge who may have to use tree structures and related algorithms, and who wishes to get a rigorous knowledge of their performance without going back to the original, often specialized, results.