第九章

Transcription

1 第八章 查找 本章教学知识点与学习要求 :( 课内教学时数 6 学时, 实践教学时数 2 学时 ) (1) 熟练掌握顺序表和有序表的查找方法 ; (2) 熟悉静态查找树的构造方法和查找算法, 理解静态查找树和折半查找的关系 ; (3) 熟练掌握二叉排序树的构造方法和查找方法 ; (4) 掌握二叉平衡树的维护平衡方法 ; (5) 理解 B- 树 B+ 树和键树的特点以及他们的建树过程 ; (6) 熟练掌握哈希表的构造方法, 深刻理解哈希表与其他结构的表的实质性差别 ; (7) 掌握描述查找过程的判定树的构造方法, 以及按定义计算各种查找方法在等 概率情况下查找成功时的平均查找长度 方法 ; 本章学习重点 : (1) 查找表的基本概念及查找原理 ; 顺序存储结构 顺序表及其类型说明 ; (2) 查找运算在查找表和有序表上的实现 ; (3) 二叉排序树的定义 性质及各结点间的键值关系, 查找算法和基本思想 ; (4) 平衡二叉排序树的概念 ;B- 树和 B+ 树的概念 ; (5) 散列表及散列存储和散列查找的基本思想 ; 各种散列表的组织 解决冲突的 (6) 在散列表上实现查找 插入和删除运算的算法 本章教学难点 : (1) 理解查找表的逻辑结构是集合, 它的运算以查找为核心 ; (2) 二叉排序树上的插入算法 ; 平衡二叉树的旋转平衡算法 ; (3) 散列表上的有关算法 8.1 基本概念 1 查找表查找表 (search table) 是由同一个类型的数据元素 ( 或记录 ) 构成的集合 由于 集合 中的数据元素之间存在着完全松散的关系, 因此查找表是一种非常灵便的数据结构 2 关键字关键字 (key) 是记录中某个数据项的值, 用它可以标识 ( 识别 ) 个记录 若此关键字可以惟 地标识一个记录, 则称此关键字为主关键字 (primary key), 反之, 称用以识别若干记录的关键字为次关键字 (secondary key) 3 查找查找 (searching) 是根据给定的关键字值, 在表中确定一个其关键字等于给定值的记录的过程 如果表中存在这样的一个记录, 则称查找成功, 查找结 1

2 果可以输出该记录的有关信息或指示记录在查找表中的位置 ; 如果表中不存在相应的记录, 则称查找不成功 此时的查找结果可以给出一个 空 记录或 空 指针 4 查找的分类按查找条件分类, 可以分为按结点的关键字查找, 关键字以外的其它数据项查找或其数据项的组合查找等 ; 按查找数据在内存或在外存分类, 可以分为内存查找和外存查找 ; 按查找目的分类, 可以分为静态查找和动态查找 5 静态查找查找的目的只是为了确定指定的记录存在与否, 称为静态查找 6 动态查找查找的目的是为确定记录的插入位置或为了删除找到的记录, 称为动态查找 7 查找操作查找表通常进行的操作有四种 :1 查询某个记录是否在查找表中存在 ; 2 检索某个记录的各种属性 ;3 在查找表中插入一个元素 ;4 在查找表中删除一个元素 8 查找方法查找表是一种非常灵活的数据结构, 可以用多种方式来存储 通常可用于查找表的存储方式有四种, 即顺序存储 链接存储 散列存储和索引存储 对于不同的存储结构, 适用的查找方法也不相同 根据查找表的存储结构, 可以将查找方法分为三类 : (1) 顺序表和链表的查找 : 将给定的值 K 与表中记录的关键字进行比较, 从而找到待查找的记录 (2) 散列表的查找 : 根据给定的值 K 直接访问待查找的记录 (3) 索引查找表的查找 : 首先根据索引确定待查找记录所在的块 ( 或子表 ), 然后在块 ( 或子表 ) 内进行查找 9 平均查找长度查找算法中的基本运算是记录的关键字与给定值所进行的比较, 其执行时间通常取决于关键字的比较次数 因此, 常以关键字与给定值进行比较的记录个数的平均值, 作为衡量查找算法好坏的依据 为了确定要查找的记录位置, 与给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度 (average search length,asl) 对于含有 n 个记录的表, 查找成功时的平均查找长度为 n ASL= i= 1 PiCi 其中 :Pi 为查找表中第 i 个记录的概率, 且 Pi=1 Ci 为找到表中其关键字与给定值相等的第 i 个记录时, 和给定值已进行 过比较的关键字个数, 且 Ci 随查找过程不同而具有不同的值 10 关键字类型说明 在本章中涉及的关键字类型定义如下 : typedef float KeyType; // 实型 typedef int KeyType; // 整型 typedef char KeyType; // 字符型 2

