数据结构-查表找课件

1、第九章 查找表1何谓查找表 ？ 查找表是由同一类型的数据元素(或记录)构成的集合。 由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。2对查找表经常进行的操作:查询某个“特定的”数据元素是否在查找表中；检索某个“特定的”数据元素的各种属性；在查找表中插入一个数据元素；从查找表中删去某个数据元素。3仅作 前两种即查询和检索操作的查找表。即检索的前后不会改变查找表的内容。静态查找表在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素,此类表为动态查找表。即检索过程中可能会改变数据元素的存储位置。动态查找表查找表可分为两类:4 检索是确定数

2、据元素集合中是否存在数据元素等于特定元素或是否存在元素满足某种给定特征的过程。 要进行检索，必须知道待检索对象的特征，也就是要知道待检索数据元素的关键字。 我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。5是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。关键字 若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。 若此关键字能识别若干记录，则称之谓“次关键字”。6 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录） 查找 若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，

3、或指示该记录在查找表中的位置； 否则称“查找不成功”，查找结果：给出“空记录”或“空指针”。79.1 静 态 查 找 表10数据对象D：数据关系R：D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。 数据元素同属一个集合。ADT StaticSearchTable /P21611 Create(&ST, n);Destroy(&ST);Search(ST, key);Traverse(ST, Visit();基本操作 P：next ADT StaticSearchTable12按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()

4、失败，则操作失败。Traverse(ST, Visit();初始条件：操作结果：静态查找表ST存在，Visit是对元素操作的应用函数；16typedef struct / 数据元素存储空间基址，建表时 / 按实际长度分配，0号单元留空 int length; / 表的长度 SSTable;假设静态查找表的顺序存储结构为ElemType *elem;17数据元素类型的定义为:typedef struct keyType key; / 关键字域 / 其它属性域 ElemType ; , TElemType ;18一、顺序查找表二、有序查找表三、索引顺序表19i0 1 2 3 4 5 6 7 8 9

5、 10 11 5 13 19 21 37 56 64 75 80 88 92找6464监视哨iiii比较次数=5比较次数：查找第n个元素： 1查找第n-1个元素：2.查找第1个元素： n查找第i个元素： n+1-i查找失败： n+1查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。例如：21ST.elemiST.elemi60ikey=64key=60i6422int Search_Seq(SSTable ST, KeyType key) / 在顺序表ST中顺序查找其关键字等于 / key的数据元素。若找到，则函数值为 / 该元素在表中的位置，否则为0。 ST.elem0.key =

6、 key; / “哨兵” for (i=ST.length; ST.elemi.key!=key; -i); / 从后往前找 return i; / 找不到时，i为0 / Search_Seq23 定义： 查找算法的平均查找长度 (Average Search Length) 也就是为确定某一结点在数据集合中的位置，给定值与集合中的结点关键字所需进行的比较次数。其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 Ci为找到该记录时，曾和给定值 比较过的关键字的个数分析顺序查找的时间性能。24在等概率查找的情况下， 顺序表查找的平均查找长度为：对顺序表而言，Ci = n-i+1ASL =

7、 nP1 +(n-1)P2 + +2Pn-1+Pn25 若查找概率无法事先测定，则查找过程采取的改进办法是，可以在记录中附设一个访问频度域，使查找概率大的记录在查找过程中不断后移，以便在以后的查找过程中减少比较次数在不等概率查找的情况下，ASLss 在 PnPn-1P2P1时取极小值ASL = nP1 +(n-1)P2 + +2Pn-1+Pn26 上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。二、有序查找表 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。271.设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给

8、定值。2.初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k=rmid.key，查找成功若krmid.key，则low=mid+13.重复上述操作，直至lowhigh时，查找失败。折半查找算法实现28ST.elemST.length例如: key=64 的查找过程如下lowhighmidlow mid high midlow 指示查找区间的下界;high 指示查找区间的上界;mid = (low+high)/2。29int Search_Bin ( SSTable ST, KeyType key ) low = 1; high = ST.leng

9、th; / 置区间初值 while (low 50时，可得近似结果 一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。因此具有n个结点的判定树的深度为 +1。为了方便起见，以满二叉树为例，树中层次为1的结点有1个，层次为2的结点有2个，层次为h的结点有2h1个.32在 n50 时，可得近似结果 可见，折半查找的效率比顺序查找高。折半查找只能适用于有序表，并且以顺序存储结构存储。33顺序表和有序表的比较34三、索引顺序表以索引顺序表表示静态查找表，search操作可用分块查找来实现。分块查找又称索引顺序查找，这是顺序查找的一种改进方法。在此查找方法中，除表

10、本身以外，尚需建立一个“索引表”。35例如 表中含有18个元素，可分成三个子表。对每个子表（或称块）建立一个索引项，其中包括两项内容：关键字项（其值为该子表内的最大关键字）和项指针（指示该子表的第一个元素在表中位置）。 索 引 表最大关键字起始地址36 索引表按关键字有序，故表或者有序，或者分块有序。所谓“分块有序” 是指一个子表中所有元素的关键字均大于前一个子表的最大关键字。 37索引顺序表的查找过程：1）由索引确定记录所在区间；2）在顺序表的某个区间内进行查找。注意：索引可以根据查找表的特点来构造。可见， 索引顺序查找的过程也是一个“缩小区间”的查找过程。381 2 3 4 5 6 7 8

11、 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38例如39索引顺序查找的平均查找长度 = 查找“索引”的平均查找长度 + 查找“顺序表”的平均查找长度40分块查找方法评价当 时，ASL取最小值 +1 41查找方法比较ASL最大最小两者之间表结构有序表、无序表有序表分块有序表存储结构顺序存储结构或线性链表顺序存储结构顺序存储结构或线性链表顺序查找折半查找 分块查找429.2 动 态 查 找 表43动态查找表的特点:表结构本身是在查找过程中动态生成。

12、若表中存在其关键字等于给定值key的记录,表明查找成功；否则插入关键字等于key的记录。44ADT DynamicSearchTable 抽象数据类型动态查找表的定义如下：数据对象D：数据关系R： 数据元素同属一个集合。D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字， 可唯一标识数据元素。45InitDSTable(&DT)/构造一个空的动态查找表DT。DestroyDSTable(&DT)/销毁动态查找表DT。SearchDSTable(DT, key);/查找 DT 中与关键字key等值的元素。InsertDSTable(&DT, e);/若 DT 中不存在其关键字等于

13、 e.key 的 数据元素，则插入 e 到 DT。DeleteDSTable(&T, key);/删除DT中关键字等于key的数据元素。TraverseDSTable(DT, Visit();/按某种次序对DT的每个结点调用函数 Visit() 一次且至多一次。基本操作：nextADT DynamicSearchTable46一、二叉排序树（二叉查找树）二、二叉平衡树三、B - 树四、B+树47一、二叉排序树（二叉查找树）1定义2查找算法3插入算法4删除算法5查找性能的分析48（1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值；1定义： 二叉排序树或者是一棵空树；或者是具有如下特

14、性的二叉树：（3）它的左、右子树也都分别是二叉 排序树。（2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值；49503080209010854035252388例如:是二叉排序树66不50 通常，取二叉链表作为二叉排序树的存储结构typedef struct BiTNode / 结点结构 struct BiTNode *lchild, *rchild; / 左右孩子指针 BiTNode, *BiTree;TElemType data;512二叉排序树的查找算法：1）若给定值等于根结点的关键字，则查找成功；2）若给定值小于根结点的关键字，则继续在左子树上进行查找；3）若给定值大于根

15、结点的关键字，则继续在右子树上进行查找。否则若二叉排序树为空，则查找不成功；5250308020908540358832例如:二叉排序树查找关键字= 50 ,505035 ,503040355090 ,50809095 53从上述查找过程可见，在查找过程中，生成了一条查找路径: 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;或者 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。 查找成功 查找不成功54BiTree SearchBST( BiTree T, KeyType key) /在根指针T所指二叉排序树中递归地查找某关键字 /等于Key的数据元素，若查

16、找成功，则返回指向 /该数据元素的指针，否则返回空指针 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); /SearchBST55二叉排序树是一种动态树表，其特点是，树的结构通常不是一次生成的，而是在查找的过程中，当树中不存在关键字等于给定值的结点时进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩

17、子结点。为此将二叉树的查找算法改为如下算法56算法描述如下：Status SearchBST (BiTree T, KeyType key, BiTree f, BiTree &p ) / 在根指针 T 所指二叉排序树中递归地查找其 / 关键字等于 key 的数据元素，若查找成功， / 则返回指针 p 指向该数据元素的结点，并返回 / 函数值为 TRUE; / SearchBST 否则表明查找不成功，返回 / 指针 p 指向查找路径上访问的最后一个结点， / 并返回函数值为FALSE, 指针 f 指向当前访问 / 的结点的双亲，其初始调用值为NULL5730201040352523fT设 ke

18、y = 48fTfT22pfTfTTTTfffp58if (!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, Bi

19、Tree &p ) / SearchBST59根据动态查找表的定义，“插入”操作在查找不成功时才进行;3二叉排序树的插入算法若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。60对于输入实例（30，20，40，10，25，45），创建二叉排序树的过程如下：（a）空树30（b）插入303020（c）插入20302040（d）插入4030204010（e）插入10 3020401025（f）插入25 302040102545（g）插入45 按照（30，20，10，25，40，45）或（30，40，45，20，10，25）的输入次序同样

20、可生成图（g）所示的二叉排序树。 但若按照（10，20，25，30，40，45）或（45，40，30，25，20，10）的次序输入，将分别生成只具有单个右分支和单个左分支的两棵二叉排序树。 61结论：二叉排序树的形态与数据的输入次序相关；62Status Insert BST(BiTree &T, ElemType e ) if (!SearchBST ( T, e.key, NULL, p ) s = (BiTree) malloc (sizeof (BiTNode); / 为新结点 分配空间s-data = e; s-lchild = s-rchild = NULL; if ( !p )

21、T = s; / 插入 s 为新的根结点else if ( LT(e.key, p-data.key) ) p-lchild = s; / 插入 *s 为 *p 的左孩子else p-rchild = s; / 插入 *s 为 *p 的右孩子return TRUE; / 插入成功 else return FALSE; / Insert BST63（1）被删除的结点是叶子；（2）被删除的结点只有左子树或者只有右子树；（3）被删除的结点既有左子树，也有右子树。4二叉排序树的删除算法可分三种情况讨论： 和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特

22、性。6450308020908540358832（1）被删除的结点是叶子结点例如:被删关键字 = 2088其双亲结点中相应指针域的值改为“空”6550308020908540358832（2）被删的结点只有左子树或只有右子树 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。被删关键字 = 40806650308020908540358832（3）被删除的结点既有左子树，也有右子树4040按中序遍历写出序列， 以被删结点其前驱替代之，然后再删除该前驱结点被删结点前驱结点被删关键字 = 506768Status DeleteBST (BiTree &T, KeyType key

23、 ) / 若二叉排序树 T 中存在其关键字等于 key 的 / 数据元素，则删除该数据元素结点，并返回 / 函数值 TRUE，否则返回函数值 FALSE if (!T) return FALSE; else / DeleteBST算法描述如下：(p230) 69if ( EQ (key, T-data.key) ) / 找到关键字等于key的数据元素else if ( LT (key, T-data.key) ) else Delete (T); return TRUE; DeleteBST ( T-lchild, key ); / 继续在左子树中进行查找DeleteBST ( T-rchil

24、d, key ); / 继续在右子树中进行查找70void Delete ( BiTree &p ) / 从二叉排序树中删除结点 p， / 并重接它的左子树或右子树 if (!p-rchild) else if (!p-lchild) else / Delete其中删除操作过程如下所描述： 71 / 右子树为空树则只需重接它的左子树q = p; p = p-lchild; free(q); pq72/ 左子树为空树只需重接它的右子树q = p; p = p-rchild; free(q);pq73q = p; s = p-lchild;while (s-rchild) q = s; s = s

25、-rchild; / s 指向被删结点的前驱/ 左右子树均不空p-data = s-data;if (q != p ) q-rchild = s-lchild; else q-lchild = s-lchild; / 重接*q的左子树free(s);745查找性能的分析 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。75由关键字序列 3，1，2，5，4构造而得的二叉排序树由关键字序列 1，2，3，4，5构造而得的二叉排序树，例如：2134535412ASL

26、 =（1+2+3+4+5）/ 5 = 3ASL =（1+2+3+2+3）/ 5 = 2.2 因此，在二叉排序树上进行检索的效率与树的形状有密切的联系。 76 在最坏的情况下，含有n个结点的二叉排序树退化成一棵深度为n的单支树（类似于单链表），它的平均查找长度与单链表上的顺序检索相同，即ASL=（n+1）/2。30404650556065707580（a） （b）图中两棵具有不同检索效率的二叉排序树 6040703050658046557577 例如，对于上图中的两棵二叉排序树，其深度分别是4和10，在检索失败的情况下，在这两棵树上的最大比较次数分别是4和10；在检索成功的情况下，若检索每个结点

27、的概率相等，则对于图（a）所示的二叉排序树其平均查找长度为：ASLa= =对于图（b）所示的二叉排序树其平均查找长度为：ASLb=（1+2+3+4+5+6+7+8+9+10）/10=5.578二、二叉平衡树何谓“二叉平衡树”？如何构造“二叉平衡树”79是平衡二叉树，不是完全二叉树不是平衡二叉树80 二叉平衡树是二叉查找树的另一种形式，其特点为：树中每个结点的左、右子树深度之差（平衡因子BF）的绝对值不大于1 例如:548254821是平衡树不是平衡树平衡二叉树BF值011001220失去平衡的最小子树81 构造二叉平衡（查找）树的方法：在插入过程中，采用平衡旋转技术。例如:依次插入的关键字为5

28、, 4, 3, 8, 19,1,2，25，2354543BF值10102（1）由于插入节点3使得树不再平衡，而3是插入在失去平衡的最小子树根节点5的左子树根节点4的左子树上。定义失去平衡的最小子树根节点为a，则该类不平衡可归纳为，在a的左子树根节点的左子树上插入导致的不平衡可使用单向右旋平衡处理，可以记为左左-右。54300082435843584358190-10-100-1-2-24358190000-1（2）由于插入节点19使得树不再平衡，而19是插入在失去平衡的最小子树根节点5的右子树根节点8的右子树上。该类不平衡可归纳为，在a的右子树根节点的右子树上插入导致的不平衡可使用单向左旋平衡

29、处理，可以记为右右-左。83458190003211-120458190003212110458190003002010先向左旋再向右旋（3）在3的左子树根节点1的右子树上插入节点2导致不平衡，可使用双向旋转：先使其子树左旋再整棵树右旋，可记为左右-左右。8445819-2-2030-2201025231045819-2-2030-220102325-10先向右旋458230-1030-12010251900再向左旋（4）在19的右子树根节点25的左子树上插入节点23导致不平衡，可使用双向旋转：先使其子树右旋再整棵树左旋，可记为右左-右左。85 构造二叉平衡（查找）树的方法是：在插入过程中，采

30、用平衡旋转技术。例如:依次插入的关键字为5, 4, 2, 8, 6, 95424258665842向右旋转一次先向右旋转再向左旋转86426589642895向左旋转一次继续插入关键字 987单向右旋转（1）LL型平衡旋转：由于在A的左孩子的左子树上插入新结点，使A的平衡度由1增至2，致使以A为根的子树失去平衡，如图(a)所示。此时应进行一次顺时针旋转，“提升”B（即A的左孩子）为新子树的根结点，A下降为B的右孩子，同时将B原来的右子树Br调整为A的左子树。A2B1BLBrArhhhLL型A0B0BLBrArhhh图 (a)旋转后保证中序序列不变88（2）RR型平衡旋转：由于在A的右孩子的右子

31、树上插入新结点，使A的平衡度由-1变为-2，致使以A为根的子树失去平衡，如图（b）所示。此时应进行一次逆时针旋转，“提升”B（即A的右孩子）为新子树的根结点，A下降为B的左孩子，同时将B原来的左子树BL调整为A的右子树。图 (b)A-2B-1BrBLALhhhRR型A0B0BrALBLhhh旋转后保证中序序列不变单向左旋转89双向旋转，先左后右（3）LR型平衡旋转：由于在A的左孩子的右子树上插入新结点，使A的平衡度由1变成2，致使以A为根的子树失去平衡，如图（c）所示。此时应进行两次旋转操作（先逆时针，后顺时针），即“提升”C（即A的左孩子的右孩子）为新子树的根结点；A下降为C的右孩子；B变为

32、C的左孩子；C原来的左子树CL调整为B现在的右子树；C原来的右子树Cr调整为A现在的左子树A2B-1ArhBLhLR型CCLh-1Crh-11A-1B0ArhBLhCLh-1Crh-1C0图(c)90双向旋转，先右后左（4）RL型平衡旋转：由于在A的右孩子的左子树上插入新结点，使A的平衡度由-1变成-2，致使以A为根的子树失去平衡，如图（d）所示。此时应进行两旋转操作（先顺时针，后逆时针），即“提升”C（即A的右孩子的左孩子）为新子树的根结点；A下降C的左孩子；B变为C的右孩子；C原来的左子树CL调整为A现在的右子树；C原来的右子树Cr调整为B现在的左子树。 B-1A0BrhALhCLh-1C

33、rh-1C0A-2B1BrhALhRL型CLh-1Crh-1C1图(d)91结点序列（120，80，30，90，45，60）逐个插入一棵空的AVL树的过程如下：1200120180012028013001200800300120180-1300900120180030-1900450120180030-290045-1600120180030090045060092三、 B - 树1定义2查找过程3插入操作4删除操作93B-树：一种平衡的多路查找树,一棵m阶的B-树或为空树，或为满足下列特性的m叉树：树中每个节点至多有m棵子树若根结点不是叶子结点，则至少有两棵子树除根结点之外的所有非终端结点至

34、少有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为子树个数。941351182437811112713934753641994阶B-树，每个节点最多4棵子树，3个关键字。一棵m阶B-树每个节点最多有m棵子树m-1个关键字,最少有m/2棵子树m/2-1个关键字95非叶结点中的多个关键字均

35、自小至大有序排列，即：K1 K2 key1.keynum中查找 i ，i使 得：p-Keyi=kkeyi+1 if (i0 & p-keyi=K) found=TRUE; else q=p; p=p-ptri; / q 指示 p 的双亲，在子树中查找 if (found) return (p,i,1); / 查找成功 else return (q,i,0); / 查找不成功 Search (Btree P , KeyType K) for (int i=0; iPkeynum &P keyi+1=k; i+); return i;1033插入1）插入后，该结点的关键字个数nm， 不修改指针;

36、例如在查找不成功之后，需进行插入。显然，关键字插入的位置必定在最下层的非叶结点，有下列几种情况：1042）插入后，该结点的关键字个数 n=m， 则需进行“结点分裂”，令 s = m/2， 在原结点中保留 （A0，K1，。， Ks-1，As-1）； 建新结点 （As，Ks+1，。 ，Kn，An）； 将（Ks，p）插入双亲结点；例如3）若双亲为空，则建新的根结点。 例如105例如:下列为 3 阶B-树50 20 40 80 插入关键字 = 60, 60 80 90,60809090 50 806030, 40 20 30 50 808030 50106 和插入的考虑相反，首先必须找到待删关键字所在

37、结点，并且要求删除之，若该结点为最下层的非终端结点，且其中的关键字数目不小于m/2 ，则删除完成，否则要进行“合并”操作.4删除10745abt24b53 90e3 12c37d50f61 70g100h下面我们只需讨论删除最小层非终端结点中的关键字情形，分3种情况讨论：1081）被删关键字所在结点中的关键字数目不小于m/2，则只需要从该结点中删去关键字ki和相应的指针pi，树的其它部分不变。 例：9084028150 20085 120508090 11584028150 20085 1205060 80删除60与1151092）被删关键字所在结点中的关键字数目等于m/2-1，而与该结点相邻

38、的右兄弟结点（或左兄弟结点）中的关键字数目大于m/2-1，则需要将其右兄弟的最小关键字（或其左兄弟的最大关键字）移至双亲结点中，而将双亲结点中小于（或大于）该上移关键字的关键字下移至被删关键字所在的结点中。例如从图中删除关键字90，结果如图所示。1208402820085 15050809084028150 20085 1205080删除901103）被删关键字所在结点中的关键字数和其相邻的兄弟结点中的关键字数目均等于m/2-1，则第（2）种情况中采用的移动方法将不奏效，此时须将被删关键字所有结点与其左或右兄弟合并。不妨设该结点有右兄弟，但其右兄弟地址由双亲结点指针pi所指，则在删除关键字之后

39、，它所在结点中剩余的关键字和指针加上双亲结点中的关键字ki一起合并到pi所指兄弟结点中（若没有右兄弟，则合并至左兄弟结点中）。 1208402820085 1505080删除12084028150 200855080111如在3阶B-树中依次删除关键字12,50，53，37，分为三种情况45abt24b53 90e3 12c37d50f61 70g100h3阶B-树11245abt24b53 90e3 c37d50f61 70g100h(1)被删关键字(12)所在节点(c)中的关键字数目不小于m/2则只须从该节点(c)中删去该关键字(12)和相应指针，树的其他部分不变。删除关键字1211345

40、abt24b53 90e3c37d50f61 70g100h（2）被删关键字(50)所在节点(f)中的关键字数目等于m/2-1,其相邻的某个兄弟结点(g)（左兄弟或右兄弟）中的关键字数目大于m/2-1，则将其兄弟结点(g)中的最小（或最大）关键字(61)上移至双亲结点中，而将双亲结点中小于（或大于）且紧靠该上移关键字(61)的关键字(53)下移至被删关键字(50)所在节点(f)中。45abt24b61 90e3c37d53f70g100h删除关键字50114（3）被删关键字(53)所在节点(f)和其相邻的兄弟结点(g)中的关键字数目均等于m/2-1(1), 假设该节点有右兄弟(g),在删去关键

41、字(53)后，他所在结点(f)中剩余的关键字和指针加上双亲结点(e)中的关键字(61)一起合并到右兄弟结点(g)中。45abt24b90e3c37d61 70g100h45abt24b61 90e3c37d53f70g100h删除关键字53115删除关键字37bt45 90e3 24c61 70g100h45abt24b90e3c37d61 70g100h45abtb90e3 24c61 70g100h如果删除后使双亲结点中的关键字数目小于m/2-1，则依此类推层层向上合并。116用依次输入的关键字23、30、51、29、2 7、15、11、17和16建一棵3阶B-树，画出建该树的变化过程示意

42、图（每插入一个结点至少有一张图）。117是B-树的一种变型四、B+树118B+树B+树是B-树的变型，m阶的B+树和m阶的B-树的区别是：关键字个数和子树个数一样多所有叶子结点中包含全部关键字信息及指向含这些关键字记录的指针，且叶子节点本身依关键字的大小自小而大顺序链接。所有非终端结点可看成索引，节点中仅含有其子树中的最大（或最小）关键字。11959 97aroot15 44 59b72 97e10 15c21 37 44d51 59f63 72g85 91 97hsqt3阶B+树1201B+树的结构特点： 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子结点彼此相链接

43、构成一个有序链表，其头指针指向含最小关键字的结点；121 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值（或最小值）； 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间。12259 97aroot15 44 59b72 97e10 15c21 37 44d51 59f63 72g85 91 97hsqt3阶B+树1232查找过程 在 B+ 树上，既可以进行缩小范围的查 找，也可以进行顺序查找； 在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束； 若在结点内查找时，给定值Ki， 则 应继续在 Ai 所指子树中进行查

44、找；1243插入和删除的操作类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并”。1259.3 哈 希 表哈希表的相关定义哈希函数的构造方法处理冲突的方法哈希表的查找哈希表的插入哈希查找分析126 散列存储的基本思想是以关键码的值为自变量，通过一定的函数关系（称为散列函数，或称Hash函数），计算出对应的函数值来，以这个值作为结点的存储地址，将结点存入计算得到的存储单元里去。 散列存储 127USk1k2k3k5k40H(k1)H(k5)H(k2)=H(k4)H(k3)H(km-1)图9.22 散列过程示例 128哈希查找基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关

45、系；这样，不经过比较，一次存取就能得到所查元素的查找方法。哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。哈希表的相关定义关键字集合存储地址集合hash129散列存储中经常会出现对于两个不同关键字xi，xj，却有H（xi）=H（xj），即对于不同的关键字具有相同的存放地址，这种现象称为冲突或碰撞。综上所述，对于Hash方法，需要研究下面两个主要问题：（1）选择一个计算简单，并且产生冲突的机会尽可能少的Hash函数；（2）确定解决冲突的方法。130Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye

46、, Dei 例如：对于如下 9 个关键字设 哈希函数 H(key) = (Ord(第一个字母) -Ord(A)+1)/2ChenZhaoQianSunLiWuHanYeDei问题: 若添加关键字 Zhou , 怎么办？能否找到另一个哈希函数？1311) 哈希函数是一个映象，即： 将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要这个地址集合的 大小不超出允许范围即可;从这个例子可见，2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1 key2，而 f(key1) = f(key2)。1323) 很难找到一个不产生冲突的哈希函数。一般情况下，只能

47、选择恰当的哈希函数，使冲突尽可能少地产生。 因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外;还需要找到一种“处理冲突” 的方法。133哈希表的定义: 根据设定的哈希函数 H(key) 和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集 (区间) 上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。134二、构造哈希函数的方法 对数字的关键字可有下列构造方法: 若是非数字关键字，则需先对其进行数字化处理。1. 直接定址法3. 平方取中法5. 除留余数法4. 折叠法6. 随机数法2

48、. 数字分析法135哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a key + b1. 直接定址法此法仅适合于：地址集合的大小 = = 关键字集合的大小1362. 数字分析法构造：对关键字进行分析，取关键字的若干位或其组合作哈希地址;例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 78 1 3 6 8 5 3 78 1 4 1 9 3 5 5. 分析： 只取8 只取1

49、只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作哈希地址1373.平方取中法构造：取关键字平方后中间几位作哈希地址4. 折叠法构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类移位叠加：将分割后的几部分低位对齐相加间界叠加：从一端沿分割界来回折送，然后对齐相加适于关键字位数很多，且每一位上数字分布大致均匀情况例 关键字为 ：0442205864，哈希地址位数为45 8 6 44 2 2 00 41 0 0 8 8H(key)=0088移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加1

50、385. 除留余数法 设定哈希函数为: H(key) = key MOD p 其中， pm (表长) 并且 p 应为不大于 m 的素数 139 给定一组关键字为: 12, 39, 18, 24, 33, 21，若取 p=9, 则他们对应的哈希函数值将为: 3, 3, 0, 6, 6, 3例如：为什么要对 p 加限制？ 可见，若 p 中含质因子 3, 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。1406.随机数法设定哈希函数为: H(key) = Random(key)其中，Random 为伪随机函数 通常，此方法用于对长度不等的关键字构造哈希函数。141 实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地