何谓查找表 ？ 查找表是由同一类型的数据元素(或记录)构成的集合。 由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。

对查找表经常进行的操作: 1）查询某个“特定的”数据元素是否在查找表中； 2）检索某个“特定的”数据元素的各种属性； 3）在查找表中插入一个数据元素； 4）从查找表中删去某个数据元素。

静态查找表 动态查找表 查找表可分为两类: 仅作查询和检索操作的查找表。 有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。

关键字 是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。 若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。 若此关键字能识别若干记录，则称 之谓“次关键字”。

查找 根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。 若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置； 否则称“查找不成功”。查找结果给出 “空记录”或“空指针”。

如何进行查找？ 由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。 查找的方法取决于查找表的结构。 为了提高查找的效率， 需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说， 用另外一种结构来表示查找表。

9.1 静态查找表 9.2 动态查找树表 9.3 哈希表

9.1 静 态 查 找 表

ADT StaticSearchTable { 据元素的集合。每个数 据元素含有类型相同的 关键字，可唯一标识数 据元素。 数据对象D： 数据关系R： 数据元素同属一个集合。

基本操作 P： Destroy(&ST); Search(ST, key); Traverse(ST, Visit()); Create(&ST, n); Destroy(&ST); Search(ST, key); Traverse(ST, Visit()); } ADT StaticSearchTable

Create(&ST, n); 构造一个含n个数据元素 的静态查找表ST。 操作结果：

Destroy(&ST); 初始条件： 操作结果： 静态查找表ST存在； 销毁表ST。

Search(ST, key); 初始条件： 操作结果： 静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；

Traverse(ST, Visit()); 初始条件： 操作结果： 静态查找表ST存在，Visit 是对元素操作的应用函数； 按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。

