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

摘要

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

目录

文摘

英文文摘

声明

第一章绪论

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主要结果

结束语

致谢

参考文献

硕士在读期间发表的论文