๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the Variance of the Height of Random Binary Search Trees

โœ Scribed by Devroye, Luc; Reed, Bruce

Book ID
118178116
Publisher
Society for Industrial and Applied Mathematics
Year
1995
Tongue
English
Weight
522 KB
Volume
24
Category
Article
ISSN
0097-5397

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

On the Total Heights of Random Rooted Bi
On the Total Heights of Random Rooted Binary Trees
โœ L. Takacs ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 306 KB

Denote by \(S_{n}\) the set of all distinct rooted binary trees with \(n\) unlabeled vertices. Define \(\sigma_{n}\) as a total height of a tree chosen at random in the set \(S_{n}\), assuming that all the possible choices are equally probable. The total height of a tree is defined as the sum of the

Binary search trees of almost optimal he
Binary search trees of almost optimal height
โœ Arne Andersson; Christian Icking; Rolf Klein; Thomas Ottmann ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Springer-Verlag ๐ŸŒ English โš– 739 KB
On the distribution of binary search tre
On the distribution of binary search trees under the random permutation model
โœ James Allen Fill ๐Ÿ“‚ Article ๐Ÿ“… 1996 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 865 KB

We study the distribution Q on the set B, of binary search trees over a linearly ordered set of n records under the standard random permutation model. This distribution also arises as the stationary distribution for the move-to-root (MTR) Markov chain taking values in B,, when successive requests ar