Uniform distribution modulo one and binary search trees

DOI10.5802/JTNB.366MaRDI QIDQ558117zbMATH OpenOpenAlexFDO

Authors Peter van der Wal, F. Michel Dekking

Publication date 30 June 2005

Published in Journal de Théorie des Nombres de Bordeaux (Search for Journal in Brave)

Full work available at URL http://www.numdam.org/item?id=JTNB_2002__14_2_415_0, https://eudml.org/doc/229169

zbMATH Keywords

binary search treesuniform distribution

Mathematics Subject Classification ID

General theory of distribution modulo (1) (11K06) Metric theory of other algorithms and expansions; measure and Hausdorff dimension (11K55) Data structures (68P05) Searching and sorting (68P10)

Review text

Sorting a sequence \(x=(x_k)\) of distinct numbers from \([0,1]\) by Quicksort generates a binary tree. Let \(H_n(x)\) denote the height of the tree generated by the prefix \(x_1,\dots,x_n\) of length \(n\) of \(x\). In the present paper it is shown that, if \(x\) is uniformly distributed in \([0,1]\), then \(H_n(x)=o(n)\) as \(n\to \infty\).

Recommendations

• A limiting distribution for quicksort
• A note on the height of binary search trees
• The height of a binary search tree: the limiting distribution perspective.
• scientific article; zbMATH DE number 852055
• On the Variance of the Height of Random Binary Search Trees

Cites work

• A note on the height of binary search trees
• A study of random Weyl trees
• Asymptotical growth of a class of random trees
• scientific article; zbMATH DE number 53861 (Why is no real title available?)
• scientific article; zbMATH DE number 1552323 (Why is no real title available?)
• scientific article; zbMATH DE number 3997916 (Why is no real title available?)
• Quicksort
• Renormalisation of curlicues
• Uniform distribution modulo one: a geometrical viewpoint.

Cited in

(1)

• scientific article; zbMATH DE number 1103060 (Why is no real title available?)

Describes a project that uses

Uses Software

• Quicksort

This page was built for publication: Uniform distribution modulo one and binary search trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q558117)