数据结构第17次课-查找C.ppt

1、第1页,1. 上机实现顺序查找的改进算法。 2.上机实现折半查找的递归及非递归算法。 选做： 3.设计一个算法，利用折半查找算法在一个 有序表中插入一个元素x，并保持表的有序 性，上机实现。,实验三,第2页,针对静态查找表的查找算法主要有：,8.2 静态查找表,一、顺序查找（线性查找） 二、折半查找（二分或对分查找） 三、静态树表的查找 四、分块查找（索引顺序查找）,上节课内容回顾,第3页,一、顺序查找（ Linear search，又称线性查找 ）,顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。 对顺序结构如何线性查找？ 挨个比较 对单链表结构如何线性查找？函数虽未给出，

2、但也很容易编写；只要知道头指针head就可以“顺藤摸瓜”； 对非线性树结构如何顺序查找?可借助各种遍历操作！,优点：算法简单，且对顺序结构或链表结构均适用。 缺点： ASL(n+1)/2 ,ASL太大，时间效率太低。,顺序查找的特点：,第4页,二、折半查找（又称二分查找或对分查找）,先给数据排序（例如按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至右半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。, low=1；high=length； / 设置初始区间 当lowhigh时，返回查找失败信息 / 表空，查找失败 lowhigh，mid=(l

3、ow+high)/2; / 取中点 a. 若kxelemmid.key，low=mid+1； 转 / 查找在右半区进行 c. 若kx=elemmid.key，返回数据元素在表中位置 / 查找成功,第5页,四、分块查找（索引顺序查找）,这是一种顺序查找的另一种改进方法。 先让数据分块有序，即分成若干子表，要求每个子表中的数值（用关键字更准确）都比后一块中数值小（但子表内部未必有序）。 然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。,索引表,最大关键字,起始地址,第1块,第2块,第3块,22,48,86,例：,特点：块间有序，块内无序,第6页,查找步骤分两步

4、进行：, 对索引表使用折半查找法（因为索引表是有序表）； 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）； 查找效率：ASL=Lb+Lw,对索引表查找的ASL,对块内查找的ASL,S为每块内部的记录个数，n/s即块的数目,例如当n=9，s=3时，ASLbs=3.5,而折半法为3.1,顺序法为5,第7页,小结：,第8页,针对动态查找表的查找算法主要有：,8.3 动态查找表,一、二叉排序树（BST） 二、平衡二叉树（AVL树） 三、 B- 、 B+树,第9页,1、二叉排序树的定义回顾,-或是一棵空树；或者是具有如下性质的非空二叉树： （1）左子树的所有结点均小于根的

5、值； （2）右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。递归定义 （4）其中序遍历序列为一个递增序列,一. 二叉排序树搜索,第10页,2、二叉排序树的插入与删除,将数据元素构造成二叉排序树的优点： 查找过程与顺序结构有序表中的折半查找相似，查找效率高； 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。,注：若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！,这种既查找又插入的过程称为动态查找。 二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。,第11页,45,如果待查找

6、的关键字序列输入顺序为： （24，53， 45，45，12，24，90）,24,讨论1：二叉排序树的插入和查找操作,则生成二叉排序树的过程为：,例：输入待查找的关键字序列=（45，24，53，45，12，24，90）,则生成的二叉排序树形态不同：,第12页,bstnode BSTSEARCH(bstnode t, keytype k) bstnode p; p=t; while (p) if (p.key= k) return p; if (p.key k) p=p.lchild; else p=p.rchild; return NULL; ,1. 二叉排序树的查找,二叉排序树的查找 p=t;

7、 if (t=NULL) return s; /原树t为空 while (p!=NULL) /找插入父结点 f=p; /保存当前节点指针 if (s.key=p.key) return t; /s在t中已经存在 if (s.keyp.key) p=p.lchild; /比当前结点小，向左 else p=p.rchild; /比当前结点大，向右 if (s.keyf.key) f.lchild=s; /找插入父结点,插入确定位置 else f.rchild=s; return t; ,二叉排序树的结点插入算法,第15页,对于二叉排序树，删除树上一个结点相当于删除有序序列中的一个记录，删除后仍需保

