Uniform distribution modulo one and binary search trees

Michel Dekking; Peter Van der Wal

doi:10.5802/jtnb.366

Michel Dekking ; Peter Van der Wal

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

Résumé
Abstract

On peut construire à partir d’une suite $x = {(x_{k})}_{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} (x)$ la hauteur de l’arbre obtenu à partir des nombres $x_{1}, \dots, x_{n} .$ Il est évident que $\frac{log n}{log 2} - 1 \leq H_{n} (x) \leq 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) \sim c log n, (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} = {α k}, k = 1, 2, \dots,$ où $α$ est une variable aléatoire uniforme sur [0,1], alors $H_{n} (x) \sim (12 / π^{2}) log n log log n, 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} (x) = o (n)$ quand $n \to \infty$ .

Any sequence $x = {(x_{k})}_{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} (x)$ be the height of the tree generated by $x_{1}, \dots, x_{n} .$ Obviously $\frac{log n}{log 2} - 1 \leq H_{n} (x) \leq 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) \sim c log n$ 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} = {α k}, k = 1, 2, \dots,$ and $α$ is distributed uniformly at random on $[0, 1]$ then $H_{n} (x) \sim (12 / π^{2}) log n log log n$ 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} (x) = o (n)$ as $n \to \infty$ .

MR 2040685 | Zbl 1075.11054

DOI : https://doi.org/10.5802/jtnb.366

@article{JTNB_2002__14_2_415_0,
     author = {Dekking, Michel and Van der Wal, Peter},
     title = {Uniform distribution modulo one and binary search trees},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     pages = {415--424},
     publisher = {Universit\'e Bordeaux I},
     volume = {14},
     number = {2},
     year = {2002},
     doi = {10.5802/jtnb.366},
     zbl = {1075.11054},
     mrnumber = {2040685},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.366/}
}

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. doi : 10.5802/jtnb.366. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.366/

Bibliographie

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

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

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

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

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

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

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

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

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