Name
Abstract | ||
|---|---|---|
We employ a Polya urn to model rotations in a random fringe-balanced binary search tree. We show that asymptotically the number of rotations to construct a tree of size n has a normal distribution with mean 2/7 n and variance 66/637 n. Exact results for mean and variance are developed in the process. (C) 1998 Published by Elsevier Science B.V. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0020-0190(97)00184-1 | Inf. Process. Lett. |
Keywords | Field | DocType |
fringe-balanced binary tree,data structure,tree,rotation,binary search tree,binary tree,normal distribution,data structures | Graph theory,Discrete mathematics,Random search,Normal distribution,Combinatorics,Treap,Binary tree,Random binary tree,Binary search tree,Mathematics,Interval tree | Journal |
Volume | Issue | ISSN |
65 | 1 | 0020-0190 |
Citations | PageRank | References |
5 | 0.53 | 13 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Hosam M. Mahmoud | 1 | 183 | 55.63 |