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