Dependence and phase changes in random m‐ary search trees
Dependence and phase changes in random m‐ary search trees
复制标题
随机玛丽搜索树中的依赖性和相位变化
DOI：
10.1002/rsa.20659
复制
发表时间：
2017
影响因子：
1
通讯作者：
R. Neininger
中科院分区：
文献类型：
--
作者：
R. Neininger
我们研究了随机m进制搜索树中空间需求和总路径长度（在所有根密钥距离上求和或在所有根节点距离上求和）的联合渐近行为。协方差原来表现出渐近行为的变化：它基本上是线性时，但成为高阶时。令人惊讶的是，相应的渐近相关系数趋于零时，但周期性振荡的largerm，我们也证明了渐近独立时。这种不太预期的现象并不例外，我们的结果可以在两个方向上扩展：一个是更一般的形状参数，另一个是其他类别的随机对数树，如边缘平衡二叉搜索树和四叉树。证明的方法联合收割机渐近转移的基本递归关系的压缩方法。© 2016 Wiley Periodicals，Inc.随机结构算法，50，353-379，2017
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 randomm‐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 largerm, 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
登录
查看更多内容
组合学、概率和通过收缩法计算 Pólya Urns
DOI：
--
发表时间：
--
期刊：
影响因子：
--
作者：
Margarete Knape;Ralph Neininger;Margarete Knapeand
通讯作者：
Margarete Knapeand
多维搜索树中的一些平均测度
DOI：
10.1016/0020-0190(87)90215-8
发表时间：
1987
期刊：
Inf. Process. Lett.
影响因子：
--
作者：
Ricardo Baeza
通讯作者：
Ricardo Baeza
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
Ralph Neininger;L. Rüschendorf
通讯作者：
L. Rüschendorf
超几何和四叉树的成本结构
DOI：
10.1002/rsa.3240070203
发表时间：
1995
期刊：
Random Struct. Algorithms
影响因子：
--
作者：
P. Flajolet;G. Labelle;Louise Laforest;B. Salvy
通讯作者：
B. Salvy
随机碎片问题中的相变及其在计算机科学中的应用
DOI：
10.1088/0305-4470/35/32/101
发表时间：
2002
期刊：
ArXiv
影响因子：
--
作者：
D. Dean;S. Majumdar
通讯作者：
S. Majumdar