随机二叉搜索树上的若干强极限性质

论文摘要

随机图论近十年已成为离散数学的主流之一,它创始于上世纪40年代,也就是图论发展的第三个阶段,由Erdos等人创立,是图论的一个分支。在随机图中,边的出现成为概率事件。随机图和经典图之间最大的区别在于引入了随机的方法,使得图的空间变得更大,其数学性质也发生了巨大的变化。本文所研究的随机二叉搜索树是随机图论二叉树的一种。本文细致讨论随机二叉搜索树的顶点数目Xn和大小为k的子树数目Sn,k的性质,根据递归等式计算Xn和Sn,k的4阶矩,再根据Chebychev不等式和Borel-Cantelli引理得到Xn和Sn,k的强极限性质,Yn和Zn的结果可类似的得到。本文在第一章中主要介绍了图论和随机图论的产生和发展。第二章介绍了图和随机二叉搜索树的基本知识。第三章考察了随机二叉搜索树的顶点数目Xn的强极限性质。第四章考察了随机二叉树子树数目Sj,k强极限性质。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 图论及随机图论的产生和发展
• 1.2 本课题研究的目的和任务
• 1.3 本课题研究的基本内容和意义
• 1.4 本课题国内外研究现状及趋势
• 第二章 预备知识
• 2.1 图的基本概念
• 2.2 树的基本概念树的性质
• 2.3 树的性质
• 2.4 随机树
• 2.5 二叉树
• 2.6 二叉树和树的差别
• 2.7 二叉树的性质
• 2.8 随机二叉搜索树
• 2.9 几个引理
• 第三章 随机二叉搜索树顶点数目的强极限定理
• 3.1 主要思想方法
• 3.2 一些相关引理
• 3.3 主要结果
• 第四章 关于随机二叉树子树大小的强极限定律
• 4.1 简介
• 4.2 主要思想方法
• 4.3 主要结果
• 结束语
• 致谢
• 参考文献
• 硕士在读期间发表的论文