Premium
A study of random Weyl trees
Author(s) -
Devroye Luc,
Goudjil Amar
Publication year - 1998
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/(sici)1098-2418(199805)12:3<271::aid-rsa4>3.0.co;2-s
Subject(s) - struct , mathematics , combinatorics , irrational number , tree (set theory) , binary search tree , binary tree , fraction (chemistry) , random tree , binary number , discrete mathematics , computer science , geometry , arithmetic , artificial intelligence , chemistry , organic chemistry , motion planning , robot , programming language
We study binary search trees constructed from Weyl sequences { n θ}, n ≥1, where θ is an irrational and {·} denotes “mod 1.” We explore various properties of the structure of these trees, and relate them to the continued fraction expansion of θ. If H n is the height of the tree with n nodes when θ is chosen at random and uniformly on [0, 1], then we show that in probability, H n ∼(12/π 2 )log n log log n . © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 271–295, 1998