您好,欢迎访问三七文档
当前位置:首页 > 财经/贸易 > 资产评估/会计 > 数据结构9(陈慧南)_搜索树_散列
数据结构第9讲DATASTRUCTUREDATASTRUCTURE第7章搜索树二叉搜索树1二叉平衡树2B-树3二叉搜索树1DATASTRUCTURE§7.1.1二叉搜索树的定义定义7.1设结点由关键字值表征,假定所有结点的关键字值各不相同,二叉搜索树或者是一棵空二叉树,或者是具有下列性质的二叉树:(1)若左子树不空,则左子树上所有结点的关键字值均小于根结点的关键字值;(2)若右子树不空,则右子树上所有结点的关键字值均大于根结点的关键字值;(3)左、右子树也分别是二叉搜索树。§7.1.1二叉搜索树的定义二分搜索树的二叉判定树DATASTRUCTURE小中大52307236548321416697DATASTRUCTURE§7.1.1二叉搜索树的定义性质7.1若以中序遍历一棵二叉搜索树,将得到一个以关键字值递增排列的有序序列。6354872369764535中序LVR算法DATASTRUCTURE§7.1.1二叉搜索树的定义二叉搜索树类templateclassTclassBSTree:publicDynamicSetT{public:BSTree(){root=NULL;}ResultCodeSearch(T&x)const;ResultCodeInsert(T&x);ResultCodeRemove(T&x);protected:BTNodeT*root;private:ResultCodeSearch(BTNodeT*p,T&x)const;:};enumResultCode{Underflow,Overflow,Success,Duplicate,NotPresent,...};DATASTRUCTURE§7.1.2二叉搜索树的搜索二叉搜索树搜索递归算法templateclassTResultCodeBSTreeT::Search(T&x)const{returnSearch(root,x);}templateclassTResultCodeBSTreeT::Search(BTNodeT*p,T&x)const{if(!p)returnNotPresent;elseif(xp-element)returnSearch(p-lChild,x);elseif(xp-element)returnSearch(p-rChild,x);else{x=p-element;returnSuccess;}}DATASTRUCTURE§7.1.2二叉搜索树的搜索二叉搜索树搜索迭代算法templateclassTResultCodeBSTreeT::Search(T&x)const{BTNodeT*p=root;while(p)if(xp-element)p=p-lChild;elseif(xp-element)p=p-rChild;else{x=p-element;returnSuccess;}returnNotPresent;}DATASTRUCTURE§7.1.3二叉搜索树的插入templateclassTResultCodeBSTreeT::Insert(T&x){BTNodeT*p=root,*q=NULL;while(p){q=p;if(xp-element)p=p-lChild;elseif(xp-element)p=p-rChild;else{x=p-element;returnDuplicate;}}p=newBTNodeT(x);if(!root)root=p;elseif(xq-element)q-lChild=p;elseq-rChild=p;returnSuccess;}搜索添加DATASTRUCTURE§7.1.3二叉搜索树的插入插入43:4343DATASTRUCTURE§7.1.4二叉搜索树的删除1.若结点p有两棵非空子树,需搜索p的中序遍历次序下的直接后继(或直接前驱)结点,设为s,将s的值复制到p中,称为替代,因为s最多只有一棵非空子树,这样一来,问题转化为“被删除的结点最多只有一棵非空子树”的情形。33DATASTRUCTURE§7.1.4二叉搜索树的删除2.若结点p只有一棵非空子树或p是叶子,以p的惟一孩子(设为c)或空子树(c=NULL)取代p,链接至p的双亲结点q。333534DATASTRUCTURE§7.1.4二叉搜索树的删除3.若被删除的结点p是根结点,则删除后,结点c成为新的根;若p是其双亲q的左孩子,则c也应成为q的左孩子,否则c成为q的右孩子。最后释放结点p所占用的空间。63548723697645356354872369764535pcqpc91DATASTRUCTURE§7.1.4二叉搜索树的删除DATASTRUCTURE§7.1.4二叉搜索树的删除templateclassTResultCodeBSTreeT::Remove(T&x){BTNodeT*c,*s,*r,*p=root,*q=NULL;while(p&&p-element!=x){//搜索q=p;if(xp-element)p=p-lChild;elsep=p-rChild;}if(!p)returnNotPresent;x=p-element;if(p-lChild&&p-rChild){//替代s=p-rChild;r=p;while(s-lChild){r=s;s=s-lChild;}p-element=s-element;p=s;q=r;}搜索替代寻找后继结点DATASTRUCTURE§7.1.4二叉搜索树的删除if(p-lChild)c=p-lChild;//删除结点elsec=p-rChild;if(p==root)root=c;elseif(p==q-lChild)q-lChild=c;elseq-rChild=c;deletep;//删除结点内容returnSuccess;}删除DATASTRUCTURE§7.1.5平均情况时间分析二叉搜索树搜索的平均时间为O(log2n)。最坏情况搜索时间为O(n)。DATASTRUCTURE§7.1.5平均情况时间分析假设在一个有n(n≥1)个关键字的序列,有i个关键字小于第一个关键字,n-i-1个关键字大于第一个关键字。由此序列构成的二叉搜索树,其左子树上有i个结点,而右子树上有n-i-1个结点。设pi(n)是在一棵有n结点,其左子树上有i个结点,而右子树上有n-i-1个结点的二叉搜索树上以等概率进行搜索,成功搜索一个关键字的平均比较次数。DATASTRUCTURE§7.1.5平均情况时间分析又设p(n)是在一棵有n个结点的二叉搜索树上成功搜索一个关键字的平均比较次数。10)(1)(niinpnnp)]1)1()(1()1)((1[1)(inpinipinnpiDATASTRUCTURE§7.1.5平均情况时间分析可用归纳法证明:2)()(21)]1()1()([11)(1)(10210210nipininpinipinnpnnpnininii2)(4log1)(21)(2102nnipinnpniO(log2n)DATASTRUCTURE第7章搜索树二叉搜索树1二叉平衡树2B-树3二叉搜索树1二叉平衡树2DATASTRUCTURE§7.2.1二叉平衡树的定义定义7.2二叉平衡树又称AVL树它或者是一棵空二叉树,或者是具有下列性质的二叉树:(1)其根的左、右子树高度之差的绝对值不超过1;(2)其根的左、右子树都是二叉平衡树。结点的平衡因子定义为该结点的左子树的高度减去右子树的高度。AVL二叉搜索树既是二叉搜索树又是AVL树。在下面的讨论中,二叉平衡树(AVL树)是指AVL二叉搜索树。DATASTRUCTURE§7.2.1二叉平衡树的定义DATASTRUCTURE第7章搜索树二叉搜索树1二叉平衡树2B-树3二叉搜索树1二叉平衡树2B-树3DATASTRUCTURE§7.3.1m叉搜索树定义7.3m叉搜索树或者是一棵空树,或者是一棵满足下列特性的树:(1)根结点最多有m棵子树,并具有如下结构:n,P0,(K1,P1),(K2,P2),…,(Kn,Pn)其中,Pi是指向子树的指针,0≤i≤nm,Ki是元素的关键字值,1≤i≤nm;(2)KiKi+1,1≤in;DATASTRUCTURE第8章跳表和散列表字典1跳表2散列表3字典1DATASTRUCTURE§8.1字典字典是记录的集合。有重复记录的字典允许字典中有多个相同关键字值的记录,在实现搜索、插入和删除操作时需要一个规则来消除歧义。线性表搜索树跳表散列表…f…DATASTRUCTURE第8章跳表和散列表字典1跳表2散列表3字典1跳表2DATASTRUCTURE§8.2.1什么是跳表二叉树可能产生退化——退化成线性表,造成算法上不均衡。AVL搜索树(平衡搜索树)——难度增加二分搜索——简便快捷,但必须可排序371922434870DATASTRUCTURE第8章跳表和散列表字典1跳表2散列表3字典1跳表2散列表3DATASTRUCTURE§8.3.1散列技术散列表是表示集合和字典的另一种有效方法。它提供了一种完全不同的存储和搜索方式:通过将关键字值映射到表中某个位置上来存储元素,而后根据关键字值直接访问。Loc(key)=h(key)其中,Loc(key)表示关键字值为key的元素的存储位置。(1)这个把关键字值映射到位置的函数h称为散列函数;(2)这样建立的表称为散列表。h(key)DATASTRUCTURE§8.3.1散列技术冲突和同义词建立全国省、市、自治区的人口统计简表。h(Hebei)=h(Henan)=h(Hubei)=h(Hunan)=8h(Shandong)=h(Shanxi)=h(Shanghai)=h(Sichuan)=19所谓冲突,是指对于关键字集合中的两个关键字值Ki和Kj,当Ki≠Kj时,有h(Ki)=h(Kj),h是散列函数。具有相同散列函数值的关键字值,对该散列函数而言称为同义词。DATASTRUCTURE§8.3.1散列技术冲突是不可避免的例1:关键字值集合有31个元素,如果我们选择一个有40个元素的记录数组的散列表,也就是说散列地址的范围从0到39。存在4031种可能的函数关系。对每个变元给出不同的地址C4031·31!=40!/9!1042而40314*1049,所以不同地址函数可能性1/107散列函数DATASTRUCTURE§8.3.2散列函数均匀的散列函数假定散列函数最多可取M个不同的值,即有0≤h(key)M。一个均匀的散列函数应当是:如果key是从关键字值集合中随机选取的一个值,则h(key)以同等概率取区间[0,M-1]中的每一个值。“好”的散列函数一个实用的散列函数h应当满足下列条件:(1)能快速计算;(2)具有均匀性。DATASTRUCTURE§8.3.2散列函数常见的散列函数(1)除留余数法除留余数法的散列函数的形式如下:h(key)=keymodM其中,key是关键字,M是散列表的大小。【注】mod是对模数求剩余。设M0,xmodM的值在[0,M-1]中。DATASTRUCTURE§8.3.2散列函数(2)平方取中法设关键字用内部码表示,内码采用八进制表示。字长W=2w,表长M=2k,w=18,k=9。W)mod(xWMh(x)2关键字值内码内码的平方散列函数值010000100000101100121000021012001440000440DATASTRUCTURE§8.3.2散列函数折叠法key=12320324111220若散列地址取3位,则
本文标题:数据结构9(陈慧南)_搜索树_散列
链接地址:https://www.777doc.com/doc-3171967 .html