第8章查找(1)

1、1第八章 查 找2 8.2 静态查找表静态查找表 8.3 动态查找表动态查找表 8.4 哈希表查找哈希表查找本章目录本章目录 小小 结结 习习 题题 8.1 基本概念与术语基本概念与术语38.1 8.1 基本概念与术语基本概念与术语关键字关键字数据项数据项 (字段字段)数据项是数据不可分割的最小单位。数据项是数据不可分割的最小单位。组合项组合项如果一个数据项是由若干项组合构成的，如果一个数据项是由若干项组合构成的，则称此数据项为组合项。则称此数据项为组合项。 数据元素数据元素（记录）（记录）数据元素是由若干数据项、组合项构成数据元素是由若干数据项、组合项构成的数据单位，是在某一问题中作为整体的

2、数据单位，是在某一问题中作为整体进行考虑和处理的基本单位。进行考虑和处理的基本单位。关键字是数据元素（记录）中某个项或关键字是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元组合项的值，用它可以标识一个数据元素（记录）。素（记录）。 48.1 8.1 基本概念与术语基本概念与术语( (续续) )动态查找表动态查找表查找表查找表查找表是由具有同一类型（属性）的数查找表是由具有同一类型（属性）的数据元素（记录）组成的集合。据元素（记录）组成的集合。静态查找表静态查找表仅对查找表进行查找操作，而不改变的仅对查找表进行查找操作，而不改变的查找表。也就说，在查找操作的过程中查找表。也就说，在

3、查找操作的过程中，查找表的结构不发生变化。查找表中，查找表的结构不发生变化。查找表中的数据元素的个数不会发生改变。的数据元素的个数不会发生改变。对查找表除进行查找操作外，可能还要对查找表除进行查找操作外，可能还要进行向表中插入数据元素，或删除表中进行向表中插入数据元素，或删除表中数据元素的表。查找表中的数据元素是数据元素的表。查找表中的数据元素是可以增加或者减少。可以增加或者减少。58.1 8.1 基本概念与术语基本概念与术语( (续续) )查找查找根据给定的某个值，在查找表中确定一个根据给定的某个值，在查找表中确定一个其关键字的值等于给定值的记录或数据元其关键字的值等于给定值的记录或数据元素

4、的操作称为查找。素的操作称为查找。数据元素类型说明数据元素类型说明typedef struct KeyType key; /关键字字段关键字字段 /其它字段其它字段 ElemType；6 由于查找表中的数据元素之间不存在由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。明显的组织规律，因此不便于查找。 为了提高查找的效率，为了提高查找的效率， 需要在查找表需要在查找表中的元素之间人为地中的元素之间人为地 附加某种确定的关附加某种确定的关系，换句话说，系，换句话说， 用另外一种结构来表示用另外一种结构来表示查找表。查找表。如何进行查找？如何进行查找？查找的方法取决于查找表的结构。查

5、找的方法取决于查找表的结构。7线性表：线性表：适用于静态查找，主要采用顺序查适用于静态查找，主要采用顺序查找技术、折半查找技术。找技术、折半查找技术。树表：树表：适用于动态查找，主要采用二叉排序适用于动态查找，主要采用二叉排序树的查找技术。树的查找技术。哈希表：哈希表：静态查找和动态查找均适用，主要静态查找和动态查找均适用，主要采用散列技术。采用散列技术。 本章讨论的查找结构本章讨论的查找结构88.2 8.2 静态查找表静态查找表静态查找表结构静态查找表结构1顺序查找顺序查找2有序表的折半查找有序表的折半查找3有序表的其他查找方法有序表的其他查找方法4分块查找分块查找59静态查找表结构静态查找

6、表结构 静态查找静态查找是指在查找的过程中查找表的结是指在查找的过程中查找表的结构不发生变化的查找操作，也就是在查找构不发生变化的查找操作，也就是在查找的过程中查找表中的数据元素既不增加也的过程中查找表中的数据元素既不增加也不减少。不减少。 静态查找表可以有多种静态查找表可以有多种表示方法表示方法，不同的，不同的表示方法其查找操作的实现也不相同表示方法其查找操作的实现也不相同。链式存储结构链式存储结构顺序存储结构顺序存储结构10链式存储结构链式存储结构template struct Node T key; /关键字域关键字域 . /其他域其他域;template class StaticSea

7、rchTablepublic: Node *ST; int index; StaticSearchTable() ST=NULL; /初始为空表初始为空表 index=0; /当前元素个数当前元素个数 ;11顺序存储结构顺序存储结构template class SqListprivate： T *elem； /表基址表基址 int length； /表长度表长度 int listsize； /表容量表容量 public： SqList(int m) ；/构造函数，构造函数， 创建容量为创建容量为m的空表的空表 SqList()；/析构函数，删除表空间析构函数，删除表空间12顺序查找顺序查找 查

