《数据结构A》第07章.ppt

1、南京邮电大学计算机学院 陈慧南 2006年9月,数据结构,Data Structures in C+,南京邮电大学计算机学院 陈慧南 2006年9月,第7章 动态集和搜索树,南京邮电大学计算机学院 陈慧南 2006年9月,7.1 二叉搜索树 7.2 二叉平衡树 7.3 B-树,南京邮电大学计算机学院 陈慧南 2006年9月,7.1 二叉搜索树,南京邮电大学计算机学院 陈慧南 2006年9月,7.1.1 二叉搜索树的定义,定义7.1 设结点由关键字值表征，假定所有结点的关键字值各不相同，二叉搜索树或者是一棵空二叉树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的关键字值均

2、小于根结点的关键字值； （2）若右子树不空，则右子树上所有结点的关键字值均大于根结点的关键字值； （3）左、右子树也分别是二叉搜索树。,南京邮电大学计算机学院 陈慧南 2006年9月,性质7.1 若以中序遍历一棵二叉搜索树，将得到一个以关键字值递增排列的有序序列。,南京邮电大学计算机学院 陈慧南 2006年9月,二叉搜索树类 template class BSTree:public DynamicSet public: BSTree()root=NULL; ResultCode Search(T,南京邮电大学计算机学院 陈慧南 2006年9月,7.1.2 二叉搜索树的搜索,二叉搜索树搜索递归算

3、法 template ResultCode BSTree:Search(T ,南京邮电大学计算机学院 陈慧南 2006年9月,template ResultCode BSTree:Search(BTNode *p, T ,南京邮电大学计算机学院 陈慧南 2006年9月,二叉搜索树搜索迭代算法 template ResultCode BSTree:Search(T ,南京邮电大学计算机学院 陈慧南 2006年9月,7.1.3 二叉搜索树的插入,template ResultCode BSTree:Insert(T ,南京邮电大学计算机学院 陈慧南 2006年9月,p=new BTNode(x);

4、 if(!root) root=p; else if(xelement) q-lChild=p; else q-rChild=p; return Success; ,南京邮电大学计算机学院 陈慧南 2006年9月,南京邮电大学计算机学院 陈慧南 2006年9月,7.1.4 二叉搜索树的删除,若结点*p有两棵非空子树 需搜索*p的中序遍历次序下的直接后继（或直接前驱）结点，设为*s，将*s的值复制到*p中，称为替代，因为*s最多只有一棵非空子树，这样一来，问题转化为“被删除的结点最多只有一棵非空子树”的情形。,南京邮电大学计算机学院 陈慧南 2006年9月,若结点*p 只有一棵非空子树或*p是叶

5、子 以*p的惟一孩子（设为*c）或空子树（cNULL）取代*p，链接至*p的双亲结点*q。 若被删除的结点*p是根结点，则删除后，结点*c成为新的根；若*p是其双亲*q的左孩子，则*c也应成为*q的左孩子，否则*c成为*q的右孩子。最后释放结点*p所占用的空间。,南京邮电大学计算机学院 陈慧南 2006年9月,删除28,南京邮电大学计算机学院 陈慧南 2006年9月,南京邮电大学计算机学院 陈慧南 2006年9月,template ResultCode BSTree:Remove(T,南京邮电大学计算机学院 陈慧南 2006年9月,if (p-lChild ,南京邮电大学计算机学院 陈慧南 2

6、006年9月,if (p-lChild) c=p-lChild; /删除结点 else c=p-rChild; if(p=root) root=c; else if (p=q-lChild) q-lChild=c; else q-rChild=c; delete p; return Success; ,南京邮电大学计算机学院 陈慧南 2006年9月,7.1.5 平均情况时间分析,二叉搜索树搜索的平均时间为O(log2n)。 最坏情况搜索时间为O(n)。,南京邮电大学计算机学院 陈慧南 2006年9月,假设在一个有n(n1)个关键字的序列，有i个关键字小于第一个关键字，n-i-1个关键字大于第一

7、个关键字。由此序列构成的二叉搜索树，其左子树上有i个结点，而右子树上有n-i-1个结点。 设pi(n)是在一棵有n结点，其左子树上有i个结点，而右子树上有n-i-1个结点的二叉搜索树上以等概率进行搜索，成功搜索一个关键字的平均比较次数。,南京邮电大学计算机学院 陈慧南 2006年9月,设p(n)是在一棵有n个结点的二叉搜索树上成功搜索一个关键字的平均比较次数 。,南京邮电大学计算机学院 陈慧南 2006年9月,可用归纳法证明：,随机情况下，二叉搜索树操作的平均时间为O(log2n)。,南京邮电大学计算机学院 陈慧南 2006年9月,7.2 二叉平衡树,南京邮电大学计算机学院 陈慧南 2006年

8、9月,7.2.1 二叉平衡树的定义,定义7.2 二叉平衡树又称AVL树 它或者是一棵空二叉树，或者是具有下列性质的二叉树： （1）其根的左、右子树高度之差的绝对值不超过1； （2）其根的左、右子树都是二叉平衡树。 结点的平衡因子定义为该结点的左子树的高度减去右子树的高度。 AVL二叉搜索树既是二叉搜索树又是AVL树。在下面的讨论中，二叉平衡树（AVL树）是指AVL二叉搜索树。,南京邮电大学计算机学院 陈慧南 2006年9月,南京邮电大学计算机学院 陈慧南 2006年9月,9.2.2 二叉平衡树类,template struct AVLNode AVLNode(const T,南京邮电大学计算机

9、学院 陈慧南 2006年9月,template class AVLTree:public DynamicSet public: AVLTree()root=NULL; ResultCode Search(T ,南京邮电大学计算机学院 陈慧南 2006年9月,private: AVLNode* root; ResultCode Insert(AVLNode* ,南京邮电大学计算机学院 陈慧南 2006年9月,7.2.3 二叉平衡树的平衡旋转,分别插入：25，35，14，44,南京邮电大学计算机学院 陈慧南 2006年9月,插入25：从根到25的路径上，所有结点的平衡因子均为0。插入新元素25后，

10、这棵树仍然是二叉平衡树，但整棵树高度加1。 插入35：从根到35的路径上，36的平衡因子不为0，新元素35被插在36的较矮的子树上。插入后，该树仍然是二叉平衡树。,南京邮电大学计算机学院 陈慧南 2006年9月,插入14：从根到14的路径上，12的平衡因子不为0，新元素14被插在12的较高的子树上，即14被插在12的右子树的左子树上，插入后，该树不再是二叉平衡树。 插入44：从根到44的路径上，43和56的平衡因子都不为0，其中56是离44最近的，平衡因子值不为零的结点。新元素44被插在56的较高的那棵子树上，即44被插在56的左子树的左子树上。插入后，该树不再是二叉平衡树。,南京邮电大学计算

11、机学院 陈慧南 2006年9月,假定新结点*q插在结点*s的左子树上的情况 （1）新结点*q已按二叉搜索树方式插入树中； （2）结点*s是新结点*q的具有非零平衡因子值(插入前的值)的最近的祖先； （3）结点*q插在结点*s的左子树上； （4）从结点*s到新结点*q的路径上所有结点（不含*s）的平衡因子值均已作修正。,南京邮电大学计算机学院 陈慧南 2006年9月,情况一 若插入前，从根结点到新结点q的插入位置的路径上，所有结点的平衡因子值均为0，插入q后，只需将根结点的平衡因子改为1，并且AVL树的高度加1，插入操作完成。,南京邮电大学计算机学院 陈慧南 2006年9月,情况二 若新结点q插

12、在结点s较矮的子树上（s的平衡因子bF为-1，并假定q插在s的左子树上），则插入后只需令s的平衡因子bF为0，插入算法终止。,南京邮电大学计算机学院 陈慧南 2006年9月,情况三: 插在较高的子树上（s-bF=+1） LL-旋转（r-bF=+1）,南京邮电大学计算机学院 陈慧南 2006年9月,LR-旋转（r-bF=-1）,南京邮电大学计算机学院 陈慧南 2006年9月,switch(u-bF) case 1:s-bF=-1;r-bF=0;break; case 0:s-bF=r-bF=0;break; case -1:s-bF=0;r-bF=1; ,南京邮电大学计算机学院 陈慧南 2006

13、年9月,template void AVLTree:LRotation(AVLNode* ,南京邮电大学计算机学院 陈慧南 2006年9月,else / LR旋转 u=r-rChild;r-rChild=u-lChild; u-lChild=r;s-lChild=u-rChild; u-rChild=s; switch(u-bF) case 1:s-bF=-1;r-bF=0;break; case 0:s-bF=r-bF=0;break; case -1:s-bF=0;r-bF=1; s=u; /s指示新子树的根 s-bF=0; /结点s的平衡因子为0 unBalanced=false; /结

14、束重新平衡操作 ,南京邮电大学计算机学院 陈慧南 2006年9月,7.2.4 二叉平衡树的插入,南京邮电大学计算机学院 陈慧南 2006年9月,二叉平衡树的插入 template ResultCode AVLTree:Insert( AVLNode* else,南京邮电大学计算机学院 陈慧南 2006年9月,if (xelement) /（ 续） result=Insert(p-lChild,x,unBalanced); if (unBalanced) switch (p-bF) case -1:p-bF=0; unBalanced=false;break; case 0:p-bF=1;bre

15、ak; case 1:LRotation(p,unBalanced); else if (x=p-element) /有重复元素 unBalanced=false; x=p-element;result=Duplicate; ,南京邮电大学计算机学院 陈慧南 2006年9月,else /（续） result=Insert(p-rChild,x,unBalanced); if (unBalanced) switch (p-bF) case 1:p-bF=0; unBalanced=false;break; case 0:p-bF=-1;break; case -1:RRotation(p,unB

16、alanced); return result; ,南京邮电大学计算机学院 陈慧南 2006年9月,7.2.6 二叉平衡树的高度,定理 具有n个结点的AVL树的高度h满足： log2 (n+1) h 1.4404 log2(n+2)-0.328,南京邮电大学计算机学院 陈慧南 2006年9月,7.3 B-树,南京邮电大学计算机学院 陈慧南 2006年9月,7.3.1 m叉搜索树,定义7.3 m叉搜索树或者是一棵空树，或者是一棵满足下列特性的树： (1) 根结点最多有m棵子树，并具有如下结构： n,P0,（K1,P1）,（K2,P2）,（Kn,Pn） 其中，Pi是指向子树的指针，0inm，Ki是

17、元素的关键字值，1i nm； (2) KiKi+1 , 1in；,南京邮电大学计算机学院 陈慧南 2006年9月,(3)子树Pi上所有关键字值都大于Ki，小于Ki+1, 0in； (4)子树P0上所有关键字值都小于K1，子树Pn上的所有关键字值都大于Kn； (5) 子树Pi，0 in也是m叉搜索树。,南京邮电大学计算机学院 陈慧南 2006年9月,南京邮电大学计算机学院 陈慧南 2006年9月,南京邮电大学计算机学院 陈慧南 2006年9月,7.3.2 B-树的定义,定义7.4 一棵m阶B-树是一棵m叉搜索树，它或者是空树，或者是满足下列特性的树： （1）根结点至少有两个孩子； （2）除根结点

18、和失败结点外的所有结点至少有m/2个孩子； （3）所有失败结点均在同一层上。,南京邮电大学计算机学院 陈慧南 2006年9月,南京邮电大学计算机学院 陈慧南 2006年9月,7.3.3 B-树的高度,性质7.2 设B-树失败结点的总数是s，那么，一棵B-树的元素总数N是B-树的失败结点的总数减，即N=s-1。 设n是非失败结点数，t 是指针总数 t =N+ns+n-1 定理7.2 有N个元素的m阶B-树的高度是 因： N+12*（m/2）h-1,南京邮电大学计算机学院 陈慧南 2006年9月,7.3.4 B-树的搜索,磁盘访问的次数最多是 1logm/2 (N+1)/2),南京邮电大学计算机学

19、院 陈慧南 2006年9月,7.3.5 B-树的插入,B-树插入新元素的方法 （1） 在B树中搜索给定关键字值的元素，如果搜索成功，表示有重复元素，插入运算失败终止，否则将新元素和一个空指针插入搜索失败处的叶结点中。 （2） 若插入新元素（和一个指针）后，结点*q未溢出，即结点中包含的元素个数未超过m-1（指针数未超过m），则插入运算成功终止。,南京邮电大学计算机学院 陈慧南 2006年9月,（3）若插入新元素（和一个指针后），结点*q已溢出，则必须进行结点的分裂操作，将结点一分为三。分裂发生在位置m/2处。关键字值Km/2之前的元素保留在原来的结点中，在它之后的元素存放在新创建的结点（设地址

20、为q）中，而关键字值为Km/2的元素和地址q 将插入结点*q的双亲结点中。这意味着在该双亲结点中新增了一个元素和一个指针，因此，必须检查此双亲结点的溢出问题。这同样可按（2）和（3）的原则，继续检查和处理该双亲结点。 （4）如果按照（3）的原则，根结点*q产生分裂，根结点没有双亲，那么分裂产生的两个结点的指针q和q以及关键字为Km/2 的元素应组成一个新的根结点，B-树增高一。只要从根结点到新元素插入结点的路径上至少有一个结点未满，B-树不会长高。,南京邮电大学计算机学院 陈慧南 2006年9月,插入59,南京邮电大学计算机学院 陈慧南 2006年9月,插入 53,南京邮电大学计算机学院 陈慧南 2006年9月,7.3.6 B-树的删除,从B-树删除元素的方法 （1）首先搜索被删除的元素，如果不存在被删除的元素，则删除运算失败终止。如果搜索成功，且被删除的元素在叶子结点中，则从该叶子结点中删除该元素；如果被删除的元素不在叶子结点中，那么由它的右侧子树上的最小元素取代之（必定在叶结点中），然后从叶子结点中删除该替代元素。 （2）如果删除