Random Trees (eBook)

Preface 6
Contents 11
1 Classes of Random Trees 16
1.1 Basic Notions 17
1.2 Combinatorial Trees 19
1.3 Recursive Trees 28
1.4 Search Trees 32
2 Generating Functions 39
2.1 Counting with Generating Functions 40
2.2 Asymptotics with Generating Functions 51
3 Advanced Tree Counting 83
3.1 Generating Functions and Combinatorial Trees 84
3.2 Additive Parameters in Trees 96
3.3 Patterns in Trees 104
4 The Shape of Galton-Watson Trees and P´olya Trees 120
4.1 The Continuum Random Tree 121
4.2 The Profile of Galton-Watson Trees 128
4.3 The Profile of P´olya Trees 167
5 The Vertical Profile of Trees 199
5.1 Quadrangulations and Embedded Trees 200
5.2 Profiles of Trees and Random Measures 208
5.3 Combinatorics on Embedded Trees 219
5.4 Asymptotics on Embedded Trees 231
6 Recursive Trees and Binary Search Trees 248
6.1 Permutations and Trees 249
6.2 Generating Functions and Basic Statistics 258
6.3 The Profile of Recursive Trees 276
6.4 The Height of Recursive Trees 291
6.5 Profile and Height of Binary Search Trees and Related Trees 302
7 Tries and Digital Search Trees 317
7.1 The Profile of Tries 318
7.2 The Profile of Digital Search Trees 335
8 Recursive Algorithms and the Contraction Method 353
8.1 The Number of Comparisons in Quicksort 355
8.2 The L2 Setting of the Contraction Method 360
8.3 Limitations of the L2 Setting and Extensions 371
9 Planar Graphs 374
9.1 Basic Notions 375
9.2 Counting Planar Graphs 377
9.3 Outerplanar Graphs 405
9.4 Series-Parallel Graphs 417
9.5 All Planar Graphs 429
Appendix 447
References 453
Index 463