Random Trees (eBook)
XVII, 458 Seiten
Springer Wien (Verlag)
978-3-211-75357-6 (ISBN)
The aim of this book is to provide a thorough introduction to various aspects of trees in random settings and a systematic treatment of the mathematical analysis techniques involved. It should serve as a reference book as well as a basis for future research.
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
| Erscheint lt. Verlag | 16.4.2009 |
|---|---|
| Zusatzinfo | XVII, 458 p. |
| Verlagsort | Vienna |
| Sprache | englisch |
| Themenwelt | Mathematik / Informatik ► Informatik ► Datenbanken |
| Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge | |
| Mathematik / Informatik ► Mathematik ► Statistik | |
| Mathematik / Informatik ► Mathematik ► Wahrscheinlichkeit / Kombinatorik | |
| Technik | |
| Schlagworte | algorithms • combinatorics • data structures • Graph • graph theory • Probability • Random trees • Stochastic Processes |
| ISBN-10 | 3-211-75357-5 / 3211753575 |
| ISBN-13 | 978-3-211-75357-6 / 9783211753576 |
| Haben Sie eine Frage zum Produkt? |
PDF (Wasserzeichen)DRM: Digitales Wasserzeichen
Dieses eBook enthält ein digitales Wasserzeichen und ist damit für Sie personalisiert. Bei einer missbräuchlichen Weitergabe des eBooks an Dritte ist eine Rückverfolgung an die Quelle möglich.
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
