Browsing by Author "Neininger, Ralph"

Now showing 1 - 2 of 2

Dependence and phase changes in random m-ary search trees
(2017-05-01)
Chern, Hua-Huai
;
Fuchs, Michael
;
Hwang, Hsien-Kuei
;
Neininger, Ralph
;
應用數學系
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 3m13, but becomes of higher order when m14. Surprisingly, the corresponding asymptotic correlation coefficient tends to zero when 3m26, but is periodically oscillating for larger m, and we also prove asymptotic independence when 3m26. 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. (c) 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 353-379, 2017
Profiles of random trees: Limit theorems for random recursive trees and binary search trees
(2006-11-01)
Fuchs, Michael
;
Hwang, Hsien-Kuei
;
Neininger, Ralph
;
應用數學系
;
Department of Applied Mathematics
We prove convergence in distribution for the profile (the number of nodes at each level), normalized by its mean, of random recursive trees when the limit ratio alpha of the level and the logarithm of tree size lies in [0, e). Convergence of all moments is shown to hold only for a E [0, 1] (with only convergence of finite moments when alpha is an element of (1, e)). When the limit ratio is 0 or 1 for which the limit laws are both constant, we prove asymptotic normality for alpha = 0 and a "quicksort type" limit law for alpha = 1, the latter case having additionally a small range where there is no fixed limit law. Our tools are based on the contraction method and method of moments. Similar phenomena also hold for other classes of trees; we apply our tools to binary search trees and give a complete characterization of the profile. The profiles of these random trees represent concrete examples for which the range of convergence in distribution differs from that of convergence of all moments.