Distribution of distances in random binary search trees. (Q1872343)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Distribution of distances in random binary search trees. |
scientific article; zbMATH DE number 1906137
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Distribution of distances in random binary search trees. |
scientific article; zbMATH DE number 1906137 |
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
