| 随机二叉搜索树的子树 |
| |
| 引用本文： | 苏淳,缪柏其,冯群强.随机二叉搜索树的子树[J].应用概率统计,2006,22(3):304-310. |
| |
| 作者姓名： | 苏淳 缪柏其 冯群强 |
| |
| 作者单位： | 中国科学技术大学统计与金融系,合肥,230026 |
| |
| 基金项目： | 受国家自然科学基金(批准号：10371117)，教育部博士点基金，中国科学技术大学高水平大学建设基金 |
| |
| 摘 要： | 本文讨论随机二叉搜索树上不同大小的子树和与给定某个二叉树同构的子树. 利用递归分布等式, 我们得出了它们各自数目的期望和方差\bd 最后, 用压缩法得出了它们的中心极限定理.
|
| 关 键 词： | 二叉搜索树 中心极限定理 概率分布的距离 不动点. |
| 收稿时间： | 2006-04-07 |
| 修稿时间： | 2006年4月7日 |
On the Subtrees of Random Binary Search Trees |
| |
| SU CHUN,MIAO BAIQI,FENG QUNQIANG.On the Subtrees of Random Binary Search Trees[J].Chinese Journal of Applied Probability and Statisties,2006,22(3):304-310. |
| |
| Authors: | SU CHUN MIAO BAIQI FENG QUNQIANG |
| |
| Institution: | Department of Statistics and Finance, University of Science and Technology of China, Hefei, 230026 |
| |
| Abstract: | The subtrees of various sizes and patterns in random binary search trees are investigated in this paper. The expectations and variances of their numbers are first derived from an essential recursive distributional equation. Applying the contraction method, we show both of their asymptotic distributions are normal. |
| |
| Keywords: | |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《应用概率统计》浏览原始摘要信息 |
| 点击此处可从《应用概率统计》下载免费的PDF全文 |
