1、1数据结构课程的内容数据结构课程的内容27.1 7.1 基本概念基本概念7.2 7.2 静态查找表静态查找表7.3 7.3 动态查找表动态查找表7.4 7.4 哈希表哈希表39.1 9.1 基本概念基本概念若表中存在特定元素，称查找成功，应输出该记录；若表中存在特定元素，称查找成功，应输出该记录；否则，称查找不成功（也应输出失败标志或失败位置）否则，称查找不成功（也应输出失败标志或失败位置）查找表查找表 查查 找找查找成功查找成功查找不成功查找不成功静态查找静态查找动态查找动态查找关键字关键字主关键字主关键字次关键字次关键字由同一类型的数据元素（或记录）构成的集合。由同一类型的数据元素（或记录
2、）构成的集合。查询查询(Searching)特定元素特定元素是否在表中。是否在表中。只查找，不改变集合内的数据元素。只查找，不改变集合内的数据元素。既查找，又改变（增减）集合内的数据元素。既查找，又改变（增减）集合内的数据元素。记录中某个数据项的值，可用来识别一个记录记录中某个数据项的值，可用来识别一个记录 (预先确定的记录的某种标志预先确定的记录的某种标志)可以可以唯一唯一标识一个记录的关键字标识一个记录的关键字例如例如“学号学号”例如例如“女女”是一种数据结构是一种数据结构识别若干记录的关键字识别若干记录的关键字4（2）对查找表常用的操作有）对查找表常用的操作有哪些？哪些？v查询某个查询某
3、个“特定的特定的”数据元素是否在表中；数据元素是否在表中；v查询某个查询某个“特定的特定的”数据元素的各种属性；数据元素的各种属性；v在查找表中插入一元素；在查找表中插入一元素；v从查找表中删除一元素。从查找表中删除一元素。（3)有哪些查找方法？有哪些查找方法？查找方法取决于表中数据的排列方式查找方法取决于表中数据的排列方式;讨论：讨论：（1）查找的过程是怎样的？）查找的过程是怎样的？给定一个值给定一个值K K，在含有，在含有n n个记录的文件中进行搜索，寻找个记录的文件中进行搜索，寻找一个关键字值等于一个关键字值等于K K的记录，如找到则输出该记录，否则输出的记录，如找到则输出该记录，否则输
4、出查找不成功的信息。查找不成功的信息。例如查字典例如查字典针对静态查找表和动态查找表的查找方法也有所不同针对静态查找表和动态查找表的查找方法也有所不同。“特定的特定的”=关键关键字字5明确：明确：查找的过程就是将给定的查找的过程就是将给定的K K值与文件中各记录的关键字值与文件中各记录的关键字项进行比较的过程。所以用比较次数的平均值来评估算法的优项进行比较的过程。所以用比较次数的平均值来评估算法的优劣。称为劣。称为平均查找长度平均查找长度（ASLASL：average search lengthaverage search length）。）。物理意义：物理意义：假设每一元素被查找的概率相同，
5、则查找每假设每一元素被查找的概率相同，则查找每一元素所需的比较次数之总和再取平均，即为一元素所需的比较次数之总和再取平均，即为ASLASL。显然，显然，ASLASL值越小，时间效率越高。值越小，时间效率越高。（4）如何评估查找方法的优劣？）如何评估查找方法的优劣？6针对静态查找表的查找算法主要有：针对静态查找表的查找算法主要有：9.2 9.2 静态查找表静态查找表静态查找表的抽象数据类型参见教材静态查找表的抽象数据类型参见教材P216。一、一、顺序查找（线性查找）顺序查找（线性查找）二、二、折半查找（二分或对分查找）折半查找（二分或对分查找）三、三、静态树表的查找静态树表的查找四、四、分块查找
6、（索引顺序查找）分块查找（索引顺序查找）7一、顺序查找（一、顺序查找（Linear search，又称线性查找又称线性查找）（1）顺序表的机内存储结构：顺序表的机内存储结构：typedef struct ElemType *elem;/表基址，表基址，0 0号单元留空。表容量为全部元素号单元留空。表容量为全部元素 int length;/表长，即表中数据元素个数表长，即表中数据元素个数SSTable;顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最顺序查找：即用逐一比较的办法顺序查找关键字，这显然是最直接的办法。直接的办法。v 对对顺序结构顺序结构如何线性查找？如何线性查找？见下页之例见
7、下页之例v 对对单链表结构单链表结构如何线性查找？函数虽未给出，但也很容易如何线性查找？函数虽未给出，但也很容易编写；只要知道头指针编写；只要知道头指针headhead就可以就可以“顺藤摸瓜顺藤摸瓜”；v 对对非线性树结构非线性树结构如何顺序查找如何顺序查找?可借助各种遍历操作！可借助各种遍历操作！8二、折半查找（又称二分查找或对分查找）二、折半查找（又称二分查找或对分查找）优点：优点：算法简单，且对顺序结构或链表结构均适用。算法简单，且对顺序结构或链表结构均适用。缺点：缺点：ASL 太长，时间效率太低。太长，时间效率太低。这是一种容易想到的查找方法。这是一种容易想到的查找方法。先给数据排序先
8、给数据排序（例如按升序排好），形成（例如按升序排好），形成有序表有序表，然后再将，然后再将keykey与正中元素相比，若与正中元素相比，若keykey小，则缩小至右半部内查找；再取其中小，则缩小至右半部内查找；再取其中值比较，每次缩小值比较，每次缩小1/21/2的范围，直到查找成功或失败为止。的范围，直到查找成功或失败为止。v 对对顺序表结构顺序表结构实现折半查找算法实现折半查找算法 v 对对单链表结构单链表结构如何折半查找？如何折半查找？无法实现！无法实现！因全部元素的定位只能从头指针因全部元素的定位只能从头指针headhead开始开始v 对对非线性非线性(树树)结构结构如何折半查找？如何折
9、半查找？可借助二叉排序树来查找（属动态查找表形式）。可借助二叉排序树来查找（属动态查找表形式）。如何改进？如何改进？讨论讨论 顺序查找的特点：顺序查找的特点：9 运算步骤运算步骤：(1)low=1,high=11,mid=6(1)low=1,high=11,mid=6，待查范围是，待查范围是 1,111,11；(2)(2)若若 ST.elemmid.keyST.elemmid.key key keykey，说明，说明keykey low,midlow,mid-1-1，则令：则令：high=mid1high=mid1;重算重算 mid mid；(4)(4)若若 ST.elemST.elem mi
10、d.key mid.key=key=key，说明查找成功，元素序号，说明查找成功，元素序号=mid;=mid;结束条件：结束条件：（1 1）查找成功）查找成功 ：ST.elemmid.keyST.elemmid.key=key=key （2 2）查找不成功）查找不成功 ：highlowhighlow （意即区间长度小于（意即区间长度小于0 0）解：解：先设定先设定3个辅助标志个辅助标志:low,high,midlow,high,mid，折半查找举例：折半查找举例：LowLow指向待查元素指向待查元素所在区间的下界所在区间的下界highhigh指向待查元素所指向待查元素所在区间的上界在区间的上界
11、midmid指向待查元素所在指向待查元素所在区间的中间位置区间的中间位置 已知如下已知如下11个元素的个元素的有序表有序表：（05 13 19 21 37 56 64 75 80 88 92）,请查找关键字为请查找关键字为21 和和85的数据元素。的数据元素。显然有：显然有：mid=(low+high)/2 10讨论讨论 若关键字不在表中，怎样得知和停止？若关键字不在表中，怎样得知和停止？典型标志是：当查找范围的上界典型标志是：当查找范围的上界下界时停止查找。下界时停止查找。讨论讨论 二分查找的效率（二分查找的效率（ASLASL）1次比较就查找成功的元素有次比较就查找成功的元素有1个个（20）
12、，即），即中间值；中间值；2次比较就查找成功的元素有次比较就查找成功的元素有2个个（21），即），即1/4处（或处（或3/4）处；）处；3次比较就查找成功的元素有次比较就查找成功的元素有4个个（22），即），即1/8处（或处（或3/8）处）处 4次比较就查找成功的元素有次比较就查找成功的元素有8个个（23），即），即1/16处（或处（或3/16）处）处 则第则第m次比较时查找成功的元素会有次比较时查找成功的元素会有（2m-1）个个；为方便起见，假设表中全部为方便起见，假设表中全部n个元素个元素 2m-1个，个，此时就不讨论第此时就不讨论第m次比较后还有剩余元素的情况了。次比较后还有剩余元素的情
13、况了。全部比较总次数为全部比较总次数为120221322423m2m1 推推导导过过程程11平均每个数据的查找时间还要除以平均每个数据的查找时间还要除以n，所以：，所以：课堂练习课堂练习（多项选择）：（多项选择）：采用链式存贮结构采用链式存贮结构 记录的长度记录的长度128 采用顺序存贮结构采用顺序存贮结构 记录按关键字递增有序记录按关键字递增有序nnnnjnASLmjj2211log1)1(log121使用折半查找算法时，要求被查文件：使用折半查找算法时，要求被查文件：思考：思考：假设在有序线性表假设在有序线性表a20上进行折半查找，则上进行折半查找，则平均查找长度为平均查找长度为 。12查
14、找过程可用查找过程可用二叉树二叉树描述：每个记录用一个结点表示；结点中值为该描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。记录在表中位置，这个描述查找过程的二叉树称为判定树。n个元素的个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。找到有序表中任一记录的过程就是找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相：走了一条从根结点到与该记录相应的结点的路径。应的结点的路径。比较的关键字个数：比较的关键字个数：为该结点在判定树上的层次数。为该结点在判定树上的层次
15、数。查找成功时查找成功时比较的关键字个数最多不超过树的深度比较的关键字个数最多不超过树的深度 d:d=log2 n +1 若所有结点的空指针域设置为一个指向一个方形结点的指针，称方若所有结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为判定树的外部结点；对应的，圆形结点为内部结点。形结点为判定树的外部结点；对应的，圆形结点为内部结点。查找不成功的过程查找不成功的过程 就是走了一条从根结点到外部结点的路径。就是走了一条从根结点到外部结点的路径。折半查找效率分析法：折半查找效率分析法：13三、分块查找（索引顺序查找）三、分块查找（索引顺序查找）这是一种顺序查找的另一种改进方法。这是一种顺
16、序查找的另一种改进方法。先让数据先让数据分块有序分块有序，即分成若干子表，要求每个子表中的关，即分成若干子表，要求每个子表中的关键字都比后一块中键字都比后一块中关键字关键字小（但子表内部未必有序）。小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个然后将各子表中的最大关键字构成一个索引表索引表，表中还要包，表中还要包含每个子表的起始地址（即头指针）。含每个子表的起始地址（即头指针）。索引表索引表最大关键字起始地址22 12 138920 33 42 44 38 24 48 60 58 74 49 86 53第第1 1块块第第2 2块块第第3 3块块224886例：例：22488617
17、13特点：块间有特点：块间有序，块内无序序，块内无序14查找步骤查找步骤分两步进行：分两步进行：对索引表使用折半查找法（因为索引表是有序表）；对索引表使用折半查找法（因为索引表是有序表）；确定了待查关键字所在的子表后，在子表内采用顺序确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；查找法（因为各子表内部是无序表）；查找效率：查找效率：ASL=LASL=Lb b+L+Lw w对索引表查找的对索引表查找的ASL对块内查找的对块内查找的ASL)21(log2)1(log22nASLnssnASLbsbsS为每块内部的记录个数，为每块内部的记录个数，n/s即块的数目即块
18、的数目例如当例如当n=9n=9，s=3s=3时时，ASLASLbsbs=3.53.5,而折半法为而折半法为3.13.1,顺序法为顺序法为5 515特点：特点：一、一、二叉排序树的定义二叉排序树的定义二、二、二叉排序树的插入与删除二叉排序树的插入与删除三、三、二叉排序树的查找分析二叉排序树的查找分析四、平衡二叉树四、平衡二叉树五、五、B-B-树和树和B+B+树树9.2 9.2 动态查找表动态查找表表结构在查找过程中动态生成。表结构在查找过程中动态生成。要求：要求：对于给定值对于给定值key,key,若表中存在其关键字等于若表中存在其关键字等于keykey的记录，则查找成功返回；的记录，则查找成功
19、返回；典型的动态表典型的动态表二叉排序树二叉排序树16一、二叉排序树的定义一、二叉排序树的定义（a）（b）练：练：下列下列2种图形中，哪个不是二叉排序树种图形中，哪个不是二叉排序树？-或是一棵空树；或者是具有如下性质的非空二叉树：或是一棵空树；或者是具有如下性质的非空二叉树：（1 1）左子树的所有结点均小于根的值；）左子树的所有结点均小于根的值；（2 2）右子树的所有结点均大于根的值；）右子树的所有结点均大于根的值；（3 3）它的左右子树也分别为二叉排序树。）它的左右子树也分别为二叉排序树。讨论：讨论：对对(a)(a)中序遍历后的结果是什么？中序遍历后的结果是什么？17二、二叉排序树的插入与删
20、除二、二叉排序树的插入与删除将数据元素构造成二叉排序树的优点：将数据元素构造成二叉排序树的优点：查找过程与顺序结构有序表中的查找过程与顺序结构有序表中的折半查找折半查找相似，查找效率高；相似，查找效率高；中序遍历中序遍历此二叉树，将会得到一个关键字的有序序列（此二叉树，将会得到一个关键字的有序序列（即实现即实现了排序运算了排序运算）；）；如果查找不成功，能够方便地将被查元素如果查找不成功，能够方便地将被查元素插入到二叉树的叶子插入到二叉树的叶子结点结点上，而且插入或删除时只需修改指针而不需移动元素。上，而且插入或删除时只需修改指针而不需移动元素。注：注：若若数据元素的数据元素的输入顺序不同，则
21、得到的二叉排序树形态输入顺序不同，则得到的二叉排序树形态也不同！也不同！这种既查找又插入的过程称为这种既查找又插入的过程称为动态查找动态查找。二叉排序树既有类似于折半查找的特性，又采用了链表存储，二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。它是动态查找表的一种适宜表示。1845452424535312129090如果待如果待查找的关键字序列输入顺序为：查找的关键字序列输入顺序为：（2424，5353，4545，4545，1212，2424，9090），），24245353454512129090查查找找成成功，功，返返回回查查找找成成功，功，返返回回讨论
22、讨论1 1：二叉排序树的插入和查找操作：二叉排序树的插入和查找操作 则生成二叉排序则生成二叉排序树的过程为：树的过程为：例例：输入待查找的关键字序列输入待查找的关键字序列=（4545，2424，5353，4545，1212，2424，9090）则生成的二叉排则生成的二叉排序树形态不同：序树形态不同：查查找找成成功，功，返返回回查查找找成成功，功，返返回回19二叉排序二叉排序 树的静态查找思想树的静态查找思想若二叉排序树为空，则查找 失败，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤，若在查找过程中遇到二叉排序树
23、的叶子结点时，还没有找到待查结点，则查找不成功。20二叉排序树的动态查找算法二叉排序树的动态查找算法查找算法查找算法：若二叉排序树为空，则返回插入位置，否则，先拿根结点值与待查值进行比较，若相等，则查找成功，若根结点值大于待查值，则进入左子树重复此步骤，否则，进入右子树重复此步骤。插入算法插入算法：若二叉排序树为空，则被查结点为新的根节点；否则，作为一个新的叶子结点插入在由查找返回的位置上。21二叉排序树的删除要删除二叉排序树中的p结点，分三种情况：p为叶子结点，只需修改p双亲f的指针f-lchild=NULL 或 f-rchild=NULL p只有左子树或右子树 p只有左子树，用p的左孩子代
24、替p (1)(2)p只有右子树，用p的右孩子代替p (3)(4)p左、右子树均非空 沿p左子树的根C的右子树分支找到S，S的右子树为空 法1：令*p的左子树为*f的左子树，*p的右子树为*s的右子树；法2：令*s代替*p 将S的左子树成为S的双亲Q的右子树，用S取代p (5)若C无右子树，用C取代p (6)22F FC CCLS SSLQLPPRQPRF FC CCLS SSLQLPPRQ法法2:2:F FC CCLS SSLQLPPRQ法法1:1:例：例：请从下面的二叉排序树中删除结点请从下面的二叉排序树中删除结点P。S SSL23SQPLP中序遍历：Q S PL PSQPL中序遍历：Q S
25、 PL(2)SPPLQ中序遍历：PL P S QSPLQ中序遍历：PL S Q(1)63421815634215删除1824中序遍历：P PR S QSPRQ中序遍历：PR S Q(3)SPPRQ中序遍历：Q S P PRSQPR中序遍历：Q S PR(4)SQPRP6342181215删除126342181525FPCPRCLQQLSSL中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：CL C QL Q SL S PR F(5)FPCPRCL中序遍历：CL C P PR FFCPRCL中序遍历：CL C PR F(6)261036241812156342
26、181215删除1027平衡二叉树又称平衡二叉树又称AVL树，它是具有如下性质的树，它是具有如下性质的二叉树：二叉树：为了方便起见，给每个结点附加一个为了方便起见，给每个结点附加一个数字数字，给，给出出该结点左子树与右子树的高度差该结点左子树与右子树的高度差。这个数字。这个数字称为结点的称为结点的平衡因子平衡因子balance。这样，可以得到这样，可以得到AVL树的其它性质：树的其它性质：即即|左子树深度左子树深度-右子树深度右子树深度|1|1左、右子树是平衡二叉树；左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值所有结点的左、右子树深度之差的绝对值 128(a)(a)平衡树平衡树
27、 (b)(b)不平衡树不平衡树例：判断下列二叉树是否例：判断下列二叉树是否AVL树？树？v任一结点的平衡因子只能取：任一结点的平衡因子只能取：-1、0 或或 1；如果；如果树中任意一个结点的平衡因子的绝对值大于树中任意一个结点的平衡因子的绝对值大于1，则这棵二叉树就失去平衡，不再是则这棵二叉树就失去平衡，不再是AVL树；树；v对于一棵有对于一棵有n个结点的个结点的AVL树，其树，其高度保持在高度保持在O(log2n)数量级，数量级，ASL也保持在也保持在O(log2n)量级。量级。0001 11 1-1-10001-129如果在一棵如果在一棵AVL树中插入一个新结点，就有可能树中插入一个新结点
28、，就有可能造成失衡，此时必须造成失衡，此时必须重新调整树的结构重新调整树的结构，使之恢，使之恢复平衡。我们称调整平衡过程为复平衡。我们称调整平衡过程为平衡旋转平衡旋转。现分别介绍这四种平衡旋转。现分别介绍这四种平衡旋转。平衡旋转可以归纳为四类：平衡旋转可以归纳为四类：v LL平衡旋转平衡旋转v RR平衡旋转平衡旋转v LR平衡旋转平衡旋转v RL平衡旋转平衡旋转30若在若在A的的左子树的左子树上插入左子树的左子树上插入结点，使结点，使A的平衡因子从的平衡因子从1增加至增加至2，需要进行一次，需要进行一次顺时针旋转顺时针旋转。(以以B为旋转轴）为旋转轴）若在若在A的的右子树的右子树上插入右子树的
29、右子树上插入结点，使结点，使A的平衡因子从的平衡因子从-1增加增加至至-2，需要进行一次，需要进行一次逆时针旋转逆时针旋转。(以以B为旋转轴）为旋转轴）31若在若在A的的右右子树的子树的左左子树上插入子树上插入结结点，使点，使A的平衡因子从的平衡因子从-1增加至增加至-2，需要需要先进行先进行顺顺时针旋转，再时针旋转，再逆逆时时针旋转针旋转。(以插入的结点以插入的结点C为旋转轴）为旋转轴）若在若在A的的左左子树的子树的右右子树上插入子树上插入结点，使结点，使A的平衡因子从的平衡因子从1增加至增加至2，需要，需要先进行先进行逆逆时针旋转，再时针旋转，再顺顺时针旋转。时针旋转。(以插入的结点以插入
30、的结点C为旋转轴）为旋转轴）这种调整规则可以保证二叉排序树的次序不变这种调整规则可以保证二叉排序树的次序不变320 013130 037370 02424例：例：请将下面序列构成一棵请将下面序列构成一棵平衡二叉排序树平衡二叉排序树：（13，24，37，90，53）0 013130 03737-1-113130 02424-1-124241313需要需要RR平衡旋转平衡旋转(绕绕B逆转逆转,B为根）为根）0 09090-1-12424-1-137370 053531 190903737需要需要RL平衡旋转平衡旋转(绕绕C先顺后逆）先顺后逆）0 037370 090900 053530 03737
31、0 090900 0535333五、五、B-B-树和树和B+B+树树B-树树一、一、B-树的基本概念树的基本概念 1.定义 一棵m阶的B-树,或为空树,或为满足下列特性的m叉树:(l)所有的非终端结点的结构如下:其中,k1,k2,.,kn为n个按从小到大顺序排列的键值;p0,pl,p2,.,pn为(n+1)个指针,用于指向该结点的(n+l)棵子树,p0所指向子树中的所有关键字的值均小于kl,pn所指向子树中的所有关键字的值均大于kn,pi(1in-1)所指向子树中的所有关键字的值均大于ki且小于ki+1;n(nm-1)为键值的个数,即子树个数为(n+l)。(2)树中每个结点至多有m棵子树。(3
32、)除非根结点为叶子结点,否则至少有两棵子树。(4)除根之外的所有非终端结点至少有m/2棵子树。(5)所有叶子结点在同一个层次上,且不含有任何信息。np0k1p1k2p2kipiknpn342.说明(1)对于非根结点的所有分支结点,n的取值范围为 m/2-1nm-1。(2)对于根结点,n的取值范围为1nm1。(3)对于叶子结点,其子树均为空树(即没有子结点),又规定不含有任何信息:所,可以把它看作不在树中的外部结点。(4)B-树的阶m可以事先任意指定,一旦指定后,就固定不变。2-3树的含义图9-13是一棵由10个键值生成的四阶B_树的示意图,该树共有四层,所有叶子点均在第四层上。35150130
33、1 951 251 55270902 35 40atbcdfgeh图9-13 B-树3 75 80 8536二、二、B-树的查找树的查找1.查找方法 由B-树的定义可知,在B-树上进行查找的过程与二叉排序树的查找类似。根据给定的键值k,先在根结点的键值的集合中采用顺序(当m较小时)或二分(当m较大时)查找方法进行查找。若有k=ki,则查找成功,根据相应的指针即可取得记录:否则,若k在ki和ki+1之间,取指针pi所指的结点,重复这个查找过程,直到在某结点中查找成功,或在某结点处出现pi 为空,查找失败.例如，在图9-13所示B_树中查找关键字80和38。372.性能分析在B-树上进行查找需比较
34、的结点数最多为B-树的高度,B-树的高度与B-树的阶m和键值总数N有关,下面就来讨论它们之间的关系。(1)若B-树的高度为h+1,则h+1层(即叶结点所在的层)的结点数为N+1。因为每个非叶结点中的指针数等于其中的键值数加1,因此有:结点总数=指针总数+1=(键值总数N+非叶结点数)+l (h+1)层的结点数=叶结点数=结点总数非叶结点数 =N+1。(2)根据B-树的定义,B-树的第一层(即根结点)的结点数至少为1个,第二层的结点数至少为2,第三层的结点数至少为2*m/2,第四层的结点数至少为2*(m/2)2,以此类推,第h+1层的结点数至少为2*(m/2)h-1。(3)综上所述,可得到如下不
35、等式:h1+logm/2(N+1)/238三、三、B-树的插入树的插入 在B-树中插入一个键值k,不是在树中添加一个叶子结点,而是首先在最低层的某个非终端结点中添加一个键值。且要使插入的结点中的键值字个数m1,将涉及到结点的“分裂问题。1.插入方法 首先要经过一个从树根结点到叶子结点的查找过程,如果键值k已在树中,则不用做其他事;否则,找出插入位置,然后再进行插入。对于叶子结点处于第(h+1)层的树,插入的位置总是在第h层。若结点的关键字值个数不超过(m-l),直接把键值插就行了;否则需要把结点分裂成两个。分裂的做法是,取一新结点,把原结点上的键和k按升序排序后,从中间位置(即m/2之处)把键
36、值(不包括中间位置的键值)成两部分,左部分所含键值放在旧结点中,右部分所含键值放在新结点中,中间位置键值连同新结点的存储位置插入到父亲结点中。如果父结点的键值个数也超过(m-l),要再分裂,再往上插,直至这个过程传到根结点为止。393065 802535 4055 6070 758550(a)插入前的3阶 B_树3025 2835 4065 8055 6070 758550(b)插入28后的 B_树4030 3825 2835 65 8055 6070 75855040(c)插入38后的 B_树30 5065 8055 6070 7585382520283540(d)插入20后的 B_树图9-
37、14 B_树的插入41四、四、B-树的删除树的删除 B-树的删除过程与插入过程类似,只是稍为复杂一些。要使删除后的结点中的键值个数m/2,将涉及到结点的“合并问题。1.删除方法 在深度为(h+l)的m阶B-树中删除一个键值k,首先要查到键值k所在的结点及在结点中的位置。若k所在结点的层数小于h,则把该结点的右边(或左边)指针所指子树中的最小(或最大)键值与k对调,使k移到第h层,这样可根据k所在结点为第h层结点的情况进行删除,从B_树上第h层结点中删除一个键值后,使得该结点的值个数n减1,此时应分以下三种情况进行处理:(1)若删除后结点中键值数目n m/21,在该结点中删去键值k连同右边的指针
38、.(2)若删除后结点中键值数目n m/2 1,且左(或右)兄弟结点的关键字数目 m/21,则把左(或右)兄弟结点中最大(或最小)键值移到父结点中,再把父结点大于(或小于)上移键值的键值下移到被删关键字所在结点中。42(3)若删除后结点中键值数目n m/2 1,及其左、右兄弟结点的键值数目都等于m/21,则就必须进行结点的“合并”,即把应删的键值删去后,将该结点中的剩余键值和指针连同父结点中指向该结点指针的左边(或右边)一个键值ki一起合并到左兄弟(或右兄弟)结点中,将ki从父结点中删去。如果因此使父结点中关键字数目 m/21,则对此父结点做同样处理,以致于可能直到对根结点做这样的处理而使整个树
39、减少一层。3065 802535 4055 6070 758550433065 8025 4055 6070 758550(a)由图9-14(a)删除35后的3阶B_树3065 7525 4055 6070 8050(b)删除85后的B_树443065 25 4055 6070 7550(c)删除80后的B_树50 65 70 7530 4055 60(d)删除25后的B_树图9-15 B_树的删除459.4.2 B+树树一、一、B+树定义树定义 1.定义 一棵m阶的B+树满足下列条件:(1)每个分支结点至多有m棵子树。(2)除根结点外,其他每个分支结点至少有(m+1)/2棵子树。(3)根结点
40、至少有两棵子树,至多有m棵子树。(4)有n棵子树的结点有n个键值。(5)所有叶结点包含全部(数据文件中记录)键值及指向相应记录的指针(或存放据文件分块后每块的最大键值及指向该块的指针),而且叶结点按键值大小顺序链接(可以把每个叶结点看成是一个基本索引块,它的指针不再指向另一级索引块,而是直指向数据文件中的记录)。(6)所有分支结点(可看成是索引的索引)中仅包含它的各个子结点(即下级索引索引块)中最大键值及指向子结点的指针.46对于m阶的B+树和m阶的B-树,定义中的前三点是相同的,主要的差异是:(1)在B+树中,具有n个关键字的结点则含有n棵子树,即每个关键字对应一棵子树,而在B-树中,具有n
41、个键值的结点含有(n+1)棵子树;(2)在B+树中,每个结点(除树根结点外)中的键值个数n的取值范围是m/2nm,根结点n的取值范围是1nm;而在B_树中,它们的取值范围分别是m/21nml和lnm1。(3)B+树中的所有叶子结点包含了全部键值,即其他非叶结点中的键值包含在叶结点中,而在B-树中,叶结点包含的键值与其他结点包含的键值是不重复的。(4)B+树中所有非叶结点仅起到索引的作用,即结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针,不含有该键值对应记录的存储地址。而在B-树中,每个键值对应一个记录的存储地址。(5)通常在B+树上有两个头指针,一个指向根结点,另一个指向键值最
42、小的叶子结点,所有叶结点链接成一个不定长的线性链表。4740 6535 4060 6555 6540 45 5520 25 3015 30 4010 15roothead图图9-16 B+树树48二、二、B+树查找树查找 在B+树中可以采用两种查找方式,一种是直接从最小键值开始进行顺序查找,另一种就是从B+树的根结点开始进行随机查找。这种查找方式与B-树的查找方法相似,只是在分支结点上的键值与查找值相等时,查找并不结束,要继续查到叶结点为止,此时若查找成功,则按所给指针取出对应记录即可。因此,在B+树中,不管查找成功与否,每次查找都是经过了一条从树根结点到叶子结点的路径。三、三、B+树插入树插
43、入 与B-树的插入操作相似,B+树的插入也从叶子结点开始,当插入后结点中的键值个数大于m时要分裂成两个结点,它们所含键值个数分别为(m+1)/2和(m+1)/2,同时要使得它们的双亲结点中包含有这两个结点的最大键值和指向它们的指针。若双亲结点的键值数目因此而大于m,应继续分裂,依此类推。49四、四、B+树删除树删除 B+树的删除也是从叶子结点开始,当叶结点中最大键值被删除时,分支结点中的值可以作为“分界键值”存在。若因删除操作而使结点中键值个数少于m/2时,则从兄弟结点中调剂键值或和兄弟结点合并,其过程和B-树相似。5051 前面介绍的所有查找都是基于待查前面介绍的所有查找都是基于待查关键字与
44、表中元素进行比较而实现的查关键字与表中元素进行比较而实现的查找方法，查找的效率依赖于查找过程中找方法，查找的效率依赖于查找过程中所进行的比较次数。理想的情况是希望所进行的比较次数。理想的情况是希望不经过任何比较，一次便能得到所查记不经过任何比较，一次便能得到所查记录。录。哈希表哈希表它既是一种查找方法，又它既是一种查找方法，又是一种存贮方法是一种存贮方法52哈希表：哈希表：即散列存储结构。即散列存储结构。散列法存储的基本思想：散列法存储的基本思想：建立关键码字与其存储位置的建立关键码字与其存储位置的对应对应关系，关系，或者说，由关键码的值决定数据的存储地址。或者说，由关键码的值决定数据的存储地
45、址。优点：优点：查找速度极快（查找速度极快（O(1)O(1)）,查找效率与元素个数查找效率与元素个数n n无关！无关！例例1 1：若将学生信息按如下方式存入计算机，如：若将学生信息按如下方式存入计算机，如：将将20010118102200101181020101的所有信息存入的所有信息存入VV0101 单元；单元；将将20010118102200101181020202的所有信息存入的所有信息存入VV0202 单元；单元；将将20010118102200101181023131的所有信息存入的所有信息存入V31V31单元。单元。欲查找学号为欲查找学号为200101181022001011810
46、21616的信息，便可直接访问的信息，便可直接访问V16V16！53例例2：有数据元素序列有数据元素序列(14(14，2323，3939，9 9，2525，11)11)，若规定，若规定每个元素每个元素k k的存储地址的存储地址H H（k k）k k，请画出存储结构图。，请画出存储结构图。（注：（注：H H（k k）k k称为散列函数）称为散列函数）解：解：根据散列函数根据散列函数H H（k k）k k，可知元素，可知元素1414应当存入地址为应当存入地址为1414的单元，元素的单元，元素2323应当存入地址为应当存入地址为2323的单元，的单元，对应散列存储表（哈希表）如下：对应散列存储表（哈
47、希表）如下：讨论：如何进行散列查找？讨论：如何进行散列查找？根据存储时用到的散列函数根据存储时用到的散列函数H(k)H(k)表达式表达式，迅即可查到结果！，迅即可查到结果！例如，查找例如，查找key=9,key=9,则访问则访问H(9)=9H(9)=9号地址，若内容为号地址，若内容为9 9则成功；则成功；若查不到，应当设法返回一个特殊值，例如空指针或空记录。若查不到，应当设法返回一个特殊值，例如空指针或空记录。地址地址 9 11 14 23 24 25 39 内容内容1411923253954选取某个函数，依该函数按关键字计算元素的存储位置，选取某个函数，依该函数按关键字计算元素的存储位置，并
48、按此存放；并按此存放；查找时，由同一个函数查找时，由同一个函数对给定值对给定值k k计算地址，计算地址，将将k k与地址单元中元素关键码进行比较，确定查找是否成与地址单元中元素关键码进行比较，确定查找是否成功。功。通常关键码的集合比哈希地址集合大得多，因而经通常关键码的集合比哈希地址集合大得多，因而经过哈希函数变换后，过哈希函数变换后，可能将不同的关键码映射到同可能将不同的关键码映射到同一个哈希地址上一个哈希地址上，这种现象称为，这种现象称为冲突冲突。若干术语若干术语哈希方法哈希方法(杂凑法杂凑法)哈希函数哈希函数(杂凑函数杂凑函数)哈希表哈希表(杂凑表杂凑表)冲冲 突突哈希方法中使用的转换函
49、数称为哈希方法中使用的转换函数称为哈希函数哈希函数(杂杂凑函数凑函数)按上述思想构造的表称为按上述思想构造的表称为哈希表哈希表(杂凑表杂凑表)55有有6个元素的关键码分别为：（个元素的关键码分别为：（14，23，39，9，25，11）。）。选取关键码与元素位置间的函数为选取关键码与元素位置间的函数为H(k)=k mod 7通过哈希函数对通过哈希函数对6 6个元素建立哈希表：个元素建立哈希表：2539239146个元素用个元素用7个个地址应该足够地址应该足够!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4 0 1 2 3 4 5 656（a a）所选函数尽可能）所选
50、函数尽可能简单简单，以便提高转换速度；，以便提高转换速度；（b b）所选函数对关键码计算出的地址，应在哈希地址集中）所选函数对关键码计算出的地址，应在哈希地址集中大致大致均匀均匀分布，以减少空间浪费。分布，以减少空间浪费。查找时，如果从哈希函数计算出的地址中查不到关键码，则查找时，如果从哈希函数计算出的地址中查不到关键码，则应当依据解决冲突的规则，有规律地查询其它相关单元。应当依据解决冲突的规则，有规律地查询其它相关单元。57二、要求一：要求一：n n个数据原仅占用个数据原仅占用n n个地址，个地址，虽然散列查找是以空间换时间，但仍虽然散列查找是以空间换时间，但仍希望散列的地址空间尽量小。希望
