《七章查找.ppt》由会员分享,可在线阅读,更多相关《七章查找.ppt(50页珍藏版)》请在三一文库上搜索。
1、第七章 查找,静态搜索表 二叉搜索树 *最佳二叉搜索树 * AVL树,搜索(Search)的概念,7.3 静态搜索表,所谓搜索,就是在数据集合中寻找满足某 种条件的数据对象。 搜索的结果通常有两种可能: 搜索成功,即找到满足条件的数据对象 这时,作为结果, 可报告该对象在结构中 的位置, 还可给出该对象中的具体信息。 搜索不成功,或搜索失败。作为结果, 应报告一些信息, 如失败标志等。,通常称用于搜索的数据集合为搜索结构,它是由同一数据类型的对象(或记录)组成。 实施搜索时有两种不同的环境。 静态环境,搜索结构不提供插入和删除等操作。 静态搜索表 动态环境,搜索结构提供插入和删除等操作。 动态
2、搜索表,顺序搜索 (Sequential Search),所谓顺序搜索, 又称线性搜索,搜索从表的一端开始, 顺序用各对象的关键码与给定值 x 进行比较。,template int searchList : Search ( const Type ,“监视哨”顺序搜索算法,顺序搜索的平均搜索长度(ASL),设搜索第 i 个元素的概率为 pi, 搜索到第 i 个元素所需比较次数为 ci, 则搜索成功的平均搜索长度:,在顺序搜索并设置“监视哨”情形: ci = i +1, i = 0, 1, , n-1,因此,搜索成功时,在等概率情形, pi = 1/n, i = 0, 1, 2, , n-1,搜
3、索不成功时,关键码比较次数为 n+1.,基于有序顺序表的折半搜索,设n个对象存放在一个有序顺序表中,并按其关键码从小到大排好了序。 折半搜索时, 先求位于搜索区间正中的对象的下标mid,用其关键码与给定值x比较: Elementmid.key = x,搜索成功; Elementmid.key x,把搜索区间缩小 到表的前半部分,继续折半搜索; Elementmid.key x,把搜索区间缩小 到表的后半部分,继续折半搜索。 如果搜索区间已缩小到一个对象,仍未找到想要搜索的对象,则搜索失败。,搜索成功的例子,-1 0 1 3 4 6 8 10 12,6,0 1 2 3 4 5 6 7 8,搜索,
4、low,mid,high,6,搜索失败的例子,-1 0 1 3 4 6 8 10 12,5,0 1 2 3 4 5 6 7 8,搜索,low,mid,high,5,template int orderedList : BinarySearch ( const Type ,有序顺序表的折半搜索的判定树 ( 10, 20, 30, 40, 50, 60 ),10,50,=,=,=,=,=,=,30,20,40,60,ASLunsucc = (2*1+3*6)/7 = 20/7,ASLsucc = (1+2*2+ 3*3)/6 = 14/6,折半搜索性能分析,搜索成功时与给定值进行关键码比较次数 h
5、 若设 n = 2h-1,则描述折半搜索的判定树是高度为 h-1 的满二叉树。 2h = n+1, h = log2(n+1),折半搜索成功时的平均搜索长度为O(log2n),定义 二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 每个结点都有一个作为搜索依据的关键码(key),所有结点的关键码互不相同。 左子树(如果存在)上所有结点的关键码都小于根结点的关键码。 右子树(如果存在)上所有结点的关键码都大于根结点的关键码。 左子树和右子树也是二叉搜索树。,7.4 二叉搜索树 (Binary Search Tree),35,15,45,50,40,25,10,20,30,二叉搜索树例,如果
6、对一棵二叉搜索树进行中序遍历,可以按从小到大的顺序,将各结点关键码排列起来,所以也称二叉搜索树为二叉排序树。,35,15,45,50,40,25,10,20,30,搜索45 搜索成功,搜索28 搜索失败,从根结点开始,沿某一个分支逐层向下进行比较判等,二叉搜索树上的搜索,template BstNode * BST : Find ( Type x, BstNode * ptr ) const /二叉搜索树的递归的搜索算法 if ( ptr = NULL ) return NULL; /搜索失败 else if ( x data ) /在左子树搜索 return Find ( x, ptr-le
7、ftChild ); else if ( x ptr-data ) /在右子树搜索 return Find ( x, ptr-rightChild ); else return ptr; /相等,搜索成功 ,二叉搜索树的插入,35,15,45,50,40,25,10,20,30,28,每次结点的插入,都要从根结点出发搜索插入位置,然后把新结点作为叶结点插入。,插入新结点28,在插入之前,先使用搜索算法在树中检查要插入元素有还是没有。 搜索成功: 树中已有这个元素,不再插入。 搜索不成功: 树中原来没有关键码等于给定值的结点,把新元素加到搜索操作停止的地方。,template void BST
8、: Insert ( Type x, BstNode * ,递归的二叉搜索树插入算法,输入数据,建立二叉搜索树的过程,输入数据 53, 78, 65, 17, 87, 09, 81, 15 ,53,二叉搜索树的删除(四种情况),在二叉搜索树中删除一个结点时,必须将因删除结点而断开的二叉链表重新链接起来,同时确保二叉搜索树的性质不会失去。 为保证在删除后树的搜索性能不至于降低,还需要防止重新链接后树的高度增加。 1. 删除叶结点,只需将其双亲结点指向它的指针清零,再释放它即可。 2. 被删结点右子树为空,可以拿它的左子女结点顶替它的位置,再释放它。,3.被删结点左子树为空,可以拿它的右子女结点顶
9、替它的位置,再释放它。 4.被删结点左、右子树都不为空,可以在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删结点中,再来处理这个结点的删除问题。,53,78,65,17,87,09,23,45,删除45,右子树空, 用左子女顶替,53,78,65,17,87,09,23,88,53,78,88,17,94,09,23,删除78,左子树空, 用右子女顶替,53,94,88,17,09,23,53,78,81,17,94,09,45,删除78,在右子树上找中序下第一个结点填补,23,65,53,81,88,17,94,09,45,23,65,二叉搜索树查找次数分析,最坏情况
10、O(n) 最好情况 O(log2n) 如何避免最坏情况呢?,AVL树的定义,一棵AVL树或者是空树,或者是具有下列性质的二叉搜索树:它的左子树和右子树都是AVL树,且左子树和右子树的高度之差的绝对值不超过1。,高度不平衡 高度平衡,A,B,C,A,B,C,D,E,D,E,7.6 AVL树 高度平衡的二叉搜索树,结点的平衡因子(balance factor),每个结点的右子树的高度减去左子树的高度所得的高度差, 即为结点的平衡因子balance 。 AVL树任一结点平衡因子只能取 -1, 0, 1 如果一个结点的平衡因子的绝对值大于1,则以该结点为根的二叉搜索树就失去了平衡, 不再是AVL树。,
11、AVL树的类定义,template class AVLTree public: struct AVLNode /AVL树结点 Type data; int balance; AVLNode * left, * right; AVLNode ( ) : left (NULL), right (NULL), balance (0) AVLNode ( Type d, AVLNode * l = NULL, AVLNode *r = NULL) : data (d), left (l), right (r), balance (0) ; ,每插入一个新结点时, AVL 树中相关结点的平衡状态会发生改
12、变。因此, 在插入一 个新结点后,需要从插入位置沿通向根的路径回溯,检查各结点的平衡因子 如果在某一结点发现高度不平衡,停止回溯。该不平衡的结点为最深的不平衡点 根据最深的不平衡点与新插入点的位置关系,进行相应的平衡化旋转 单旋转:左单旋转或右单旋转 双旋转:先左后右旋转和先右后左旋转,平衡化旋转,右单旋转,左单旋转,左右双旋转,右左双旋转,四种不同的平衡化旋转,表示最深的不平衡,如果最深的不平衡点与新插入点处于一条直线上,则采用单旋转进行平衡化(左单旋转或右单旋转)。 如果最深的不平衡点与新插入点处于一条折线上,则采用双旋转进行平衡化(双旋转分为先左后右和先右后左两类)。,插入新结点后导致结
13、点A的平衡因子变成2,出现不平衡。为使树恢复平衡,以结点B为旋转轴,让结点A反时针旋转。,1.左单旋转 (RotateLeft ),/左单旋转的算法 template void AVLTree : RotateLeft ( AVLNode * Tree, AVLNode * ,插入新结点后结点A的平衡因子增到-2,造成不平衡。为使树恢复平衡,以结点B为旋转轴,将结点A顺时针旋转。,2.右单旋转 (RotateRight ),/右单旋转的算法 template void AVLTree : RotateRight ( AVLNode * Tree, AVLNode * ,左单 旋转,A,C,B,
14、3.先左后右双旋转(RotationLeftRight),插入新结点后,结点A的平衡因子变为-2,造成不平衡。 首先,以结点C为旋转轴,将结点B反时针旋转,以C代替原来B的位置。 其次,再以结点C为旋转轴,将结点A顺时针旋转,以C代替原来A的位置。 。,template void AVLTree : LeftBalance ( AVLNode * &Tree, int & taller ) ,左平衡算法实现(包含右单旋转和左右旋转),AVLNode *leftsub = Tree-left, *rightsub; switch ( leftsub-balance ) case -1 : Tre
15、e-balance = leftsub-balance = 0; RotateRight ( Tree, Tree); taller = 0; break; case 0 : cout right; switch ( rightsub-balance ) ,case -1: Tree-balance = 1; leftsub-balance = 0; break; case 0 : Tree-balance = leftsub-balance = 0; break; case 1 : Tree-balance = 0; leftsub-balance = -1; rightsub-balanc
16、e = 0; RotateLeft ( leftsub, Tree-left ); RotateRight ( Tree, Tree); taller = 0; ,4.先右后左双旋转 (RotationRightLeft),插入新结点后,结点A的平衡因子变为2,发生了不平衡。 首先,以结点C为旋转轴,将结点B顺时针旋转,以C代替原来B的位置。 其次,再以结点C为旋转轴,将结点A反时针旋转,以C代替原来A的位置。,template void AVLTree:RightBalance ( AVLNode * &Tree, int& taller ) ,右平衡算法实现(包含左单旋转和右左旋转),AV
17、LNode *rightsub = Tree-right, *leftsub; switch ( rightsub-balance ) case 1 : Tree-balance = rightsub-balance = 0; RotateLeft ( Tree, Tree); taller = 0; break; case 0 : cout left; switch ( leftsub-balance ) ,case 1 : Tree-balance = -1; rightsub-balance = 0; break; case 0 : Tree-balance = rightsub-bal
18、ance = 0; break; case -1 : Tree-balance = 0; rightsub-balance = 1; break; leftsub-balance = 0; RotateRight ( rightsub, Tree-right); RotateLeft ( Tree, Tree); taller = 0; ,AVL树的插入,在向一棵本来是高度平衡的AVL树中插入一个新结点时,如果树中某个结点的平衡因子的绝对值 |balance| 1,则出现了不平衡,需要做平衡化处理。 算法从一棵空树开始,通过输入一系列对象关键码,逐步建立AVL树。在插入新结点时使用平衡旋转方法
19、进行平衡化处理。,16,16,例: 输入关键码序列为 16, 3, 7, 11, 9, 26, 18, 14, 15 ,插入和调整过程如下。,0,3,16,3,-1,0,7,0,1,-2,左右双旋,7,3,16,0,0,0,7,3,11,0,-1,1,7,3,16,16,11,9,0,-1,-2,右单旋,3,7,16,9,0,0,0,1,3,7,11,26,9,16,11,0,1,1,2,2,18,18,0,3,16,3,-1,0,16,0,2,右左双旋,7,3,9,0,0,0,18,26,11,-1,7,3,26,16,11,9,-1,左单旋,9,7,16,14,0,0,1,7,11,26,
20、26,9,1,1,11,15,18,2,3,18,16,-2,左右双旋,7,3,0,0,0,11,7,14,9,-1,16,15,0,1,11,26,26,14,1,-2,9,从空树开始的建树过程,算法从树的根结点开始,递归向下找插入位置。在找到插入位置(空指针)后,为新结点动态分配存储空间,将它作为叶结点插入,并置success(记载新结点是否存储分配成功)为1,再将taller置为1,以表明插入成功。在退出递归沿插入路径向上返回时做必要的调整。 在发现不平衡时立即执行相应的平衡化旋转操作,使得树中各结点重新平衡化。 下面的算法将通过递归方式将新结点作为叶结点插入并逐层修改各结点的平衡因子。
21、,template int AVLTree : Insert ( AVLNode* if ( taller ),switch ( tree-balance ) case -1 : LeftBalance ( tree, taller ); break; case 0 : tree-balance = -1; break; case 1 : tree-balance = 0; taller = 0; else if ( x tree-data ) success = Insert ( tree-right, x, taller ); if ( taller ) switch ( tree-balance ) case -1 : tree - balance = 0; taller = 0; break; case 0 : tree - balance = 1; break; case 1 : RightBalance ( tree, taller );, return success; ,
链接地址:https://www.31doc.com/p-2582832.html