Abstract
Let H n be the height of a binary search tree with n nodes constructed by standard insertions from a random permutation of 1, … , n . It is shown that H n /log n → c = 4.31107 … in probability as n → ∞, where c is the unique solution of c log((2 e )/ c ) = 1, c ≥ 2. Also, for all p > 0, lim n →∞ E ( H p n )/ log p n = c p . Finally, it is proved that S n /log n → c * = 0.3733 … , in probability, where c * is defined by c log((2 e )/ c ) = 1, c ≤ 1, and S n is the saturation level of the same tree, that is, the number of full levels in the tree.
Keywords
CombinatoricsMathematicsBinary search treeBinary logarithmPermutation (music)Tree (set theory)Random permutationBinary numberLog-log plotRandom binary treeSelf-balancing binary search treeBinary treeDiscrete mathematicsK-ary treePhysicsArithmeticTree structureBlock (permutation group theory)
Affiliated Institutions
Related Publications
Good quantum error-correcting codes exist
A quantum error-correcting code is defined to be a unitary mapping (encoding)\nof k qubits (2-state quantum systems) into a subspace of the quantum state\nspace of n qubits such...
Empirical graph Laplacian approximation of Laplace–Beltrami operators: Large sample results
Let ${M}$ be a compact Riemannian submanifold of ${{\\bf R}^m}$ of dimension\n$\\scriptstyle{d}$ and let ${X_1,...,X_n}$ be a sample of i.i.d. points in ${M}$\nwith uniform dist...
Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
Recently, several algorithms using number field sieves have been given to factor a number n in heuristic expected time $L_n [1/3; c]$, where \[ L_n [ v ;c ] = \exp \left\{ ( c +...
Error probability bounds for M-PSK and M-DPSK and selective fading diversity channels
A method is described for obtaining tight closed-form bounds on the probability of error for M-ary phase-shift keying (M-PSK) and M-ary differential phase-shift keying (M-DPSK) ...
Design of balanced and constant weight codes for VLSI systems
A constant weight, w, code with k information bits and r check bits is a binary code of length n=k+r and cardinality 2/sup k/ such that the number of 1s in each code word is equ...
Publication Info
- Year
- 1986
- Type
- article
- Volume
- 33
- Issue
- 3
- Pages
- 489-498
- Citations
- 232
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
232
OpenAlex
Cite This
Luc Devroye
(1986).
A note on the height of binary search trees.
Journal of the ACM
, 33
(3)
, 489-498.
https://doi.org/10.1145/5925.5930
Identifiers
- DOI
- 10.1145/5925.5930