南京邮电大学数据结构A第7章

数据结构A·第7章第7章搜索树引言集合可以采用树形结构表示，比如，用二叉搜索树、二叉平衡树、B-树等表示，通常称这些为搜索树。搜索树有较高的搜索效率，又能有效地插入和删除元素，因而更适合表示动态集。本课程讨论这三种常见的用于表示动态集的树形数据结构：二叉搜索树、二叉平衡树和B-树。第7章搜索树内容提要1、二叉搜索树的定义；2、二叉搜索树的搜索、插入、删除运算及其分析；3、二叉平衡树的定义；4、二叉平衡树的插入运算及其实现；5、m叉搜索树的定义；6、B-树的定义；7、B-树的搜索、插入和删除运算。7.1二叉搜索树二叉搜索树也称二叉排序树，是一种最容易实现的搜索树。课堂提要第7章搜索树7.1二叉搜索树7.1.1二叉搜索树的定义7.1.2二叉搜索树的搜索7.1.3二叉搜索树的插入7.1.4二叉搜索树的删除7.1二叉搜索树7.1.1二叉搜索树的定义定义7.1假定所有结点的关键字值各不相同，二叉搜索树或者是一棵空二叉树，或者是具有下列性质的二叉树：(1)若左子树不空，则左子树上所有结点的关键字值均小于根结点关键字值；(2)若右子树不空，则右子树上所有结点的关键字值均大于根结点关键字值；(3)左、右子树也分别是二叉搜索树。递归定义课堂提要第7章搜索树7.1二叉搜索树7.1.1二叉搜索树的定义7.1.2二叉搜索树的搜索7.1.3二叉搜索树的插入7.1.4二叉搜索树的删除7.1二叉搜索树7.1.1二叉搜索树的定义性质7.1若以中序遍历一棵二叉搜索树，将得到一个以关键字值递增排列的有序序列。6354874569762335图7-1二叉搜索树7.1二叉搜索树7.1.1二叉搜索树的定义程序7.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;…};7.1二叉搜索树7.1.2二叉搜索树的搜索1.二叉搜索树搜索的递归算法2.二叉搜索树搜索的迭代算法课堂提要第7章搜索树7.1二叉搜索树7.1.1二叉搜索树的定义7.1.2二叉搜索树的搜索7.1.3二叉搜索树的插入7.1.4二叉搜索树的删除7.3B树7.1二叉搜索树7.1.2二叉搜索树的搜索(1)若二叉树为空，则搜索失败。(2)否则，将x与根结点比较，若x小于该结点的值，则以同样的方法搜索左子树，而不必搜索右子树；若x大于该结点的值，则以同样的方法搜索右子树，而不必搜索左子树；若x等于该结点的值，则搜索成功终止。1.二叉搜索树搜索的递归算法查找与x的关键字值相同的元素的递归算法可描述如下：7.1二叉搜索树7.1.2二叉搜索树的搜索程序7.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;}}7.1二叉搜索树7.1.2二叉搜索树的搜索2.二叉搜索树的迭代算法二叉搜索树的迭代算法使用while循环，从根结点开始搜索，将待查元素x与当前元素比较。若x等于该结点的值，则搜索成功终止；若x小于该结点的值，则继续搜索左子树；否则继续搜索右子树。只有搜索到空子树时，才失败终止。7.1二叉搜索树7.1.2二叉搜索树的搜索程序7.3二叉搜索树搜索的迭代算法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;}63548745697623357.1二叉搜索树7.1.3二叉搜索树的插入二叉搜索树的插入步骤与单链表的插入步骤类似。(1)查找插入元素的位置；(2)生成新结点；(3)插入新结点(有可能修改root指针)课堂提要第7章搜索树7.1二叉搜索树7.1.1二叉搜索树的定义7.1.2二叉搜索树的搜索7.1.3二叉搜索树的插入7.1.4二叉搜索树的删除7.3B树7.1二叉搜索树7.1.3二叉搜索树的插入在二叉搜索树上插入一个新元素，首先应搜索新元素的插入位置，同时，需要在自根结点向下搜索过程中，记录当前结点的双亲结点，设为q。如果二叉树中有重复元素，应返回Duplicate。搜索到达空子树时，构造一个新结点p存放新元素x，并连接至结点q，成为q的孩子（p是q的左孩子还是右孩子取决于x与q关键字值的大小）；如果原二叉搜索树是空树，则新结点p成为新二叉搜索树的根。7.1二叉搜索树7.1.3二叉搜索树的插入在二叉搜索树中插入43的执行过程:282136332543q=∧pq43p=∧p7.1二叉搜索树7.1.3二叉搜索树的插入213633432528下图显示了从空树开始通过依次插入元素，构造一棵二叉搜索树的过程。(a)空树(b)插入28(c)插入21(d)插入25(e)插入36(f)插入33(g)插入437.1二叉搜索树7.1.3二叉搜索树的插入程序7.4二叉搜索树的插入运算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;}查找插入位置生成新结点插入新结点7.1二叉搜索树7.1.4二叉搜索树的删除在二叉搜索树上删除一个结点与插入运算类似，应先搜索被删除结点p，并记录p的双亲结点q。课堂提要第7章搜索树7.1二叉搜索树7.1.1二叉搜索树的定义7.1.2二叉搜索树的搜索7.1.3二叉搜索树的插入7.1.4二叉搜索树的删除7.3B树HibbardDeletion,19607.1二叉搜索树7.1.4二叉搜索树的删除如果不存在指定删除的元素，应返回NotPresent。否则，删除结点p的操作由下列几步组成：(1)若结点p有两棵非空子树，需搜索结点p的中序遍历次序下的直接后继结点，设为s。将s中的值复制到p中，删除s结点。如果s结点是p的直接后继，则s必定没有左孩子（右孩子）。此时，问题就简化为“被删除的结点最多只有一棵非空子树”的情形。(2)若结点p只有一棵非空子树或p是叶子，以结点p的唯一孩子（设为结点c）或空子树（c=NULL）取代p。(3)若被删除的结点p是根结点，则删除后，结点c成为新的根；否则，若p是其双亲q的左孩子，则结点c也应该成为q的左孩子，不然c成为q的右孩子。最后释放结点p所占的空间。7.1二叉搜索树7.1.4二叉搜索树的删除2833删除2128213633432523353423删除23282136334325353421删除2825364335342833二叉搜索树上删除元素7.1二叉搜索树7.1.4二叉搜索树的删除2928下图结合程序，演示删除一个有左右孩子结点的过程。282536433230例如删除2834prsq=∧x=29q7.1二叉搜索树7.1.4二叉搜索树的删除程序7.5二叉搜索树的删除运算templateclassTResultCodeBSTreeT::Remove(T&x){BTNodeT*c,*s,*r,*p=root,*q=NULL;while(p&&p-element!=x){q=p;//q为p的双亲if(xp-element)p=p-lChild;elsep=p-rChild;}if(!p)returnNotPresent;x=p-element;搜索要删除的结点28213633432523353421qp7.1二叉搜索树7.1.4二叉搜索树的删除if(p-lChild&&p-rChild){s=p-rChild;r=p;while(s-lChild){//结点s是p的中序后继，r=s;s=s-lChild;//r是s的双亲}p-element=s-element;//将s的值复制到p中，p=s;q=r;//准备删除p，指针q指示p的双亲}if(p-lChild)c=p-lChild;elsec=p-rChild;//准备以结点c取代结点pif(p==root)root=c;//以结点c取代结点pelseif(p==q-lChild)q-lChild=c;elseq-rChild=c;deletep;returnSuccess;}转化为被删除的结点p最多只有一个孩子2821363343252335347.1二叉搜索树二叉搜索树搜索算法分析最好情况和一般情况：O(log2n)最坏情况：单支树，O(n)输入：28,21,36,25,33,35,43.输入：28,21,25,33,43,36,35.输入：21,25,28,33,35,36,43.282125363343352821253335433621252843...7.1二叉搜索树平均情况下，二叉搜索树的搜索、插入和删除操作的渐近时间复杂度均为O(log2n)。由关键字序列3，1，2，5，4构造而得的二叉排序树由关键字序列1，2，3，4，5构造而得的二叉排序树，ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2(a)(b)21345354127.2二叉平衡树二叉平衡树（Self-BalancingBinarySearchTree），又称AVL树，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于1。hL-hR=17.2二叉平衡树G.M.Adelson-Velskii&E.M.Landis(俄罗斯，1962)7.2二叉平衡树定义7.2二叉平衡树又称AVL树，它或者是一棵空二叉树，或者是具有下列性质的二叉树：(1)其根的左、右子树高度之差的绝对值不超过1；(2)其根的左、右子树都是二叉平衡树。平衡因子（BF）:结点左子树的高度减去右子树的高度。7.2二叉平衡树625888479362588859936258884799355137739362588847993551377393(1)(2)(3)(4)010-10BF=27.2二叉平衡树最小不平衡子树：距离插入结点最近的且平衡因子的绝对值大于1的结点为根的子树。当插入新结点37时62885899356073934751370-11002最小不平衡子树7.2二叉平衡树AVL树实现原理实例：{3，2，1，4，5，6，7，10，9，8}3425167109847251610983二叉排序树AVL树7.2二叉平衡树AVL树实现原理实例：{3，2，1，4，5，6，7，10，9，8}3插入3插入23032102