8、找方法查找方法：从表的一端开始，向另一端逐个将给定值从表的一端开始，向另一端逐个将给定值key与关键字进行比较与关键字进行比较: 若相等，若相等，查找成功查找成功，给出数据元素在表中的，给出数据元素在表中的位置；位置； 若整个表检测完，仍未找到与若整个表检测完，仍未找到与key相同的关相同的关键字，则键字，则查找失败查找失败。13顺序表的顺序查找顺序表的顺序查找 算法思想算法思想： 将顺序表中的将顺序表中的0号单元设置为号单元设置为“哨兵哨兵” 。查找。查找时从顺序表中的最后一个元素开始，依次向前进时从顺序表中的最后一个元素开始，依次向前进行查找。行查找。 算法算法：int s_search1

9、(SqList & L，KeyType k) L.elem0.key = k； for( i = L.length;L.elemi.key k ;i- )； return i； 14顺序表的顺序查找顺序表的顺序查找 算法分析算法分析 查找成功时：查找成功时： ASL 查找不成功时：查找不成功时：ASL= 时间复杂度：时间复杂度：T(n)=O(n) 111(1)2ninnin n+115单链表的顺序查找单链表的顺序查找 算法思想：算法思想：从单链表的从单链表的首元结点首元结点开始，向后一个一个检查开始，向后一个一个检查结点的值域，同时设置一个结点的值域，同时设置一个计数器计数器，用以标记

10、所，用以标记所访问结点在链表中的序号。若查找成功，返回序访问结点在链表中的序号。若查找成功，返回序号的值，否则返回号的值，否则返回0。 P P a1ana216单链表的顺序查找单链表的顺序查找 算法：算法：int s_search2(Linklist head，KeyType k) p=head-next;j=1; while(p!=NULL &p-data!=k) p=p-next; j+; if(p-data= =k) return j; else return 0;17平均查找长度较大，特别是当待查找集合中元素较多平均查找长度较大，特别是当待查找集合中元素较多时，查找效率较低。时

11、，查找效率较低。缺点：缺点：算法简单而且使用面广。算法简单而且使用面广。对表中记录的存储没有任何要求，顺序存储和链接对表中记录的存储没有任何要求，顺序存储和链接存储均可；存储均可；对表中记录的有序性也没有要求，无论记录是否按对表中记录的有序性也没有要求，无论记录是否按关键码有序均可。关键码有序均可。优点：优点：顺序查找分析顺序查找分析18有序表的折半查找有序表的折半查找 算法思想：算法思想：1 将给定值与中间元素的关键字比较：将给定值与中间元素的关键字比较：1.1若若相等相等，则，则查找成功查找成功；1.2若若小于小于，则在，则在左半区左半区继续查找；继续查找；1.3若若大于大于，则在，则在右

12、半区右半区继续查找。继续查找。2 不断重复上述查找过程，直到查找成功，或所查不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，找的区域无数据元素，查找失败查找失败。19有序表的折半查找有序表的折半查找 例如例如：已知如下：已知如下11个数据元素的有序表（关键字即为数据元素个数据元素的有序表（关键字即为数据元素的值）：（的值）：（05，13，19，21，37，56，64，75，80，88，92）现要查找关键字为现要查找关键字为64和和60的数据元素。的数据元素。Play20折半查找判定树折半查找判定树 判定树判定树：折半查找的过程可以用二叉树来描折半查找的过程可以用二叉树来描述，树中

13、的每个结点对应有序表中的一个记述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在录，结点的值为该记录在表中的位置。通常表中的位置。通常称这个描述折半查找过程的二叉树为折半查称这个描述折半查找过程的二叉树为折半查找判定树，简称找判定树，简称判定树判定树。21 当当n=0时，折半查找判定树为空；时，折半查找判定树为空； 当当n0时，折半查找判定树的根结点是有序表中时，折半查找判定树的根结点是有序表中序号为序号为mid=( (n+1) )/2的记录，根结点的左子树是与有的记录，根结点的左子树是与有序表序表r1 rmid- -1相对应的折半查找判定树，根结相对应的折半查找判定树，根结点的点的

14、右子树是与右子树是与rmid+1 rn相对应的折半查找判相对应的折半查找判定树。定树。 判定树的构造方法判定树的构造方法22查找成功：查找成功：在表中查找任一记录的过程，即是在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树径，和给定值的比较次数等于该记录结点在树中的层数。中的层数。查找不成功：查找不成功：查找失败的过程就是走了一条查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的关键码的比较次数等于该路

15、径上内部结点的个数。的个数。折半查找性能分析折半查找性能分析 23有序表的折半查找有序表的折半查找 算法分析：算法分析：假设表中每个元素的查找是等概率的假设表中每个元素的查找是等概率的 当当n较大时，可以近似为：较大时，可以近似为：ASL= -1所以有：所以有：T(n)=O(log2n )121111*2log (1) 1nhjiiiinASLp cjnnn2log (1)n24顺序表顺序表有序表有序表表的特性表的特性无序有序存储结构存储结构顺序 或 链式顺序插删操作插删操作易于进行需移动元素ASL的值的值大小查找性能对比查找性能对比25有序表的其它查找方法有序表的其它查找方法 插值查找插值查

