Details
| Original language | English |
|---|---|
| Pages (from-to) | 1781-1802 |
| Number of pages | 22 |
| Journal | Annals of Applied Probability |
| Volume | 19 |
| Issue number | 5 |
| Publication status | Published - Oct 2009 |
Abstract
A zero-one sequence describes a path through a rooted directed binary tree T; it also encodes a real number in [0, 1]. We regard the level of the external node of T along the path as a function on the unit interval, the silhouette of T. We investigate the asymptotic behavior of the resulting stochastic processes for sequences of trees that are generated by the binary search tree algorithm.
Keywords
- Analysis of algorithms, Contraction method, Convergence in distribution, External path length, Functional limit theorems
ASJC Scopus subject areas
- Mathematics(all)
- Statistics and Probability
- Decision Sciences(all)
- Statistics, Probability and Uncertainty
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Annals of Applied Probability, Vol. 19, No. 5, 10.2009, p. 1781-1802.
Research output: Contribution to journal › Article › Research › peer review
}
TY - JOUR
T1 - On the silhouette of binary search trees
AU - Grübel, Rudolf
PY - 2009/10
Y1 - 2009/10
N2 - A zero-one sequence describes a path through a rooted directed binary tree T; it also encodes a real number in [0, 1]. We regard the level of the external node of T along the path as a function on the unit interval, the silhouette of T. We investigate the asymptotic behavior of the resulting stochastic processes for sequences of trees that are generated by the binary search tree algorithm.
AB - A zero-one sequence describes a path through a rooted directed binary tree T; it also encodes a real number in [0, 1]. We regard the level of the external node of T along the path as a function on the unit interval, the silhouette of T. We investigate the asymptotic behavior of the resulting stochastic processes for sequences of trees that are generated by the binary search tree algorithm.
KW - Analysis of algorithms
KW - Contraction method
KW - Convergence in distribution
KW - External path length
KW - Functional limit theorems
UR - http://www.scopus.com/inward/record.url?scp=73949119948&partnerID=8YFLogxK
U2 - 10.1214/08-AAP593
DO - 10.1214/08-AAP593
M3 - Article
AN - SCOPUS:73949119948
VL - 19
SP - 1781
EP - 1802
JO - Annals of Applied Probability
JF - Annals of Applied Probability
SN - 1050-5164
IS - 5
ER -