On the silhouette of binary search trees (Q983879): Difference between revisions
From MaRDI portal
Set profile property. |
Changed an Item |
||
Property / arXiv ID | |||
Property / arXiv ID: 0910.3825 / rank | |||
Normal rank |
Revision as of 19:19, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On the silhouette of binary search trees |
scientific article |
Statements
On the silhouette of binary search trees (English)
0 references
13 July 2010
0 references
A zero-one sequence is used to describe a path through a rooted directed binary tree \(T\). It also encodes a real number in \([0,1]\), given by its binary expansion. The silhouette of the tree is defined as function on \([0,1]\), which at point \(s\) has as value the height of the tree along the binary path corresponding \(s\). For a sequence of random binary search trees a limit theorem for the silhouette process is established, where convergence is understood in the sense of linear functionals on some function space. The proof combines martingale arguments with the contraction method.
0 references
analysis of algorithms
0 references
contraction method
0 references
convergence in distribution
0 references
external path length
0 references
functional limit theorems
0 references