|
|||||
|
|
A study of random Weyl trees |
|
| Authors: | Luc Devroye Amar Goudjil |
| Abstract: | 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 Hn 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, Hn∼(12/π2)log n log log n. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 12, 271–295, 1998 |
| Keywords: | Weyl sequence random number generation binary search trees probabilistic analysis tree height |