# Uniform distribution modulo one and binary search trees

Michel Dekking; Peter Van der Wal

Journal de théorie des nombres de Bordeaux (2002)

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

## Access Full Article

top## Abstract

top## How to cite

topDekking, 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$ > $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$ > $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] M.V. Berry, J. Goldberg, Renormalisation of curlicues. Nonlinearity1 (1988), 1-26. Zbl0662.10029MR928946
- [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] 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] 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] L. Devroye, A note on the height of binary search trees. J. Assoc. Comput. Mach.33 (1986), 489-498. Zbl0741.05062MR849025
- [6] L. Devroye, A. Goudjil, A study of random Weyl trees. Random Structures Algorithms12 (1998), 271-295. Zbl0919.68025MR1635260
- [7] C.A.R. Hoare, Quicksort. Comput. J.5 (1962), 10-15. Zbl0108.13601MR142216
- [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] B. Pittel, Asymptotical growth of a class of random trees. Ann. Probab.13 (1985), 414-427. Zbl0563.60010MR781414

## NotesEmbed ?

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