本书主要基于作者参与的随机树研究成果和国内外重要相关研究,结合具有代表性的研究方法,围绕均匀递归树、随机搜索树、区间树三类模型的概率极限性质展开,系统介绍该领域的研究方法、成果和动态。全书共8章,包括简介、随机树模型的研究方法、均匀递归树的顶点距离、均匀递归树子树的多样性、随机搜索树的顶点类别、随机搜索树的子树大小、单边区间树、完全区间树。
样章试读
目录
- 目录
前言
记号
第1章简介1
1.1基本概念1
1.2随机树模型概述7
1.3随机树模型的极限性质概述9
第2章随机树模型的研究方法12
2.1概率距离12
2.2生成函数26
第一部分均匀递归树的极限性质
第3章均匀递归树的顶点距离33
3.1均匀递归树的定义33
3.2顶点距离的相关研究35
3.3任意两个顶点间的距离38
第4章均匀递归树子树的多样性47
4.1均匀递归子树大小的多样性47
4.2Sn,k矩的计算48
4.2.1均值48
4.2.2方差49
4.2.3解析方法下分析子树大小多样性52
4.3固定大小的子树多样性极限分布69
4.4固定形状的子树多样性74
第二部分随机搜索树的极限性质
第5章随机搜索树的顶点类别79
5.1随机搜索树的定义79
5.2递归方程84
5.3极限分布90
第6章随机搜索树的子树大小99
6.1子树大小的矩与极限分布101
6.2与给定树同构的子树数目106
6.3子树大小的多样性107
第三部分随机区间树的极限性质
第7章单边区间树121
7.1单边区间树的定义121
7.1.1单边区间分割的定义121
7.1.2单边区间树大小与高度的性质124
7.2单边区间树的最大间隔130
第8章完全区间树136
8.1完全区间树的定义136
8.2完全区间树的概率空间与递归方程138
8.3完全区间树大小的矩141
8.4完全区间树的极限定理150
参考文献158