（基础数学专业论文）随机二叉搜索树上的若干强极限性质.pdf

江苏大 学 硕 士 学 位论 文 摘要 随机图论近十年已成为离散数学的主流之一，它创始于上世纪4 0 年代，也就是图论发展的第三个阶段，由e r d o s 等人创立，是图论的 一个分支。在随机图中，边的出现成为概率事件。随机图和经典图之 间最大的区别在于引入了随机的方法，使得图的空间变得更大，其数 学性质也发生了巨大的变化。 本文所研究的随机二叉搜索树是随机图论二叉树的一种。本文细 致讨论随机二叉搜索树的顶点数目以和大小为k 的子树数目最。的性 质，根据递归等式计算邑和最。的4 阶矩，再根据c h e b y c h e v 不等式和 b o r e l c a n t e l l i 引理得到瓦和最。的强极限性质，k 和乙的结果可类似的 得到。本文在第一章中主要介绍了图论和随机图论的产生和发展。第 二章介绍了图和随机二叉搜索树的基本知识。第三章考察了随机二叉 搜索树的顶点数目x 。的强极限性质。第四章考察了随机二叉树子树数 目s ，。强极限性质。 关键词0 图，二叉树，随机图，随机二又搜索树，顶点，子树，极限 性质 江苏大 学 硕 士 学位论 文 a b s t r a c t s t o c h a s t i cg r a p ht h e o r yi nt h er e c e n tt e ny e a r sh a v eb e c o m eo n eo f d i s c r e t em a t h e m a t i c sm a i n s t r e a m s ，i ti n i t i a t e di nt h e1 9 4 0 s ，w a sa l s ot h e g r a p ht h e o r yd e v e l o p m e n tt h i r ds t a g e ，b ye r d o se ta 1 e s t a b l i s h e d ，w a sa g r a p ht h e o r yb r a n c h i ns t o c h a s t i cg r a p h ，a p p e a r a n c ei n t op r o b a b i l i t ye v e n t b e t w e e nt h es t o c h a s t i cg r a p ha n dt h ec l a s s i c a lg r a p ht h eb i g g e s td i f f e r e n c e l a yi nh a si n t r o d u c e dt h es t o c h a s t i cm e t h o d ，c a u s e dt h es p a c eo ft h eg r a p h b e c o m e sb i g g e r , i t sm a t h e m a t i c sn a t u r eh a sa l s oh a dt h eh u g ec h a n g e i nt h i sp a p e r ，t h es t u d yo fr a n d o m b i n a r ys e a r c ht r e ei sar a n d o mg r a p h t h e o r i e so fat r e e t h i sa r t i c l ed e t a i l e dd i s c u s st h ep e a kn u m b e rx 。a n dt h e n u m b e ro fs u b t r e e s 瓯io fr a n d o mb i n a r ys e a r c ht r e e a c c o r d i n gt ot h e r e c u r s i v ec a l c u l a t i o no ft h ee q u a t i o na n dt h e4 - o r d e rm o m e n to fx n a n d s 。，t ，a c c o r d i n gt oc h e b y c h e vi n e q u a l i t ya n dt h eb o r e l - c a n t e u il e m m a t ob es t r o n gl i m i tn a t u r eo f x 。a n d s n i nt h i sp a p e r ，i nt h ef i r s tc h a p t e r i n t r o d u c e st h er a n d o mg r a p ht h e o r ya n dg r a p ht h e o r yo ft h eb i r t ha n d d e v e l o p m e n t t h es e c o n dc h a p t e ri sd e v o t e dt ot h eb a s i ck n o w l e d g eo fm a p a n dr a n d o mb i n a r ys e a r c ht r e e t h et h i r dc h a p t e ri sa b o u tt h es t r o n gl i m i t l a wo ft h ep e a kn u m b e rx n t h e f o u r t hc h a p t e ri sa b o u tt h es t r o n gl i m i t l a wo ft h en u m b e ro fs u b t r e e s s 。，i k e y w o r d s ：g r a p h ，b i n a r ys e a r c ht r e e ，r a n d o mg r a p h ，r a n d o mb i n a r y s e a r c ht r e e ，p e a kn u m b e r ，s u b t r e e ，l i m i tp r o p e r t y 江苏大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在 年解密后适用本授权书。 不保密团。 笋苇荔 坦导教师笃名：飞习彳趴 弦。净 、玛l 归 、 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：卢霄孝 日期：力军层月莎自 江苏大学 硕士 学位论 文 第一章绪论 1 1 图论及随机图论的产生和发展 图论( g r a p ht h e o r y ) 的产生和发展经历了二百多年的历史，大体上可以划分 为三个阶段。 第一阶段是从1 7 3 6 年到到1 9 世纪中叶。这时的图论处于萌芽阶段，多数问题 是围绕着游戏产生的，最有代表性的工作是著名的瑞士数学家l e u l e r 于1 7 3 6 年的 k 6 n i g s b e r g 七桥问题。他的那篇论文被公认为图论历史上第一篇论文。 第二阶段是从1 9 世纪中叶至1 1 9 3 6 年。这个时期中图论问题大量出现，如四色 问题( 1 8 5 2 年) 和h a m i l t o n 问题( 1 8 5 6 年) 。同时出现了以图为工具去解决其他 领域中一些问题的成果。最有代表性的工作是k r i c h h o f f ( 1 8 4 7 年) 和c a y l e y ( 1 8 5 7 年) 分别用树的概念去研究电网络方程组和有机化合物的分子结构问题。“图 ( g r a p h ) ”这个词第一次出现是在1 8 7 8 年的英国 杂志中，进入2 0 世纪3 0 年 代，出现了一大批精彩的新理论和结果，如m e n g e r 定理( 1 9 2 7 年) ，k u r a t o w s k i 定理( 1 9 3 0 年) 和r a m s e y 定理( 1 9 3 0 年) 等等。这些理论和结果为图论的发展 奠定了基础。1 9 3 6 年，匈牙利数学家d k o n i g 写出了第一本图论专著有限图和 无限图理论。图论作为数学的一个新分支已基本形成。 1 9 3 6 年以后是第三个阶段。由于生产管理、军事、交通运输、计算机和通讯 网络等方面许多离散性问题的出现，大大促进了图论的发展。进入7 0 年代以后， 特别是大型电子计算机的出现，使大规模求解成为可能。图的理论及其在物理、 化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及 经济管理等几乎所有学科领域中个方面应用的研究都得到“爆炸性发展 。 图论的研究有其丰富的内涵，主要体现在以下两个方面： 1 图论提供了一个自然的结构，其中包括大量极具挑战性的问题，而由此 产生的数学模型几乎适合于所有科学( 自然科学和社会科学) 领域，只要这个领 域研究的主题是“对象 与“对象”之间的关系。 江 苏 大 学硕 士 学位 论文 2 图论已经形成了自己的丰富词汇语言，它能简洁地表示出各个领域中“对 象一关系”结构复杂而又难懂的概念。图论思想和方法越来越多的被许多科学领 域所接受，并已发挥且将日益发挥它的作用。反过来，这些得益于图论的科学领 域又向图论提出新的研究课题，新的概念和新的研究方法，从而进一步使图论的 知识得到丰富和扩充。 随机图论近十年已成为离散数学的主流之一，它创始于上世纪4 0 年代，也 就是图论发展的第三个阶段，由e r d o s 等人创立，是图论的一个分支。最早提出 的经典随机图模型就是e r 模型。在随机图中，边的出现成为概率事件。随机图 和经典图之间最大的区别在于引入了随机的方法，使得图的空间变得更大，其数 学性质也发生了巨大的变化，在随机图的经典数学模型中，随机图上的顶点度数 分布服从泊松分布。 经过长达6 0 多年的研究，最近由圣塔非的m e jn e w m a n 等人将随机图中 的度数分布扩展到任意度数分布，我们称之为”广义随机图”，这使得对复杂网络 的研究有了进一步的深入。虽然广义随机图理论在解决p o w e r - l a w 问题上仍然存 在这一定的缺陷。但是至少它在仿真上已经被证实了。 1 2 本课题研究的目的和任务 概率论是研究大量随机现象统计规律的- i 1 学科，所谓“大量 ，从数学角 度来讲，就是当对随机现象的观测次数趋向无穷时它的“极限 所呈现出来的某 种规律性因此，强极限定理一直以来都在概率论中有着极其重要的地位，并且 也是概率论其他分支的重要基础前苏联著名概率论学者科尔莫戈罗夫和格涅坚 科在评论概率论极限理论时曾说：“概率论的认识论的价值只有通过极限理论才 能被揭示，没有极限定理就不可能去理解概率论的基本概念的真正含义( 文 1 ) 概率论的真正历史被公认为从十七世纪中叶开始，从那时至今，惠更斯、 贝努里、高斯、马尔可夫、柯尔夫莫哥洛夫等数学家将概率论不断向前推进，而 极限理论也同时得到了发展十九世纪二十年代之前，中心极限定理是概率论研 究的中心课题随着其他理论的不断健全，科学家们对近代极限理论的研究至今 2 江 苏 大 学硕 士 学 位论文 方兴未艾，他们的研究不仅深化了经典理论的许多基本结果，也极大的拓展了今 后的研究领域 本文主要研究随机二叉搜索树上的强极限定理。对随机树的研究起源于上个 世纪六七十年代，当时的背景主要来自组合数学，例如随机标号根树，随机无标 号根树等等。而现在考察的随机树模型的背景非常广泛，例如二叉搜索树，数字 搜索树，索回树等来源于计算机算法。 1 3 本课题研究的基本内容和意义 ( 3 1 ) 式和( 4 1 ) 式中的两个递推关系式是本文计算的基础。本文通过计 算z 。和s 础的4 阶矩，再根据c h e b y c h e v 不等式和b o r e l - c a n t e l l i 引理得到x 。和 最。的强极限性质，匕和z 。的结果可类似的结果得到。 通过对这些随机树的概率分析，可以对提高数据的存储，搜索，排序的速度 起一定的指导作用；而随机递归树不仅跟计算机科学中的u n i o n - f i n d 算法有关 系，还可以用来模拟传染病的传播，刻画计算机网络的随机扩张等等；在有机化 学中，很多分子的结构也是树状的，如烷，炳，烯等各自的分子族就构成了一个 随机树族。 1 4 本课题国内外研究现状及趋势 已有很多计算机科学家和数学家在文献和著作中深入讨论过随机二叉搜索 树的一些参数的性质。例如：例如k i r s c h e n h o f e r ( 文 1 ) 考察了随机二叉搜索树 的高度和叶点数目；p a n h o l z e r 和p r o d i n g e r ( 文 2 ) 研究了任意给定顶点的祖先和 后代的数目；d e v r o y e 和n e i n i n g e r ( 文 3 ) 得到了任意两个顶点距离的高阶矩的 阶和尾部的界；m a h m o n d 和n e i n i n g e r ( 文 4 ) 则得到了任意一对顶点间距离的 g a u s s 极限分布。并刻画了它的收敛速度；s v a n t e ( 文 5 ) 准确地得到了随机二叉 搜索树左右子树路径总长之差的矩和极限分布。d e v r o y e ( 文 6 ) 用s t e i n 方法研 究了随机二叉搜索树上若干参数的渐近性质。此外，还有其他学者讨论了随机二 叉搜索树的高度，并得到了它的一些性质。如：期望和方差的渐近式，极限分布( 文 3 江 苏 大 学 硕 士 学 位论文 7 ， 8 ) 。 p r o d i n g e r ( 文 9 ) 计算了大小为”的均匀分布的二叉树中包含f 个具有两个 后代的顶点的概率。r o t e ( 文 1 0 ) 用3 中组合方法计算了含有给定数目带有0 ， 1 和2 个后代的顶点的二叉搜索树的个数。刘杰和苏淳等( 文 1 1 ) 研究了带有0 ， l 和2 个后代的顶点的数目的极限定理。苏淳和缪柏其等( 文 1 2 ) 研究了随机二 叉搜索树的大小为k 的子树的数目的若干极限性质。 4 江 苏大 学 硕 士 学 位论文 2 1 图的基本概念 第二章预备知识 弟一早 耿冒刘以 在自然界和人类社会的实际生活中，用图形来描述某些对象或事物之间所具 有某种特定关系时常常感到特别的方便。例如用工艺流程图描述某项工程中各工 序之间的先后关系，用竞赛图来描述某循环比赛中各选手之间的胜负关系，用网 络图来描述某通讯系统中各通讯站之间的信息传递关系。用交通图来描述某地区 内各城市之间的铁路连接关系。用原理电路图描述某电器内各元件之间的导线连 接关系，等等， 图形中的点表示对象( 如上例中的工序，选手，通讯站等) ，两点之间的有 向或无向线段表示两对象之间所具有的某种特定关系在( 如上例中的先后关系， 胜负关系，传递关系，连接关系等) 。事实上，任何一种包含了某种二元关系的 系统都可以用图形来模拟，由于我们感兴趣的是图形中两对象之间是否有某种特 定关系，所以图形中两点连接与否甚为重要，而连接线的曲直长短则无关紧要， 由此数学抽象产生了图的概念。 定义2 1 - 1 图，顶点，边 ( 1 ) 图是指有序三元组g = ，e ，y ) ，其中y 是非空顶点集，e 为边集，沙是 矿到e 元素有序对或无序对簇v v 的函数。 ( 2 ) y 中元素称为顶点。 ( 3 ) e 中元素称为边。 定义2 1 2 有向图和无向图 ( 1 ) v v 中元素若全是有序对，那么g 称为有向图。 ( 2 ) 若全是无序对，那么g 称为无向图。 注：( 1 ) 若无向图中边e e 的两个端点为x 和y ( 或有向图中边e 以x 为起 点，y 为终点) ，我们也可以将e 记作砂。 5 江 苏大 学 硕 士 学位论 文 ( 2 ) 一般的图也可以简写为g = ，e ) 。 定义2 1 3 图形表示 我们采用“图 这个词，是因为我们所定义的图可以用图形来表示，而且这 种图形表示比较直观而有助于我们理解图的许多性质。每个顶点用点来表示。有 向图的每条边用一条从起点对应的点连到终点对应的点的有向线段来表示，这样 的图形称为图的图形表示。 注：( 1 ) 因为表示顶点的点和表示边的曲线段的相对位置是无关紧要的，所 以图形表示并不是唯一的。 ( 2 ) 图是一个抽象的数学概念。尽管我们能用图形来表示，使图的结构形 象化，但是图的定义与这些图形毫不相干。然而，我们常常给出图的图形表示， 把它的点称为“顶点 ，它的曲线段称为“边”。因此，当我们画出图的图形表示 时，每条线段的内部自身不要相交，也不要穿过表示顶点的点。 图论中的大多数定义和概念是根据图的图形表示提出来的。 定义2 1 4 关联的和相邻的 ( 1 ) 边与它的两端点称为关联的。 ( 2 ) 与同一条边关联的两端点或者与同一个顶点关联的两条边称为相邻的。 定义2 1 4 环，平行边( 重边) ，对称边 ( 1 ) 两端点相同的边称为环。 ( 2 ) 如果两个顶点之间有多条边，则称这些边为平行边或重边。 ( 3 ) 两端点相同但方向互为相反的两条有向边称为对称边。 定义2 1 5 无环并且没有平行边的图称为简单图。 我们下面讨论的图均指简单图。 定义2 1 6 图的同构 如果两个图的两顶点集之间存在一个保持相邻关系的一一映射，则称这两个 图是同构的。即对图g = ，e ) 和图g = ，e7 ) ，若存在一个一一映射：v v 使得边x y e 当且仅当边( 力矽( y ) e ，则图g 和g7 是同构的。 定义2 1 7 顶点的度数 设g = ，e ) 为无向图，v 为g 上的一个顶点。与顶点，相邻的顶点数称 6 江苏大 学 硕 士 学位论 文 为y 的度数，记为砧( d 。 定义2 1 8 路和圈 ( 1 ) 对图上的顶点和唯，若存在另外七一1 个互不相同的顶点m ，屹，k 一，使 得m 和m + 。相邻，f = 0 ，1 ，k 一1 ，那么就称顶点，咋以及边h ，咋一1 屹组成 了一个长度为k 的路。 ( 2 ) 两个端点相同的路称为闭路或圈。 定义2 1 9 连通的和连通图 ( 1 ) 设x ，y y ，若g 中存在连接x 和y 的路，则称x 和y 是连通的。 ( 2 ) 若图g 中任意两个顶点都是连通的，则称g 为连通图。 随机树是我们本文研究的重点，下面首先介绍一下树的基本概念，通过此可 使我们 2 2 树的基本概念树的性质 当人们用图来模拟某一个系统时，常常遇到这种系统，代表该系统的模拟图 不含圈。例如，城市供水、供电系统就是这样的系统。若把该供水系统中所有的 阀门或供电系统中所有的开关作为模拟图的顶点，而把供水管道或供电线路作为 模拟图的边，则这样构作出来的模拟图不含圈。 定义2 2 1 森林和树 ( 1 ) 不含圈的图称为森林。 ( 2 ) 不含圈的连通图称为树。 定义2 2 2 树的另一定义 树是刀0 个顶点( 顶点或元素) 的有限集。在一棵非空树中： ( 1 ) 有且仅有一个特定的称为根的顶点； ( 2 ) 当疗 1 时，其余顶点可分为m ( m o ) 互不相交的有限集互，疋，已，其 中每一个集合本身又是一棵树，并且称为根的子树。每棵子树同样有自己的根顶 点。 树是树型结构的简称。它是一种重要的非线性数据结构。显然，树的另一 7 江 苏大 学 硕 士 学 位论文 定义是递归的，树是一种递归的数据结构。树的递归定义，将为以后实现树的各 种运算提供方便。 引理2 2 3 树上任意两顶点“，之间有且仅有一条路相连接。 定义2 2 4 距离和大小 ( 1 ) 连接甜，v 的路所包含的边数称为“，v 两顶点之间的距离。 ( 2 ) 树丁上所有顶点的数目就称为z 的大小。 注：不难知道，大小为刀的树恰有 一1 条边。 定义2 2 。5 树的度 树中所有顶点的度的最大值被定义为该树的度。 定义2 2 5 根树 设图r 为树，若指定某点，为根点，则称j f l 为以，为根点的根树。 定义2 2 6 顶点的深度或高度 顶点，和根点，之间的距离称为v 的深度或高度。 定义2 2 7 子点( 孩子) ，父点( 父亲) ， 若根树z 上的两点x 和y 相邻，且x 离根点较近，那么我们称y 是x 的子点 或者x 是y 的父点。 定义2 2 8 没有子点的顶点称为叶。 定义2 2 9 兄弟，子孙，祖先 ( 1 ) 具有同一父亲的孩子互称兄弟。 ( 2 ) 每个顶点的所有子树中的顶点被称作该顶点的子孙。 ( 3 ) 每个顶点的祖先则被定义为从树根顶点到达该顶点的路径上经过的所 有顶点。 如在图1 的树t 中，b 顶点的孩子为d ，e ，f 顶点，双亲为a 顶点，d ，e ，f 互 为兄弟，b 顶点的子孙为d ，e ，h ，i ，f 顶点，i 顶点的祖先为a ，b ，e 顶点，对于树 t 中的其它顶点亦可进行同样的分析。 8 江 苏 大 学 硕 士 学 位论 文 图1 由子点和父点的定义可知：在一棵树中，根顶点没有父点，叶子顶点没有子 点，其余顶点既有父点也有子点。如在图1 的树t 中，根顶点a 没有父点，叶子 顶点d ，h ，i ，f ，g 没有孩子。 定义2 2 1 0 顶点的层数和树的深度 树既是一种递归结构，也是一种层次结构，树中的每个顶点都处在一定的层 数上。顶点的层数从树根开始定义，根顶点为第一层，它的子点为第二层，以此 类推。树中顶点的最大层数称为树的深度或高度。 定义2 2 1 l 树z 中所有深度为k 的顶点组成的集合称为第k 代顶点。特别 地，根点是第o 代顶点。 一般地，根树可被看作无向图，也可被看作有向图。看作有向图时，每条边 的方向规定为远离根点的方向，因此，根树也可被称为外向树。更多的关于图论 的基本知识，可参阅b o l l 0 6 s ( 1 9 9 8 ) 或徐俊i j f j ( 1 9 9 8 ) 。 定义2 2 1 2 有序树和无序树 若树中各顶点的子树是按照一定的次序从左向右安排的，则称之为有序树， 否则称之为无序树。 注：因为任何无序树都可以当作任一次序的有序树来处理，所以以后若不特 别指明，均认为树是有序的。 2 3 树的性质 性质2 3 1 树中的顶点数等于所有顶点的度数加1 。 证明：根据树的定义，在一棵树中，除树根顶点外，每个顶点有且仅有一个 前驱顶点，也就是说，每个顶点与指向它的一个分支一一对应，所以除树根顶点 之外的顶点数等于所有顶点的分支数( 即度数) ，从而可得树中的顶点数等于所 9 江苏大学硕 士 学 位论文 有顶点的度数加i 。 性质2 3 2 度为k 的树中第f 层上至多有k 卜1 个顶点i 1 。 证明：对于第一层显然是成立的，因为树中的第一层上只有一个顶点，即整 个树的根顶点，而由i = 1 代入k h ，也同样得到只有一个顶点，即 k ：k h = k o = 1 ： 假设对于第f 一1 层( i 1 ) 命题成立，即度为k 的树中第f i 层上至多有 k 卜1 - 1 = k 卜2 个顶点，则根据树的度的定义，度为k 的树中每个顶点至多有k 个孩 子，所以第f 层上的顶点数至多为第f 一1 层上顶点数的k 倍，即至多为k 卜2 k = k h 个，命题成立。 性质2 3 3 深度为办的七叉树至多有百k h - 1 个顶点。 证明：显然当深度为h 的k 叉树( 即度为k 的树) 上每一层都达到最多顶点 数时，所有顶点的总和才能最大，即整个k 叉树具有最多顶点数。 善h 圹1 = h 州= 百k h - 1 当一棵七叉树上的顶点数等于百k h - 1 时，则称该树为满k 叉树。例如，对于 一棵深度为4 的满二叉树，其顶点数为2 4 1 ，即1 5 ；对于一棵深度为4 的满三 叉树，其顶点数为丁3 4 - 1 ，即4 。 性质2 3 4 具有玎个顶点的k 叉树的最小深度为l o g ( 甩( 七- 0 + 1 ) 。 证明：设具有刀个顶点的k 叉树的深度为h ，若在该树中前h l 层都是满的， 即每一层的顶点数都等于七卜1 个( f 1 j 1 ) ，第h 层( 即最后一层) 的顶点数可能 满，也可能不满，则该数具有最小的深度。根据性质2 3 3 ，其深度h 的计算公 式为： k 6 一一1 k 6 1 n 1 0 江 苏 大 学 硕 士 学位论 文 可得 k 6 1 n ( k - 1 ) + l k 6 以k 为底取对数 h 一1 e ) 事。 引理2 9 2 ( b r o e l c a n t e l l i 不等式) ( 1 ) 对事件列他，n 1 ， p ) 0 有 ( 3 1 3 ) ( 3 1 4 ) 一3 _ 2 一d 一珍 2 一+ 一+ 一一珂 1 一小 晶南 喊 丽 而 一m = k 时，我们有递归型的分布等式 n 瓯，= 乒+ s 乏乒 ( 4 1 ) n 其中，t - - s ；并且气 和，。是条件独立的。在这里，条件独且祧, 疋i e i 指尽 江 苏大 学 硕 士 学位论 文 管墨乒和，。是非条件独立的( 因为兄= 刀一1 一厶) ，但是给定厶( 或者r ) 之 后它们是独立的，也就是说，对所有的整数f ，j o ，随机变量s ，。和q 乒是相互独 立的。 ( 4 1 ) 式将是我们本章讨论的基础。 根据以上的分析下面我们来证明在大小为刀的随机二叉搜索树l 上，大小为 七的子树的数目s 础的强大数定律。 引理4 2 1 文1 2 当刀 | i 时， e s 乒2 揣； 汪2 ， 当刀 2 k 时， 讫吸 = 高器 ：= o + 1 ) 蠢 ( 4 3 ) 其中e x 和v a r x 分别表示随机变量z 的数学期望和方差 4 3 主要结果 定理4 3 1 大小为r 的随机二叉搜索树乙上，对任蒽给定的正整数七，最i 表 示大小为七的子树的数目，则 l i m s n k ：生一a e ( 4 4 ) 2 + 。n + 1 【七+ 1 ) ( 七+ z ) 证明：利用性质l 及厶和r 的对称性，注意到对歹 七时， 饿上一番志】4 = e ( 屯乒一揣) + ( 跤 一揣) r 江苏大 学 硕 士 学 位论文 弓c 一揣) 】4 蚂w 一高) 】4 = i n - i 研一广 ，j = 七暑】4( 七+ 1 ) ( 七十2 ) 。 + i 6n 缶- k - ie 【t ，t 一石+ 2 ( 1 j ) ( + 七1 + ) 2 ) 1 2e t s ；一。一，乒一揣】2 一等，芝= n - k 揣2 阶高，3刀，二一( 七+ 1 ) ( 七+ ) ( 七+ 1 ) ( 七+ 2 ) 1 】4 + 等_ 4 善n i l ( 川砌卅一鬈( 川砌1 _ 埘 一高o ( k ，3( 后+ 2 ) 。 一jffi塞n 1k 旷h 驴赭嵩- 1 - 】3 )一一 l t1 八二， + 孚t ，妻c 揣】2 ( 川卜，黑。c 高器】2 ( 川， 5 ， 注意到( 4 5 ) 中的第2 项 了6 0 , k 4t 善n - l ( 圳( 叫) 一鬈( 圳( 硝棚) ：3 ( n - 欲一1 ) 蠢+ 6 ( n - k ) ( k + 1 ) u 。4 厅 = d 0 + 1 ) 其次由盟l 得( 4 5 ) 中的第3 项 ( 4 6 ) 江 苏大 学 硕 士 学 位论 文 等t 黑。蒿器峨t 一揣r 一，塞高恕峨t 一高高n = 一荔刁f ；而1 6 ，n 邑- 2e i s , j 一揣】3 一i 刁衢i s 一- 乒一i f ；而2 n 】3 + 丽1 6砜嘶一揣】3 = 丽1 丽6 ，驴n - 2 孚+ 揣觋一揣) 2 】 + 丽1 6 昧孚+ 高) ( 一丽2 n ) 2 】( 七+ 1 ) ( 七+ 2 ) “ 疗 ( 后+ 1 ) ( 后+ 2 ) 、”1 一( 后+ 1 ) ( 后+ 2 ) 7 1 +丽16昧半一翥髓-l-k,k一丽2(n-k)n(k ) 2 】 ( 七+ 1 ) ( 后+ 2 ) “ 拧 + 1 ) ( 七+ 2 ) 、”( 后+ 1 ) ( | j + 2 ) 。 而1丽6，芝=n-k=n-k揣n(k( 一番- i - 器- i - ) 2( 尼+ 1 ) ( 后+ 2 ) ，二一 + 1 ) ( 后+ 2 ) 、 ( 尼1 ) ( 后2 ) 7 + 而丽3 2e ( 乒一面而2 n 丽) 2 + 了e ( ，。一) 2 【( | j + 1 ) ( 七+ 2 ) 】2 、”1 ， ( 七+ 1 ) ( 七+ 2 ) 7 e 学( 乩矿丽2 ( n - k ) i f ) 2 】 刀i 庀+ ) l+ z v n - 2 娅+ 兰垫重+ 1 6 ( - k ) o ；k 缌 n 【 + 1 ) ( 七+ 2 ) 】2 + 1 ) + 2 ) 最后( 4 5 ) 中的第4 项 孚t ，薹c 揣】2 ( 川卜，詈。c 揣】2 ( 川， = 丽丽4 8 0 - 4 可，量n - 2 ( 沏叫母丽4 8 0 4 一躺 4 8 ( n - 1 ) ( 2 k - 1 ) ( k - ：1 ) o 一- ： 哪 + 1 ) + 2 ) 】2 = o ( n + 1 ) ( 4 7 ) ( 4 8 ) 堂一曲 一 一 o - o 一嗽 伙 江 苏 大 学 硕士 学位论 文 由( 4 5 ) ，( 4 6 ) ，( 4 7 ) 和( 4 8 ) 我们可以得到 饿乒一揣】4 了n + l 巩 一志】4 + + 1 ) ( 4 9 ) 重复使用( 4 9 ) 可得 竺二盎盏l 一 刀+ 1 由( 4 1 0 ) ，对充分大的n 0 有 p c l 监n + l 一两高陋啦。 由占的任意性和( 4 1 2 ) 式知，( 4 4 ) 式成立。证毕。 ( 4 1 2 ) 江苏大 学 硕士 学位论 文 结束语 当图( g r a p h ) 这个词第一次出现在1 8 7 8 年的英国人自然杂志里距今已 有二百多年的历史了。1 9 3 6 年匈牙利数学家d k o n i g 写出了第一本图论专著有 限图与无线图，由此，图论作为数学的一个新分支己基本形成。图论以它自己 丰富的词汇语言，简洁地表示出各个领域“对象关系结构复杂而又难懂的概念， 由此产生的数学模型几乎是适合于所有科学( 自然科学和社会科学) 领域。 近年来，关于随机图论的研究越来越引起人们的关注，尤其是关于随机树及 其极限性质的研究，由于受到来自众多自然科学领域和实际应用领域需求的推 动，更是成为随机图论研究中的研究热点。 本文研究了随机二叉搜索树的顶点数目x 。和大小为k 的子树数目s 。的强 极限性质，由于研究时间，研究经验，实践条件的限制，研究方法还有待于进一 步扩张，在后续研究中将着重开展以下几个方面的研究： 1 进一步研究顶点数目j 。的渐进正态性 2 进一步探讨随机二叉树的其它参数的强极限性质 3 试图将本文采用的方法推广到完全区间树和随机递归树上 江苏大 学 硕士 学位论 文 致谢 本文是在导师杨卫国教授的精心指导下完成的，在此表示衷心的感谢! 三年 来，在杨老师的悉心指导和无私教诲下，不仅顺利完成了课程学习，而且也改变 了我的人生观。在杨老师身上我看到了严谨求实的治学风范、严密活跃的科学思 维、勤勤恳恳的工作作风，这在学习、生活以及以后的工作中都将深深影响了我， 使我懂得务实上进。 感谢江苏大学理学院所有专家和老师的教诲，本人受益匪浅。同时感谢理学 院各位领导的关心。 还要感谢0 6 研各位学友，他们在我学习期间给予了极大的帮助。 最后，对我的父母表示深深的感谢! 她们给了我精神和生活上的巨大支持， 没有她们，这篇论文是不可能完成的。 江 苏 大 学硕 士 学 位论文 参考文献 【1 】k i r s c h e n h o f e rp o nt h eh e i g h to fl e a v e si nb i n a r yt r e e s 【j 】c o m b i ni n f o r ms y ss c i 19 8 3 ，8 ： 4 4 _ 6 0 【2 】p a n h o l z e ra ，p r o d i n g e rh d e s c e n d a n t sa n da s c e n d a n t si nb i n a r yt r e e s 忉d i s c r e t em a t h t h e o rc o m p u ts c i 19 9 7 1 ：2 4 7 - 2 6 6 【3 】d e v r o y el ，n e i n i n g e rr d i s t a n c e sa n df i n g e rs e a r c hi nr a n d o mb i n a r ys e a r c ht r e e s 阴s i a m jc o m p u t , 2 0 0 4 ，3 3 ：6 4 7 - 6 5 8 4 】m a h m o u dh ，n e i n i n g e rr d i s t r i b u t i o no fd i s t a n c e si nr a n d o mb i n a r ys e a r c ht r e e s j 】a n n a p p lp m b a b 2 0 0 3 ，l3 ( 1 ) ：2 5 3 2 7 6 【5 】s v a n t ej l e f ta n dr i g h tp a t h l e n g h t si nr a n d o mb i n a r yt r e e s 【j 】a l g o r i t h m i c a , 2 0 0 6 ，4 6 ： 4 1 9 - 4 2 9 【6 】d e v r o y el a p p l i c a t i o n so fs t e i n sm e t h o di nt h ea n a l y s i so fr a n d o mb i n a r ys e a r c ht r e e s m c h e nl ，b a r b o u ra s t e i n sm e t h o