Dependence and phase changes in random m-ary search trees

檔案

本條目沒有附加檔案。

至出版者網站查看(DOI) ›

日期

2017-05-01

類型

期刊名稱

RANDOM STRUCTURES & ALGORITHMS

卷期與頁次

第 50 卷,頁 353–379

ISSN

1042-9832

語言

英文

摘要

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

所屬典藏

期刊論文
顯示完整詮釋資料 統計資料

引用此條目

Chern, H.-H., Fuchs, M., Hwang, H.-K., & Neininger, R. (2017). Dependence and phase changes in random m-ary search trees. RANDOM STRUCTURES & ALGORITHMS, 50, 353–379. https://doi.org/10.1002/rsa.20659

BibTeX RIS

引用文字依 APA 第 7 版格式自動產生,使用前請再核對。

分享

永久網址:https://ir.lib.nycu.edu.tw/handle/11536/145164