Uniform distribution modulo one and binary search trees
Journal de théorie des nombres de Bordeaux, Tome 14 (2002) no. 2, pp. 415-424

Any sequence x=(x k ) 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 ,⋯,x n . Obviously

log n log 2 - 1 ≤ H n ( x ) ≤ 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 (x)∼clogn as n→∞ 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 ={αk},k=1,2,⋯, and α is distributed uniformly at random on [ 0 , 1 ] then
H n ( x ) ∼ ( 12 / π 2 ) log n log log n
as n→∞ 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→∞.

On peut construire à partir d’une suite x=(x k ) k=1 ∞ 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 (x) la hauteur de l’arbre obtenu à partir des nombres x 1 ,⋯,x n . Il est évident que

log n log 2 - 1 ≤ H n ( x ) ≤ 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 (x)∼clogn,(n→∞), presque-sûrement. Récemment, Devroye et Goudjil ont montré que si les x sont les suites de Weyl, i.e., x k ={αk},k=1,2,⋯, où α est une variable aléatoire uniforme sur [0,1], alors
H n ( x ) ∼ ( 12 / π 2 ) log n log log n , n → ∞ ,
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 (x)=o(n) quand n→∞.

@article{JTNB_2002__14_2_415_0,
     author = {Michel Dekking and Peter Van der Wal},
     title = {Uniform distribution modulo one and binary search trees},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {415--424},
     year = {2002},
     publisher = {Universit\'e Bordeaux I},
     volume = {14},
     number = {2},
     zbl = {1075.11054},
     mrnumber = {2040685},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/item/JTNB_2002__14_2_415_0/}
}
TY  - JOUR
AU  - Michel Dekking
AU  - Peter Van der Wal
TI  - Uniform distribution modulo one and binary search trees
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2002
SP  - 415
EP  - 424
VL  - 14
IS  - 2
PB  - Université Bordeaux I
UR  - https://jtnb.centre-mersenne.org/item/JTNB_2002__14_2_415_0/
LA  - en
ID  - JTNB_2002__14_2_415_0
ER  - 
%0 Journal Article
%A Michel Dekking
%A Peter Van der Wal
%T Uniform distribution modulo one and binary search trees
%J Journal de théorie des nombres de Bordeaux
%D 2002
%P 415-424
%V 14
%N 2
%I Université Bordeaux I
%U https://jtnb.centre-mersenne.org/item/JTNB_2002__14_2_415_0/
%G en
%F JTNB_2002__14_2_415_0
Michel Dekking; Peter Van der Wal. Uniform distribution modulo one and binary search trees. Journal de théorie des nombres de Bordeaux, Tome 14 (2002) no. 2, pp. 415-424. https://jtnb.centre-mersenne.org/item/JTNB_2002__14_2_415_0/

[1] M.V. Berry, J. Goldberg, Renormalisation of curlicues. Nonlinearity 1 (1988), 1-26. | Zbl | MR

[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. | Zbl | MR

[3] F.M. Dekking, M. Mendès France, Uniform distribution modulo one: a geometrical viewpoint. J. Reine Angew. Math. 329 (1981), 143-153. | Zbl | MR

[4] J.-M. Deshouillers, Geometric aspect of Weyl sums. In Elementary and analytic theory of numbers (Warsaw, 1982), pages 75-82. PWN, Warsaw, 1985. | Zbl | MR

[5] L. Devroye, A note on the height of binary search trees. J. Assoc. Comput. Mach. 33 (1986), 489-498. | Zbl | MR

[6] L. Devroye, A. Goudjil, A study of random Weyl trees. Random Structures Algorithms 12 (1998), 271-295. | Zbl | MR

[7] C.A.R. Hoare, Quicksort. Comput. J. 5 (1962), 10-15. | Zbl | MR

[8] H.M. Mahmoud, Evolution of random search trees. John Wiley & Sons Inc., New York, 1992. Wiley-Interscience Series in Discrete Mathematics and Optimization. | Zbl | MR

[9] B. Pittel, Asymptotical growth of a class of random trees. Ann. Probab. 13 (1985), 414-427. | Zbl | MR