Name
Abstract | ||
|---|---|---|
We use Poisson approximation techniques for sums of indicator ran- dom variables to derive explicit error bounds and central limit theo- rems for several functionals of random trees. In particular, we consider (i) the number of comparisons for successful and unsuccessful search in a binary search tree and (ii) internode distances in increasing trees. The Poisson approximation setting is shown to be a natural and fairly simple framework for deriving asymptotic results. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1002/(SICI)1098-2418(199608/09)9:1/2<79::AID-RSA5>3.0.CO;2-8 | Random Struct. Algorithms |
Keywords | Field | DocType |
binary search tree,binary search trees | Geometry of binary search trees,Discrete mathematics,Combinatorics,Metric tree,Weight-balanced tree,Poisson distribution,Random binary tree,Mathematics | Journal |
Volume | Issue | ISSN |
9 | 1-2 | 1042-9832 |
Citations | PageRank | References |
11 | 2.10 | 6 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert P. Dobrow | 1 | 35 | 5.28 |
| Robert T. Smythe | 2 | 92 | 39.96 |