Name
Abstract | ||
|---|---|---|
We study the variety of subtrees lying on the fringe of recursive trees and binary search trees by analyzing the distributional behavior of $X_{n,k}$, which counts the number of subtrees of size $k$ in a random tree of size $n$, with $k = k(n)$ dependent on $n$. Using analytic methods we can characterize for both tree families the phase change behavior of $X_{n,k}$ as follows. In the subcritical case, when $k(n)/\sqrt{n} \to 0$, we show that $X_{n,k}$ is (after normalization) asymptotically normally distributed, whereas in the supercritical case, when $k(n)/\sqrt n \to \infty$, $X_{n,k}$ converges to 0. In the critical case, when $k(n) = \Theta(\sqrt{n}\,)$, we show that if $k/\sqrt{n}$ approaches a limit, then $X_{n,k}$ converges in distribution to a Poisson random variable, whereas if $k/\sqrt{n}$ does not approach a finite nonzero limit, the size oscillates and does not converge in distribution to any random variable. In regard to recursive trees and binary search trees, this provides an understanding of the complete spectrum of phases of $X_{n,k}$ and the gradual change from the subcritical to the supercritical phase. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1137/060653950 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
random recursive,phase changes,distributional behavior,subcritical case,poisson random variable,critical case,moments,riccati equation,recurrence,random variable,size oscillates,subtree varieties,supercritical case,binary search trees,binary search tree,random trees,sqrt n,random tree,oscillations,phase change,spectrum,convergence in distribution | Random tree,Discrete mathematics,Combinatorics,Random variable,Tree (data structure),Binary tree,Poisson distribution,Distribution function,Binary search tree,Mathematics,Search tree | Journal |
Volume | Issue | ISSN |
22 | 1 | 0895-4801 |
Citations | PageRank | References |
5 | 0.55 | 11 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qunqiang Feng | 1 | 5 | 1.56 |
| Hosam M. Mahmoud | 2 | 183 | 55.63 |
| Alois Panholzer | 3 | 157 | 25.61 |