均匀递归树的度和随机二叉搜索树同构的极限定理

摘要

本文主要涉及均匀递归树和m-delayed均匀递归树上顶点的度相关问题以及随机二叉搜索树上子树的式样问题.
　　 对于第一部分，主要研究了大小为n的均匀递归树上，{1，2,…，n}上均匀分布Un的度的分布情况，我们在任意顶点i的度的基础上，再运用独立的条件，得到Un的度DUn的均值和方差，以及它的确切分布，并在此基础上运用递归方程得到它的极限分布;接着研究了m-delayed均匀递归树上任意顶点i的度Dmi的分布情况，同样我们把Dmi用Bernulli独立随机变量和的形式表现出来，由此得到它的均值和方差，并在此基础上用矩母函数得出Dmi的中心极限定理以及其他极限性质.
　　 在另一部分，主要研究了随机二叉搜索树上子树样式的重复问题.对于固定形状的无编号树Γ，首先我们构造一个样式函数，再通过分布等式得到随机二叉搜索树上子树与Γ同构的数目RΓ[n]的均值和方差，最后我们证明了RΓ[n]的中心极限定理.证明过程中我们运用了压缩法.

目录

声明

摘要

第一章 绪论

1．1 图的简介

1．2 树和随机树简介

1．3 本文的主要研究成果

第二章 均匀递归树任意顶点的度

2．1 均匀递归树的定义

2．2 均匀递归树任意顶点的度

2．3 均匀递归树随机顶点的度

2．4 m-delayed均匀递归树的任意顶点的度

第三章 随机二叉搜索树子树的式样问题

3．1 随机二叉搜索树

3．2 关于与给定树同构的研究

3．3 随机二叉搜索树中与给定树同构的子树数目

3．4 Rn的矩

3．4．1 Rn的期望

3．4．2 Rn的方差

3．5 Rn的极限分布

参考文献

附录A 推论5．2

致谢