3 11 记录类型说明 在本章中涉及的数据元素 ( 或记录 ) 类型定义如下 : typedef struct{ KeyType key; // 关键字域 // 其他域 }ElemType; 8.2 顺序表的查找 顺序表 (sequential list) 是指线性表的顺序存储结构 在顺序表上进行查 找主要有顺序查找 折半查找以及索引顺序表的查找 下面分别介绍这几种 方法 查找表的顺序存储结构 : typedef struct { // 顺序查找表的类型定义 KeyType *elem; // 数据元素存储空间基址, 建表时按实际长度分配,0 号单元留空 int length; // 表长度 }SSTable; // 顺序查找表的类型名 简单顺序表的查找 1 顺序查找的方法描述顺序查找过程为 : 从表的一端开始, 逐个进行记录关健字值与给定值 key 的比较, 若某个记录关键字值与给定值 key 相等, 则查找成功 ; 反之, 若已查找到表的另一端, 仍未找到关键字值与给定值相等的记录, 则查找不成功 2 顺序查找的算法算法 <8.1> < 顺序查找 > int Search_Seq ( SSTable ST, KeyType key ) // 在表 ST 中顺序查找其关键字等于 key 的数据元素 // 如果找到, 则函数值为该元素在表中的位置, 否则为 0 { ST.elem[0].key = key; // 哨兵 FOR ( i = ST.length; ( ST.elem[i].key! = key ); --i ); // 从后往前找 RETURN (i); // 找不到时,i 为 0 } // Search_Seq 3 顺序查找的性能分析在顺序查找算法中,ST.elem[i].key 表示第 i 个记录的关键字域,ST.length 表示静态查找表中记录的个数,key 为查找时的给定值 当查找成功时, 返回记录的序号, 反之则返回 0 在算法中, 利用 ST.elem[0].key=key, 简化了算法, 否则需要判断是否全部检测完毕 在此,ST.elem[0] 是 哨兵, 起到了监视哨的作用 就顺序查找算法的性能分析来说, 顺序查找不论给定值 key 为何, 若第 1 个记录符合给定值, 则只要比较 1 次 ; 若第 n 个记录符合给定值, 则要比较 n 次 那么 : 3

4 (1) 如果每个记录的查找概率相等, 且每次查找都是成功的, 即 Pi=1/ n, 则在等概率的情况下, 顺序查找的平均查找长度为 n 1 ASL= P ici = n i= 1 n i= 1 1 n + 1 n + 1 n i = n = n (2) 如果查找不成功, 则比较次数为 n 十 1 因此, 顺序查找算法的时间复杂度为 O(n) 顺序查找的优点是 : 算法简单且无论记录是否按关键字有序均可应用 顺序查找的缺点 : 平均查找长度较大, 当 n 很大时, 查找效率较低 折半查找折半查找 (binary search) 是对有序表的一种效率较高的线性查找, 也称二分查找 进行折半查找的静态查找表必须是有序的, 即静态查找表中的记录必须按关键字值递增的次序顺序排列, 且为顺序存储结构 1 方法描述折半查找的过程是 : 首先确定待查记录所在的范围 ( 区间 ), 然后逐渐缩小范围直至得到查找结果为止 假设指针 low 指向待查记录所在范围的下界 ( 即有序表中关键字值最小的记录 ), 指针 high 指向待查记录所在范围的上界 ( 即有序表中关键字值最大的记录 ), 指针 mid 指向待查记录所在范围的中间位置, 即 mid= (low + high)/2 先用给定值 key 与 mid 指定的值相比, 若相等, 则表示查找成功 若不相等, 此时存在如下两种情况 : key 值小于 mid 所指的值, 说明待查元素的位置在 low 和 mid 之间, 则令指针 high= mid-1, 在表的前半部分再取中间位置的记录进行比较 ; key 值大于 mid 所指的值, 说明待查元素的位置在 mid 和 high 之间, 则令指针 low= mid+1, 在表的后半部分再取中间位置的记录进行比较 如此反复进行, 直至找到或找完全表而找不到为止 2 算法设计算法 <8.2> < 折半查找 > int Search_Bin ( SSTable ST, KeyType key ) // 在有序表 ST 中折半查找其关键字等于 key 的数据元素 // 如果找到, 则函数值为该元素在表中的位置, 否则为 0 { low = 0; high = ST.length; // 置区间初值 WHILE ( low <= high ) { mid = ( low + high ) / 2; IF ( key== ST.elem[mid].key ) RETURN (mid); // 找到待查记录 ELSE IF ( key < ST.elem[mid].key ) high = mid 1; // 继续在前半区间进行查找 ELSE 4

5 low = mid + 1; // 继续在后半区间进行查找 END IF } END WHILE RETURN (0); // 有序表中不存在待查记录 } //Search_Bin 3 应用例 : 对有 11 个记录的有序表, 其关键字依次为 (10,15,18,20,26,28, 33,36,38,43,48), 对于给定值 18 和 39 时, 进行折半查找的过程分别如下所示 (1) 查找 18 的过程 1 初始时,low=0,high=10,mid= ( ) / 2 =5 10, 15, 18, 20, 26, 28, 33, 36, 38, 43, 48 low mid high 2 当 key=18 时, 小于 ST.elem[mid].key=28, 说明 key 值应在 low 与 mid-1 区间内, 则令 high=5-1=4, 再令 mid= ( 0 + 4) / 2 =2, 此时 ST.elem[mid].key=18, 与给定值相等, 查找成功 10, 15, 18, 20, 26, 28, 33, 36, 38, 43, 48 low mid high (2) 查找 39 的过程 1 初始时,low=0,high=10,mid= ( ) / 2 =5 10, 15, 18, 20, 26, 28, 33, 36, 38, 43, 48 low mid high 2 key=39 时, 大于 ST.elem[mid].key=28, 说明 key 值应在 mid+1 与 high 区间内, 则令 low=5+1=6,mid= ( ) / 2 =8 10, 15, 18, 20, 26, 28, 33, 36, 38, 43, 48 low mid high 3 因为 key 大于 ST.elem[mid].key=38, 则令 low=8+1=9,mid= ( ) / 2 =9 10, 15, 18, 20, 26, 28, 33, 36, 38, 43, 48 low mid high 4 这时 key 小于 ST.elem[mid].key=43, 令 high=9-1=8<low, 从而 5

6 查找不成功 10, 15, 18, 20, 26, 28, 33, 36, 38, 43, 48 high low mid 4 折半查找的性能分析折半查找算法的时间复杂度可以用二叉树来进行分析 图 9-1 是一棵描述查找过程的二叉树, 树中每个结点表示一个记录, 结点的编号为该记录在表中的位置 找到一个记录的过程就是走了一条从根结点到该记录结点的路径, 和给定值进行比较的次数正好是该结点所在的层次数 图 8-1 描述折半查找过程的判定树由此可见, 在图 8-1 中有 11 个记录的有序表中, 查找编号为 5 的关键字时, 因为处于第一层上, 比较次数为 1; 查找编号为 2 8 的关键字时, 因为处于第二层上, 比较次数为 2 因此, 折半查找在查找成功时比较关键字的 次数最多不超过树的深度, 而具有 n 个结点的二叉树的深度为 log 2 n +1 所以, 折半查找在查找成功时和给定值进行比较的关键字的个数至多为 log 2 n +1 同理, 查找不成功的过程也是走了一条从根结点到某一个终端 结点的路径 在查找概率相同的情况下,Pi=1/n, 查找成功的平均查找长度为 n n + 1 ASL= P ici = log 2 ( n + 1) 1 log 2 ( n + 1) 1 n i= 1 因此, 折半查找算法的时间复杂性度 O(log2n) 折半查找的优点是 : 折半查找算法比顺序查找算法的平均查找长度小, 查找速度快 折半查找的缺点是 : 折半查找只限于顺序存储结构的有序表 例 : 画出对长度为 10 的有序表 (10,20,30,40,50,60,70,80,90,100) 进行折半查找的判定树, 并求出其等概率时查找成功的平均查找长度 解 : 判定树共 4 层 : 第 1 层表示比较一次可以查到的结点有 1 个, 第 2 层表示比较两次可以查到的结点有 2 个, 第 3 层表示比较 3 次可以查到的结点有 4 个, 第 4 层表示比较 4 次可以查到的结点有 3 个 对应的折半查找的判定树如图 8-2 所示 6

7 图 8-2 折半查找的判定树计算等概率时查找成功的平均查找长度为 ( )/10=29/ 索引顺序表的查找索引顺序表的查找又称为分块查找, 是顺序查找方法的另一种改进 1 分块查找的操作分块查找特点是 : 按照表内记录的某种属性把表分成 n(n>1) 个块 ( 子表 ), 并建立一个相应的 索引表, 索引表的每个元素对应一个块, 其中包括该块内最大关键字值和块中第一个记录位置的地址指针 而且按其关键字有序或者按块有序, 即一个块中所有记录的关键字值都应该比前一个块中所有记录的关键字值大, 而在一个块内关键字值的大小可以无序 分块查找过程可以分为两步 : 首先要在索引表中确定给定值所在的块 ; 其次在这个块中查找给定值 例如 : 图 8-3 中的线性表被分成 3 块, 每个块中有 5 个记录 图 8-3 一个线性表及其索引表 (1) 索引表中有序地存放每块的最大关键字值 :33,66,99 (2) 线性表中记录的关键字值用数组 ST.elem[i].key 表示, 其中 i 为记录的顺序号 若给定值 key=50, 那么首先将 key 值与索引表中的索引值相比较, 即与索引表中各块最大关键字值相比较, 由于 33<key<66, 所以可以确定 key 值如果存在的话, 应该在第 2 个块中 ; 然后, 由于 key 值所在块的地址指针指向块内第一个记录, 即是线性表中的顺序号为 5 的记录, 则 key 值应该在表中顺序号为 5 和 9 的记录之间 此时, 若在该块中顺序查找到与 key 值相等的关键字值, 由于 key=st.elem[6].key=50, 所以查找成功 ; 若在该块中找不到与 key 值相等的关键字值, 则查找不成功 另外, 需提醒读者注意的是, 由于索引表是按关键字值有序排列的, 所以确定块的查找既可以用顺序查找, 也可以用折半查找 ; 而块中的记录可以 7

8 是任意排列的, 则在块内的查找只能是顺序查找 2 分块查找的性能分析在分块查找中, 一般可以将表长为 n 的静态查找表分成 b 块, 第 1 个块 至第 b-1 个块每块的记录数为 s= n / b, 第 b 个块的记录数等于或小于 s; 若 表中每个记录的查找概率相等, 则每个块的查找概率为 1/b, 块中每个记录的查找概率为 1/s 此时, 分块查找的平均查找长度为 : 查找索引表确定值所在块的平均长度 + 在块内查找关键值的平均长度 (1) 如果用顺序查找确定所在块, 则分块查找的平均长度为 b s 1 1 b + 1 s n ASL= j + i = + = ( + s) + 1 b s s j= 1 i= 1 此时, 若 s=(n) 1/2, 则可以得到 ASL 的最小值 (n) 1/2 +1 (2) 如果用折半查找确定所在块, 则分块查找的平均长度为 : n s ASL log 2( + 1) + s 树表的查找 二叉排序树 1 二叉排序树的定义二叉排序树 (Binary Sort Tree) 又称二叉查找树 (Binary Search Trees), 简称 BST 其定义为 : 二叉排序树或者是空树, 或者是满足下列性质的二叉树 (1) 若左子树不空, 则左子树上所有结点的值都小于其根结点的值 ; (2) 若右子树不空, 则右子树上所有结点的值都大于 ( 若允许具有相同值的结点存在, 则大于等于 ) 其根结点的值 ; (3) 左 右子树分别也是一棵二叉排序树 上述定义是以递归的方式来定义二叉排序树的, 按此定义, 也就是说一棵二叉排序树中每一个结点的值都大于其左子树上所有结点的值, 而且小于其右子树上所有结点的值 如图 8-4 所示的就是一棵二叉排序树 根据二叉排序树的定义, 我们可以推出它的一个重要性质 : 按照中序遍历一棵二叉排序树所得到的结点的序列是一个递增序列, 如图 9-4 所示的二叉排序树的中序序列为 :1,3,5,6,8,9, 是一个递增有序序列 图 8-4 二叉排序树 2 动态查找表的二叉链表存储结构 typedef struct { // 二叉链表存储结构定义 ElemType data; // 数据域 Struct BSTNode lchild,rchild; // 左 右孩子指针域 }BSTNode, *BiTree; // 二叉链表存储结构类型 8

9 名 3 查找算法假设要查找关键字等于 key 的记录, 根据二叉排序树的性质, 首先令 key 与根结点的关键字进行比较, 若相等则表示找到, 查找成功 如果 key 值小于根结点的关键字 则往左子树去查找, 否则往右子树查找 若沿着某条路径碰到一个终端结点还未查到, 则查找不成功 算法如下 : 算法 <8.3> < 二叉排序树查找 > int SearchBST ( BiTree T, KeyType key, BiTree f, BiTree &p ) // 在根指针 T 所指二叉排序树中递归地查找某关键字等于 key 的数据元素 ; // 若查找成功, 则指针 p 指向该数据元素结点, 并返回 1; // 否则指针 p 指向查找路径上访问的最后一个结点并返回 0; // 指针 f 指向 T 的双亲, 其初始调用值为 NULL { IF (! T ) { p = f; RETURN (0); } // 查找不成功 ELSE IF ( key == T->data.key ) { p = T; RETURN (1); } // 查找成功 ELSE IF ( key < T->data.key ) // 在左子树中继续查找 SearchBST ( T->lchild, key, T, p ); ELSE SearchBST ( T->rchild, key, T, p ); // 在右子树中继续查找 END IF } // SearchBST 4 插入和构造算法在二叉排序树中插入一个新结点, 要保证插入后仍满足 BST 性质 因此在二叉排序树 T 中插入一个结点 e 时, 若二叉树为空, 则令结点 e 为插入后的二叉树的根结点 ; 否则将 e 的关键字与根结点的关键字进行比较, 若相等, 则说明树中已有此关键字的结点, 不需插入 ; 若 e.key<t->key, 则将 e 插入到 T 的左子树中, 否则插入到 T 的右子树中 这个过程与二叉排序树的查找过程基本相似, 算法描述如下 : 算法 <8.4> < 二叉排序树的插入 > int InsertBST ( BiTree &T, ElemType e ) // 当二叉排序树 T 中不存在关键字等于 e.key 的数据元素时, // 插入 e 并返回 TRUE, 否则返回 FALSE { IF (! SearchBST ( T, e, NULL, p ) ) // 查找不成功 9

10 { s = ( BiTree ) malloc(sizeof( BSTNode ) ); s->data = e; s->lchild = NULL; s->rchild = NULL; IF (! p ) T = s; // 被插结点 *s 为新的根结点 ELSE IF ( e.key < p->data.key ) p->lchild = s; // 被插结点 *s 为左孩子 ELSE p->rchild = s; // 被插结点 *s 为右孩子 END IF RETURN (1); } ELSE RETURN(0); // 树中已有关键字相同的结点, 不再插入 END IF } // InsertBST 需要说明的是 : 构造一棵二叉排序树, 实际上就是调用上述的插入算法向一棵空树中插入若干个结点, 即可以构造一棵二叉排序树 平衡二叉树从前面的讨论可知, 二叉排序树是一种查找效率比较高的组织形式, 可是二叉排序树平均查找长度的大小受树的形态的影响很大 当树的形态是比较均衡时查找效率很好, 而当树的形态明显偏向某一个方向时查找效率就会大大降低, 这是我们所不期望的. 因此我们希望找到一种更好的二叉排序树, 它的形态总是均衡的, 使得在它上面查找时总能得到最好的效率, 这就是平衡二叉排序树 1 平衡二叉树的定义平衡二叉树 (balanced binary tree 或 height-balanced tree) 是在 1962 年由 Adelson-Velskii( 艾德尔森 维尔斯基 ) 和 Landis( 兰迪斯 ) 提出的, 所以又称 AVL 树 平衡二叉树或者是一棵空树, 或者是满足下列性质的二叉树 : (1) 左子树深度与右子树深度之差的绝对值不大于 1; (2) 左子树和右子树都是平衡二叉树 我们把二叉树上一个结点的左子树的深度减去它的右子树的深度定义为该结点的平衡因子 (balance factor) 因此平衡二叉树上每个结点的平衡因子只可能是 1 或 -1 或 0 只要二叉树上有一个结点的平衡因子的绝对值大于 1, 则该二叉树是不平衡的 反过来我们可以推证 : 如果二叉树中每个结点的平衡因子的绝对值小于等于 1, 则该二叉树一定是平衡二叉树 如图 8-7(A) 所示为一棵平衡二叉树, 而 8-7(B) 所示为一棵不平衡二叉树, 图中数字为该结点的平衡因子 10

11 (A) 平衡二叉树 (B) 非平衡二叉树图 8-7 平衡二叉树与非平衡二叉树示例如果一棵二叉树既是二叉排序树, 又是平衡二叉树, 则称这棵二叉树为平衡二叉排序树 (Balance Binary Sort Trees), 如图 8-8 所示就是一棵平衡二叉排序树 图 8-8 平衡二叉排序树因为 AVL 树上任何结点的左子树和右子树的深度之差都不超过 1, 因此可以证明它的深度和 log2n 是同数量级的 ( 其中 n 为结点个数 ) 由此, 它的平均查找长度和 log2n 为同一数量级 2 平衡二叉树的调整在对平衡二叉排序树进行插入或删除一个结点后, 通常会影响到从根结点到插入结点的路径上的某些结点 以插入结点为例, 这种影响有三种 : 一是以某些结点为根的子树的深度发生变化 ; 二是某些结点的平衡因子发生变化 ; 三是某些结点失衡 很显然, 当对某个结点, 出现第一种影响时, 该结点的平衡因子也会发生变化, 也存在第二种影响 ; 而当出现第二种影响时, 则说明该结点的左子树或右子树的深度发生了变化, 因此从该结点到插入结点的路径上的各个结点的平衡因子和子树的深度都要发生变化, 但以该结点为根的子树深度未必会发生变化 ; 但当一个结点失衡时, 那么该结点的平衡因子和子树深度都会发生变化 平衡化旋转是从离插入或删除位置最近的失衡结点的位置开始调整的 一般情况下, 假定由于在二叉排序树上插入结点而失去平衡的最小子树的根结点指针为 a( 即 a 是离插入结点最近, 且平衡因子绝对值超过 1 的祖先结点 ), 则失去平衡后进行调整的规律可归纳为下列四种情况 (1)LL 型平衡旋转方法这种情况是由于在结点 a 的左孩子的左子树上插入结点, 而使结点 a 失去平衡在插入结点前是平衡的, 故 a 在插入结点前的平衡因子是 1, 而插入结点后变成为 2 设 b 为 a 的左孩子, 那么 b 的平衡因子也会发生变化 由于是在 b 的左子树上插入结点, 且 b 在插入结点前是平衡的, 则 b 在插入前的平衡因子只能是 0 如果插入前是 1, 当在 b 的左子树上插入一个结点后 b 的平衡因子就会变成 2,b 就失去平衡了, 这与 a 是失去平衡的最小子树的根结点不符 ; 如果是 -1, 当在 b 的左子树上插入一个结点后, 并不能改变以 b 为根结点的子 11

12 树深度, 则 a 应该维持平衡. 故插入后 b 的平衡因子只能是 l 此时平衡化旋转的方法是进行一次顺时针旋转操作, 如图 9-9 所示, 即用 b 取代 a 的位置,a 作为 b 的右子树的根结点,b 原来的右子树作为 a 的左子树 图 8-9 LL 型平衡旋转示意图我们来看看经过 LL 旋转后各个结点的平衡因子 : 若设插入后 b 的左子树的深度为 HbL, 此时 b 的右子树的深度为 HbR=HbL-1, 并且 a 的左子树的深度为 HbL+1 由于 a 的平衡因子为 2, 所以 a 的右子树的深度为 HaR=HaL-2=HbL-1 在旋转后 a 的右子树没有变, 左子树为 b 原来的右子树, 故 a 的平衡因子为 HbR-HaR=0, 所以 a 是平衡的 此时以 a 为根结点的子树的深度为 HbL,b 的左子树没有变化, 右子树以 a 为根结点, 故此时 b 的平衡因子为 0, 所以 b 也是平衡的, 并且以 b 为根结点的子树的深度为 HbL+1, 这正好与插入前的 a 子树深度相同, 因此该子树的上层结点的平衡因子没有变化, 即整个二叉树现在是平衡的 (2)RR 型平衡旋转方法在结点 a 的右子树的右子树上插入结点, 而使结点 a 失去平衡, 则要进行一次逆时针旋转操作, 如图 8-10 所示, 即用 b 取代 a 的位置,a 作为 b 的左子树的根结点,b 原来的左子树作为 a 的右子树 这种情况与 LL 型平衡旋转是对称的, 而且相对比较简单, 在此不作更详细的讨论了 图 8-10 RR 型平衡旋转示意图 (3)LR 型平衡旋转方法这种情况是由于在结点 a 的左子树的右子树上插入结点, 而使结点 a 失去平衡 插入结点前的平衡因子是 1, 而插入结点后变成为 2 设 b 为 a 的左孩子,c 为 b 的右孩子, 由于 b 在插入前和插入后都是平衡的, 如果插入前 b 的平衡因子是 1, 则在 b 的右子树上插入一个结点将不会改变 b 子树的深度, 也就不会失去平衡, 这与 a 失去平衡是不符的 : 如果插入前 b 的平衡因子是 -1, 则在 b 的右子树上插入一个结点后,b 的平衡因子会变成 -2, 失去平衡 故在插入结点前 b 的平衡因子只能是 0, 插入后 b 的平衡因子变为 -1 同样可以推出插入前 c 的平衡因子只能是 0, 否则 c 会失 12

13 衡或者 c 的深度不会变化 而插入后 c 的平衡因子的变化有下列三种情况 (1) 插入后 c 的平衡因子为 1, 即在 c 的左子树上插入 设此时 c 的左子树的深度为 l, 则 c 的右子树的深度为 HcL-1 由于 b 的平衡因子是 -1, 故 b 的左子树的深度是 HcL, 子树 b 的深度为 HcL+2 由于 a 的平衡因子是 2, 则 a 的右子树的深度为 HcL (2) 插入后 c 的平衡因子为 0, 即 c 本身是插入结点 设此时 c 的左子树的深度为 HcL 则 c 的右子树的深度也为 HcL 由于 b 的平衡因子是 -1, 故 b 的左子树的深度是 HcL, 而子树 b 的深度为 HcL+2 由于 a 的平衡因子是 2, 则 a 的右子树的深度为 HcL (3) 插入后 c 的平衡因子为 -1, 即在 c 的右子树上插入 设此时 c 的左子树的深度为 HcL, 则 c 的右子树的深度为 HcL+1 由于 b 的平衡因子是 -1, 故 b 的左子树的深度是 HcL+1 由于 a 的平衡因子是 2, 则 a 的右子树的深度为 HcL+1 此时先以 b 进行一次逆时针旋转, 即先将以 b 为根的子树旋转为以 c 为根, 再进行以 a 进行一次顺时针旋转, 即将整个子树旋转为以 c 为根,c 的右子树移到 a 的左子树的位置上,c 的左子树移动到 b 的右子树的位置上 如图 8-11 所示 图 8-11 LR 型平衡旋转示意图下面我们依据前面的分类来看看旋转后各个结点的平衡因子的情况 (1) 若旋转前 c 的平衡因子为 1, 则旋转后 a 的右子树没有变化, 左子树是 c 原来的右子树, 故 a 的平衡因子为 -1;b 的左子树没有变化, 右子树是 c 原来的左子树, 故 b 的平衡因子为 0;c 的左右子树分别是以 b 和 a 为根的子树, 故 c 的平衡因子为 0 (2) 若旋转前 c 的平衡因子为 0, 同样道理, 我们很容易利用前面求出的各个子树的深度求出旋转后 a b c 的平衡因子都为 0 (3) 若旋转前 c 的平衡因子为 -1, 旋转后 a 的平衡因子为 0,b 的平衡因子为 1,c 的平衡因子为 0 在此也可以验证整棵树的深度没有变化 因此上层结点都不需要调整 (4)RL 型平衡旋转方法这种情况是由于在结点 a 的右孩子的左子树上插入结点, 而使结点 a 失去平衡, 它与 LR 旋转情况正好是对称的 插入前 a 的平衡因子为 -1, 而插入结点后变为 -2 设 b 为 a 的右孩子,c 为 b 的左孩子, 由于 b 在插入前和插入后都是平衡的, 故在插入前 b 的平衡因子只能是 0, 插入后变为 1 我们依据插入后 c 的平衡因子的不同分情况讨论 (1) 插入后 c 的平衡因子为 1 设此时 c 的左子树的深度为 HcL, 则 c 的右子树的深度为 HcL-1 由于 b 的平衡因子是 1, 故 b 的右子树的深度是 HcL 13

14 由于 a 的平衡因子是 -2, 则 a 的左于树的深度为 HcL (2) 插入后 c 的平衡因子为 0 设此时 c 的左子树的深度为 HcL, 则 c 的右子树的深度为 HcL 由于 b 的平衡因子是 1, 故 b 的右子树的深度是 HcL 由于 a 的平衡因子是 -2, 则 a 的左子树的深度为 HcL (3) 插入后 c 的平衡因子为 -1 设此时 c 的左子树的深度为 HcL, 则 c 的右子树的深度为 HcL+1 由于 b 的平衡因子是 1, 故 b 的右子树的深度是 HcL 由于 a 的平衡因子是 -2, 则 a 的左子树的深度为 HcL+1 RL 型旋转先要进行一次顺时针旋转操作, 即先将以 b 为根的子树旋转为以 c 为根, 再进行一次逆时针旋转操作, 即将整个子树旋转为以 c 为根,c 的右子树移到 b 的左子树的位置上,c 的左子树移动到 a 的右子树的位置上 如图 8-12 所示 图 8-12 RL 型平衡旋转示意图下面我们依据前面的分类来看看旋转后各个结点的平衡因子的情况 (1) 若旋转前 c 的平衡因子为 1, 那么旋转后 a 的平衡因子为 0,b 的平衡因子为 -1,c 的平衡因子为 0 (2) 若旋转前 c 的平衡因子为 0, 旋转后 a b c 的平衡因子都为 0 (3) 若旋转前 c 的平衡因子为 -1, 旋转后 a 的平衡因子为 1,b 的平衡因子为 0,c 的平衡因子为 0 容易验证此时整棵子树的深度不变 B - 树和 B + 树 1 B - 树的定义一棵 m 阶 B - 树, 或者是空树, 或者是满足如下性质的 m 叉树 : (1) 根结点或者为叶子, 或者至少有两棵子树, 至多有 m 棵子树 ; (2) 除根结点外, 所有非终端结点至少有 m / 2 棵子树, 至多有 m 棵 子树 ; (3) 所有叶子结点都在树的同一层上 ; (4) 每个结点中应包含如下信息 : (n, A0,K1,A1,K2,A2,,Kn,An) 其中 :Ki(1 i n) 为关键字, 且 Ki<Ki+1(1 i n-1), 即关键字递增有序 ; Ai(0 i n) 为指向子树根结点的指针, 且 Ai 所指子树中所有结点的关键字均小于 Ki+1,An 所指子树中所有结点的关键字均大于 Kn ; n 为结点中关键字的个数, 满足 m / 2-1 n m-1( 当该结点为根时满足 2 n m-1), 显然 n+1 为子树个数 14

15 例如图 8-13 是一棵包含 13 个关键字的 4 阶 B - 树 图 8-13 一个 4 阶 B - 树 2 B - 树的查找由 B - 树的定义可知, 在 B - 树上进行查找的过程和二叉排序树的查找相似 例如, 在图 8-13 所示的 B - 树上查找关键字 42 的过程如下 : 首先从根开始, 根据根指针 t 找到 a 结点, 因为给定值 42 大于关键字 32, 若给定值存在, 则必在指针 A1 所指的子树内 ; 顺指针找到 c 结点, 因为给定值 42 小于 64, 大于 40, 则顺时针找到 g 结点, 在该结点中顺序查找, 找到关键字 42, 查找成功 查找不成功的过程也类似 例如在同一棵 B - 树上查找关键字 23 的过程如下 : 首先从根结点开始, 因为给定值 23 小于 32, 则顺根结点中指针 A0 找到 b 结点, 又因为 b 结点中只有一个关键字 16, 且 23 大于 16, 所以顺结点中第二个指针 A1, 找到 e 结点 同理, 因为 23 小于 28, 则顺指针往下找, 此时因为指针所指为叶子结点, 说明此棵 B - 树中不存在关键字 23, 查找失败 由此可见, 在 B - 树上进行查找的过程是一个顺指针查找结点和在结点的关键字中进行查找交叉进行的过程 3 B - 树的插入将关键字 k 插入到 m 阶 B - 树中去, 必须保证插入后的树仍然是 m 阶 B - 树 插入的方法是 : 首先在 B - 树中查找关键字 k, 若找到, 则说明该关键字已经存在, 直接返回 ( 假定不插入相同的关键字 ); 否则查找操作必失败于某个最低层的非终端结点上, 将 k 插入到该结点中, 若该结点的关键字个数小于 m-1( 即该结点的分枝小于 m, 是不满的 ), 则将关键字 k 直接插入该结点中 ; 若该结点的关键字个数等于 m-1, 则将该结点 分裂 为两个结点, 分裂的具体做法如下所述 假设待分裂结点 p 包含的信息为 (m,a0,k1,a1,k2,a2,,km,am) 则将它从中间位置划分为两个结点 : ( m / 2-1,A0,K1,A1,K2,A2,,K m / 2 1,Am / 2 1 (m- m / 2,A m / 2,K m / 2 +1,A m / 2 m ) +1,,Km,Am) 并将中间关键字 K m / 2 插入到 p 的父结点中, 以分裂后的两个结点作 15

16 为关键字 K m / 2 的左边和右边的孩子 由于将关键字 K m / 2 插入到 p 的父结点后, 父结点也可能不满足 m 阶 B - 树的要求 ( 分枝数大于 m), 此时亦需对父结点进行分裂 这样一直向上分裂时, 因为没有父结点, 故建立一个新的根, 此时树增高一层 例如在一个 3 阶 B - 树 ( 如图 8-14a) 上插入结点 65,24,50 和 38, 则 B - 树的变化过程如图 8-14b~h 所示 图 8-14 在 B - 树中进行插入的过程在 3 阶 B - 树中, 每个结点的关键字个数最少为 1, 最多为 2, 当插入后关键字的个数为 3 时, 就得分裂成两个结点, 让原有结点只保留第一个关键字和它前后的两个指针, 让新分配的结点保存原有结点中的最后一个 ( 即第 3 个 ) 关键字和它前后的两个指针, 让原有结点的第 2 个关键字和指向新结点的指针作为新结点的索引项插入到原有结点的前驱结点中, 若没有前驱结点, 则生成一个新的树根结点, 然后再插入 4 B - 树的删除若在 B - 树上删除一个关键字 k 也和在二叉排序树上类似, 都首先要经过一个从树根结点到待删除关键字所在结点的查找过程, 然后再分情况进行删 16

17 除 若被删除的关键字在最低层的非终端结点中, 则直接从该结点中删除之, 否则首先要将被删除的关键字同它的中序前驱关键字 ( 即它的左边指针所指子树的最右下结点中的最大关键字 ) 或中序后继关键字 ( 即它的右边指针所指子树的最左下结点中的最小关键字 ) 进行对调, 然后再从对应的结点中删除之 例如 : 若从图 8-14h 中删除关键字 46 时, 首先要将它与中序前驱关键字 38 或中序后继关键字 50 对调, 然后再从对调后的结点中删除关键字 46 从 B - 树上一个结点中删除一个关键字后, 使得该结点的关键字个数减 1, 此时应分以下三种情况进行处理 : (1) 若删除后该结点的关键字个数 n m / 2 在图 9-14a 中删除关键字 18 或 32 时就属于这种情况 (2) 若删除后该结点的关键字个数 n< m / 2-1, 则删除完成 例如 -1, 它的左兄弟 ( 或右 兄弟 ) 结点中的关键字个数 n> m / 2-1, 则首先将双亲结点中的指向该结点 指针的左边 ( 或右边 ) 一个关键字下移至该结点中, 接着将它的左兄弟 ( 或右兄弟 ) 结点中的最大关键字 ( 或最小关键字 ) 上移至它们的双亲结点中刚空出的位置上, 然后再将左兄弟 ( 或右兄弟 ) 结点中的 An 指针 ( 或 A0 指针 ) 赋给该结点的 A0 指针域 ( 或 An 指针域 ) 例 1: 从图 8-14a 中删除关键字 58 后需首先把 46 下移至被删除关键字 58 的结点中, 接着把它的左兄弟结点中的最大关键字 32 上移至原 46 的位置上, 然后把左兄弟结点中的原 A2 指针 ( 即为空 ) 赋给被删除关键字 58 结点的 A0 指针域, 得到 B - 树如图 8-15a 所示 例 2: 从图 8-14d 中删除关键字 32 后, 需首先把双亲结点中的 46 下移至该结点中, 接着把右兄弟结点中的最小关键字 58 上移至双亲结点中刚空出的位置上, 然后把右兄弟结点的原 A0 指针 ( 即为空 ) 赋给被删除关键字 32 结点的 A1 指针域, 删除结果如图 8-15b 所示 图 8-15 B - 树的删除 (3) 若删除后该结点的关键字个数 n< m / 2-1, 同时它的左兄弟和右兄 弟 ( 若有的话 ) 结点中的关键字个数均等于 m / 2-1, 在这种情况下, 就无 法从它的左 右兄弟中通过双亲结点调剂到关键字以弥补自己的不足, 此时就必须进行结点的 合并, 即将该结点中的剩余关键字和指针连同双亲结点中指向该结点指针的左边 ( 或右边 ) 一个关键字一起合并到左兄弟 ( 或右兄弟 ) 结点中, 然后回收 ( 即删除 ) 掉该结点 17

18 例如 : 从图 8-15b 所示的 3 阶 B - 树中删除关键字 46 后, 该结点 ( 即被删除关键字 46 的结点 ) 中剩余的关键字个数为 0, 低于规定的下限 1, 但它的左兄弟和右兄弟中的关键字个数都只有一个 ( 即为最低限 ), 所以只能将该结点中剩余的关键字 ( 在此没有 ) 和指针 ( 在此为空 ) 连同双亲结点中的关键字 24 一起合并到左兄弟结点中, 然后将包含被删除关键字 46 的结点回收掉, 删除 46 后得到的 B - 树如图 8-15c 所示 当从一棵 B - 树的最低层的非终端结点中删除一个关键字后, 可能出现上面所述的第 3 种情况, 此时需要合并结点, 在合并结点的同时, 实际上又从它们的双亲结点中删除 ( 即因合并而被下移 ) 了一个关键字, 而双亲结点被删除一个关键字后, 同从叶子结点中删除一个关键字一样, 又可分为上面所述的三种情况处理, 当属于第 3 种情况时, 又需要进行合并, 以此类推 在最坏的情况下, 这种从叶子结点开始的合并要一直传递到树根结点, 使只包含有一个关键字的根结点同它的两个孩子结点合并, 形成以一个孩子结点为根结点的 B - 树, 从而使整个 B - 树的高度减少 l 例如, 假定图 8-16a 是一棵 5 阶的 B - 树, 则树中每个结点 ( 除树根结点外 ) 的关键字个数应最少为 2, 最多为 4 当从该树中删除关键字 26 时, 应首先把它与中序前驱关键宇 20 对调位置, 然后再从对应的结点 e 中删除之, 删除 26 后得到的中间结果如图 9-16b 所示 ;e 结点被删除一个关键字后只剩下一个关键字, 低于下限值 2, 它的左 右兄弟结点中正好只有最低的关键字个数 2, 所以必须把该结点中的一个关键字 15 和左 右两个空指针同 b 结点中的关键字 12( 或 20) 一起合并到 d 结点 ( 或 f 结点 ) 中, 得到的中间结果如图 8-16c 所示 (e 结点已被回收 );b 结点被删除一个关键字 12 后, 只剩下一个关键字 20, 同时它的右兄弟 ( 没有左兄弟 ) 结点中只含有两个关键字, 所以又得继续合并, 即把 b 结点中的一个关键字和两个指针同根结点 a 的一个关键字一起合并到 c 结点中, 使 c 结点成为新的树根结点, 导致整个 B - 树减少一层, 最后得到的结果如图 8-16d 所示 (b 结点和 a 结点都已回收 ) 18

19 图 8-16 在 5 阶 B - 树中进行删除的过程 5 B + 树前面提到的 B - 树对于组织大型文件系统是很有用的, 但在实际文件系统中几乎不使用 B - 树, 而普遍使用的是 B - 树的一种变体, 称为 B + 树 它与 B - 树最显著的不同是 B + 树只在叶子结点中存储记录 ( 或记录指针 ) 在 B + 树中, 所有的非终端结点可以看成是索引部分, 非终端结点中的关键字作为 分界关键字, 用来界定某一关键字的记录所在的子树 如图 8-17 所示为一棵 3 阶 B + 树 通过对比可以发现一棵 m 阶 B + 树与 m 阶 B - 树的差异在于 : (1) 如果一个结点有 n 棵子树, 那么它含有 n 个关键字 (2) 所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针, 而且叶子结点按关键字的大小从小到大顺序链接 19

20 (3) 所有的非终端结点可以看成是索引的部分, 结点中只含有其子树的根结点中最大 ( 或最小 ) 关键字 图 8-17 一棵 3 阶 B + 树示例与 B - 树相比, 在 B + 树上不仅可以从根结点开始, 按关键字进行随机查找, 而且可以从最小关键字起, 按叶子结点的链接顺序进行顺序查找 在 B + 树上进行随机查找 插入及删除的过程基本上与 B - 树类似 在 B + 树上做随机查找时, 若非终端结点上的关键字等于给定值 k, 并不终止, 而是继续向下直到查找到叶子结点 因为只有叶子结点中才存储有记录 ( 或记录指针 ) 所以, 在 B + 树上进行查找, 不管成功与否, 都是走一条从根结点到叶子结点的一条路径 在 B + 树上插入关键字时, 仅仅在叶子上进行 当叶子结点中的关键字个数大于 m 时, 要分裂成两个结点, 这两个结点中所含有的关键字个数分别是 m + 1 m 和 2, 并且将这两个结点中提升到最大关键字父结点中, 用它 们替代原结点在双亲中所对应的关键字 当然提升后可能会引起父结点分裂, 依此类推, 最后可能会引起根结点分裂, 从而使 B + 树增加一层 如图 9-17 所示的 B + 树中插入关键字 61 后, 得到的 B + 树如图 9-18 所示 图 8-18 在图 8-17 的 B + 树中插入 61 后的 B + 树在 B + 树上删除关键字时, 也仅在叶子结点上进行 当叶子结点中最大的关键字被删除时, 其非终端结点中的值可以作为一个分界关键字存在 若因 删除而使叶子结点中的关键字个数少于 m / 2 时, 则从兄弟结点移动一个多 余的关键字或与兄弟结点合并, 这个过程也和 B - 树类似 散列表 8.4 散列表 20

21 散列表, 又称杂凑表 哈希表, 是一种非常实用的查找表 1 散列函数及散列表实际上, 最理想的情况是希望不经过任何比较, 一次访问就能得到所查的记录, 那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系, 使每个关键字和结构中一个惟一的存储位置相对应 因而在查找时, 给定值 key 根据这个对应关系就能找到记录的位置 如果存在关键字和给定值相等的记录, 则必定在此存储位置上, 由此, 不需要进行比较便可以直接取得所查记录 我们称这个对应关系为散列函数, 或者哈希 ( hash) 函数, 记为 hash() 这一构造过程称为散列, 或者哈希造表 按这个思想构造的表称为散列表, 或者哈希表 散列表能够进行快速查找 例如, 要将关键字值序列 {3,15,22,24}, 存储到编号为 0 到 4 的表长为 5 的散列表中 计算存储地址的散列函数可以采用除以 5 的取余数算法, 即 hash(key)=key % 5, 则散列表如图 9-19 所示 图 8-19 一个散列表由此可得如下概念 3 映像由散列函数得到的散列表是一个映像, 所以散列函数的设定比较灵活, 只要使任何关键字由散列函数所得的值都在散列表长允许的范围即可 4 冲突可能会出现两个不同的关键字 key1 和 key2, 它们的散列函数值相等 : hash(key1)=hash(key2) 并且 key1!=key2, 这种现象称为冲突 (collision) 5 同义词具有相同的函数值的关键字对该散列函数来说称为同义词 如上例, 当关键字值 key1=32 时, 可以产生散列地址值为 2; 而当关键字值 key2=22 时, 产生的散列地址值也为 2, 则称关键字 key1 和 key2 为同义词 6 均匀的散列函数如果散列函数使一组关键字得到的对应的散列地址, 能均匀分布在整个地址区间中, 从而减少冲突, 那么该散列函数被认为是均匀的 换句话说, 对于关键字集合中的任一个关键字, 经散列函数映像到地址集合中任一个地址的概率是相等的, 则为均匀的散列函数 由此可知散列函数设定合适就可以减少地址的冲突现象 然而, 在一般情况下, 冲突只能尽可能地减少, 而不能完全避免, 因为散列函数是关键字集合到地址集合的映像 通常, 关键字集合的元素包括所有可能的关键字, 而地址集合的元素仅为散列表中的地址值 假如散列表长为 n, 则哈希地址为 0~n-1 为了有效地使用散列技术, 需要解决下面两个问题 : (1) 找一个好的散列函数, 使出现冲突的机会尽可能少 ; (2) 设计有效的解决冲突的方法 散列函数的构造方法常用的构造散列函数的方法有以下 6 种 : 1 直接定址法 21

22 直接定址法取关键字值或关键字的某个线性函数值作为散列地址 如, hash(key)=key 或者 hash(key)=a*key+b, 其中 a 和 b 是常数 例如, 在人口统计中, 如果要统计从 1 岁 ~120 岁的人口数, 年龄为关键字, 取关键字本身为散列函数值, 如图 8-20(a) 所示 ; 如果要统计从 1949 年到今年出生的人口数字, 年份为关键字, 散列函数是 hash(key)=key+ (-1948), 如图 8-20(b) 所示 地址 年龄 人数 (a) 以年龄为关键字的散列表 地址 年份 人数 (b) 以年份为关键字的散列表 图 8-20 人口统计的散列表 显然, 如果所有元素的关键字都不相同, 则采用这种方法不会产生冲突 2 数字分析法 当关键字值的位数大于存储地址码 ( 散列地址码 ) 位数时, 对关键字值的 各位数字进行分析, 从中取出与散列地址位数相同的位 具体的做法是 : 舍 去数字分布不均匀的位, 取分布均匀的位作为地址 例如, 图 9-21 所示的是一组 7 位数字的关键字表, 散列地址位数为 2 位 关键字位数 图 8-21 一组关键字表对所有关键字 key 的 7 位数字分布进行分析, 可以看出关键字的第 位的数字介于 1~9 之间, 分布基本上是随机的 而第 1 位数字全是 1, 第 2 位数字集中在 7,8,9 三个数字上, 第 4 位数字集中在数字 0~2 之间, 第 6 位集中在 5,6,7 三个数字上, 所以可以取关键字的第 的任意 2 位数字组成散列地址, 也可以由这 3 位组成算术公式作为散列地址 数字分析法仅适用于当所有的关键字可能出现的值都是已知的情况下 在许多情况下, 构造散列函数的时候, 不一定能够事先知道关键字的全部情况, 那么使用数字分析法就不一定合适 3 取模法取模法, 又叫除留余数法, 也是比较简单的一种散列函数 它的思想是 : 22

23 将关键字值除以一个整数 m 后, 把所得的余数作为散列函数的值,m 叫做模, 这样定义的函数称为取模函数, 记为 hash(key)=key %m 例如, 对以下的 4 个关键字及其内部代码, 如果取 1000 为模, 则有图 9-22(a) 中的函数关系 显然, 这样取模的散列函数很容易导致 冲突 如果取 内部代码 的低三位为散列值时,key3 和 key4 的值都是 525, 便产生了冲突 理论分析和实验结果表明, 对于取模散列函数来说, 要尽可能避免 冲突, 一般取模 m 为素数 对上面的例子, 如果给出的存储区长度 Max=1000, 取模 m=997 为小于 Max 的最大素数, 则所得结果如图 9-22(b) 所示 关键字 内部代码 key MOD 1000 key key key key (a) 取模为 1000 关键字 内部代码 key MOD 997 key key key key (b) 取模为 997 图 8-22 取模法 4 平方取中法 其构造原则是, 先计算出关键字值的平方, 然后取它的中间几位作为散 列地址编码 例如, 对于图 9-22 中 4 个关键字值, 若将它们的内部代码自乘, 然后取其中间的 3 位作为散列函数的值, 则可以得到图 9-23 所示的结果 关键字 内部代码 内部代码的平方值 hash(key) key key key key 图 8-23 平方取中法 这种方法是要使关键字内部代码的每一位都在散列过程中起作用 ; 至于 取中间的几位和哪几位作为散列函数的值, 视具体情况而定 由于一个数平 方后的中间几位数和数的每一位都相关, 因此使随机分布的关键字得到的散 列地址也是随机的 5 折叠法 折叠法是将关键字分成位数相同的几部分, 然后取这几部分的叠加和 ( 舍 去进位 ) 作为散列地址的方法 这种方法适用于关键字位数很多, 而且关键 字中每一位上的数字分布基本均匀的情况 根据叠加方法的不同, 可以分为移位叠加法和折叠叠加法 移位叠加法 是将分割之后的每一部分的最低位对齐相加, 就像来回折叠纸条一样 例如, 23

24 设某关键字 key 的值为十进制数, 即 key=d1,d2,d3,,dr,dr+1,,d2r, d2r+1,,d3r, 要把 key 映射为 r 个十进制数表示的地址的散列函数, 如图 9-24 所示 d1,d2,d3,,dr,dr+1,,d2r,d2r+1,,d3r 第一段 第二段 第三段 (a) 将关键字分成三段 d1 d2 dr d1 d2 dr dr+1 dr+2 d2r d2r d2r-1 dr+1 + d2r+1 d2r+2 d3r + d3r d3r-1 d2r+1 (b) 移位叠加法 (c) 折叠叠加法 图 8-24 叠加法 例如, 国际标准图书编号 (ISBN) 是一个几位的十进制数字编码, 某藏 书种类小于 的图书馆采用叠加法来构造一个产生 4 位数地址的散列函 数 生成如下对于书号 ISBNO 图书其散列地址叠加过程如图 9-25 所示 图 9-25 叠加法的应用 6 随机数法随机数适用于关键字长度不等的情况 选择一个随机函数, 取关键字的随机函数值为它的散列地址, 即 hash(key)=random(key), 其中 random 为随机函数 综上所述, 构造较好的散列函数, 需要考虑的因素有 : (1) 计算散列函数的效率, 即所需要的时间 ( 包括硬件指令的因素 ); (2) 关键字的长度, 包括是否等长 ; (3) 散列表的大小 ; (4) 关键字的分布情况 ; (5) 记录的查找频率 冲突及其解决方法 常用的处理冲突的方法有 : 开放地址法 链地址法和再哈希法 1 开放定址法用开放定址法处理冲突就是当冲突发生时, 形成一个地址序列, 沿着这个序列逐个探测, 直到找到一个 空 的地址, 将发生冲突的记录值存放到该地址中去 例如, hashi=(hash(key)+d(i))% m,i=1,2,,k(k m-1) 其中 :hash(key) 为散列函数 ; m 为散列表长 ; d 为增量函数,d(i)=d1,d2,d3,,dn-1 24

25 增量序列的取法不同, 可以得到不同的处理方法 (1) 线性探测法此时增量函数为 d(i)=1,2,3, m-1,i 为探测次数 这种方法在解决冲突时, 依次探测下一个地址, 若仍冲突, 再探测下一个地址, 直至有空地址后插入, 若所有地址都找遍仍无空地址, 则产生溢出 例如, 在表长为 11 的散列表中有关键字值为 {29,17,60,38} 的记录, 构造散列函数 hash(key)=key % 11, 如图 9-26(a) 所示 有第 4 个记录, 其关键值为 38, 其散列函数值为 5, 与关键字 60 的散列地址相冲突 ; 采用线性探测法解决冲突时可以得到下一个地址 6, 与关键字 17 冲突 ; 再求下一个地址 7, 与关键字 29 相冲突 ; 直至地址 8 时, 才找到空的位置, 此时处理冲突的过程结束, 将记录填入散列表中序列为 8 的位置上, 如图 8-26(b) 所示 (2) 二次探测法这时增量函数为 d(i)=1 2,-1 2,2 2,-2 2,,±k 2 (k m/2) 例如, 对于图 9-26(a) 所示的表, 如果采用二次探测法解决关键字 38 的冲突, 则应填入散列地址为 4 的位置, 如图 9-26(c) 所示 (3) 伪随机探测法此时的增量函数 d(i) 为一个构造出的随机函数 例如, 对于图 9-26(a) 所示的表, 如果取伪随机函数为 d(i)=(d+p) % m, 其中 :m 为表长 11; d 的初始值为 hash(38)=5; p 为一个质数, 如果取 p=9, 则得到的散列地址为 (5+9) % 11=3 如图 9-26(d) 所示 (a) 插入前 (b) 线性探测法 (c) 二次探测法 (d) 伪随机探测图 8-26 开放定址法的应用 1 链地址法用链地址法解决冲突的方法是 : 把所有关键字为同义词的记录存储在一个线性链表中, 这个链表称为同义词链表, 即把具有相同散列地址的记录存放在同义词链表中 25

26 假如某散列函数产生的散列地址在 [0,m-1] 上, 用数组 s[m] 存放各个链表的头指针 当第 i 个散列地址中存在同义词时, 则将其插入到以 s[i] 为头指针的链表中去 在链表中的插入位置可以在表头或者表尾, 也可以插在中间 例如, 对于表长为 m=5, 散列函数为 hash(key)=key % 5, 关键字值序列为 {1,2,5,7,9,10} 的散列表而言, 用链地址法解决冲突构造的散列表如图 8-27 所示 图 8-27 链地址法的应用 3 再散列法用再散列法解决冲突可得到如下的地址序列 :hashi=rhashi(key),(i=1, 2,,k) 这个散列函数序列表示在产生冲突现象时, 计算另一个散列函数, 从而得到另一个散列地址, 直到冲突不再发生, 即 Rhashi 均为不同的散列函数 由此可知, 这种方法虽然可以解决冲突, 但增加了计算时间 散列表的查找及其分析 1 散列表的查找在散列表上进行查找的过程和散列造表的过程基本一致 (1) 给定 key 值, 根据造表时设定的散列函数求得散列地址 ; (2) 如果此散列地址上没有记录, 则查找不成功, 否则比较关键字 ; (3) 比较关键字有两种情况 : 若相等, 则查找成功 ; 若不相等, 则根据造表时设置的处理冲突的方法找下一地址, 直至某个位置上为空或关键字比较相等为止 2 散列表的查找分析从散列表的查找过程可见, 虽然散列表是在关键字和存储位置之间直接建立了映像, 然而由于 冲突 的产生, 散列表的查找过程仍然是一个和关键字比较的过程 因此, 仍需用平均查找长度来衡量散列表的查找效率 查找过程中与关键字比较的次数取决于散列造表时选择的散列函数和处理冲突的方法 散列函数的 好 与 坏 首先影响出现冲突的频率, 设散列函数是均匀的, 即它对同样一组随机的关键字出现冲突的可能性是相同的 因而, 散列表的查找效率主要取决于散列造表时处理冲突的方法 发生冲突的次数是和散列表的装填因子有关 装填因子是指散列表中已经被结点所占用的空间 ( 散列表中的记录数 ) 与散列表整个空间 ( 散列表的长度 ) 的比 即 散列表中的记录数 α= 散列表的长度 α 越大, 即表越满, 发生冲突的可能性越大, 查找时所用的比较次数也就越多 α 越小, 发生冲突的可能性就越小 通常取 α 为小于 1 而大于 1/2 26

27 的适当的数, 散列表查找成功的平均查找长度 Sn 和 α 有关 线性探测再散列的散列表查找成功时的平均查找长度为 1 1 Snl (1 + ) 2 1 α 伪随机探测再散列, 二次探测再散列以及再散列的散列表查找成功时的平均查找长度为 1 Snr - ln(1 + α) α 链地址法处理冲突的散列表查找成功的平均查找长度为 α Snc 1+ 2 散列表在查找不成功时有如下平均查找长度 线性探测再散列的散列表查找不成功时的平均查找长度为 (1 α)2 Unl (1 + ) 伪随机探测再散列, 二次探测再散列以及再散列法的散列表查找不成功时的平均查找长度为 1 Unr 1 α 链地址法处理冲突的散列表查找不成功时的平均查找长度为 Unc α+e -a 由上式可见, 散列表的平均查找长度是 α 的函数, 而不是表中记录数 n 的函数 因此, 不管表长多大, 总可以选择一个适合的装填因子以便将平均查找长度限定在一个范围内 正是由于这个特性, 散列法成为一种受欢迎的组织符号表的方法 例 1: 设有一组关键字 (17,13,14,153,29,35) 需要插入到表长为 12 的散列表中, 请回答如下问题 : (1) 设计一个适合该散列表的散列函数 ; (2) 用设计的散列函数将上述关键字插入到散列表中, 画出其结构, 并指出用线性探测法解决冲突时构造的散列表的装填因子为多少? 解 : (1) 由于散列表的长度为 12, 则可以选择不超过表长的最大素数 11 作为取模法的模, 则可以得到散列函数 hash(key)=key % 11 (3) 如果用线性探测法解决冲突, 则可以构造出散列表如图 9-28 所示 图 8-28 线性探测法 其中 ;1 3 表示线性探测的次数 此时, 散列表的装填因子为 : α=6/12=1/2 27