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

作　　者：刘杰[1] 苏淳[1] 陈昱[1] 

机构地区：[1]中国科学技术大学统计与金融系,合肥230026

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

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

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

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

分 类 号：O211.4[理学—概率论与数理统计]