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
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
@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}, 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, Volume 14 (2002) no. 2, pp. 415-424. https://jtnb.centre-mersenne.org/item/JTNB_2002__14_2_415_0/
[1] Renormalisation of curlicues. Nonlinearity 1 (1988), 1-26. | MR | Zbl
, ,[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 | Zbl
, , ,[3] Uniform distribution modulo one: a geometrical viewpoint. J. Reine Angew. Math. 329 (1981), 143-153. | MR | Zbl
, ,[4] Geometric aspect of Weyl sums. In Elementary and analytic theory of numbers (Warsaw, 1982), pages 75-82. PWN, Warsaw, 1985. | MR | Zbl
,[5] A note on the height of binary search trees. J. Assoc. Comput. Mach. 33 (1986), 489-498. | MR | Zbl
,[6] A study of random Weyl trees. Random Structures Algorithms 12 (1998), 271-295. | MR | Zbl
, ,[7] Quicksort. Comput. J. 5 (1962), 10-15. | MR | Zbl
,[8] Evolution of random search trees. John Wiley & Sons Inc., New York, 1992. Wiley-Interscience Series in Discrete Mathematics and Optimization. | MR | Zbl
,[9] Asymptotical growth of a class of random trees. Ann. Probab. 13 (1985), 414-427. | MR | Zbl
,