8、持二叉排序树的特性。 （对链表进行删除操作是很方便的） 具体算法参看树D课件,讨论2：二叉排序树的删除操作,第16页,1) 二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。 比较的关键字次数此结点的层次数; 最多的比较次数树的深度（或高度），即 log2 n+1 2) 一棵二叉排序树的平均查找长度为：,3.二叉排序树的查找分析,其中： ni 是每层结点个数； ci 是结点所在层次数； m 为树深。,第17页,最坏情况：即插入的n个元素从一开始就有序， 变成单支树的形态！ 此时树的深度为n ; ASL= (n+1)/2 此时查找效率与顺序查找情况相同。,最好情况

9、：即：与折半查找中的判定树相同（形态比较均衡）,树的深度为：log 2n +1 ； ASL=(n+1)/n*log 2(n+1) 1 ；与折半查找相同。,第18页,3）对有 n 个关键字的二叉排序树的平均查找长度: 设每种树态出现概率相 同 ，查找每个关键字也是等概率的。 则ASL求解过程可推导。,结论：二叉排序树的ASL2（11/n）ln n,问：如何能让二叉排序树的查找过程保持最好情况？,第19页,二 平衡二叉树( AVL树）,什么是平衡二叉树(Balanced Binary Tree) ? 平衡二叉树是空树,或者是具有以下性质的二叉树: 它的左子树和右子树也都是平衡二叉树并且 左子树和右

10、子树的深度之差的绝对值不超过1 结点的平衡因子BF (Balance Factor)是 左子树的深度减去右子树的深度,它只可能是 -1, 0, 1 平衡二叉树(也称AVL树)的深度为O(log2N) (其中N为结点个数) 它的平均查找长度也是O(log2N),第20页,平衡二叉树及平衡因子举例,平衡的二叉树,第21页,不平衡的二叉树,不平衡二叉树及平衡因子举例,第22页,二叉排序树在结点添加过程中失衡 的几种情况,第23页,二叉排序树转成平衡树失去平衡后需要进行调整的四种情况,(1) 单向右旋平衡处理LL 当在左子树上插入左结点,使平衡因子由1增至2时 (2) 单向左旋平衡处理RR 当在右子树

11、上插入右结点,使平衡因子由-1增至-2时 (3) 双向旋转(先左后右)平衡处理LR 当在左子树上插入右结点,使平衡因子由1增至2时 (4) 双向旋转(先右后左)平衡处理RL 当在右子树上插入左结点,使平衡因子由-1增至-2时,第24页,1、 LL型平衡旋转 A的左子树的左子树上插入结点，作顺时针旋转。,第25页,2、 RR型： A的右子树的右子树上插入结点，作逆时针旋转。,第26页,3、 LR型： A的左子树的右子树上插入结点，作两次（逆、顺）旋转。,第27页,4 RL型： 在A的右子树的左子树上插入结点，作两次（顺、逆）旋转。,第28页,二叉排序树在结点添加平衡化方法总结,第29页,二叉排序

12、树转成平衡树示例设关键字序列为(13,24,37,90,53),0 13,-1 13,0 24,0 37,0 13,-2 13,-1 24,0 24,0 37,0 53,0 13,0 13,0 37,0 90,0 53,-1 24,1 90,-2 37,-2 24,(a),(b),(c),(d),(e),(f),(g),(h),24,13,37,53,90,(h),24,13,37,53,90,第30页,练习：下列情况属于哪种失衡状况？应该操作哪些结点？,LR 12,7,9,RR 12,19,第31页,二叉排序树在结点添加平衡化实例,例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结

13、构的变化。 15，12，7，19，24，9，8，5，6,第32页,例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。 15，12，7，19，24，9，8，5，6,第33页,例：给定平衡二叉排序树的输入结点序列，请图示结点插入过程树结构的变化。 15，12，7，19，24，9，8，5，6,第34页,失衡二叉排序树平衡化过程特性,1、 树的高度不会增加；h1 2、 保持了二叉排序树的基本性质。 3、 使二叉排序查找性能趋近二分查找。,第35页,在平衡树上进行查找的过程和二叉排序树相同，因此在查找过程中和给定值进行比较的关键码个数不超过树的深度。为了确定含有n个关键码的平衡树的最

14、大深度，先分析深度为h的平衡树所具有的最少结点数。,平衡二叉树查找性能分析,(查找插入平衡化）,斐波那契序列： F00，F11，FiFi-1+ Fi-2,F00，F11，F21, F3=2, F4=3, F5=5, F6=8, F7=13, F821,第36页,假设以Nh表示深度为h的平衡树中含有的最少结点数。显然，N0=0，N1=1，N2=2，并且Nh=Nh-1+Nh-2+1。这个关系和斐波那契序列极为相似。利用归纳法容易证明：当h0.,因此，在平衡二叉树上进行查找的时间复杂度为O(log2n)。,问：深度为6的平衡树最少具有多少结点？,20,第37页,平衡树以二叉链表作为存储结构,每个结点

15、还要增加一个平衡因子域。 平衡树的查找运算与普通树型查找完全相同，由于平衡树附加了平衡条件，其高度与结点数相同的完全树属于同一数量级，所以有较快的查找速度。 在插入新结点时，当确定了新结点应插入的位置后，需向上寻找有关平衡因子变为+2或-2的祖先，如有这种结点，则取其中层数居最低者，根据不同的情况进行单旋转或双旋转，使整个树仍然符合平衡树的条件，每次插入结点后，还需对有关祖先的平衡因子加以修改。,平衡二叉排序树编程实现注意事项,第38页,B-树的形态和本质,三 B、B+树,本质：多路查找树，查找过程类似于二叉排序树,非终端结点中包含下列信息数据（n，A0，K1， A1，K2，A2， Kn，An

16、）,第39页,B-树的定义或曰性质 一棵m阶的B-树，或为空树，或为满足下列特性的m叉树：,1、 树中每个结点至多有m棵子树； 2、 若根结点不是叶子结点，则至少有两棵子树； 3、 除根之外的所有非终端结点至少有m/2棵子树； 4、 所有的非终端结点中包含下列信息数据（n，A0，K1， A1，K2，A2， Kn，An），其中Ki为关键字，关键字个数n 必须满足 m/2 1=n=m-1。 5 、所有的叶子结点都出现在同一层次上，并且不带信息。,第40页,例：一棵四阶的B-树。,第41页,B-树的插入（要求保持B-树性质不变） B-树的生成也是从空树起，逐个插入关键字而得。但由于B-树结点中得关键

17、字个数必须m/2-1，因此，每次插入一个关键字不是在树中添加一个叶子接点，而是首先在最低层的某个非终端结点中添加一个关键字，若该结点的关键字个数不超过m-1， 则插入完成，否则要产生结点的分裂。,例：在下面是一棵3阶的B-树，从中插入元素30，26，85。,第42页,第43页,第44页,问：此时插入关键字7，如何改变树结构？动手练习一下！,第45页,B-树的删除 若在B-树中删除一个关键字，则首先应找到该关键字所在结点，并丛中删除之。 若该结点为最下层的非终端结点，且其中的关键字数目不小于m/2，则删除完成，否则进行“合并”结点的操作。,第46页,假若所删除关键字为非终端结点中的Ki， 则可以

18、指针Ai所指子树中的最小关键字Y替代Ki，然后在相应的结点中删除Y。,第47页,因此，下面我们可以只需讨论删除最下层非终端结点中的关键字的情形。有下面三种可能： 1、被删除关键字所在结点中的关键字数目不小于m/2，则只需从该结点中删去该关键字Ki和相应指针Ai，树的其它部分不变。 2、被删除关键字所在结点的关键字数目等于m/2-1，而与该结点相邻的右兄弟（或左兄弟）结点中的关键字数目大于m/2-1， 则只需将其右兄弟结点中的最小（或左兄弟结点中的最大）的关键字上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字的关键字下移至被删除关键字所在结点中。,第48页,第49页,3、被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于m/2-1。若该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，则在删去关键字之后，它所