数据结构课程讲义.ppt

第九章 查找,这也是线性表的基本运算之一。通常称为检索、查询等。 1 线性查找 11 顺序检索 基本思想： 从线性表的一端开始，逐个地将待查找元素的关键字与每个元素的关键字进行比较，若找到，则返回1，否则返回0。 该算法的时间复杂度为O(n).,1 线性查找,顺序查找采用从头至尾逐个比较 最快O(1) 最慢O(n) 查找成功的等概率平均时间复杂性 O(n+1)/2) 1/n(1+2+3+n)=(n+1)/2 查找失败O(n+1) 查找的等概率平均时间复杂性 O(3(n+1)/4) 查找成功失败各半 1/2n(1+2+n)+n(n+1)=3(n+1)/4,1 线性查找,1 线性查找,12 二分查找 亦称折半查找，是基于提高查找速度的一种方法。检索时要求元素是排序的。 基本思想： 每次将待查找元素的关键字与已排序元素序列的中间点元素进行比较，如相等，则返回1，否则修改高点或低点，重新进行查找比较。 该算法的时间复杂度为O(n).,这是有序表的查找查找,对已排序的查找结构先确定中点，比较待查关 键字与中点关键字的大小，反复直到成功。 求n个数据折半查找的等概率成功查找的平均时 间复杂性 1 2 3 4 5 6 7 8 9 10,1,2,2,3,3,3,3,4,4,4,1+2*2+4*3+3*4=29 O(29/10),n个元素的折半查找,2k-1n2k+1-1 查找成功平均概率时间复杂性 介于 log2(2k)-1 和 log2(2k+1)-1 之间 即 k-1 和 k 之间 k=log2(n+1) n个元素的折半查找成功平均概率时间复杂性 log2(n+1)-1/2,1 线性查找,13 分块查找 亦称索引顺序查找。也是基于提高查找速度的一种方法。检索时要求元素构成的块间是排序的，而块内是未排好序的。 基本思想： 将所有元素按关键字值划分成若干块，块之间是排序的，而块内暂时是无序的。查找时候，首先折半查找确定元素所在的块，然后再在块内进行顺序查找即可比较。,3、索引顺序查找,分块有序 后一子表中的关键字都大于前一子表中的关键字,最大关键字 起始地址,索引表,索引顺序表的查找,查找 关键字key=38 1. 先检索索引表 确定子表位置 2. 再在子表中查找,索引表,分块查找成功的平均概率时间复杂性,索引表查找时间+子表查找时间 设索引表长为s，查找表长为n,被平均分成s块， 每块长n/s, 索引表平均查找时间 (s+1)/2 子表平均查找时间 (n/s+1)/2 (s+1)+ (n/s+1)= (s+n/s)+1 当 s=n 时 有最小值 n +1,当索引顺序表已经排序时，子块查找可以用折半查找。 平均查找时间： (s+1)/2 +log2(1+n/s)-1/2 = log2(1+n/s)+s/2 索引也用折半查找，平均查找时间 log2(s+1)-1/2 +log2(1+n/s)-1/2 = log2(s+1)(1+n/s)-1 当s= n 时 2 log2(n +1)-1,2 树形结构的查找,21 二叉排序树及其查找过程 二叉树BT是二叉排序树，只要BT是满足如下的条件： （1）若BT的左子树非空，则其左子树上所有结点的值均小于其根结点的值；（2）若其右子树上所有结点的值均大于其根结点的值；（3）其左右子树均为二叉排序树。 对二叉排序树的中序遍历的结果就是一个升序序列。 二叉排序树又称为二叉查找树。 于是，只要将元素序列组织成二叉排序树，在进行查找时，让待查找元素与根结点值进行比较，若相等，则查找成功，否则，如果比根结点小，则只需要在左子树中查找即可；如果比根结点大，则只需要在右子树中查找即可。,2 树形结构的查找,其所涉及到的数据结构如下： typedef struct btnode keytype key; datatype other; struct btnode *lchild,*rchild; BSTNODE; BSTNODE *ptr; 则*ptr就表示一棵二叉排序树。,2 树形结构的查找,22 二叉排序树实现查找运算 根据二叉排序树的定义和性质，不难得到其查找算法： int bstsearch(*Pt,x) pkey=x) return(1); if(p-keyx) prchild; else plchild; ,二叉查找树的查找分析,平均等概率查找时间 (1+2+2+3+3+3)/6=14/6,45,12,57,8,20,60,45,12,8,20,3,11,(1+2+3+4+5+6)/6=7/2,随机二叉查找树等概率平均查找时间,P(n)2(1+1/n)lnn O(log2n) 最坏 O(n/2),特点：用于频繁进行插入、删除、查找的所谓动态查找表。,122,250,300,110,200,99,二叉排序树,L,N,P,E,M,C,Y,105,230,216,查找步骤：若根结点的关键字值等于查找的关键字，成功。 否则，若小于根结点的关键字值，查其左子树。 若大于根结点的关键字值，查其右子树。 在左右子树上的操作类似。,122,250,300,110,200,99,105,230,216,2 树形结构的查找,2.2 二叉排序树的插入运算 由于插入运算是二叉树的基本运算之一，所以利用二叉树的插入运算就可以实现在线性升序序列中插入结点，使之仍然是升序的功能。 其实现过程为：若二叉排序树为空，则待插入结点*s就作为根结点插入到空二叉树中；若二叉树非空，则比较s-key:p-key,若，就插入到右子树中，若=则不必插入。 该过程是递归的，很容易得到递归算法，也可以得到非递归算法。,2 树形结构的查找,void insertbst(*pt,*s) pkeykey) plchild; else prchild; if(pt=NULL) ptkeykey) f-lchildrchild=s; 显然，插入运算是将待插入结点作为叶子插入的。所以算法的目的就是首先找到插入的位置。,2、插入算法： 首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。 注意：新插入的结点总是叶子结点。,e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树。,122,2、插入算法： 首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。 注意：新插入的结点总是叶子结点。,e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树。,122,122,99,2、插入算法： 首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。 注意：新插入的结点总是叶子结点。,e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树。,122,122,99,122,250,99,2、插入算法： 首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。 注意：新插入的结点总是叶子结点。,e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树。,122,122,99,122,250,99,122,250,110,99,2、插入算法： 首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。 注意：新插入的结点总是叶子结点。,e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树。,122,122,99,122,250,99,122,250,110,99,122,250,300,110,99,2、插入算法： 首先执行查找算法，找出被插结点的父亲结点。 判断被插结点是其父亲结点的左、右儿子。将被 插结点作为叶子结点插入。 若二叉树为空。则首先单独生成根结点。 注意：新插入的结点总是叶子结点。,122,250,300,110,280,99,e、g：将数的序列：122、99、250、110、300、280 作为二叉排序树的结 点的关键字值，生成二叉排序树。,122,122,99,122,250,99,122,250,110,99,122,250,300,110,99,2、插入算法：,执行实例：插入值为 280 的结点,15,60,70,30,20,50,3、二叉排序树的查找分析,平均情况分析（在成功查找两种的情况下）,e.g: 下述两种情况下的成功的平均查找长度 ASL,15,60,70,30,20,50,ASL=(1+2+2+3+3+3)/6=14/6,ASL=(1+2+3+4+5+6)/6=21/6,2 树形结构的查找,2.3 二叉排序树的删除运算 由于删除结点运算也是二叉树的基本运算之一，所以利用二叉树的删除运算就可以实现在线性升序序列中删除结点，使之仍然是升序的序列。 其实现过程为： 若待删除结点不在二叉排序树，则不进行任何操作；否则，假设找到的待删除结点为*p，fath指向*p的双亲，那么，删除*p的过程可以采用如下的方法：*p是否有左（右）子树来分别进行处理。,2 树形结构的查找,（1）若*p没有左子树，则只需要将*p的右子树按照二叉排序树的特性，连接到合适的位置即可。若*p没有根结点，则只需要将*p的右子树的根作为新的根结点；若*p不是根，则必须将它与其双亲*fath之间的连接断开，可以采用将将连接到*p的右子树连接到*fath的左（右）链域上。当然，若*p的右子树也为空，则*p就是叶子结点，即p-rchild=NULL,则就相当于将空树连接到*fath的左（右）链域中。,2 树形结构的查找,（2）若*p有左子树，则*p也可能有右子树，需要将*p的左、右子树按照二叉排序树的特性，连接到合适的位置。此时可以采用两种处理方法：一种是令p的左子树直接连接到*p的双亲*fath的左（右）链域上，而*p的右子树下接到*p的中序前趋结点*s的右链域上。（这里*s是*p的左子树中最右下的结点，其右链域肯定为空）。 另外一种处理方法是：采用以*p的中序前趋*s顶替*p(相当于将*s的内容复制到*p中)，将*s的左子树直接上接到*s的双亲*q左（右）链域上，再删去*s。,叶子结点：直接删除，更改它的父亲结点的相应指针域为空。如：删除关键字为 15、70 的结点。,15,60,70,30,20,50,60,30,20,50,子树的根结点：通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？左子树中最大的结点 或 右子树中最小的结点，参看图。 要点：维持二叉排序树的特性不变。在中序周游中紧靠着被删结点的结点才有资格作为“替身”。,122,250,300,110,200,99,105,230,216,400,450,500,子树的根结点：若被删结点的左儿子为空或者右儿子为空。 如下图所示，删除结点的关键字为 99 、200 的结点。,被删结点,122,250,300,200,230,216,400,450,500,110,105,删除,99,122,250,300,110,200,99,105,230,216,400,450,500,被删结点,子树的根结点：若被删结点的左儿子为空或者右儿子为空。 如下图所示，删除结点的关键字为 99 、200 的结点。,122,250,300,230,216,400,450,500,删除,200,110,99,105,122,250,300,110,200,99,105,230,216,400,450,500,被删结点,子树的根结点：若被删结点的左儿子为空或者右儿子为空。 如下图所示，删除结点的关键字为 99 、200 的结点。,结论：将被删结点的另一儿子作为它的父 亲结点的儿子，究竟是作为左儿子 还是右儿子依原替身结点和其父亲 结点的关系而定。 释放被删结点的空间。,被删结点,子树的根结点：若被删结点的左、右子树皆不空，通常的做法：选取“替身”取代被删结点。有资格充当该替身的是谁哪？ 左子树中最大的结点(被删结点的左子树中的最右的结点，其右儿子指针域为空) 或 右子树中最小的 结点(被删结点的右子树中的最左的结点，其左儿子指针域为空) ，参看下图。 要点：维持二叉排序树的特性不变。在中序周游中紧靠着被删 结点的结点才有资格作为“替身”。,做法：将替身的关键字复制到被删结 点的关键字。 将结点 的左儿子作为 的父结点 的右儿子。,110,110,99,注意：结点 右儿子必为空 结点 的父结点为,110,110,99,200,250,300,110,99,105,230,216,400,450,500,做法：将替身的关键字复制到被删结 点的关键字。 将结点 的右儿子作为 的父结点 的左儿子。,注意：结点 左儿子必为空 结点 的父结点为,200,200,200,200,250,结论： 先将替身的关键字复制到被删结点 将原替身的另一儿子作为它的父亲 结点的儿子，究竟是作为左儿子还 是右儿子依原替身结点和其父亲结 点的关系而定。 释放原替身结点的空间。,F,S,C,Q,QL,SL,F,C,Q,QL,S,SL,F,PL、PR皆 空， 直接删除 。,PL或PR为空，,PL为空，删除后的情况。,1.删除法,2.删除法,2 树形结构的查找,24 平衡二叉树简介 由于二叉排序树的结构形态直接影响到查找的效率，所以必须构造出平衡二叉树。只要满足平衡因子（即任何两个子树的高度之差）只能是-1，0，1的，则称为平衡二叉树。 通常情况下，平衡二叉树的深度是很低的，所以其查找效率是最高的。,D,G,E,D,A,B,C,F,E,G,B,A,平衡二叉排序树,起因：提高查找速度，避免最坏情况出现。如右图情况的出现。 虽然完全树的树型最好，但构造困难。常使用平衡树。,C,F,平衡因子（平衡度）：结点的平衡度是结点的左子树的高度右子树的高度。 平衡二叉树：每个结点的平衡因子都为 1、1、0 的二叉树。或者说每个 结点的左右子树的高度最多差一的二叉树。 注意：完全树必为平衡树，平衡树不一定是完全树。,平衡树的 Adelson 算法的本质特点： 以插入为例： 在左图所示的平衡树中插入关键字为 2 的结点。 插入之后仍应保持平衡排序二叉树的性质不变。,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,平衡树,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度为 0,危机结点,如何用最简单、最有效的办法保持平衡排序二叉树的性质不变？,平衡树的 Adelson 算法的本质特点： 以插入为例： 在左图所示的平衡树中插入关键字为 2 的结点。 插入之后仍应保持平衡排序二叉树的性质不变。,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度为 0,危机结点,如何用最简单、最有效的办法保持平衡排序二叉树的性质不变？,解决方案： 不涉及到危机结点的父亲结点，即以危机结点为根的子树的高度应保持不变（左图为 3 ）。 新结点插入后，找到第一个平衡度不为 0 的结点（如左图结点 ）即可。新插入的结点和 第一个平衡度不为 0 的结点（也可能是危机结点）之间的结点，其平衡度皆为 0 在调整中，仅调整那些在平衡度变化的路径上的结点（如： ），其它结点不予调整。 仍应保持排序二叉树的性质不变。,9,3,5,9,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度为 0,危机结点,如何用最简单、最有效的办法保持平衡排序二叉树的性质不变？,2,3,5,9,7,12,2,3,5,9,7,12,不可以以结点 为子树的根结点！虽然，对本例来说是可以行得通的。,7,14,12,5,3,9,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,0,2,+1,+1,+2,原平衡度为 0,危机结点,关键：将导致出现危机结点的情况全部分析清除，就可以使得平衡排序二叉树的性质保持不变！,14,9,3,2,5,28,63,53,60,50,17,18,7,30,+1,+1,-1,-1,-1,0,0,0,0,0,0,0,12,0,0,2.5 非平衡二叉树的平衡处理方法,若一棵二叉排序树是平衡二叉树，插入某个结点后，可能会变成非平衡二叉树，这时，就可以对该二叉树进行平衡处理，使其变成一棵平衡二叉树。处理的原则应该是处理与插入点最近的、而平衡因子又比1大或比-1小的结点。我们分四种情况讨论平衡处理。,1、LL型 的处理(左左型) 如下图所示，在A的左孩子B上插入一个左孩子结点C，使A的平衡因子由1变成了2，成为不平衡的二叉树序树。这时的平衡处理为：将A顺时针旋转，成为B的右子树，而原来B的右子树则变成A的左子树，待插入结点C作为B的左子树。(注：图中结点旁边的数字表示该 结点的平衡因子)，即左改组。,左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 1、LL 情况：（LL：表示新插入结点在危机结点的左子树的左子树上）,A,B,+1,h-1,0,+2,+1,h,h-1,h-1,LL 改组,BL,BR,AR,B,A,0,h,0,h-1,h-1,BL,BR,AR,危机结点,改组前：高度为 h + 1 中序序列：,A,B,BL,BR,AR,改组后：高度为 h + 1 中序序列：,A,B,BL,BR,AR,注意：改组后 平衡度为 0,A,B,2、LR型的处理(左右型) 如下图所示，在A的左孩子B上插入一个右孩子C，使的A的平衡因子由1变成了2，成为不平衡的二叉排序树。这是的平衡处理为：将C变到B与A 之间，使之成为LL型，然后按第(1)种情形LL型处理。此LR型又存在下列三种情形：,左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情形1：,A,B,+1,h-1,0,+2,-1,h-1,LR 改组,BL,AR,危机结点,改组前： 高度为 h + 1 中序序列：,注意：改组后 平衡度为 0,0,-1,C,B,C,CL,CR,h-2,h-2,h-1,0,+1,C,B,0,h-1,h-1,BL,AR,A,CR,h-2,CL,h-1,-1,0,A,B,BL,AR,C,CL,CR,改组后： 高度为 h + 1 中序序列：,A,B,BL,AR,C,CL,CR,A,左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情形2：,A,B,+1,h-1,0,+2,-1,h-1,LR 改组,BL,AR,危机结点,改组前： 高度为 h + 1 中序序列：,注意：改组后 平衡度为 +1,0,0,C,B,C,CR,CL,h-1,h-2,h-2,0,-1,C,B,0,h-1,h-1,BL,AR,A,CR,h-1,CL,h-2,+1,0,A,B,BL,AR,C,CR,CL,改组后： 高度为 h + 1 中序序列：,A,A,B,BL,AR,C,CR,CL,左改组（新插入结点出现在危机结点的左子树上进行的调整）的情况分析： 2、LR 情况：（LR：表示新插入结点在危机结点的左子树的右子树上） 情形3：,A,B,+1,0,+2,-1,LR 改组,危机结点,改组前： 高度为 2 中序序列：,注意：改组后 平衡度为 0,0,0,C,B,C,0,A,B,C,A,新插入结点,A,B,C,改组后： 高度为 2 中序序列：,C,B,0,A,0,0,四种情况的区分： 如果 的平衡度为1 则为 LL型改组； 否则为 LR型改组：若 的平衡度为1、1 、0 ；则分别为 LRA、LRB、LRC型改组。,B,C,3、RR型的处理(右右型) 如图下所示，在A的右孩子B上插入一个右孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将A逆时针旋转，成为B的左子树，而原来B的左子树则变成A的右子树，待插入结点C成为B的右子树。,4、RL型的处理(右左型) 如下图所示，在A的右孩子B上插入一个左孩子C，使A的平衡因子由-1变成-2，成为不平衡的二叉排序树。这时的平衡处理为：将C变到A与B之间，使之成为RR型，然后按第3 种情形RR型处理。,这里的右改组方法（新插入结点出现在危机结点的右子树上进行的调整）的情况分析： 1、RR 情况：（RR：表示新插入结点在危机结点的右子树的右子树上） 处理图形和 LL 镜象相似 2、RL 情况：（RL：表示新插入结点在危机结点的右子树的左子树上） 1、处理图形和 LRA 镜象相似 2、处理图形和 LRB 镜象相似 3、处理图形和 LRC 镜象相似 。,例2，给定一个关键字序列4,5,7,2,1,3,6，试生成一棵平衡二叉树。 分析：平衡二叉树实际上也是一棵二叉排序树，故可以按建立二叉排序树的思想建立，在建立的过程中，若遇到不平衡，则进行相应平衡处理，最后就可以建成一棵平衡二叉树。具体生成过程见下图。,26 平衡二叉树的查找及性能分析,平衡二叉树本身就是一棵二叉排序树，故它的查找与二叉排序树完全相同。但它的查找 性能优于二叉排序树，不像二叉排序树一样，会出现最坏的时间复杂度O(n)，它的时间复杂度与二叉排序树的最好时间复杂相同，都为O(log2n)。,例3 对例2给定的关键字序列4,5,7,2,1,3,6，试用二叉排序树和平衡二叉树两种方法查找，给出查找6的次数及成功的平均查找长度。 分析：由于关键字序列的顺序己经确定，故得到的二叉排序树和平衡二叉树都是唯一的,得到的平衡二叉树见上图，得到的二叉排序树见下图。,从上图的二叉排序树可知，查找6需4次，平均查找长度ASL=(1+2+2+3+3+3+4)/7=18/72.57。 从图8-14的平衡二叉树可知，查找6需2次，平均查找长度 ASL=(1+2+2+3+3+3+3)=17/72.43。,从结果可知，平衡二叉树的查找性能优于二叉排序树。,1、为什么采用B_ 树和 B+ 树： 大量数据存放在外存中，通常存放在硬盘中。由于是海量数据，不可能一次调入内存。因此，要多次 访问外存。但硬盘的驱动受机械运动的制约，速度慢。所以，主要矛盾变为减少访外次数。 在 1970 年由 R bayer 和 E macreight 提出用B_ 树作为索引组织文件。提高访问速度、减少时间。,内存,E.G: 用二叉树组织文件，当文件的记录个数为 100，000时，要找到给定关键字的记录，需访问外存17次（log100,000）,太长了！,50,25,10,75,15,35,60,90,20,30,40,55,70,80,95,索引文件,数据文件,文件头，可常驻内存,文件访问示意图：索引文件、数据文件存在盘上,8.2.2 B_ 树和 B+ 树,2、B_ 树是一种多分支数，首先介绍 m 阶 B_ 树： 定义： m 阶 B_ 树满足或空，或： A、根结点要么是叶子，要么至少有两个儿子 B、除根结点和叶子结点之外，每个结点的儿子个数为: m/2 K1 且 Kn 的结点的地址（指在该 B_ 树中） 注意：K1 =K2 = . = Kn D、所有的叶子结点都出现在同一层上，不带信息（可认为外部结点或失败结点）。,例如：m = 4 阶 B_ 树。除根结点和叶子结点之外，每个结点的儿子个数 至少为 m/2 = 2 个；结点的关键字个数至少为 1 。该 B_ 树的深度为 4。 叶子结点都在第 4 层上。,1，99,3，47，58，64,1，39,1，27,1，11,2，43，78,1，18,1，35,第 1 层,第 2 层,第 3 层(L层),第 4 层(L1层),3、B_ 树的查找代价分析： 查找过程，类似于二叉树的查找。如查找关键字为 KEY 的记录。 从根开始查找，如果 Ki = KEY 则查找成功，Ri 为关键字为 KEY 的记录的地址。 若 Ki Kn; 查找 An指向的结点 若 找到叶子，则查找失败。 注意：每次查找将去掉 （s-1）/s 个分支，比二分查找快得多。 设关键字的总数为 N ，求 m阶 B_ 树的最大层次 L。 层次 结点数 关键字的个数（最少） 1 1 1 2 2 2（ m/2 -1） 3 2（ m/2 ） 2（ m/2 ） （ m/2 -1） 4 2（ m/2 ） 2 2（ m/2 ）2 （ m/2 -1） L 2（ m/2 ）L-2 2（ m/2 ）L-2 （ m/2 -1） L+1 2（ m/2 ）L-1 所以，N=1 2（ m/2 -1） +.+ 2（ m/2 ）L-2 （ m/2 -1） = 2 m/2 L-1 -1 故：Llog （N+1）/2）+ 1,3、B_ 树的查找代价分析： 设关键字的总数为 N ，求 m阶 B_ 树的最大层次 L。 故：Llog m/2 （N+1）/2）+ 1 设 N 1000，000 且 m256 ，则 L = 3；最多 3 次访问外存可找到所有的记录。,4、B_ 树的插入操作 1、确定插入位置，将结点插入到第 L 层（注意：第 L+1 层为叶子结点） 2、找到插入位置，将关键字和其它信息按序插入。 3、若被插入结点的关键字个数 m-1, 则该结点满。必须分裂成两个结点。否则不满结束。 如结点原为： （m-1, A0, (K1, A1), (K2, A2), (Km-1, Am-1)） 插入一个关键字之后变为： （m, A0, (K1, A1), (K2, A2), (Km, Am)） 该结点将进行分裂： . (K m/2 , p ) . （m/2-1, A0, (K1, A1), (K m/2 , A m/2 )） （m- m/2 , A m/2 , (Km, Am)） 生成新结点 p, 将原结点的后半部分复制过去。若分裂一直进行到根结点，树可能长高一层。,P,P,(K m/2 , p ) 数据项插入上层结点之中,B-树的插入方法 设要插入关键值为k的记录，指向k所在记录的指针为p。 首先找到k应插入的叶子结点，将 k和p插入。然后，判断被插入结点是否满足m叉B-树的定义，即插入后结点的分支数是否大于m（结点的关键字数是否大于m-1)，若不大于，则插入结束；否则，要把该结点分裂成两个。方法是： 申请一个新结点，由指针p指向，将插入后的结点按照关键字的值大小分成左、中、右三部分，中间只含一项，左边的留在原结点，右边的移入新结点，中间的构成新的插入项，插入到它们的双亲结点中，若双亲结点在插入后也要分裂，则在分裂后再往上插入。,例如：3 阶 B_ 树的插入操作。m=3, m/2 - 1 = 1; 至少 1 个关键字，二个儿子结点。,3，12,7 24 30,24，30,45，70,53,90,26,100,39,50,61,85,3,45，70,53,90,26,100,39,50,61,85,12,30,3,24 45 70,53,90,26,100,39,50,61,85,12,7,30,3,24,53,90,26,100,39,50,61,85,12,7,45,70,7插入,5、B_ 树的删除操作 1、查找具有给定键值的关键字 Ki 2、如果 在第 L 层，可直接删除（注意：第 L+1 层为叶子结点），转 4 。 3、否则，则首先生成 “替身”。用 的右子树中的最左面的结点的关键字值，即 处于第 L 层上的最小 关键字值取代 。然后，删除第 L 层上的该关键字。 4、从第 L 层开始进行删除。 A、不动：若删除关键字值的那个结点的关键字的个数仍处于 m/2 -1和 m-1之间。则结束。 B、借：若删除关键字值的那个结点的关键字的个数原为 m/2 -1 。而它们的左或右邻居结 点的关键字的个数 m/2 -1 ; 则借一个关键字过来。处理结束。 C、并：若该结点的左或右邻居结点的关键字的个数为 m/2 -1 ; 则执行合并结点的操作。 如结点原为： （ . (Ki, Ai), (Ki+1, Ai+1), . ） （ A0, (K1, A1 ) ） （ A0, (K1, A1 ) ） K1L ,第 L 层：找到了被删结点的替身。,例如：3 阶 B_ 树的删除操作。m=3, m/2 - 1 = 1; 至少 1 个关键字，二个儿子结点。,3,24,45,53 90,37,100,50,61，70,被删关键字,3,24,45,61 90,37,100,53,70,借：向被删结点方向旋转,假定再删除该关键字,3,24,45,90,37,100,61，70,假定再删除该关键字,3，24,45,90,100,61，70,3，24,45 90,100,61，70,并,并,并,并：和父结点的一个关键字、及邻居合并。有可能进行到根，使B_ 树的深度降低一层！,3 散列查找,由于前两种查找方法中，记录在结构中的相对位置是随机的，和其关键码值之间没有直接的联系，因此在进行检索时，必须采用“比较”手段来实现，显然，查找的效率依赖于检索过程中进行比较的次数。 于是，理想的查找是不经过任何比较或少经过比较就能够得到所查找的元素，则必须在记录与其关键字值之间建立一个确定的对应关系h，使得每个关键字和结构中的一个唯一的存储位置相对应，这样在检索时，找到给定值K的影象H（K），若记录中存在关键码和k相等的记录，则必然存储在h(k)的存储位置上，因此不需要进行比较即可直接得到所查找的记录。通常称这个对应关系h为散列函数，采用该散列函数所建立的表称为散列表。,3 散列查找,实践表明： （1）如果散列表是一一对应的函数，则根据散列函数对给定的值进行某种运算，即可得到待查找元素的位置； （2）散列表占用的空间可能比结点空间多； （3）散列函数的构造原则：运算尽量简单，而且所占用空间均匀分布； （4）不同的关键字值可能得到相同的函数值，即可能有冲突产生。,3 散列查找,由此可见：散列查找必须解决两个问题： （1）构造一个尽量简单但冲突少、“均匀”的“好”散列函数； （2）正视而且必须解决面临的“地址冲突”问题。 可见：实际上第一个问题包容了第二个问题。因为一个“优秀的”散列函数必须解决地址冲突问题。 所以只要解决了第一个问题即可解决第二个问题。给出较好的散列函数是由HASH给出的，故散列查找又称HASH查找。,3 散列查找,【例】11个元素的关键码分别为 18，27，1，20，22，6，10，13，41，15，25。选取关键码与元素位置间的函数为 f(key)=key mod 11 1. 通过这个函数对11个元素建立查找表如下： 0 1 2 3 4 5 6 7 8 9 10 2. 查找时，对给定值kx依然通过这个函数计算出地址，再将kx与该地址单元中元素的关键码比较，若相等，查找成功。,22 | 1 | 13 | 25 | 15 | 27 | 6 | 18 | 41 | 20 | 10,哈希表与哈希方法： 选取某个函数H，依该函数按关键码计算元素的存储位置，并按此存放；查找时，由同一个函数对给定值kx计算地址，将kx与地址单元中元素关键码进行比，确定查找是否成功，这就是哈希方法(杂凑法)； 哈希方法中使用的转换函数称为哈希函数(杂凑函数)； 按这个思想构造的表称为哈希表(杂凑表)。,哈希查找的基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 定义 哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象 哈希函数可写成：addr(ai)=H(ki) ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字,哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫 哈希查找又叫散列查找，利用哈希函数进行查找的过程叫,以编号作关键字， 构造哈希函数：H(key)=key H(1)=1 H(2)=2,以地区别作关键字，取地区 名称第一个拼音字母的序号 作哈希函数：H(Beijing)=2 H(Shanghai)=19 H(Shenyang)=19,从例子可见： 哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可 冲突：key1key2，但H(key1)=H(key2)的现象叫 同义词：具有相同函数值的两个关键字，叫该哈希函数的 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法,哈希函数的构造方法 1、直接定址法 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=akey+b 特点 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突 实际中能用这种哈希函数的情况很少,2、数字分析法 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况,例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数,分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机 所以：取任意两位或两位 与另两位的叠加作哈希地址,3、平方取中法 构造：取关键字平方后中间几位作哈希地址 适于不知道全部关键字情况 折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类 移位叠加：将分割后的几部分低位对齐相加 间界叠加：从一端沿分割界来回折送，然后对齐相加 适于关键字位数很多，且每一位上数字分布大致均匀情况,例 关键字为 ：0442205864，哈希地址位数为4,4、除留余数法 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，pm 特点 简单、常用，可与上述几种方法结合使用 p的选取很重要；p选的不好，容易产生同义词 5、随机数法 构造：取关键字的随机函数值作哈希地址，即H(key)=random(key) 适于关键字长度不等的情况,选取哈希函数，考虑以下因素： 计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围） 关键字分布情况 记录的查找频率,3.2 处理冲突的方法 开放定址法 方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,k(km-1) 其中：H(key)哈希函数 m哈希表表长 di增量序列 分类 线性探测再散列：di=1,2,3,m-1 二次探测再散列：di=1,-1,2,-2,3,k(km/2) 伪随机探测再散列：di=伪随机数序列,例 表长为11的哈希表中已填有关键字为17，60，29的记录， H(key)=key MOD 11,现有第4个记录，其关键字为38， 按三种处理冲突的方法，将它填入表中,(1) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5+2) MOD 11=7 冲突 H3=(5+3) MOD 11=8 不冲突,38,(2) H(38)=38 MOD 11=5 冲突 H1=(5+1) MOD 11=6 冲突 H2=(5-1) MOD 11=4 不冲突,38,(3) H(38)=38 MOD 11=5 冲突 设伪随机数序列为9，则： H1=(5+9) MOD 11=3 不冲突,38,再哈希法 方法：构造若干个哈希函数，当发生冲突时，计算下一个哈希地址，即：Hi=Rhi(key) i=1,2,k 其中：Rhi不同的哈希函数 特点：计算时间增加 链地址法 方法：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针,例 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 用链地址法处理冲突,3.3 哈希查找过程及分析 哈希查找过程,哈希查找分析 哈希查找过程仍是一个给定值与关键字进行比较的过程 评价哈希查找效率仍要用ASL 哈希查找过程与给定值进行比较的关键字的个数取决于： 哈希函数 处理冲突