Distribution of distances in random binary search trees. (Q1872343)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Distribution of distances in random binary search trees. |
scientific article |
Statements
Distribution of distances in random binary search trees. (English)
0 references
6 May 2003
0 references
The authors prove asymptotic normality for the depth of a randomly selected node and for the distance between two randomly selected nodes in a random binary search tree. They also establish logarithmic convergence rates w.r.t. the Zolotarev metric. The proof is based on the contraction method.
0 references
random trees
0 references
recurrence
0 references
fixed-point equation
0 references
contraction method
0 references
0 references
