Dependence and phase changes in random m‐ary search trees |
| |
| Authors: | Hua‐Huai Chern Michael Fuchs Hsien‐Kuei Hwang Ralph Neininger |
| |
| Institution: | 1. Department of Computer Science, National Taiwan Ocean University, Keelung, Taiwan;2. Department of Applied Mathematics, National Chiao Tung University, Hsinchu, Taiwan;3. Institute of Statistical Science, Academia Sinica, Taipei, Taiwan;4. Institute for Mathematics, Goethe University, Frankfurt a.M., Germany |
| |
| Abstract: | We study the joint asymptotic behavior of the space requirement and the total path length (either summing over all root‐key distances or over all root‐node distances) in random m‐ary search trees. The covariance turns out to exhibit a change of asymptotic behavior: it is essentially linear when  , but becomes of higher order when  . Surprisingly, the corresponding asymptotic correlation coefficient tends to zero when  , but is periodically oscillating for larger m, and we also prove asymptotic independence when  . Such a less anticipated phenomenon is not exceptional and our results can be extended in two directions: one for more general shape parameters, and the other for other classes of random log‐trees such as fringe‐balanced binary search trees and quadtrees. The methods of proof combine asymptotic transfer for the underlying recurrence relations with the contraction method. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 353–379, 2017 |
| |
| Keywords: | m‐ary search tree correlation dependence recurrence relations asymptotic analysis limit law asymptotic transfer contraction method |
|
|
, but becomes of higher order when 
. Surprisingly, the corresponding asymptotic correlation coefficient tends to zero when 
, but is periodically oscillating for larger m, and we also prove asymptotic independence when 
. Such a less anticipated phenomenon is not exceptional and our results can be extended in two directions: one for more general shape parameters, and the other for other classes of random log‐trees such as fringe‐balanced binary search trees and quadtrees. The methods of proof combine asymptotic transfer for the underlying recurrence relations with the contraction method. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 353–379, 2017