假设静态查找表的顺序存储结构为 typedef struct { // 数据元素存储空间基址，建表时 ElemType *elem; // 按实际长度分配，0号单元留空 int length; // 表的长度 } SSTable; ElemType *elem;

数据元素类型的定义为: typedef struct { keyType key; // 关键字域 … … // 其它属性域 … … // 其它属性域 } ElemType ; , TElemType ;

一、顺序查找表 二、有序查找表 三、静态查找树表 四、索引顺序表

一、顺序查找表 以顺序表或线性链表表示静态查找表

回顾顺序表的查找过程： k k ST.elem 假设给定值 e=64, 要求 ST.elem[k] = e, 问: k = ?

int location( SqList L, ElemType& e, Status (*compare)(ElemType, ElemType)) { k = 1; p = L.elem; while ( k<=L.length && !(*compare)(*p++,e))) k++; if ( k<= L.length) return k; else return 0; } //location

i i ST.elem 64 key=64 i i ST.elem 60 key=60

ST.elem[0].key = key; // “哨兵” 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

分析顺序查找的时间性能 (Average Search Length) 其中: n 为表长，Pi 为查找表中第i个记录的概率， 定义： 查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中: n 为表长，Pi 为查找表中第i个记录的概率， 且 　 ， Ci为找到该记录时，曾和给定 值比较过的关键字的个数。

对顺序表而言，Ci = n-i+1 ASL = nP1 +(n-1)P2 + +2Pn-1+Pn 在等概率查找的情况下， 顺序表查找的平均查找长度为：

在不等概率查找的情况下，ASLss 在 Pn≥Pn-1≥···≥P2≥P1 时取极小值 若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。

二、有序查找表 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。 但平均查找长度较大，特别不适用于表长较大的查找表。 上述顺序查找表的查找算法简单， 但平均查找长度较大，特别不适用于表长较大的查找表。 若以有序表表示静态查找表，则查找过程可以基于“折半”进行。

例如: key=64 的查找过程如下： low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2 ST.length ST.elem low low high high mid mid mid low 指示查找区间的下界 high 指示查找区间的上界 mid = (low+high)/2

int Search_Bin ( SSTable ST, KeyType key ) { low = 1; high = ST.length; // 置区间初值 while (low <= high) { mid = (low + high) / 2; if （EQ (key , ST.elem[mid].key) ) return mid; // 找到待查元素 else if ( LT (key , ST.elem[mid].key) ) high = mid - 1; // 继续在前半区间进行查找 else low = mid + 1; // 继续在后半区间进行查找 } return 0; // 顺序表中不存在待查元素 } // Search_Bin

分析折半查找的平均查找长度 6 3 9 4 7 1 10 5 8 2 11 先看一个具体的情况，假设：n=11 3 4 2 3 4 1 3 判定树 6 3 9 4 7 1 10 5 8 2 11

一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。 假设 n=2h-1 并且查找概率相等 则 在n>50时，可得近似结果

三、静态查找树表 例如: 在不等概率查找的情况下，折半查找不是有序表最好的查找方法。 关键字: A B C D E Pi: 0.2 0.3 0.05 0.3 0.15 Ci: 2 3 1 2 3 此时 ASL=20.2+30.3+10.05+20.3+30.15=2.4 若改变Ci的值 2 1 3 2 3 则 ASL=20.2+10.3+30.05+20.3+30.15=1.9

定义: 使 达最小的判定树称为最优二叉树， 其中:

介绍一种次优二叉树的构造方法： 为计算方便，令 wi = pi 选择二叉树的根结点， 使 达最小 为便于计算，引入累计权值和 使 达最小 为便于计算，引入累计权值和 并设 wl-1 = 0 和 swl-1 = 0， 则推导可得

l h h 例如: l h h 2 3 8 11 15 18 23 21 18 12 4 3 3 10 18 9 6 8 5 3 3 1 1 2 A C E G

E C G A D F B 所得次优二叉树如下所示: D B F A C E G 和折半查找相比较 查找比较“总次数” = 32+41+25+33 +14+33+25 = 52 查找比较“总次数” = 32+21+35+13 +34+23+35 = 59

构造次优二叉树的算法 // 由有序表R[low..high]及其累计权值表sw Status SecondOptimal(BiTree &T, ElemType R[], float sw[], int low, int high) { // 由有序表R[low..high]及其累计权值表sw // 递归构造次优查找树T。 选择最小的ΔPi值 if (!(T = (BiTree)malloc(sizeof(BiTNode)))) return ERROR; T->data = R[i]; // 生成结点 CONTINUE

if (i==low) T->lchild = NULL; // 左子树空 else SecondOptimal(T->lchild, R, sw, low, i-1); // 构造左子树 if (i==high) T->rchild = NULL; // 右子树空 else SecondOptimal(T->rchild, R, sw, i+1, high); // 构造右子树 return OK; } // SecondOptimal

次优查找树采用二叉链表的存储结构 Status CreateSOSTre(SOSTree &T, SSTable ST) { // 由有序表 ST 构造一棵次优查找树 T // ST 的数据元素含有权域 weight if (ST.length = 0) T = NULL; else { FindSW(sw, ST); // 按照有序表 ST 中各数据元素 // 的 weight 值求累计权值表 SecondOpiamal(T, ST.elem, sw, 1, ST.length); } return OK; } // CreatSOSTree

索引顺序表的查找过程： 1）由索引确定记录所在区间； 2）在顺序表的某个区间内进行查找。 可见， 索引顺序查找的过程也是一个 “缩小区间”的查找过程。 注意：索引可以根据查找表的特点来构造。

索引顺序查找的平均查找长度 = 查找“索引”的平均查找长度 + 查找“顺序表”的平均查找长度

ADT DynamicSearchTable { 抽象数据类型动态查找表的定义如下： ADT DynamicSearchTable { D是具有相同特性的数据元素的集合。 每个数据元素含有类型相同的关键字， 可唯一标识数据元素。 数据对象D： 数据关系R： 数据元素同属一个集合。

基本操作P： InitDSTable(&DT) DestroyDSTable(&DT) SearchDSTable(DT, key); InsertDSTable(&DT, e); DeleteDSTable(&T, key); TraverseDSTable(DT, Visit()); }ADT DynamicSearchTable

InitDSTable(&DT); 操作结果： 构造一个空的动态查找表DT。

DestroyDSTable(&DT); 初始条件： 操作结果： 动态查找表DT存在； 销毁动态查找表DT。

SearchDSTable(DT, key); 初始条件： 操作结果： 动态查找表DT存在，key 为和关键字类型相同的给 定值； 若DT中存在其关键字等于 key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。

InsertDSTable(&DT, e); 初始条件： 操作结果： 动态查找表DT存在， e 为待插入的数据元素； 若DT中不存在其关键字 等于 e.key 的 数据元素， 则插入 e 到DT。

DeleteDSTable(&T, key); 初始条件： 操作结果： 动态查找表DT存在，key 为和关键字类型相同的给 定值； 若DT中存在其关键字等于key的数据元素，则删 除之。

初始条件： 操作结果： TraverseDSTable(DT, Visit()); 动态查找表DT存在，Visit 是对结点操作的应用函数； 则操作失败。

9.2 动 态 查 找 树 表

综合上一节讨论的几种查找表的特性： 查找 插入 删除 (n) (logn) (1) (n) (nlogn) (n) (1) 查找 插入 删除 (n) (logn) (1) (n) (nlogn) (n) (1) (nlogn) 无序顺序表 无序线性链表 有序顺序表 有序线性链表 静态查找树表

可得如下结论： 1）从查找性能看，最好情况能达 (logn)，此时要求表有序； 2）从插入和删除的性能看，最好 情况能达(1)，此时要求存储 结构是链表。

一、二叉排序树（二叉查找树） 二、二叉平衡树 三、B - 树 四、B+树 五、键 树

一、二叉排序树 （二叉查找树） 1．定义 2．查找算法 3．插入算法 4．删除算法 5．查找性能的分析

1．定义： 二叉排序树或者是一棵空树；或者 （3）它的左、右子树也都分别是二叉 是具有如下特性的二叉树： （1）若它的左子树不空，则左子树上 所有结点的值均小于根结点的值； （2）若它的右子树不空，则右子树上 所有结点的值均大于根结点的值； （3）它的左、右子树也都分别是二叉 排序树。

例如: 50 30 80 20 40 90 10 25 35 85 66 23 88 不 是二叉排序树。

typedef struct BiTNode { // 结点结构 struct BiTNode *lchild, *rchild; 通常，取二叉链表作为 二叉排序树的存储结构 typedef struct BiTNode { // 结点结构 struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; TElemType data;

2．二叉排序树的查找算法： 若二叉排序树为空，则查找不成功； 否则， 1）若给定值等于根结点的关键字，则查找成功； 2）若给定值小于根结点的关键字，则继续在左子树上进行查找； 3）若给定值大于根结点的关键字，则继续在右子树上进行查找。

例如: 二叉排序树 50 50 50 50 50 50 30 30 80 80 20 40 40 90 90 35 35 85 32 88 查找关键字 == 50 , 35 , 90 , 95 ,

从上述查找过程可见， 在查找过程中，生成了一条查找路径： 从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点; ——查找成功 或者 从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。 ——查找不成功

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

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 ); // 在右子树中继续查找

f f T 设 key = 48 22 f T f f T f T p 30 T 20 40 T f 10 25 35 p T f 23 T

3．二叉排序树的插入算法 根据动态查找表的定义，“插入”操作在查找不成功时才进行； 若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。

… … Status Insert BST(BiTree &T, ElemType e ) { { } else return FALSE; // 当二叉排序树中不存在关键字等于 e.key 的 // 数据元素时，插入元素值为 e 的结点，并返 // 回 TRUE; 否则，不进行插入并返回FALSE if (!SearchBST ( T, e.key, NULL, p )) { } else return FALSE; } // Insert BST … …

s = (BiTree) malloc (sizeof (BiTNode)); // 为新结点分配空间 s->data = e; s->lchild = s->rchild = NULL; if ( !p ) T = s; // 插入 s 为新的根结点 else if ( LT(e.key, p->data.key) ) p->lchild = s; // 插入 *s 为 *p 的左孩子 else p->rchild = s; // 插入 *s 为 *p 的右孩子 return TRUE; // 插入成功

4．二叉排序树的删除算法 可分三种情况讨论： 和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。 可分三种情况讨论： （1）被删除的结点是叶子； （2）被删除的结点只有左子树或者只有右子树； （3）被删除的结点既有左子树，也有右子树。

（1）被删除的结点是叶子结点 例如: 被删关键字 = 20 88 50 30 80 20 40 90 35 85 32 88 其双亲结点中相应指针域的值改为“空”

（2）被删除的结点只有左子树 或者只有右子树 被删关键字 = 40 80 50 30 80 20 40 90 35 85 32 88 其双亲结点的相应指针域的值改为 “指向被删除结点的左子树或右子树”。

（3）被删除的结点既有左子树，也有右子树 被删关键字 = 50 40 50 30 80 20 40 40 90 35 85 32 88 前驱结点 被删结点 以其前驱替代之，然后再删除该前驱结点

… … 算法描述如下： Status DeleteBST (BiTree &T, KeyType key ) { // 数据元素，则删除该数据元素结点，并返回 // 函数值 TRUE，否则返回函数值 FALSE if (!T) return FALSE; // 不存在关键字等于key的数据元素 else { } } // DeleteBST … …

if ( EQ (key, T->data.key) ) else if ( LT (key, T->data.key) ) else { Delete (T); return TRUE; } DeleteBST ( T->lchild, key ); // 继续在左子树中进行查找 DeleteBST ( T->rchild, key ); // 继续在右子树中进行查找

… … … … … … 其中删除操作过程如下所描述： void Delete ( BiTree &p ){ // 并重接它的左子树或右子树 if (!p->rchild) { } else if (!p->lchild) { } else { } } // Delete … … … … … …

q = p; p = p->lchild; free(q); // 右子树为空树则只需重接它的左子树 q = p; p = p->lchild; free(q); p p

q = p; p = p->rchild; free(q); // 左子树为空树只需重接它的右子树 q = p; p = p->rchild; free(q); p p

while (!s->rchild) { q = s; s = s->rchild; } // s 指向被删结点的前驱 // 左右子树均不空 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); q p s

5．查找性能的分析 对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的 ASL 值，显然，由值相同的 n 个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长 度的值不同，甚至可能差别很大。

ASL =（1+2+3+4+5）/ 5 = 3 ASL =（1+2+3+2+3）/ 5 = 2.2 例如： 由关键字序列 1，2，3，4，5构造而得的二叉排序树， 2 3 4 ASL =（1+2+3+4+5）/ 5 = 3 5 由关键字序列 3，1，2，5，4构造而得的二叉排序树， 3 1 5 ASL =（1+2+3+2+3）/ 5 = 2.2 2 4

不失一般性，假设长度为 n 的序列中有 k 个关键字小于第一个关键字，则必有 n-k-1 个关键字大于第一个关键字,由它构造的二叉排序树： 下面讨论平均情况: 不失一般性，假设长度为 n 的序列中有 k 个关键字小于第一个关键字，则必有 n-k-1 个关键字大于第一个关键字,由它构造的二叉排序树： k n-k-1 的平均查找长度是 n 和 k 的函数 P(n, k) ( 0 k  n-1 )。

假设 n 个关键字可能出现的 n! 种排列的可能性相同，则含 n 个关键字的二叉排序树的平均查找长度： 在等概率查找的情况下，

由此 可类似于解差分方程，此递归方程有解：

二、二叉平衡树 何谓“二叉平衡树”？ 如何构造“二叉平衡树” 二叉平衡树的查找性能分析

二叉平衡树是二叉查找树的另一种形式，其特点为： 树中每个结点的左、右子树深度之差的绝对值不大于1 。 例如: 5 5 4 8 4 8 2 2 是平衡树 不是平衡树 1

构造二叉平衡（查找）树的方法是： 在插入过程中，采用平衡旋转技术。 例如:依次插入的关键字为5, 4, 2, 8, 6, 9 5 4 4 4 向右旋转 一次 6 先向右旋转 再向左旋转

向左旋转一次 4 2 6 5 8 6 9 4 8 继续插入关键字 9 2 9 5

平衡树的查找性能分析： 在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡 树的深度。 问：含 n 个关键字的二叉平衡树可能达到的最大深度是多少？

n = 0 n = 1 n = 2 空树 n = 4 n = 7 先看几个具体情况: 最大深度为 1 最大深度为 2 最大深度为 0 最大深度为 3 最大深度为 4

反过来问，深度为 h 的二叉平衡树中所含结点的最小值 Nh 是多少？ 一般情况下 Nh = Nh-1 + Nh-2 + 1 利用归纳法可证得 Nh = Fh+2 - 1

由此推得，深度为 h 的二叉平衡树中所含结点的最小值 Nh = h+2/5 - 1。 反之，含有 n 个结点的二叉平衡树能达到的最大深度 hn = log(5 (n+1)) - 2。 因此，在二叉平衡树上进行查找时， 查找过程中和给定值进行比较的关键字的个数和 log(n) 相当。

三、 B - 树 1．定义 2．查找过程 3．插入操作 4．删除操作 5．查找性能的分析

1．B-树的定义 B-树是一种 平衡 的 多路 查找 树：

在 m 阶的B-树上，每个非终端结点可能含有： n 个关键字 Ki（1≤ i≤n） n<m n 个指向记录的指针 Di（1≤i≤n） n+1 个指向子树的指针 Ai（0≤i≤n） 多叉树的特性

B-树结构的C语言描述如下: typedef struct BTNode { int keynum; // 结点中关键字个数，结点大小 struct BTNode *parent; // 指向双亲结点的指针 KeyType key[m+1]; // 关键字（0号单元不用） struct BTNode *ptr[m+1]; // 子树指针向量 Record *recptr[m+1]; // 记录指针向量 } BTNode, *BTree; // B树结点和B树的类型

非叶结点中的多个关键字均自小至大有序排列，即：K1< K2 < … < Kn ； Ai-1 所指子树上所有关键字均小于Ki ； Ai 所指子树上所有关键字均大于Ki ； 查找树的特性

树中所有叶子结点均不带信息，且在树中的同一层次上； 根结点或为叶子结点，或至少含有两棵子树； 其余所有非叶结点均至少含有m/2棵子树，至多含有 m 棵子树； 平衡树的特性

2.查找过程： 从根结点出发，沿指针搜索结点和在 结点内进行顺序（或折半）查找 两个过程 交叉进行。 若查找成功，则返回指向被查关键字所在结点的指针和关键字在结点中的位置； 若查找不成功，则返回插入位置。

假设返回的是如下所述结构的记录： typedef struct { BTNode *pt; // 指向找到的结点的指针 int i; // 1..m，在结点中的关键字序号 int tag; // 标志查找成功(=1)或失败(=0) } Result; // 在B树的查找结果类型

… … 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 … …

p=T; q=NULL; found=FALSE; i=0; while (p && !found) { n=p->keynum; i=Search(p, K); // 在p->key[1..keynum]中查找 i ， p->key[i]<=K<p->key[i+1] if (i>0 && p->key[i]==K) found=TRUE; else { q=p; p=p->ptr[i]; } // q 指示 p 的双亲 } if (found) return (p,i,1); // 查找成功 else return (q,i,0); // 查找不成功

3．插入 在查找不成功之后，需进行插入。 显然，关键字插入的位置必定在最下 层的非叶结点，有下列几种情况： 1）插入后，该结点的关键字个数n<m， 不修改指针; 例如

2）插入后，该结点的关键字个数 n=m， 则需进行“结点分裂”，令 s = m/2， 在原结点中保留 （A0，K1，…… ， Ks-1，As-1）； 建新结点 （As，Ks+1，…… ，Kn，An）； 将（Ks，p）插入双亲结点；例如 3）若双亲为空，则建新的根结点。 例如

例如:下列为 3 阶B-树 50 30 50 80 50 80 30 80 50  20   20  40   40   80  60  60  80  608090 90 插入关键字 = 60, 90, 30,

4．删除 和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后，结点中关键字的个数不能小于m/2-1，否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的“合并”。

问：含 N 个关键字的 m 阶 B-树可能达到的最大深度 H 为多少？ 5．查找性能的分析 在B-树中进行查找时，其查找时间 主要花费在搜索结点（访问外存）上， 即主要取决于B-树的深度。 问：含 N 个关键字的 m 阶 B-树可能达到的最大深度 H 为多少？

反过来问： 深度为H的B-树中， 至少含有多少个结点？ 先推导每一层所含最少结点数： 第 1 层 1 个 第 2 层 2 个 第 3 层 2m/2 个 第 4 层 2(m/2)2 个 … … 第 H+1 层 2(m/2) H-1 个

由此可推得下列结果： N+1≥2(m/2)H-1 H-1≤logm/2((N+1)/2) H≤logm/2((N+1)/2)+1 假设 m 阶 B-树的深度为 H+1，由于 第 H+1 层为叶子结点，而当前树中含有 N 个关键字，则叶子结点必为 N+1 个， 由此可推得下列结果： N+1≥2(m/2)H-1 H-1≤logm/2((N+1)/2) H≤logm/2((N+1)/2)+1

在含 N 个关键字的 B-树上进行一次查找，需访问的结点个数不超过 结论： 在含 N 个关键字的 B-树上进行一次查找，需访问的结点个数不超过 logm/2((N+1)/2)+1

四、B+树 是B-树的一种变型

1．B+树的结构特点： ※ 每个叶子结点中含有 n 个关键字和 n 个指向记录的指针；并且，所有叶子结点彼此相链接构成一个有序链表，其头指针指向含最小关键字的结点；

※ 每个非叶结点中的关键字 Ki 即为其相应指针 Ai 所指子树中关键字的最大值； ※ 所有叶子结点都处在同一层次上，每个叶子结点中关键字的个数均介于 m/2和 m 之间。

2．查找过程 找，也可以进行顺序查找； 与否，都必须查到叶子结点才能结束； 应继续在 Ai 所指子树中进行查找。 ※在 B+ 树上，既可以进行缩小范围的查 找，也可以进行顺序查找； ※ 在进行缩小范围的查找时，不管成功 与否，都必须查到叶子结点才能结束； ※若在结点内查找时，给定值≤Ki， 则 应继续在 Ai 所指子树中进行查找。

3．插入和删除的操作 类似于B-树进行，即必要时，也需要进行结点的“分裂”或“归并”。

root 50 96 15 50 62 78 96 sq 20 26 43 50 56 62 3 8 15 71 78 84 89 96

五、键 树 1. 键树的结构特点 2. .双链树 3. Trie树

1. 键树的结构特点： ※ 关键字中的各个符号分布在从根结点到叶的路径上，叶结点内的符号为“结束”的标志符。因此，键树的深度和关键字集合的大小无关； ※ 键树被约定为是一棵有序树，即同一层中兄弟结点之间依所含符号自左至右有序，并约定结束符‘$’小于任何其它符号。

{HAD, HAS, HAVE, HE, HER, HERE, HIGH, HIS } 例如: H A E I D S V $ R G S $ $ E $ E H $ $ $ $ 表示关键字集合 {HAD, HAS, HAVE, HE, HER, HERE, HIGH, HIS }

2. 双链树 — 以二叉链表作存储结构实现的键树 结点结构: typedef enum { LEAF, BRANCH }NodeKind; 2. 双链树 — 以二叉链表作存储结构实现的键树 结点结构: 分支结点 叶子结点 first symbol next infoptr symbol next 指向孩子结点 的指针 指向兄弟结点 的指针 指向记录 的指针 typedef enum { LEAF, BRANCH }NodeKind; // 两种结点：{叶子 和 分支}

T …   H A D E   $ $ I  R G HAD HE   $ H S    E $ $ HER  $ 分支结点 A 叶子结点 D E   $ … $ I  R G HAD HE   $ H S    E $ $ 含关键字 的记录 HER  $ HIGH HIS HERE

struct DLTNode *next; // 指向兄弟结点的指针 NodeKind kind; union { typedef struct DLTNode { char symbol; struct DLTNode *next; // 指向兄弟结点的指针 NodeKind kind; union { Record *infoptr; // 叶子结点内的记录指针 struct DLTNode *first; // 分支结点内的孩子链指针 } } DLTNode, *DLTree; // 双链树的类型

char ch[MAXKEYLEN]; // 关键字 int num; // 关键字长度 } KeysType; // 关键字类型 #define MAXKEYLEN 16 //关键字的最大长度 typedef struct { char ch[MAXKEYLEN]; // 关键字 int num; // 关键字长度 } KeysType; // 关键字类型

在双链树中查找记录的过程: 假设: T 为指向双链树根结点的指针， K.ch[0..K.num-1] 为待查关键字 (给定值)。 则查找过程中的基本操作为进行下列比较: K.ch[i] =? p->symbol 其中: p 指向双链树中某个结点， 0 ≤ i ≤ K.num-1

初始状态: p=T->first; i = 0; 若 ( p && p->symbol == K.ch[i] && i<K.num-1) 则继续和给定值的下一位进行比较 p=p->first; i++; 若 ( p && p->symbol != K.ch[i] ) 则继续在键树的同一层上进行查找 p=p->next; 若 ( p == NULL) 则表明查找不成功，返回“空指针”; 若 ( p && p->symbol==K.ch[i] && i==K.num-1) 则 查找成功，返回指向相应记录的指针 p->infoptr

3. Trie树 — 以多重链表作存储结构实现的键树 结点结构: 分支结点 叶子结点 指向下层结点的指针 指向记录 每个域对应一个“字母” 0 1 2 3 4 5 … … 24 25 26 关键字 指向下层结点的指针 每个域对应一个“字母” 指向记录 的指针

T          HAD HAS HAVE HE HIGH HIS HER HERE 8(H) 分支结点 0 1(A) 3 4 5(E) 9(I) … … 26          4(D) 19(S) 22(V) 0 18(R) 7(G) 19 HAD HAS HAVE HE 0 5(E) HIGH HIS HER HERE 叶子结点 指向记录 的指针

结点结构的 C 语言描述: typedef struct TrieNode { NodeKind kind; // 结点类型 union { struct { KeyType K; Record *infoptr } lf; // 叶子结点(关键字和指向记录的指针) struct { TrieNode *ptr[27]; int num } bh; // 分支结点(27个指向下一层结点的指针) } } TrieNode, *TrieTree; // 键树类型

在 Trie 树中查找记录的过程: 假设: T 为指向 Trie 树根结点的指针， K.ch[0..K.num-1] 为待查关键字(给定值)。 则查找过程中的基本操作为： 搜索和对应字母相应的指针: 若 p 不空，且 p 所指为分支结点， 则 p = p->bh.Ptr[ord(K.Ch[i])] ; ( 其中: 0 ≤ i ≤ K.num-1 )

初始状态: p=T; i = 0; 若 ( p && p->kind == BRANCH && i<K.num) 则继续搜索下一层的结点 p=p->bh.ptr[ord(K.ch[i])]; i++; 其中，ord 为求字符在字母表中序号的函数 若 ( p && p->kind==LEAF && p->lf.K==K) 则 查找成功，返回指向相应记录的指针 p->lf.infoptr 反之，即 ( !p || p->kind==LEAF && p->lf.K!=K ) 则表明查找不成功，返回“空指针”;

9.3 哈 希 表 一、哈希表是什么？ 三、处理冲突的方法 四、哈希表的查找 五、哈希表的删除操作 六、对静态查找表，．．． 9.3 哈 希 表 一、哈希表是什么？ 二、哈希函数的构造方法 三、处理冲突的方法 四、哈希表的查找 五、哈希表的删除操作 六、对静态查找表，．．．

一、哈希表是什么？ 以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系， 查找的过程为给定值依次和关键字集合中各个关键字进行比较， 查找的效率取决于和给定值进行比较的关键字个数。

用这类方法表示的查找表，其平均查找长度都不为零。 不同的表示方法，其差别仅在于： 关键字和给定值进行比较的顺序不同。

对于频繁使用的查找表， 希望 ASL = 0。 只有一个办法：预先知道所查关键字在表中的位置， 即，要求：记录在表中位置和其关键字之间存在一种确定的关系。

例如：为每年招收的 1000 名新生建立一张查找表，其关键字为学号，其值的范围为 xx000 ~ xx999 (前两位为年份)。 若以下标为000 ~ 999 的顺序表表示之。 则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。

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

{Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei} 例如：对于如下 9 个关键字 {Zhao, Qian, Sun, Li, Wu, Chen, Han, Ye, Dei} 设 哈希函数 f(key) = (Ord(第一个字母) -Ord('A')+1)/2 Chen Dei Han Li Qian Sun Wu Ye Zhao 问题: 若添加关键字 Zhou , 怎么办？ 能否找到另一个哈希函数？

从这个例子可见： 1) 哈希函数是一个映象，即： 将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要这个地址集合的 1) 哈希函数是一个映象，即： 将关键字的集合映射到某个地址集合上， 它的设置很灵活，只要这个地址集合的 大小不超出允许范围即可； 2) 由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即： key1 key2，而 f(key1) = f(key2)。

因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突” 的方法。 3) 很难找到一个不产生冲突的哈希函数。 一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。 因此，在构造这种特殊的“查找表” 时，除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突” 的方法。

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

二、构造哈希函数的方法 1. 直接定址法 4. 折叠法 2. 数字分析法 5. 除留余数法 3. 平方取中法 6. 随机数法 对数字的关键字可有下列构造方法： 1. 直接定址法 4. 折叠法 2. 数字分析法 5. 除留余数法 3. 平方取中法 6. 随机数法 若是非数字关键字，则需先对其进行 数字化处理。

1. 直接定址法 哈希函数为关键字的线性函数 H(key) = key 或者 H(key) = a  key + b 此法仅适合于： 地址集合的大小 = = 关键字集合的大小

2. 数字分析法 假设关键字集合中的每个关键字都是由 s 位数字组成 (u1, u2, …, us)，分析关键字集中的全体， 并从中提取分布均匀的若干位或它们的组合作为地址。 此方法仅适合于： 能预先估计出全体关键字的每一位上各种数字出现的频度。

以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。 3. 平方取中法 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值” 的目的是“扩大差别” ，同时平方值的中间各位又能受到整个关键字中各位的影响。 此方法适合于: 关键字中的每一位都有某些数字重复出现频度很高的现象。

4. 折叠法 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。 此方法适合于: 关键字的数字位数特别多。

5. 除留余数法 设定哈希函数为: H(key) = key MOD p 其中， p≤m (表长) 并且 p 应为不大于 m 的素数 或是 不含 20 以下的质因子

例如： 为什么要对 p 加限制？ 给定一组关键字为：12, 39, 18, 24, 33, 21， 3, 3, 0, 6, 6, 3 可见，若 p 中含质因子 3， 则所有含质因子 3 的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。

6.随机数法 H(key) = Random(key) 设定哈希函数为: 其中，Random 为伪随机函数 通常，此方法用于对长度不等的关键字构造哈希函数。

实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。

三、处理冲突的方法 “处理冲突” 的实际含义是： 为产生冲突的地址寻找下一个哈希地址。 1. 开放定址法 2. 链地址法

为产生冲突的地址 H(key) 求得一个地址序列： 1. 开放定址法 为产生冲突的地址 H(key) 求得一个地址序列： H0, H1, H2, …, Hs 1≤ s≤m-1 其中：H0 = H(key) Hi = ( H(key) + di ) MOD m i=1, 2, …, s

对增量 di 有三种取法： 1) 线性探测再散列 di = c i 最简单的情况 c=1 di=i×H2(key) (又称双散列函数探测)

注意：增量 di 应具有“完备性” 即：产生的 Hi 均不相同，且所产生的 s(m-1)个 Hi 值能覆盖哈希表中所有 地址。则要求： ※ 平方探测时的表长 m 必为形如 4j+3 的素数（如: 7, 11, 19, 23, … 等）； ※ 随机探测时的 m 和 di 没有公因子。

例如: 关键字集合 { 19, 01, 23, 14, 55, 68, 11, 82, 36 } 设定哈希函数 H(key) = key MOD 11 ( 表长=11 ) 若采用线性探测再散列处理冲突 55 01 23 14 68 11 82 36 19 1 1 2 1 3 6 2 5 1 若采用二次探测再散列处理冲突 55 01 23 14 36 82 68 19 11

H2(key) 是另设定的一个哈希函数，它的函数值应和 m 互为素数。 若 m 为素数，则 H2(key) 可以是 1 至 m-1 之间的任意数； 若 m 为 2 的幂次，则 H2(key) 应是 1 至 m-1 之间的任意奇数。 例如，当 m=11时， 可设 H2(key)=(3 key) MOD 10+1 23 01 68 14 11 82 55 19 36 2 1 1 1 2 1 2 1 3

2. 链地址法 将所有哈希地址相同的记录 都链接在同一链表中。 例如:同前例的关键字，哈希函数为 H(key)=key MOD 7  1 1 2 3 4 5 6  14  01 36  23  ASL=(6×1+2×2+3)/9=13/9  11  19 68 82  55

四、哈希表的查找 查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为： 对于给定值 K， 计算哈希地址 i = H(K) 若 r[i] = NULL 则查找不成功 若 r[i].key = K 则查找成功 否则 “求下一地址 Hi” ，直至 r[Hi] = NULL (查找不成功) 或 r[Hi].key = K (查找成功) 为止。

//--- 开放定址哈希表的存储结构 --- int hashsize[] = { 997, ... }; typedef struct { ElemType *elem; int count; // 当前数据元素个数 int sizeindex; // hashsize[sizeindex]为当前容量 } HashTable; #define SUCCESS 1 #define UNSUCCESS 0 #define DUPLICATE -1

Status SearchHash (HashTable H, KeyType K, int &p, int &c) { // 在开放定址哈希表H中查找关键码为K的记录 } // SearchHash p = Hash(K); // 求得哈希地址 while ( H.elem[p].key != NULLKEY && !EQ(K, H.elem[p].key)） collision(p, ++c); // 求得下一探查地址 p if (EQ(K, H.elem[p].key)) return SUCCESS; // 查找成功，返回待查数据元素位置 p else return UNSUCCESS; // 查找不成功

Status InsertHash (HashTable &H, Elemtype e){ c = 0; if ( HashSearch ( H, e.key, p, c ) == SUCCESS ) return DUPLICATE; // 表中已有与 e 有相同关键字的元素 else H.elem[p] = e; ++H.count; return OK; // 查找不成功时，返回 p为插入位置 if ( c < hashsize[H.sizeindex]/2 ) { // 冲突次数 c 未达到上限，（阀值 c 可调） } else RecreateHashTable(H); // 重建哈希表

哈希表查找的分析: 决定哈希表查找的ASL的因素： 从查找过程得知，哈希表查找的平均查找长度实际上并不等于零。 1) 选用的哈希函数； 1) 选用的哈希函数； 2) 选用的处理冲突的方法； 3) 哈希表饱和的程度，装载因子 α=n/m 值的大小（n—记录数，m—表的长度）

一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。 例如：前述例子 线性探测处理冲突时， ASL = 22/9 双散列探测处理冲突时，ASL = 14/9 链地址法处理冲突时， ASL = 13/9

可以证明：查找成功时有下列结果： 线性探测再散列 随机探测再散列 链地址法

从以上结果可见： 哈希表的平均查找长度是  的函数，而不是 n 的函数。 这说明，用哈希表构造查找表时，可以选择一个适当的装填因子  ，使得平均查找长度限定在某个范围内。 —— 这是哈希表所特有的特点。

五、哈希表的删除操作 从哈希表中删除记录时，要作特殊处理，相应地，需要修改查找的算法。

六、哈希表也可以用来构造静态查找表 并且，对静态查找表，有时可以找到不发生冲突的哈希函数。即，此时的哈希表的 ASL=0, 称此类 哈希函数为理想（perfect）的哈希函数。

1. 顺序表和有序表的查找方法及其平均查找长度的计算方法。 2. 静态查找树的构造方法和查找算法,理解静态查找树和折半查找的关系。 3. 熟练掌握二叉排序树的构造和查找方法。

4. 理解B-树、B+树和建树的特点以及它们的建树和查找的过程。 5. 熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。 6. 掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。