16、找 插值查找是插值查找是平均性能最好平均性能最好的查找方法，但的查找方法，但只适合于只适合于关键字均匀分布关键字均匀分布的表，其时间效的表，其时间效率仍然是率仍然是O(log2n)。 26有序表的其它查找方法有序表的其它查找方法 斐波那契查找斐波那契查找 斐波那契查找通过斐波那契查找通过斐波那契数列斐波那契数列对有序表对有序表进行分割，查找区间的两个端点和中点都进行分割，查找区间的两个端点和中点都与斐波那契数有关。与斐波那契数有关。27 分块查找分块查找 适用条件：适用条件：将查找表分成若干个子表，将查找表分成若干个子表，子表为非子表为非有序表有序表，但要求，但要求子表之间子表之间是存在着是存

17、在着有有序序关系。关系。 28 分块查找分块查找 算法思想：算法思想：1 用给定值用给定值k在索引表中检测在索引表中检测索引项索引项，以确定，以确定所要进行的查找在查找表中的查找所要进行的查找在查找表中的查找分块分块 (由由于索引项按关键字字段有序，可用顺序查找于索引项按关键字字段有序，可用顺序查找或折半查找或折半查找) ;2 对该分块进行顺序查找。对该分块进行顺序查找。 29分块查找分块查找 示例示例 1 2 3 4 5 6 7 8 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 532

18、2 48 861 7 13索引表查38找到！找到！30分块查找分块查找 算法分析：算法分析： 设设n个数据元素的查找表分为个数据元素的查找表分为m个子表，且每个子表，且每个子表均为个子表均为t个元素，则个元素，则t= 。 分块查找的平均查找长度为：分块查找的平均查找长度为： mn318.3 8.3 动态查找表动态查找表 二叉排序二叉排序树树1平衡二叉树（平衡二叉树（AVL树）树）2B-树和树和B+树树332二叉排序树二叉排序树 二叉排序树（二叉排序树（Binary Sort Tree）或者是一棵空树；或或者是一棵空树；或者是具有下列性质的二叉树：者是具有下列性质的二叉树： 若左子树不空若左子树

19、不空，则左子，则左子树上所有结点的值均小于根树上所有结点的值均小于根结点的值；结点的值；若右子树不空若右子树不空，则右子树上所有结点的值均则右子树上所有结点的值均大于根结点的值。大于根结点的值。 左右子树也都是二叉排左右子树也都是二叉排序树序树。45125333724100619078一棵二叉排序树示例一棵二叉排序树示例33二叉排序树二叉排序树 查找过程查找过程1 若根结点的关键字值若根结点的关键字值等于等于查找的关键字，成功；查找的关键字，成功；2 若根结点的关键字值若根结点的关键字值不等于不等于查找的关键字，查找的关键字，2.1 若若小于小于根结点的关键字值，查其左子树；根结点的关键字值，

20、查其左子树；2.2 若若大于大于根结点的关键字值，查其右子树。在根结点的关键字值，查其右子树。在左右子树上的操作类似。左右子树上的操作类似。3450308020908540358832例如例如:查找关键字查找关键字= 50 ,505035 ,503040355090 ,50809095 ,35从上述查找过程可见，在查找过程中，从上述查找过程可见，在查找过程中，生成了一条查找路径生成了一条查找路径: : 从根结点出发，沿着左分支或右分支逐层向下直从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点至关键字等于给定值的结点;或者 从根结点出发，沿着左分支或右分支逐层向下直从根结点出发

21、，沿着左分支或右分支逐层向下直至指针指向空树为止。至指针指向空树为止。 查找成功查找成功 查找不成功查找不成功36查找性能的分析查找性能的分析 对于每一棵特定的二叉排序树，均对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的值，显然，由值相同的 n 个关键字，个关键字，构造所得的不同形态的各棵二叉排序树构造所得的不同形态的各棵二叉排序树的平均查找长的平均查找长 度的值不同，甚至可能度的值不同，甚至可能差别很大。差别很大。37二叉排序树二叉排序树 例4024123755122437405540，24，12，37，55 12

