数据结构查表找课件

1,第九章 查找表,2,何谓查找表 ？,查找表是由同一类型的数据元素(或记录)构成的集合。,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。,3,对查找表经常进行的操作:,查询某个“特定的”数据元素是否在查找表中； 检索某个“特定的”数据元素的各种属性； 在查找表中插入一个数据元素； 从查找表中删去某个数据元素。,4,仅作 前两种即查询和检索操作的查找表。 即检索的前后不会改变查找表的内容。,静态查找表,在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素,此类表为动态查找表。即检索过程中可能会改变数据元素的存储位置。,动态查找表,查找表可分为两类:,5,检索是确定数据元素集合中是否存在数据元素等于特定元素或是否存在元素满足某种给定特征的过程。,要进行检索，必须知道待检索对象的特征，也就是要知道待检索数据元素的关键字。,我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。,6,是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。,关键字,若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。,若此关键字能识别若干记录，则称 之谓“次关键字”。,7,根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）,查找,若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置； 否则称“查找不成功”，查找结果：给出 “空记录”或“空指针”。,8,如果查找表中的数据元素之间不存在明显的组织规律，则不便于查找。 例：查阅英文单词时，由于字典是按单词的字母在字母表中的次序编排的，因此查找时不需要从字典中第一个单词比较起，而只要根据待查单词的每个字母在字母表中的位置查到该单词。,如何进行查找？,查找的方法取决于查找表的结构。即取决于数据元素依何种关系组织在一起。,9,线性结构是数据元素间最常见的数据结构，基于线性表的检索运算在各类程序中应用非常广泛，我们介绍三种在线性表上进行检索的方法，它们分别是顺序检索、二分法检索与分块检索。为简化问题，本节所介绍的检索方法均视为是基于静态查找表上的操作。,10,9.1 静 态 查 找 表,11,数据对象D：,数据关系R：,D是具有相同特性的数 据元素的集合。每个数 据元素含有类型相同的 关键字，可唯一标识数 据元素。,数据元素同属一个集合。,ADT StaticSearchTable /P216,12,Create(,Destroy(,Search(ST, key);,Traverse(ST, Visit();,基本操作 P：,next, ADT StaticSearchTable,13,构造一个含n个数据元素 的静态查找表ST。,Create(,操作结果：,14,销毁表ST。,Destroy(,初始条件： 操作结果：,静态查找表ST存在；,15,若 ST 中存在其关键字等于 key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。,Search(ST, key);,初始条件： 操作结果：,静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；,16,按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。,Traverse(ST, Visit();,初始条件： 操作结果：,静态查找表ST存在，Visit 是对元素操作的应用函数；,17,typedef struct / 数据元素存储空间基址，建表时 / 按实际长度分配，0号单元留空 int length; / 表的长度 SSTable;,假设静态查找表的顺序存储结构为,ElemType *elem;,18,数据元素类型的定义为:,typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ;, TElemType ;,19,一、顺序查找表,二、有序查找表,三、索引顺序表,20,以顺序表或线性链表表示静态查找表。 从表的一端开始，顺序（逐个）扫描线性表，依次将扫描到的结点关键字和给定值Key相比较，若当前扫描到的结点关键字与Key相等，则检索成功；若扫描结束后，仍未找到关键字等于Key的结点，则检索失败。,一、顺序查找表,21,0 1 2 3 4 5 6 7 8 9 10 11,5 13 19 21 37 56 64 75 80 88 92,找64,64,监视哨,比较次数=5,比较次数： 查找第n个元素： 1 查找第n-1个元素：2 . 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1,查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。 例如：,22,ST.elem,i,ST.elem,i,60,i,key=64,key=60,i,64,23,int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 ST.elem0.key = key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找 return i; / 找不到时，i为0 / Search_Seq,24,定义： 查找算法的平均查找长度 (Average Search Length) 也就是为确定某一结点在数据集合中的位置，给定值 与集合中的结点关键字所需进行的比较次数。 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 Ci为找到该记录时，曾和给定值 比较过的关键字的个数,分析顺序查找的时间性能。,25,在等概率查找的情况下， 顺序表查找的平均查找长度为：,对顺序表而言，Ci = n-i+1,ASL = nP1 +(n-1)P2 + +2Pn-1+Pn,26,若查找概率无法事先测定，则查找过程采取的改进办法是，可以在记录中附设一个访问频度域，使查找概率大的记录在查找过程中不断后移，以便在以后的查找过程中减少比较次数,在不等概率查找的情况下，ASLss 在 PnPn-1P2P1 时取极小值,ASL = nP1 +(n-1)P2 + +2Pn-1+Pn,27,上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。,二、有序查找表,若以有序表表示静态查找表，则查找过程可以基于“折半”进行。,28,1.设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。 2.初始时，令 low=1,high=n,mid=(low+high)/2 让k与mid指向的记录比较 若k=rmid.key，查找成功 若krmid.key，则low=mid+1 3.重复上述操作，直至lowhigh时，查找失败。,折半查找算法实现,29,ST.elem,ST.length,例如: key=64 的查找过程如下,low,high,mid,low,mid,high,mid,low 指示查找区间的下界; high 指示查找区间的上界; mid = (low+high)/2。,30,int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.length; / 置区间初值 while (low = high) mid = (low + high) / 2; if （EQ (key , ST.elemmid.key) ) return mid; / 找到待查元素 else if ( LT (key , ST.elemmid.key) ) high = mid - 1; / 继续在前半区间进行查找 else low = mid + 1; / 继续在后半区间进行查找 return 0; / 顺序表中不存在待查元素 / Search_Bin,31,先看一个具体的情况，假设：n=11,分析折半查找的平均查找长度,6,3,9,1,4,2,5,7,8,10,11,判定树,1,2,2,3,3,3,3,4,4,4,4,32,在n50时，可得近似结果,一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。因此具有n个结点的判定树的深度为 +1。为了方便起见，以满二叉树为例，树中层次为1的结点有1个，层次为2的结点有2个，层次为h的结点有2h1个.,33,在 n50 时，可得近似结果,可见， 折半查找的效率比顺序查找高。 折半查找只能适用于有序表，并且以顺序存储结构存储。,34,顺序表和有序表的比较,35,三、索引顺序表,以索引顺序表表示静态查找表，search操作可用分块查找来实现。 分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在此查找方法中，除表本身以外，尚需建立一个“索引表”。,36,例如,表中含有18个元素，可分成三个子表。对每个子表（或称块）建立一个索引项，其中包括两项内容：关键字项（其值为该子表内的最大关键字）和项指针（指示该子表的第一个元素在表中位置）。,索 引 表,最大关键字,起始地址,37,索引表按关键字有序，故表或者有序，或者分块有序。所谓“分块有序” 是指一个子表中所有元素的关键字均大于前一个子表的最大关键字。,38,索引顺序表的查找过程：,1）由索引确定记录所在区间；,2）在顺序表的某个区间内进行查找。,注意：索引可以根据查找表的特点来构造。,可见， 索引顺序查找的过程也是一个 “缩小区间”的查找过程。,39,1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18,22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53,22 48 86,1 7 13,索引表,查38,例如,40,索引顺序查找的平均查找长度 = 查找“索引”的平均查找长度 + 查找“顺序表”的平均查找长度,41,分块查找方法评价,当 时，ASL取最小值 +1,42,查找方法比较,顺序查找,折半查找,分块查找,43,9.2 动 态 查 找 表,44,动态查找表的特点:表结构本身是在查找过程中动态生成。若表中存在其关键字等于给定值key的记录,表明查找成功；否则插入关键字等于key的记录。,45,ADT DynamicSearchTable ,抽象数据类型动态查找表的定义如下：,数据对象D： 数据关系R：,数据元素同属一个集合。,D是具有相同特性的数据元素的集合。 每个数据元素含有类型相同的关键字， 可唯一标识数据元素。,46,InitDSTable(/按某种次序对DT的每个结点调用函数 Visit() 一次且至多一次。,基本操作：,next,ADT DynamicSearchTable,47,一、二叉排序树（二叉查找树）,二、二叉平衡树,三、B - 树,四、B+树,48,一、二叉排序树 （二叉查找树）,1定义,2查找算法,3插入算法,4删除算法,5查找性能的分析,49,（1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值；,1定义：,二叉排序树或者是一棵空树；或者 是具有如下特性的二叉树：,（3）它的左、右子树也都分别是二叉 排序树。,（2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值；,50,50,30,80,20,90,10,85,40,35,25,23,88,例如:,是二叉排序树,66,不,51,通常，取二叉链表作为 二叉排序树的存储结构,typedef struct BiTNode / 结点结构 struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;,TElemType data;,52,2二叉排序树的查找算法：,1）若给定值等于根结点的关键字，则查找成功； 2）若给定值小于根结点的关键字，则继续在左子树上进行查找； 3）若给定值大于根结点的关键字，则继续在右子树上进行查找。,否则,若二叉排序树为空，则查找不成功；,53,50,30,80,20,90,85,40,35,88,32,例如:,二叉排序树,查找关键字,= 50 ,50,50,35 ,50,30,40,35,50,90 ,50,80,90,95,54,从上述查找过程可见，,在查找过程中，生成了一条查找路径:,从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;,或者,从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。,查找成功,查找不成功,55,BiTree SearchBST( BiTree T, KeyType key) /在根指针T所指二叉排序树中递归地查找某关键字 /等于Key的数据元素，若查找成功，则返回指向 /该数据元素的指针，否则返回空指针 if (!T)| EQ(key, T-data.key) return (T);/查找结束 else if LT(key, T-data.key) return(SearchBST(T-lchild, key) else return (SearchBST(T-rchild, key); /SearchBST,56,二叉排序树是一种动态树表，其特点是，树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字等于给定值的结点时进行插入。 新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。为此将二叉树的查找算法改为如下算法,57,算法描述如下：,Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree / SearchBST, ,否则表明查找不成功，返回 / 指针 p 指向查找路径上访问的最后一个结点， / 并返回函数值为FALSE, 指针 f 指向当前访问 / 的结点的双亲，其初始调用值为NULL,58,30,20,10,40,35,25,23,f,T,设 key = 48,f,T,f,T,22,p,f,T,f,T,T,T,T,f,f,f,p,59,if (!T) else if ( EQ(key, T-data.key) ) else if ( LT(key, T-data.key) ) else, p = f; return FALSE; / 查找不成功, p = T; return TRUE; / 查找成功,SearchBST (T-lchild, key, T, p ); / 在左子树中继续查找,SearchBST (T-rchild, key, T, p ); / 在右子树中继续查找,Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) , / SearchBST,60,根据动态查找表的定义，“插入”操作在查找不成功时才进行;,3二叉排序树的插入算法,若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。,61,对于输入实例（30，20，40，10，25，45），创建二叉排序树的过程如下：,按照（30，20，10，25，40，45）或（30，40，45，20，10，25）的输入次序同样可生成图（g）所示的二叉排序树。,但若按照（10，20，25，30，40，45）或（45，40，30，25，20，10）的次序输入，将分别生成只具有单个右分支和单个左分支的两棵二叉排序树。,62,结论： 二叉排序树的形态与数据的输入次序相关；,63,Status Insert BST(BiTree / Insert BST,64,（1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树； （3）被删除的结点既有左子树，也有右子树。,4二叉排序树的删除算法,可分三种情况讨论：,和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。,65,50,30,80,20,90,85,40,35,88,32,（1）被删除的结点是叶子结点,例如:,被删关键字 = 20,88,其双亲结点中相应指针域的值改为“空”,66,50,30,80,20,90,85,40,35,88,32,（2）被删的结点只有左子树或只有右子树,其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。,被删关键字 = 40,80,67,50,30,80,20,90,85,40,35,88,32,（3）被删除的结点既有左子树，也有右子树,40,40,按中序遍历写出序列， 以被删结点其前驱替代之，然后再删除该前驱结点,被删结点,前驱结点,被删关键字 = 50,68,69,Status DeleteBST (BiTree else / DeleteBST,算法描述如下：(p230), ,70,if ( EQ (key, T-data.key) ) / 找到关键字等于key的数据元素 else if ( LT (key, T-data.key) ) else, Delete (T); return TRUE; ,DeleteBST ( T-lchild, key ); / 继续在左子树中进行查找,DeleteBST ( T-rchild, key ); / 继续在右子树中进行查找,71,void Delete ( BiTree &p ) / 从二叉排序树中删除结点 p， / 并重接它的左子树或右子树 if (!p-rchild) else if (!p-lchild) else / Delete,其中删除操作过程如下所描述：, , , ,72,/ 右子树为空树则只需重接它的左子树,q = p; p = p-lchild; free(q);,p,q,73,/ 左子树为空树只需重接它的右子树,q = p; p = p-rchild; free(q);,p,q,74,q = p; s = p-lchild; while (s-rchild) q = s; s = s-rchild; / s 指向被删结点的前驱,/ 左右子树均不空,p-data = s-data; if (q != p ) q-rchild = s-lchild; else q-lchild = s-lchild; / 重接*q的左子树 free(s);,75,5查找性能的分析,对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。,76,由关键字序列 3，1，2，5，4构造而得的二叉排序树,由关键字序列 1，2，3，4，5构造而得的二叉排序树，,例如：,2,1,3,4,5,3,5,4,1,2,ASL =（1+2+3+4+5）/ 5 = 3,ASL =（1+2+3+2+3）/ 5 = 2.2,因此，在二叉排序树上进行检索的效率与树的形状有密切的联系。,77,在最坏的情况下，含有n个结点的二叉排序树退化成一棵深度为n的单支树（类似于单链表），它的平均查找长度与单链表上的顺序检索相同，即ASL=（n+1）/2。,（a） （b） 图中两棵具有不同检索效率的二叉排序树,78,例如，对于上图中的两棵二叉排序树，其深度分别是4和10，在检索失败的情况下，在这两棵树上的最大比较次数分别是4和10；在检索成功的情况下，若检索每个结点的概率相等，则对于图（a）所示的二叉排序树其平均查找长度为： ASLa= = 对于图（b）所示的二叉排序树其平均查找长度为：ASLb=（1+2+3+4+5+6+7+8+9+10）/10=5.5,79,二、二叉平衡树,何谓“二叉平衡树”？,如何构造“二叉平衡树”,80,是平衡二叉树，不是完全二叉树,不是平衡二叉树,81,二叉平衡树是二叉查找树的另一种形式，其特点为：树中每个结点的左、右子树深度之差（平衡因子BF）的绝对值不大于1,例如:,是平衡树,不是平衡树,平衡二叉树,BF值,0,1,1,0,0,1,2,2,0,失去平衡的最小子树,82,构造二叉平衡（查找）树的方法： 在插入过程中，采用平衡旋转技术。 例如:依次插入的关键字为5, 4, 3, 8, 19,1,2，25，23,5,4,5,4,3,BF值,1,0,1,0,2,（1）由于插入节点3使得树不再平衡，而3是插入在失去平衡的最小子树根节点5的左子树根节点4的左子树上。定义失去平衡的最小子树根节点为a，则该类不平衡可归纳为，在a的左子树根节点的左子树上插入导致的不平衡可使用单向右旋平衡处理，可以记为左左-右。,5,4,3,0,0,0,83,4,3,5,8,4,3,5,8,4,3,5,8,19,0,-1,0,-1,0,0,-1,-2,-2,4,3,5,8,19,0,0,0,0,-1,（2）由于插入节点19使得树不再平衡，而19是插入在失去平衡的最小子树根节点5的右子树根节点8的右子树上。该类不平衡可归纳为，在a的右子树根节点的右子树上插入导致的不平衡可使用单向左旋平衡处理，可以记为右右-左。,84,4,5,8,19,0,0,0,3,2,1,1,-1,2,0,4,5,8,19,0,0,0,3,2,1,2,1,1,0,4,5,8,19,0,0,0,3,0,0,2,0,1,0,先向左旋,再向右旋,（3）在3的左子树根节点1的右子树上插入节点2导致不平衡，可使用双向旋转：先使其子树左旋再整棵树右旋，可记为左右-左右。,85,4,5,8,19,-2,-2,0,3,0,-2,2,0,1,0,25,23,1,0,4,5,8,19,-2,-2,0,3,0,-2,2,0,1,0,23,25,-1,0,先向右旋,4,5,8,23,0,-1,0,3,0,-1,2,0,1,0,25,19,0,0,再向左旋,（4）在19的右子树根节点25的左子树上插入节点23导致不平衡，可使用双向旋转：先使其子树右旋再整棵树左旋，可记为右左-右左。,86,构造二叉平衡（查找）树的方法是： 在插入过程中，采用平衡旋转技术。,例如:依次插入的关键字为5, 4, 2, 8, 6, 9,5,4,2,4,2,5,8,6,6,5,8,4,2,向右旋转 一次,先向右旋转 再向左旋转,87,4,2,6,5,8,9,6,4,2,8,9,5,向左旋转一次,继续插入关键字 9,88,单向右旋转,（1）LL型平衡旋转：由于在A的左孩子的左子树上插入新结点，使A的平衡度由1增至2，致使以A为根的子树失去平衡，如图(a)所示。此时应进行一次顺时针旋转，“提升”B（即A的左孩子）为新子树的根结点，A下降为B的右孩子，同时将B原来的右子树Br调整为A的左子树。,图 (a),旋转后保证中序序列不变,89,（2）RR型平衡旋转：由于在A的右孩子的右子树上插入新结点，使A的平衡度由-1变为-2，致使以A为根的子树失去平衡，如图（b）所示。此时应进行一次逆时针旋转，“提升”B（即A的右孩子）为新子树的根结点，A下降为B的左孩子，同时将B原来的左子树BL调整为A的右子树。,图 (b),旋转后保证中序序列不变,单向左旋转,90,双向旋转，先左后右,（3）LR型平衡旋转：由于在A的左孩子的右子树上插入新结点，使A的平衡度由1变成2，致使以A为根的子树失去平衡，如图（c）所示。此时应进行两次旋转操作（先逆时针，后顺时针），即“提升”C（即A的左孩子的右孩子）为新子树的根结点；A下降为C的右孩子；B变为C的左孩子；C原来的左子树CL调整为B现在的右子树；C原来的右子树Cr调整为A现在的左子树,图(c),91,双向旋转，先右后左,（4）RL型平衡旋转：由于在A的右孩子的左子树上插入新结点，使A的平衡度由-1变成-2，致使以A为根的子树失去平衡，如图（d）所示。此时应进行两旋转操作（先顺时针，后逆时针），即“提升”C（即A的右孩子的左孩子）为新子树的根结点；A下降C的左孩子；B变为C的右孩子；C原来的左子树CL调整为A现在的右子树；C原来的右子树Cr调整为B现在的左子树。,图(d),92,结点序列（120，80，30，90，45，60）逐个插入一棵空的AVL树的过程如下：,93,三、 B - 树,1定义,2查找过程,3插入操作,4删除操作,94,B-树：一种平衡的多路查找树,一棵m阶的B-树或为空树，或为满足下列特性的m叉树： 树中每个节点至多有m棵子树 若根结点不是叶子结点，则至少有两棵子树 除根结点之外的所有非终端结点至少有m/2 棵子树 所有的非终端结点中包含下列信息数据(n,A0,K1,A1,K2,A2,Kn,An) 其中Ki(i=1,n)为关键字，且KiKi+1,(i=1,n-1); Aj（0jn）为指向子树根结点的指针，且Aj（0jn） 所指子树中所有结点的关键字均小kj+1; An所指子树中 所有结点的关键字均大于kn; n（m/2-1nm-1）为关键字的个数；n+1为子树个数。,95,4阶B-树，每个节点最多4棵子树，3个关键 字。一棵m阶B-树每个节点最多有m棵子树m-1 个关键字,最少有m/2棵子树m/2-1个关键 字,96,非叶结点中的多个关键字均自小至大有序排列，即：K1 K2 Kn; 且 Ai-1 所指子树上所有关键字均小于Ki; Ai 所指子树上所有关键字均大于Ki;,97,树中所有叶子结点均不带信息，且在树中的同一层次上;（实际这些结点不存在，指向这些结点的指针为空） 根结点或为叶子结点，或至少含有两棵子树; 其余所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树;,98,2 50 80,root,2 20 40,2 55 70,例：一棵3阶的B-树,99,2.查找过程：,2 50 80,root,2 20 40,2 55 70,100,typedef struct BTNode int keynum; / 结点中关键字个数，结点大小 struct BTNode *parent; / 指向双亲结点的指针 KeyType keym+1; / 关键字（0号单元不用） struct BTNode *ptrm+1; / 子树指针向量 Record *recptrm+1; / 记录指针向量 BTNode, *BTree; / B树结点和B树的类型,B-树结构的C语言描述如下:,101,typedef struct BTNode *pt; / 指向找到的结点的指针 int i; / 1m，在结点中的关键字序号 int tag; / 标志查找成功(=1)或失败(=0) Result; / 在B树的查找结果类型,假设返回的是如下所述结构的记录:,102,Result SearchBTree(BTree T, KeyType K) / 在m 阶的B-树 T 中查找关键字 K, 返回 / 查找结果 (pt, i, tag)。若查找成功，则 / 特征值 tag=1, 指针 pt 所指结点中第 i 个 / 关键字等于 K; 否则特征值 tag=0, 等于 / K 的关键字应插入在指针 pt 所指结点 / 中第 i 个关键字和第 i+1个关键字之间 / SearchBTree, ,103,p=T; q=NULL; found=FALSE; i=0; while (p / 查找不成功,Search (Btree P , KeyType K) for (int i=0; iPkeynum ,104,3插入,1）插入后，该结点的关键字个数nm， 不修改指针; 例如,在查找不成功之后，需进行插入。 显然，关键字插入的位置必定在最下 层的非叶结点，有下列几种情况：,105,2）插入后，该结点的关键字个数 n=m， 则需进行“结点分裂”，令 s = m/2， 在原结点中保留 （A0，K1，。， Ks-1，As-1）； 建新结点 （As，Ks+1，。 ，Kn，An）； 将（Ks，p）插入双亲结点；例如,3）若双亲为空，则建新的根结点。 例如,106,例如:下列为 3 阶B-树,50, 20 40 , 80 ,插入关键字 = 60, 60 80 ,90,608090,90,50 80,60,30, 40 , 20 ,30 50 80,80,30,50,107,和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之，若该结点为最下层的非终端结点，且其中的关键字数目不小于m/2 ，则删除完成，否则要进行“合并”操作.,4删除,108,下面我们只需讨论删除最小层非终端结点中的关键字情形，分3种情况讨论：,109,1）被删关键字所在结点中的关键字数目不小于m/2，则只需要从该结点中删去关键字ki和相应的指针pi，树的其它部分不变。,例：,110,2）被删关键字所在结点中的关键字数目等于m/2-1，而与该结点相邻的右兄弟结点（或左兄弟结点）中的关键字数目大于m/2-1，则需要将其右兄弟的最小关键字（或其左兄弟的最大关键字）移至双亲结点中，而将双亲结点中小于（或大于）该上移关键字的关键字下移至被删关键字所在的结点中。例如从图中删除关键字90，结果如图所示。,111,3）被删关键字所在结点中的关键字数和其相邻的兄弟结点中的关键字数目均等于m/2-1，则第（2）种情况中采用的移动方法将不奏效，此时须将被删关键字所有结点与其左或右兄弟合并。不妨设该结点有右兄弟，但其右兄弟地址由双亲结点指针pi所指，则在删除关键字之后，它所在结点中剩余的关键字和指针加上双亲结点中的关键字ki一起合并到pi所指兄弟结点中（若没有右兄弟，则合并至左兄弟结点中）。,112,如在3阶B-树中依次删除关键字12,50，53，37，分为三种情况,3阶B-树,113,(1)被删关键字(12)所在节点(c)中的关键字数目不小于m/2则只须从该节点(c)中删去该关键字(12)和相应指针，树的其他部分不变。,删除关键字12,114,（2）被删关键字(50)所在节点(f)中的关键字数目等于m/2-1,其相邻的某个兄弟结点(g)（左兄弟或右兄弟）中的关键字数目大于m/2-1，则将其兄弟结点(g)中的最小（或最大）关键字(61)上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字(61)的关键字(53)下移至被删关键字(50)所在节点(f)中。,删除关键字50,115,（3）被删关键字(53)所在节点(f)和其相邻的兄弟结点(g)中的关键字数目均等于m/2-1(1), 假设该节点有右兄弟(g),在删去关键字(53)后，他所在结点(f)中剩余的关键字和指针加上双亲结点(e)中的关键字(61)一起合并到右兄弟结点(g)中。,删除关键字53,116,删除关键字37,如果删除后使双亲结点中的关键字数目小于m/2-1，则依此类推层层向上合并。,117,用依次输入的关键字23、30、51、29、2 7、15、11、17和16建一棵3阶B-树，画出建该树的变化过程示意图（每插入一个结点至少有一张图）。,118,是B-树的一种变型,四、B+树,119,B+树,B+树是B-树的变型，m阶的B+树和m阶的B-树的区别是： 关键字个数和子树个数一样多 所有叶子结点中包含全部关键字信息及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。 所有非终端结点可看成索引，节点中仅含有其子树中的最大（或最小）关键字。,120,121,1B+树的结构特点：, 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；,122, 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值（或最小值）；, 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间。,123,124,2查找过程,在 B+ 树上，既可以进行缩小范围的查 找，也可以进行顺序查找；, 在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束；,若在结点内查找时，给定值Ki， 则 应继续在 Ai 所指子树中进行查找；,125,3插入和删除的操作,类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并”。,126,9.3 哈 希 表,哈希表的相关定义 哈希函数的构造方法 处理冲突的方法 哈希表的查找 哈希表的插入 哈希查找分析,127,散列存储的基本思想是以关键码的值为自变量，通过一定的函数关系（称为散列函数，或称Hash函数），计算出对应的函数值来，以这个值作为结点的存储地址，将结点存入计算得到的存储单元里去。,散列存储,128,U,S,k1,k2,k3,k5,k4,0,H(k1),H(k5),H(k2)=H(k4),H(k3),H(km-1),图9.22 散列过程示例,129,哈希查找 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。 哈希函数 在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。,哈希表的相关定义,130,散列存储中经常会出现对于两个不同关键字xi，xj，却有H（xi）=H（xj），即对于不同的关键字具有相同的存放地址，这种现象称为冲突或碰撞。,综上所述，对于Hash方法，需要研究下面两个主要问题： （1）选择一个计算简单，并且产生冲突的机会尽可能少的Hash函数； （2）确定解决冲突的方法。,131,Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei,例如：对于如下 9 个关键字,设 哈希函数 H(key) = (Ord(第一个字母) -Ord(A)+1)/2,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Dei,问题: 若添加关键字 Zhou , 怎么办？,能否找到另一个哈希函数？,132,1) 哈希函数是一个映象，即： 将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要这个地址集合的 大小不超出允许范围即可;,从这个例子可见，,2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1 key2，而 f(key1) = f(key2)。,133,3) 很难找到一个不产生冲突的哈希函数。 一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。,因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外;还需要找到一种“处理冲突” 的方法。,134,哈希表的定义:,根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。,135,二、构造哈希函数的方法,对数字的关键字可有下列构造方法:,若是非数字关键字，则需先对其进行 数字化处理。,1. 直接定址法,3. 平方取中法,5. 除留余数法,4. 折叠法,6. 随机数法,2. 数字分析法,136,哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b,1. 直接定址法,此法仅适合于： 地址集合的大小 = = 关键字集合的大小,137,2. 数字分析法 构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址;,例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数,分析： 只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机 所以：取任意两位或两位 与另两位的叠加作哈希地址,138,3.平方取中法 构造：取关键字平方后中间几位作哈希地址 4. 折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类 移位叠加：将分割后的几部分低位对齐相加 间界叠加：从一端沿分割界来回折送，然后对齐相加 适于关键字位数很多，且每一位上数字分布大致均匀情况,例 关键字为 ：0442205864，哈希地址位数为4,139,5. 除留余数法,设定哈希函数为: H(key) = key MOD p 其中， pm (表长) 并且 p 应为不大于 m 的素数,140,给定一组关键字为: 12, 39, 18, 24, 33, 21，若取 p=9, 则他们对应的哈希函数值将为: 3, 3, 0, 6, 6, 3,例如：,为什么要对 p 加限制？,可见，若 p 中含质因子 3, 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。,141,6.随机数法,设定哈希函数为: H(key) = Random(key) 其中，Random 为伪随机函数,通常，此方法用于对长度不等的关键字构造哈希函数。,142,实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范