Some Strong Limit Properties In Binary Search Trees

Stochastic graph theory in the recent ten years have become one of discrete mathematics mainstreams,it initiated in the 1940s,was also the graph theory development third stage,by Erdos et al.established,was a graph theory branch.In stochastic graph,appearance into probability event. Between the stochastic graph and the classical graph the biggest difference lay in has introduced the stochastic method,caused the space of the graph becomes bigger,its mathematics nature has also had the huge change.In this paper,the study of random binary search tree is a random graph theories of a tree.This article detailed discuss the peak number x,and the number of subtrees S_n,k of random binary search tree.According to the recursive calculation of the equation and the 4-order moment of X_n and S_n,k according to Chebychev inequality and the Borel-Cantelli lemma to be strong limit nature of X_n and S_n,k.In this paper,in the first chapter introduces the random graph theory and graph theory of the birth and development.The second chapter is devoted to the basic knowledge of map and random binary search tree.The third Chapter is about the strong limit law of the peak number X_n.The fourth Chapter is about the strong limit law of the number of subtrees S_n,k.