Uniform distribution modulo one and binary search trees

Dekking, Michel ; Van der Wal, Peter

Journal de théorie des nombres de Bordeaux, Tome 14 (2002) no. 2, pp. 415-424

Abstract (VO)

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>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 (12/{\pi }^2)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$.

Résumé

On peut construire à partir d’une suite $x={\left(x_k\right)}_{k=1}^{\infty }$ de nombres distincts de l’intervalle [0,1] un arbre binaire en plaçant successivement ces nombres sur les noeuds selon un algorithme “gauche-droite” (cela revient à classer les nombres selon l’algorithme Quicksort). On note $H_n\left(x\right)$ la hauteur de l’arbre obtenu à partir des nombres $x_1,\cdots ,x_n.$ Il est évident que

$$\frac{logn}{log2}-1\le H_n\left(x\right)\le n-1.$$

Si la suite $x$ est obtenue comme valeurs de variables aléatoires indépendantes uniformes sur [0,1], alors on sait qu’il existe $c>0$ tel que $H_n\left(x\right)\sim clogn,(n\to \infty )$, presque-sûrement. Récemment, Devroye et Goudjil ont montré que si les $x$ sont les suites de Weyl, i.e., $x_k=\left\{\alpha k\right\},k=1,2,\cdots ,$ où $\alpha$ est une variable aléatoire uniforme sur [0,1], alors

$$H_n\left(x\right)\sim (12/{\pi }^2)lognloglogn,n\to \infty ,$$

en probabilité. Dans ce papier nous considérons la classe de toutes les suites $x$ uniformément réparties pour lesquelles nous montrons que l’on a nécessairement $H_n\left(x\right)=o\left(n\right)$ quand $n\to \infty$.