# Uniform distribution modulo one and binary search trees

• Volume: 14, Issue: 2, page 415-424
• ISSN: 1246-7405

top

## Abstract

top
Any sequence $x={\left({x}_{k}\right)}_{k=1}^{\infty }$ of distinct numbers from [0,1] generates a binary tree by storing the numbers consecutively at the nodes according to a left-right algorithm (or equivalently by sorting the numbers according to the Quicksort algorithm). Let ${H}_{n}\left(x\right)$ be the height of the tree generated by ${x}_{1},\cdots ,{x}_{n}.$ Obviously$\frac{logn}{log2}-1\le {H}_{n}\left(x\right)\le n-1.$If the sequences $x$ are generated by independent random variables having the uniform distribution on [0, 1], then it is well known that there exists $c$ &gt; $0$ such that ${H}_{n}\left(x\right)\sim clogn$ as $n\to \infty$ for almost all sequences $x$. Recently Devroye and Goudjil have shown that if the sequences $x$ are Weyl sequences, i.e., defined by ${x}_{k}=\left\{\alpha k\right\},k=1,2,\cdots ,$ and $\alpha$ is distributed uniformly at random on [0, 1] then${H}_{n}\left(x\right)\sim \left(12/{\pi }^{2}\right)lognloglogn$as $n\to \infty$ in probability. In this paper we consider the class of all uniformly distributed sequences $x$, and we show that the only behaviour that is excluded by the equidistribution of $x$ is that of the worst case, i.e., for these $x$ we necessarily have ${H}_{n}\left(x\right)=o\left(n\right)$ as $n\to \infty$.

## How to cite

top

Dekking, Michel, and Van der Wal, Peter. "Uniform distribution modulo one and binary search trees." Journal de théorie des nombres de Bordeaux 14.2 (2002): 415-424. <http://eudml.org/doc/248909>.

@article{Dekking2002,
abstract = {Any sequence $x = (x_k)^\infty _\{k=1\}$ of distinct numbers from [0,1] generates a binary tree by storing the numbers consecutively at the nodes according to a left-right algorithm (or equivalently by sorting the numbers according to the Quicksort algorithm). Let $H_n(x)$ be the height of the tree generated by $x_1, \dots , x_n.$ Obviously\begin\{equation*\}\frac\{\log n\}\{\log 2\} -1 \le H\_n(x) \le n-1.\end\{equation*\}If the sequences $x$ are generated by independent random variables having the uniform distribution on [0, 1], then it is well known that there exists $c$ &gt; $0$ such that $H_n(x) \sim c \log n$ as $n \rightarrow \infty$ for almost all sequences $x$. Recently Devroye and Goudjil have shown that if the sequences $x$ are Weyl sequences, i.e., defined by $x_k = \lbrace \alpha k\rbrace , k = 1, 2, \dots ,$ and $\alpha$ is distributed uniformly at random on [0, 1] then\begin\{equation*\} H\_n(x) \sim (12 / \pi ^2) \log n \log \log n \end\{equation*\}as $n \rightarrow \infty$ in probability. In this paper we consider the class of all uniformly distributed sequences $x$, and we show that the only behaviour that is excluded by the equidistribution of $x$ is that of the worst case, i.e., for these $x$ we necessarily have $H_n(x) = o(n)$ as $n \rightarrow \infty$.},
author = {Dekking, Michel, Van der Wal, Peter},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {uniform distribution; binary search trees},
language = {eng},
number = {2},
pages = {415-424},
publisher = {Université Bordeaux I},
title = {Uniform distribution modulo one and binary search trees},
url = {http://eudml.org/doc/248909},
volume = {14},
year = {2002},
}

TY - JOUR
AU - Dekking, Michel
AU - Van der Wal, Peter
TI - Uniform distribution modulo one and binary search trees
JO - Journal de théorie des nombres de Bordeaux
PY - 2002
PB - Université Bordeaux I
VL - 14
IS - 2
SP - 415
EP - 424
AB - Any sequence $x = (x_k)^\infty _{k=1}$ of distinct numbers from [0,1] generates a binary tree by storing the numbers consecutively at the nodes according to a left-right algorithm (or equivalently by sorting the numbers according to the Quicksort algorithm). Let $H_n(x)$ be the height of the tree generated by $x_1, \dots , x_n.$ Obviously\begin{equation*}\frac{\log n}{\log 2} -1 \le H_n(x) \le n-1.\end{equation*}If the sequences $x$ are generated by independent random variables having the uniform distribution on [0, 1], then it is well known that there exists $c$ &gt; $0$ such that $H_n(x) \sim c \log n$ as $n \rightarrow \infty$ for almost all sequences $x$. Recently Devroye and Goudjil have shown that if the sequences $x$ are Weyl sequences, i.e., defined by $x_k = \lbrace \alpha k\rbrace , k = 1, 2, \dots ,$ and $\alpha$ is distributed uniformly at random on [0, 1] then\begin{equation*} H_n(x) \sim (12 / \pi ^2) \log n \log \log n \end{equation*}as $n \rightarrow \infty$ in probability. In this paper we consider the class of all uniformly distributed sequences $x$, and we show that the only behaviour that is excluded by the equidistribution of $x$ is that of the worst case, i.e., for these $x$ we necessarily have $H_n(x) = o(n)$ as $n \rightarrow \infty$.
LA - eng
KW - uniform distribution; binary search trees
UR - http://eudml.org/doc/248909
ER -

## References

top
1. [1] M.V. Berry, J. Goldberg, Renormalisation of curlicues. Nonlinearity1 (1988), 1-26. Zbl0662.10029MR928946
2. [2] F.M. Dekking, S. De Graaf, L.E. Meester, On the node structure of binary search trees. In Mathematics and Computer Science - Algorithms, Trees, Combinatorics and Probabilities (Eds. Gardy, D. and Mokkadem, A.), pages 31-40. Birkhauser, Basel, 2000. Zbl0965.68068MR1798285
3. [3] F.M. Dekking, M. Mendès France, Uniform distribution modulo one: a geometrical viewpoint. J. Reine Angew. Math.329 (1981), 143-153. Zbl0459.10025MR636449
4. [4] J.-M. Deshouillers, Geometric aspect of Weyl sums. In Elementary and analytic theory of numbers (Warsaw, 1982), pages 75-82. PWN, Warsaw, 1985. Zbl0616.10031MR840473
5. [5] L. Devroye, A note on the height of binary search trees. J. Assoc. Comput. Mach.33 (1986), 489-498. Zbl0741.05062MR849025
6. [6] L. Devroye, A. Goudjil, A study of random Weyl trees. Random Structures Algorithms12 (1998), 271-295. Zbl0919.68025MR1635260
7. [7] C.A.R. Hoare, Quicksort. Comput. J.5 (1962), 10-15. Zbl0108.13601MR142216
8. [8] H.M. Mahmoud, Evolution of random search trees. John Wiley & Sons Inc., New York, 1992. Wiley-Interscience Series in Discrete Mathematics and Optimization. Zbl0762.68033MR1140708
9. [9] B. Pittel, Asymptotical growth of a class of random trees. Ann. Probab.13 (1985), 414-427. Zbl0563.60010MR781414

## NotesEmbed?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.