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