Any sequence 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 be the height of the tree generated by Obviously If the sequences are generated by independent random variables having the uniform distribution on [0, 1], then it is well known that there exists such that as for almost all sequences . Recently Devroye and Goudjil have shown that if the sequences are Weyl sequences, i.e., defined by and is distributed uniformly at random on then as in probability. In this paper we consider the class of all uniformly distributed sequences , and we show that the only behaviour that is excluded by the equidistribution of is that of the worst case, i.e., for these we necessarily have as .
On peut construire à partir d’une suite 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 la hauteur de l’arbre obtenu à partir des nombres Il est évident que Si la suite est obtenue comme valeurs de variables aléatoires indépendantes uniformes sur [0,1], alors on sait qu’il existe tel que , presque-sûrement. Récemment, Devroye et Goudjil ont montré que si les sont les suites de Weyl, i.e., où est une variable aléatoire uniforme sur [0,1], alors en probabilité. Dans ce papier nous considérons la classe de toutes les suites uniformément réparties pour lesquelles nous montrons que l’on a nécessairement quand .
@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}, 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/} }
TY - JOUR TI - Uniform distribution modulo one and binary search trees JO - Journal de Théorie des Nombres de Bordeaux PY - 2002 DA - 2002/// SP - 415 EP - 424 VL - 14 IS - 2 PB - Université Bordeaux I UR - https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.366/ UR - https://zbmath.org/?q=an%3A1075.11054 UR - https://www.ams.org/mathscinet-getitem?mr=2040685 UR - https://doi.org/10.5802/jtnb.366 DO - 10.5802/jtnb.366 LA - en ID - JTNB_2002__14_2_415_0 ER -
Michel Dekking; Peter Van der Wal. Uniform distribution modulo one and binary search trees. Journal de Théorie des Nombres de Bordeaux, Volume 14 (2002) no. 2, pp. 415-424. doi : 10.5802/jtnb.366. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.366/
[1] Renormalisation of curlicues. Nonlinearity 1 (1988), 1-26. | MR: 928946 | Zbl: 0662.10029
, ,[2] 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] Uniform distribution modulo one: a geometrical viewpoint. J. Reine Angew. Math. 329 (1981), 143-153. | MR: 636449 | Zbl: 0459.10025
, ,[4] 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] A note on the height of binary search trees. J. Assoc. Comput. Mach. 33 (1986), 489-498. | MR: 849025 | Zbl: 0741.05062
,[6] A study of random Weyl trees. Random Structures Algorithms 12 (1998), 271-295. | MR: 1635260 | Zbl: 0919.68025
, ,[7] Quicksort. Comput. J. 5 (1962), 10-15. | MR: 142216 | Zbl: 0108.13601
,[8] 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] Asymptotical growth of a class of random trees. Ann. Probab. 13 (1985), 414-427. | MR: 781414 | Zbl: 0563.60010
,Cited by Sources: