数据结构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)(10210210nipininpinipinnpnnpnininii2)(4log1)(21)(2102nnipinnpniO(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而40314*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位，则