Uniform distribution modulo one and binary search trees

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 -