Name
Title | ||
|---|---|---|
Bimodality and Phase Transitions in the Profile Variance of Random Binary Search Trees |
Abstract | ||
|---|---|---|
We show that the variances of the profile (number of nodes at each level) of random binary search trees undergoes asymptotically four phase transitions and exhibits a bimodal or "two-humped" behavior, in contrast to the unimodality of the expected value of the profiles. Precise asymptotic approximations are derived. The same types of phenomena also hold for the profile of random recursive trees. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1137/S0895480104440134 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
undergoes asymptotically,random binary search tree,expected value,precise asymptotic approximation,random recursive tree,phase transition,random binary search trees,profile variance,phase transitions,stirling numbers of the first kind,binary search trees,binary search tree,bessel functions | Random search,Unimodality,Combinatorics,Saddle point,Phase transition,Expected value,Random binary tree,Bimodality,Mathematics,Binary search tree | Journal |
Volume | Issue | ISSN |
19 | 1 | 0895-4801 |
Citations | PageRank | References |
8 | 0.56 | 17 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Drmota | 1 | 438 | 54.46 |
| Hsien-Kuei Hwang | 2 | 365 | 38.02 |