Dependence and phase changes in random m-ary search trees

Hua Huai Chern, Michael Fuchs*, Hsien Kuei Hwang, Ralph Neininger

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 3 ≤ m ≤ 13, but becomes of higher order when m ≥ 14. Surprisingly, the corresponding asymptotic correlation coefficient tends to zero when 3 ≤ m ≤ 26, but is periodically oscillating for larger m, and we also prove asymptotic independence when 3 ≤ m ≤ 26. 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.

Original languageEnglish
Pages (from-to)353-379
Number of pages27
JournalRandom Structures and Algorithms
Volume50
Issue number3
DOIs
StatePublished - 1 May 2017

Keywords

  • asymptotic analysis
  • asymptotic transfer
  • contraction method
  • correlation
  • dependence
  • limit law
  • m-ary search tree
  • recurrence relations

Fingerprint Dive into the research topics of 'Dependence and phase changes in random m-ary search trees'. Together they form a unique fingerprint.

Cite this