22、，24，37，40，5535 / ) 54321 (1niiicp1i2 . 25/ ) 23221 (*niicp38二叉排序树二叉排序树 算法分析：算法分析：在二叉排序树中进行查找的平均查找长在二叉排序树中进行查找的平均查找长度和二叉树的形态有关，即，度和二叉树的形态有关，即，最坏最坏: O(n)（单支树）（单支树）最好最好: O(log2n)（形态匀称，与二分查（形态匀称，与二分查找的判定树相似）找的判定树相似）39 根据动态查找表的定义，根据动态查找表的定义，“插入插入”操作操作在在查找不成功查找不成功时才进行时才进行;二叉排序树的插入二叉排序树的插入 若二叉排序树为空树，则新插入的结

23、点若二叉排序树为空树，则新插入的结点为为新的根结点新的根结点；否则，新插入的结点必；否则，新插入的结点必为一个为一个新的叶子结点新的叶子结点，其插入位置由查，其插入位置由查找过程得到。找过程得到。40二叉排序树的插入二叉排序树的插入例：在下图给定的二叉排序树中插入结点例：在下图给定的二叉排序树中插入结点20451253337241006190782041二叉排序树的构造二叉排序树的构造例例 关键字序列为关键字序列为 10， 18， 3， 8， 12， 2， 7， 3 1018381227342二叉排序树删除二叉排序树删除 操作要点：操作要点：1 从二叉排序树删除一个结点之后，要使得从二叉排序树

24、删除一个结点之后，要使得删删除之后除之后二叉树二叉树还是还是一棵一棵二叉排序树二叉排序树；2 从二叉排序树删除一个结点，既可能是叶子从二叉排序树删除一个结点，既可能是叶子结点也可能是分支结点，处理的方法不同。结点也可能是分支结点，处理的方法不同。43二叉排序树删除二叉排序树删除三种情况三种情况 ：设待删结点为设待删结点为p，其双亲结点为，其双亲结点为f 。（1）p结点为叶结点结点为叶结点（2）p结点只有右子树结点只有右子树pr或只有左子树或只有左子树pl（3）p结点既有左子树结点既有左子树pl又有右子树又有右子树pr44二叉排序树删除二叉排序树删除 第一种情况：第一种情况：p结点为叶结点结点为

25、叶结点 由于删去叶结点后不影响整棵树的特性，由于删去叶结点后不影响整棵树的特性，所以，只需将被删结点的双亲结点相应指针所以，只需将被删结点的双亲结点相应指针域改为空指针。域改为空指针。63421815X45二叉排序树删除二叉排序树删除 第二种情况：第二种情况：p结点只有右子树结点只有右子树pr或只有左子树或只有左子树pl，此时，只，此时，只需将需将pr或或pl替换替换f结点的结点的p子树即可。子树即可。63421812156342181546二叉排序树删除二叉排序树删除中序遍历：中序遍历：P PR S QSPRQ中序遍历：中序遍历：PR S Qp结点只有右子树结点只有右子树pr(1)SPPRQ

26、中序遍历：中序遍历：Q S P PRSQPR中序遍历：中序遍历：Q S PRp结点只有右子树结点只有右子树pr(2)SQPRP删除删除1263421812156342181547二叉排序树删除二叉排序树删除SPPLQ中序遍历：中序遍历：PL P S QSPLQ中序遍历：中序遍历：PL S Qp结点只有左子树结点只有左子树pl（1）SQPLP中序遍历：中序遍历：Q S PL PSQPL中序遍历：中序遍历：Q S PLp结点只有左子树结点只有左子树pl（2）63421815634215删除删除1848二叉排序树删除二叉排序树删除 第三种情况：第三种情况：p结点既有左子树结点既有左子树pl又有右子树

27、又有右子树pr ，可按中序遍，可按中序遍历保持有序进行调整。历保持有序进行调整。10362418121549二叉排序树删除二叉排序树删除FPCPRCLQQLSSL中序遍历：中序遍历：CL C QL Q SL S P PR FFSCPRCLQQLSL中序遍历：中序遍历：CL C QL Q SL S PR Fp结点既有左子树结点既有左子树pl又有右子树又有右子树pr(1)FPCPRCL中序遍历：中序遍历：CL C P PR FFCPRCL中序遍历：中序遍历：CL C PR Fp结点既有左子树结点既有左子树pl又有右子树又有右子树pr(2)50二叉排序树删除二叉排序树删除10362418121563

28、42181215删除删除10例例51p / 右子树为空树则只需重接它的左子树q = p; p = p-lchild; delete(q);pqq52/ 左子树为空树只需重接它的右子树q = p; p = p-rchild; delete(q);ppqq53q = 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的左子树delete

29、(s);pqs54平衡二叉树平衡二叉树(AVL(AVL树树) )n定义：定义：平衡二叉树又称平衡二叉树又称AVL树，树，它或者是一棵空树，或者是它或者是一棵空树，或者是具有下列性质的二叉树具有下列性质的二叉树：n平衡因子平衡因子balance：结点左子树与右子树的高度差。结点左子树与右子树的高度差。即即 |左子树深度左子树深度-右子树深度右子树深度| 1左、右子树是平衡二叉树；左、右子树是平衡二叉树；所有结点的左、右子树深度之差的绝对值所有结点的左、右子树深度之差的绝对值 155判断下列二叉树是否判断下列二叉树是否AVL树？树？n任一结点的平衡因子只能取：任一结点的平衡因子只能取：-1、0 或

30、或 1；否则，；否则，这棵二叉树就失去平衡，不再是这棵二叉树就失去平衡，不再是AVL树；树；n对于一棵有对于一棵有n个结点的个结点的AVL树，其树，其高度保持在高度保持在O(log2n)数量级，数量级，ASL也保持在也保持在O(log2n)量级。量级。平衡二叉树平衡二叉树(AVL(AVL树树) )56平衡二叉树平衡二叉树(AVL(AVL树树) )平衡平衡旋转旋转 如果在一棵如果在一棵AVL树中插入一个新结点，树中插入一个新结点，就有可能造成失衡，此时必须就有可能造成失衡，此时必须重新调整树重新调整树的结构的结构，使之恢复平衡。称调整平衡过程，使之恢复平衡。称调整平衡过程为为平衡旋转平衡旋转。L

31、L平衡平衡旋转旋转RR平衡平衡旋转旋转LR平衡平衡旋转旋转RL平衡平衡旋转旋转57若在若在A的的左子树的左子树上插入左子树的左子树上插入结结点，使点，使A的平衡因子从的平衡因子从1增加至增加至2，需要进行一次需要进行一次顺时针旋转顺时针旋转。(以以B为旋转轴）为旋转轴）ABCABC若在若在A的的右子树的右子树上插入右子树的右子树上插入结结点，使点，使A的平衡因子从的平衡因子从-1增加至增加至-2，需要进行一次需要进行一次逆时针旋转逆时针旋转。(以以B为旋转轴）为旋转轴）2）RR平衡旋转：平衡旋转：ABC1）LL平衡旋转：平衡旋转：ABC平衡二叉树平衡二叉树(AVL(AVL树树) )58若在若在

32、A的的右右子树的子树的左左子树上插入子树上插入结结点，使点，使A的平衡因子从的平衡因子从-1增加至增加至-2，需要需要先进行先进行顺顺时针旋转，再时针旋转，再逆逆时时针旋转针旋转。(以插入的结点以插入的结点C为旋转轴）为旋转轴）4）RL平衡旋转：平衡旋转：ABCABCABC若在若在A的的左左子树的子树的右右子树上插入子树上插入结点，使结点，使A的平衡因子从的平衡因子从1增加至增加至2，需要，需要先进行先进行逆逆时针旋转，再时针旋转，再顺顺时针旋转。时针旋转。(以插入的结点以插入的结点C为旋转轴）为旋转轴）ABCABCABC3）LR平衡旋转：平衡旋转：平衡二叉树平衡二叉树(AVL(AVL树树)

33、)59基本思想：基本思想：在构造二叉排序树的过程中，每在构造二叉排序树的过程中，每插入一个结点时，先检查是否因插入而破坏插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子了树的平衡性，若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。进行相应的旋转，使之成为新的平衡子树。在插入过程中，采用平衡旋转技术。在插入过程中，采用平衡旋转技术。构造平衡二叉树构造平衡二叉树(AVL(AVL树树) )60例：例：请将下面

34、序列构成一棵请将下面序列构成一棵平衡二叉排序树平衡二叉排序树： （ 13，24，37，90，53）需要需要RR平衡旋转平衡旋转(绕绕B逆转逆转,B为根）为根）需要需要RL平衡旋转平衡旋转(绕绕C先顺后逆）先顺后逆）平衡二叉树平衡二叉树(AVL(AVL树树) )61 查找分析查找分析: 在平衡树上进行查找的过程和二叉排序树相同在平衡树上进行查找的过程和二叉排序树相同 深度为深度为 h 的二叉平衡树中所含结点的最小值的二叉平衡树中所含结点的最小值 含有含有 n 个结点的二叉平衡树能达到的最大深度个结点的二叉平衡树能达到的最大深度 在平衡树上进行查找的时间复杂度为在平衡树上进行查找的时间复杂度为 O

35、(logn)平衡二叉树平衡二叉树(AVL(AVL树树) )62 B-B-树树 2 3 7 2 20 253 79 84 93 4 35 41 51 53 2 66 682 71 762 12 302 69 781 54tF F FFF FFFFFFFFFFFFFFFFabcdeghfi一棵一棵5阶的阶的B-树树 B-树是一种 平衡平衡 的 多路多路 查找查找 树：63 在在 m 阶的阶的B-树上，每个非终端结点可能含有树上，每个非终端结点可能含有： n 个关键字关键字 Ki（1 in） nm n 个指向记录的指针指向记录的指针 Di（1in） n+1 个指向子树的指针指向子树的指针 Ai（0i

36、n）;多叉树的特性多叉树的特性 B-B-树树64 非叶结点中的非叶结点中的多个关键字多个关键字均均自小至大自小至大有序排有序排列，即：列，即：K1 K2 Kn; 且且 Ai-1 所指子树上所有关键字均小于所指子树上所有关键字均小于Ki; Ai 所指子树上所有关键字均大于所指子树上所有关键字均大于Ki;查找树的特性查找树的特性 B-B-树树65平衡树的特性平衡树的特性 树中所有叶子结点均不带信息，且在树中的树中所有叶子结点均不带信息，且在树中的同一层次上同一层次上; 根结点或为叶子结点，或至少含有两棵子树根结点或为叶子结点，或至少含有两棵子树; 其余所有非叶结点均至少含有其余所有非叶结点均至少含

37、有 m/2 棵棵子树，子树，至多含有至多含有 m 棵子树棵子树; B-B-树树66从根结点出发，沿指针搜索结点和在结从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找点内进行顺序（或折半）查找 两个过程交两个过程交叉进行：叉进行： 若若查找成功查找成功，则返回指向被查关键字所在结点，则返回指向被查关键字所在结点的指针和关键字在结点中的位置；的指针和关键字在结点中的位置； 若若查找不成功查找不成功，则返回插入位置。，则返回插入位置。 B-B-树的查找树的查找67 在查找不成功之后，需进行插入。显然，关在查找不成功之后，需进行插入。显然，关键字插入的位置必定在最下层的非叶结点，键字插入的

38、位置必定在最下层的非叶结点，有下列几种情况：有下列几种情况： 插入后该结点的关键字个数插入后该结点的关键字个数nm，不修改指针，不修改指针; 插入后该结点的关键字个数插入后该结点的关键字个数n=m，则需进行，则需进行“结结点分裂点分裂”； 若双亲为空，则建新的根结点。若双亲为空，则建新的根结点。 B-B-树的插入树的插入683 阶阶B-树的插入树的插入50 20 40 80 插入关键字插入关键字 = 60, 60 80 90, 60 80 90 90 50 80 60 30 40 20 30 50 808030 50 B-B-树的插入树的插入69n找到待删关键字所在结点；找到待删关键字所在结点

39、；n 删除该结点之后，结点中关键字的个数删除该结点之后，结点中关键字的个数不能小于不能小于 m/2 -1，否则，要从其左，否则，要从其左(或右或右)兄弟结点兄弟结点“借调借调”关键字；关键字；n 若其左和右兄弟结点均无关键字可借若其左和右兄弟结点均无关键字可借(结结点中只有最少量的关键字点中只有最少量的关键字)，则必须进行，则必须进行结点的结点的“合并合并”. B-B-树的删除树的删除70B+B+树树 71B+树的结构特点：树的结构特点： 每个叶子结点中含有每个叶子结点中含有 n 个关键字和个关键字和 n 个指向记录的指针；个指向记录的指针；并且，所有叶子结点并且，所有叶子结点彼此相链接构成一

40、个彼此相链接构成一个有序链表有序链表，其其头指针头指针指向含最小关键字的结点；指向含最小关键字的结点；B+B+树树 72 每个非叶结点中的关键字每个非叶结点中的关键字 Ki 即即为为其相应其相应指针指针 Ai 所指子树中关键字的最大值；所指子树中关键字的最大值； 所有叶子结点都处在所有叶子结点都处在同一层次同一层次上，每个上，每个叶子结点中关键字的个数均介于叶子结点中关键字的个数均介于 m/2 和和 m 之间。之间。B+B+树树 73B+B+树的查找过程树的查找过程n既可以进行缩小范围的查找，也可以进行既可以进行缩小范围的查找，也可以进行顺序查找；顺序查找；n 在在进行缩小范围进行缩小范围的查

41、找时，不管成功与否，的查找时，不管成功与否，都必须查到叶子结点才能结束；都必须查到叶子结点才能结束；n 若在若在结点内结点内查找时，给定值查找时，给定值Ki， 则应继续在则应继续在 Ai 所指子树中进行查找。所指子树中进行查找。74B+B+树的插入和删除树的插入和删除n类似于类似于B-树树n必要时，也需要进行结点的必要时，也需要进行结点的“分裂分裂”或或“归并归并”。758.4 8.4 哈希表查找哈希表查找( (杂凑法、散列法杂凑法、散列法) )哈希表与哈希方哈希表与哈希方法法1常用的哈希函数常用的哈希函数2处理冲突的方法处理冲突的方法3哈希表的查找分析哈希表的查找分析476 以上两节讨论的表

42、示查找表的各种结构的共以上两节讨论的表示查找表的各种结构的共同特点：同特点：记录在表中的位置和它的关键字之间记录在表中的位置和它的关键字之间不存在一个确定的关系。不存在一个确定的关系。 查找的过程查找的过程为给定值依次和关键字集合中为给定值依次和关键字集合中各个关键字进行比较。各个关键字进行比较。 查找的效率查找的效率取决于和给定值进行比较的关取决于和给定值进行比较的关键字个数。键字个数。77 用这类方法表示的查找表，其平均查找用这类方法表示的查找表，其平均查找长度都不为零长度都不为零 只有一个办法：预先知道所查关键字在表只有一个办法：预先知道所查关键字在表中的位置，中的位置， 对于频繁使用的

43、查找表，希望对于频繁使用的查找表，希望 ASL = 0。 即要求：即要求：记录在表中位置和其关键字之间记录在表中位置和其关键字之间存在一种确定的关系存在一种确定的关系。78若以下标为若以下标为000 999 的顺序表表示之。的顺序表表示之。例如：为每年招收的例如：为每年招收的 1000 名新生建立一张查名新生建立一张查找表，其关键字为学号，其值的范围为找表，其关键字为学号，其值的范围为 xx000 xx999 (前两位为年份前两位为年份)。则查找过程可以简单进行：取给定值（学号）则查找过程可以简单进行：取给定值（学号）的后三位，的后三位，不需要经过比较便可直接从顺序表不需要经过比较便可直接从顺

44、序表中找到待查关键字。中找到待查关键字。79但是，对于但是，对于动态查找表动态查找表而言，而言，因此在一般情况下，需在关键字与记录在表因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，中的存储位置之间建立一个函数关系，以以 f(key) 作为关键字为作为关键字为 key 的记录在表中的位置，的记录在表中的位置，通常称这个函数通常称这个函数 f(key) 为哈希函数。为哈希函数。1) 表长不确定；表长不确定；2) 在设计查找表时，只知道关键字所属范在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。围，而不知道确切的关键字。80Zhao, Qian, Sun, Li

45、, Wu, Chen, Han, Ye, Dei 例如：对于如下例如：对于如下 9 个关键字个关键字设设 哈希函数哈希函数 f(key) = (Ord(第一个字母第一个字母) -Ord(A)+1)/2 ChenZhaoQianSunLiWuHanYeDei问题问题: 若添加关键字若添加关键字 Zhou , 怎么办？怎么办？能否找到另一个哈希函数？能否找到另一个哈希函数？811) 哈希哈希(Hash)函数是一个函数是一个映象，映象，即：即： 将关键字的集合映射到某个地址集合上，将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要这个地址集合的它的设置很灵活，只要这个地址集合的 大小不超出允

46、许范围即可大小不超出允许范围即可;2) 由于哈希函数是一个由于哈希函数是一个压缩映象，压缩映象，因此，因此，在一般情况下，很容易产生在一般情况下，很容易产生“冲突冲突”现象，现象，即：即： key1 key2，而而 f(key1) = f(key2)。823) 很难很难找到一个不产生冲突的哈希函数。找到一个不产生冲突的哈希函数。一般情况下，一般情况下，只能选择恰当的哈希函数，只能选择恰当的哈希函数，使冲突尽可能少地产生。使冲突尽可能少地产生。 因此，在构造这种特殊的因此，在构造这种特殊的“查找表查找表” 时，除了需要选择一个时，除了需要选择一个“好好”(尽可能少尽可能少产生冲突产生冲突)的的哈

47、希函数哈希函数之外之外;还需要找到一还需要找到一种种“处理冲突处理冲突” 的方法。的方法。83哈希表的定义哈希表的定义: : 根据设定的根据设定的哈希函数哈希函数 H(key) 和所选中的和所选中的处处理冲突的方法理冲突的方法，将一组关键字，将一组关键字映象到映象到一个有一个有限的、地址连续的地址集限的、地址连续的地址集 (区间区间) 上，并以关上，并以关键字在地址集中的键字在地址集中的“象象”作为相应记录在表作为相应记录在表中的中的存储位置存储位置，如此构造所得的查找表称之，如此构造所得的查找表称之为为“哈希表哈希表”。84哈希表与哈希方法哈希表与哈希方法 需解决两个问题：需解决两个问题：（

48、1）构造好的哈希函数：构造好的哈希函数：所选函数尽可能简单，以便提高转换速度。所选函数尽可能简单，以便提高转换速度。所选函数对关键字计算出的地址，应在哈希地所选函数对关键字计算出的地址，应在哈希地址集中大致均匀分布，以减少空间浪费。址集中大致均匀分布，以减少空间浪费。（2）制定解决冲突的方案。制定解决冲突的方案。85哈希表与哈希方法哈希表与哈希方法 例如：已知例如：已知ki：12，33，65，9，38，71，82，63，75，15，24，57，54，88，98；分布在；分布在20个单元个单元中，一个单元存放一个关键字（中，一个单元存放一个关键字（m=20），如果选），如果选H(ki)=ki/5

49、（除法求整数）作为哈希函数，则得到（除法求整数）作为哈希函数，则得到的的Hash表为：表为：0123456789101112131415161718199121524333854576365717582889886常用的哈希函数常用的哈希函数 直接定址法直接定址法 除留余数法除留余数法乘余取整法乘余取整法数字分析法数字分析法平方取中法平方取中法折叠法折叠法(Folding)87常用的哈希函数常用的哈希函数直接定址法直接定址法 Hash(key)=akey+b (a、b为常数为常数) 即取关键字的某个线性函数值为哈希地址即取关键字的某个线性函数值为哈希地址 特点特点：所得地址集合与关键字集合大小

50、相等，所得地址集合与关键字集合大小相等，不会发生冲突。不会发生冲突。适用情况？适用情况？事先知道关键码，关键码集合不是很大且连续性较好。事先知道关键码，关键码集合不是很大且连续性较好。 88常用的哈希函数常用的哈希函数例例 关键字集合为关键字集合为100，300，500，700，800，900，选取哈希函数为：选取哈希函数为：Hash(key)=key/100，则所建立，则所建立的哈希表如下：的哈希表如下： Hash(100)=100/100=1 Hash(300)=300/100=3 Hash(500)=500/100=5 0 1 2 3 4 5 6 7 8 9 Hash(700)=700/

51、100=7 Hash(800)=800/100=8 Hash(900)=900/100=9100900300500700 80089常用的哈希函数常用的哈希函数除留余数法除留余数法Hash(key)=key mod p (p是一个整数是一个整数) 即取关键字除以即取关键字除以p的余数作为哈希地址。的余数作为哈希地址。 选取合适的选取合适的p很重要，若哈希表表长为很重要，若哈希表表长为m，则，则要求要求pm，且接近，且接近m或等于或等于m。p一般选取一般选取质质数数，也可以是不包含小于，也可以是不包含小于20质因子的合数。质因子的合数。 90 给定一组关键字为给定一组关键字为: 12, 39,

52、18, 24, 33, 21，若取若取 p=9, 则他们对应的哈希函数值将为则他们对应的哈希函数值将为: 3, 3, 0, 6, 6, 3例如：例如：为什么要对为什么要对 p p 加限制？加限制？ 可见，若可见，若 p 中含质因子中含质因子 3, 则所有含质因子则所有含质因子 3 的的关键字均映射到关键字均映射到“3 的倍数的倍数”的地址上，从而增的地址上，从而增加了加了“冲突冲突”的可能。的可能。91除留余数法举例除留余数法举例已知一组关键字已知一组关键字19,14,23,01,68,20,84,27,55,11,10,79设表长设表长m为为16，试构造哈希表。，试构造哈希表。 分析：分析：

53、取哈希函数取哈希函数 H(key) = key mod p , 且取且取p=13, (13为小于为小于16的最大素数的最大素数)， 则有哈希函数则有哈希函数 H(key) = key mod 13。 由此由此,H(19) = 6, H(14) = 1, H(23) = 10, H(01)=1, ,H(68) = 3, H(20) = 7, H(84) = 5, H(27) = 1, H(55) = 3, 可见在利用以上函数构造哈希表可见在利用以上函数构造哈希表时，发生了冲突。其中，时，发生了冲突。其中，14，01，27，79为同义为同义词，词，.92常用的哈希函数常用的哈希函数乘余取整法乘余取

54、整法Hash(key)= B*(A*key mod 1) (A、B均为均为常数，且常数，且0A1，B为整数为整数) B取什么值并不关键，但取什么值并不关键，但A的选择却很重要，的选择却很重要，最佳的选择依赖于关键字集合的特征。最佳的选择依赖于关键字集合的特征。一般取一般取A= 0.6180339较为理想。较为理想。93常用的哈希函数常用的哈希函数数字分析法数字分析法 对关键字进行分析，取关键字的若干位或其组合对关键字进行分析，取关键字的若干位或其组合作哈希地址作哈希地址例例 有有80个记录，关键字为个记录，关键字为8位十进制数，哈希地位十进制数，哈希地址为址为2位十进制数位十进制数8 1 3

55、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 只取只取3、4 只取只取2、7、5 数字分布近乎随机数字分布近乎随机所以：取所以：取任意两位或两位任意两位或两位 与另两位的叠加作哈希地址与另两位的叠加作哈希地址94常用的哈希函数常用的哈希函数数字分析法数字分析法 对关键字进行分析，取关键字的若干位或其组合对关键字进行分析，取关键字的若干位或其组合作哈希地址作哈希地址例例 有

56、有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. 适用情况适用情况:能预先估计出全部关键码能预先估计出全部关键码的每一位上各种数字出现的每一位上各种数字出现的频度，不同的关键码集的频度，不同的关键码集合需要重新分析。合需要重新分析。95常用的哈希函数常用的哈希函数平方取中法平方取中法 取关键字平方

57、后的中间几位为哈希地址取关键字平方后的中间几位为哈希地址 事先不知道关键码的分布且关键码的位数不是很大。事先不知道关键码的分布且关键码的位数不是很大。适用情况适用情况:例：散列地址为例：散列地址为2位，则关键码位，则关键码1234的散列地址为：的散列地址为：(1234)2152275696常用的哈希函数常用的哈希函数6. 折叠法折叠法(Folding)将关键字自左到右分成位数相等的几部分，将关键字自左到右分成位数相等的几部分，最后一部分位数可以短些，然后将这几部分最后一部分位数可以短些，然后将这几部分叠加求和。叠加求和。有两种叠加方法：有两种叠加方法： （1） 移位法移位法 。 （2） 间界叠

58、加法间界叠加法 。适用情况适用情况:关键码位数很多，事先不知道关键码的分布。关键码位数很多，事先不知道关键码的分布。 97常用的哈希函数常用的哈希函数 例例 关键字为关键字为 ：0442205864，哈希地址位数为，哈希地址位数为45 8 6 44 2 2 0 0 41 0 0 8 8H(key)=0088移位叠加移位叠加5 8 6 40 2 2 40 4 6 0 9 2H(key)=6092间界叠加间界叠加98随机数法随机数法设定哈希函数为设定哈希函数为: H(key) = Random(key)其中，其中，Random 为伪随机函数为伪随机函数 通常，此方法用于对长度不等的关键字构造哈希函

59、数。通常，此方法用于对长度不等的关键字构造哈希函数。99 实际造表时，采用何种构造哈希函数的方实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况法取决于建表的关键字集合的情况(包括关键字包括关键字的范围和形态的范围和形态)，总的原则是总的原则是使产生冲突的可能使产生冲突的可能性降到尽可能地小。性降到尽可能地小。100处理冲突的方法处理冲突的方法 开放定址法开放定址法 由关键字得到的哈希地址一旦产生了由关键字得到的哈希地址一旦产生了冲突冲突，就去寻找下一个空的哈希地址。就去寻找下一个空的哈希地址。 即即 Hi=(H(key)+di)MOD m，i=1,2,k(k m-1)其中：其

60、中：H(key)为为哈希函数哈希函数m为为哈希表表长哈希表表长di为为增量序列增量序列101处理冲突的方法处理冲突的方法 分类分类 线性探测法线性探测法 di=1,2,3,，m-1 二次探测法二次探测法di=1,-1,2,-2,3,k(k m/2) 双哈希函数探测法双哈希函数探测法 di=伪随机数序列伪随机数序列102例如例如: 关键字集合关键字集合 19, 01, 23, 14, 55, 68, 11, 82, 36 设定哈希函数设定哈希函数 H(key) = key MOD 11 ( 表长表长=11 ) 0 1 2 3 4 5 6 7 8 9 10 0 1 2 3 4 5 6 7 8 9 10190123