随机二又搜索树上顶点数目的极限定理

导出

摘要主要研究大小为n的随机二叉搜索树上3种不同类型的顶点数目.分别以X_n,Y_n和Z_n表示树中含有0,1,2个子点的顶点的数目.在建立X_n递归关系式的基础上,得到了X_n的期望、方差和大数律,并用压缩法证得了X_n的渐近正态性.对于Y_n和Z_n,也得到了类似的结论.

作者刘杰苏淳陈昱

机构地区中国科学技术大学统计与金融系

出处《中国科学（A辑）》 CSCD 北大核心 2007年第9期1047-1058,共12页 Science in China(Series A)

基金国家自然科学基金(批准号:10671188) 中国科学院知识创新工程重要方向项目基金(KJCX3-SYW-S02) 中国科学技术大学高水平大学建设基金

关键词随机二叉搜索树顶点大数律压缩法极限分布

参考文献26

1Kirschenhofer P. On the height of leaves in binary trees.J Combin Inform Sys Sci, 8:44-60 (1983)
2Panholzer A, Prodinger H. Descendants and ascendants in binary trees. Discrete Math Theor Comput Sci, 1:247-266 (1997)
3Devroye L, Neininger R. Distances and finger search in random binary search trees. SIAM J Comput, 33: 647-658 (2004)
4Mahmoud H, Neininger R. Distribution of distances in random binary search trees. Ann Appl Probab, 13(1): 253-276 (2003)
5Svante J. Left and right pathlenghts in random binary trees. Algorithmica, 46:419-429 (2006)
6Devroye L. Applications of Stein's method in the analysis of random binary search trees. In: Chen L, Barbour A, eds. Stein's Method and Applications. Institute for Mathematical Sciences Lecture Notes Series, vol. 5. Singapore: World Scientific Press, 2005, 247-297
7Drmota M. An analytic approach to the height of binary search trees. J Assoc Comput Mach, 29:89-119 (2001)
8Drmota M. An analytic approach to the height of binary search trees Ⅱ. J Assoc Comput Mach, 50:333-374 (2003)
9Devroye L. A note on the height of binary search trees. J Assoc Comput Mach, 33:489-498 (1986)
10Devroye L. Branching processes in the analysis of the height of trees. Acta Inform, 24:277-298 (1987)

1Aldous,D.& Pitman,J.,Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent,Probab.Theory Relat.Fields,2000,118:455-482.
2Devroye,L.,A note on the height of binary search trees,J.Assoc.Comput.Mach.,1986,33:489-498.
3Fill,J.,Mahmoud,H.& Szpankowski,W.,On the distribution for the duration of a randomized leader election algorithm,Ann.Appl.Prob.,1996,6,1260-1283.
4Itoh,Y.& Hosam,M.,One-side variations on interval trees,J.Appl.Prob.,2003,40:654-670.
5Mahmoud,H.,Evolution of Random Seach Trees,John Wiley,New York,1992.
6Mahmoud,H.,One-side variations on binary search trees,Ann.Inst.Statist.Math.,2003,55:885-900.
7Petrov,V.V.,Limit Theorems of Probability Theory,Clarendon Press,Oxford,1995.
8Prodinger,H.,How to select a loser,Discrete Math.,1993,120:149-159.
9Rachev,S.T.,Probability Metrics and the Stability of Stochastic Models,Wiley,New York,1991.
10Sibuya,M.& Itoh,Y.,Random sequential bisection and its associated binary tree,Ann.Inst.Statist.Math.,1987,39:69-84.

1LIU Jie,SU Chun,CHEN Yu.Limiting theorems for the nodes in binary search trees[J].Science China Mathematics,2008,51(1):101-114. 被引量：1
2卢霄青,彭维才.随机二叉搜索树上的若干强极限性质[J].安徽工业大学学报（自然科学版）,2009,26(1):96-101.

1卢霄青,彭维才.随机二叉搜索树上的若干强极限性质[J].安徽工业大学学报（自然科学版）,2009,26(1):96-101.
2蔡日增.化重积分为累次积分的压缩法[J].大学数学,1994,15(4):154-157.
3苏淳,缪柏其,冯群强.随机二叉搜索树的子树[J].应用概率统计,2006,22(3):304-310. 被引量：2
4骆崇亮,冯群强,张曙光.随机二叉树的几种拓扑指标(英文)[J].中国科学技术大学学报,2013,43(12):967-974.
5余长安.三项非齐次变系数递归关系解的结构[J].武汉大学学报（自然科学版）,1992(1):117-119.
6杨欣芳.代数学中涉及的组合数学知识——从利用递归关系式计算行列式说起[J].韶关师专学报,1991(1):31-36.
7杨利民.S^(n)={K_i:1≤i≤n}-因子数的递归关系式[J].Journal of Mathematical Research and Exposition,1991,11(1):78-78. 被引量：11
8袁南桥.关于{F_n}的一类恒等式的证明[J].达县师范高等专科学校学报,2000,10(2):21-22.
9刘晓君,李险峰,何万生,杨丽新.二维三次方离散系统的混沌控制与广义混沌同步[J].河北师范大学学报（自然科学版）,2010,34(4):406-410. 被引量：2
10杨传富,代成.线性非齐次递归式的求解[J].安庆师范学院学报（自然科学版）,2006,12(4):84-85.

中国科学（A辑）

2007年第9期

内容加载中请稍等...