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$ > $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 -
