第九章 查找 2019/2/16

基本概念 查找(search) 关键字(key) 查找表(search table) 根据给定的某个值，确定一个关键字等于给定值的元素在表中的位置 关键字(key) 元素中的某个数据项，其值可以标识该元素 不同元素的关键字互不相同 查找表(search table) 同一数据类型的元素的集合 2019/2/16

基本概念 查找结果 查找表类型 成功：找到关键字值等于给定值的元素 失败：未找到关键字值等于给定值的元素 静态(static)：表元素的个数固定 只执行查找 动态(dynamic)：表元素的个数可变 可执行查找、插入、删除 2019/2/16

基本概念 影响查找速度的因素 时间复杂度函数 T( n, k ) 规模：查找表的元素个数 n 特征：待查关键字在查找表中的位置 k 平均查找长度 ASL (Average Search Length) 2019/2/16

基本概念 平均查找长度 ASL (Average Search Length) 为确定元素在表中的位置，与给定值进行比较的关键字平均个数 (期望值) n：查找表的元素个数 pi：查找第 i 个元素的概率 (与算法无关，只与问题相关) ci：查找第 i 个元素所需的关键字比较次数 (由算法决定) 2019/2/16

9.1 静态查找表:表元素个数固定 9.1.1 顺序表的查找：线性查找 i i i i i 9.1 静态查找表:表元素个数固定 9.1.1 顺序表的查找：线性查找 查找过程：从表的一端开始，逐个进行关键字与给定值的比较 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92 找 64 数组 r 64 i i i i i 监视哨 比较次数＝5 从后往前 2019/2/16

9.1 静态查找表 9.1.1 顺序表的查找：线性查找 算法9.1 int Search_Seq ( int r[], int n, int key){ //在数组 r 中顺序查找值＝key 的元素 //若找到，则函数值＝该元素在表中的位置，否则为0 r[0] = key; //0 号元素作为监视哨 for ( i=n; r[i] != key; --i ); //从后往前 return i； //找不到时，i＝0 } // Search_Seq 2019/2/16

顺序查找法的性能分析 顺序查找操作的性能分析:等概率情况下 查找成功的平均查找长度： 查找不成功时的平均查找长度: 任意关键字查找不成功的比较次数为n＋1 xi查找成功的比较次数为n－i＋1（1≤i≤n） 查找成功的平均查找长度： 查找不成功时的平均查找长度: 顺序查找的平均查找长度为：

9.1 静态查找表 顺序查找方法的性能 (ASL) 如果是不等概率，如何改进查找性能？ 预处理：元素按查找概率排序 9.1 静态查找表 顺序查找方法的性能 (ASL) 如果是不等概率，如何改进查找性能？ 预处理：元素按查找概率排序 自适应：实时调整查找频度大的元素的位置 移动查找频度大的元素的位置 调整查找成功的元素的位置 2019/2/16

9.1 静态查找表 9.1.2 有序表的查找：折半(二分)查找 原理：每次将待查元素所在区间缩小一半 采用数组存储元素 元素按关键字排序 9.1 静态查找表 9.1.2 有序表的查找：折半(二分)查找 原理：每次将待查元素所在区间缩小一半 采用数组存储元素 元素按关键字排序 2019/2/16

9.1.2 有序表的查找 (折半查找) [初始] 令 low=1, high=n, mid = (low+high)/2 low、high、mid 分别指向待查区间内元素下标的上界、下界和中点 k：给定的查找值 [初始] 令 low=1, high=n, mid = (low+high)/2 [比较] 让 k 与 mid 指向元素的关键字比较 若 k ＝ elem[mid].key，查找成功 若 k ＜ elem[mid].key，则 high = mid-1 若 k ＞ elem[mid].key，则 low = mid+1 重复比较，当 low>high 时查找失败 2019/2/16

查找过程示例（如下按关键字递增有序的顺序表） 1) 查找关键字等于21的记录 1 2 3 4 5 6 7 8 9 10 11 13 19 21 37 56 64 75 80 88 92 r[mid]>21 5 13 19 21 37 56 64 75 80 88 92 r[mid]<21 5 13 19 21 37 56 64 75 80 88 92 r[mid]=21(查找成功）

失败 2) 查找关键字等于85的记录 r[mid]<85 r[mid]<85 r[mid]>85 1 2 3 4 5 6 7 8 9 10 11 13 19 21 37 56 64 75 80 88 92 r[mid]<85 5 13 19 21 37 56 64 75 80 88 92 5 13 19 21 37 56 64 75 80 88 92 r[mid]<85 r[mid]>85 5 13 19 21 37 56 64 75 80 88 92 失败

int BinSearch(int r[], int n, int k) {//在有序数组 r 中二分查找 int low, high, mid; low=1; high=n; while ( low<=high ) { mid = (low+high) / 2; //中间元素 if( k>r[mid]) low=mid+1; else if( k<r[mid] ) high=mid-1; else return mid; //查找成功 } return -1;//查找失败 二分查找算法思想简单，但写出正确的算法不简单。 第一个二分查找算法于1946年出现，但第一个完全正确的二分查找算法直到1962才出现 2019/2/16

折半查找算法的性能分析 为了分析二分查找的性能，可以用二叉树来描述二分查找过程。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树。 9 6 3 1 4 7 10 2 5 8 11 -1 3-4 6-7 9-10 1-2 2-3 4-5 5-6 7-8 8-9 10-11 11-

第 i (1  i  h) 层结点有 2i -1个，查找第 i 层结点要比较 i次，…。假定每个结点的查找概率相等，即pi = 1/n，则查找成功的平均查找长度为 可以用归纳法证明

二分查找算法时间复杂度评价 n 个结点的判定树深度＝log2n + 1 设元素个数 n=2h-1，则h=log2(n+1) 11 8 5 2 10 7 4 1 9 3 6 设元素个数 n=2h-1，则h=log2(n+1) 设元素查找概率相等，即pi=1/n 故 ASL＝O(log2n)，比顺序查找快 2019/2/16

9.1 静态查找表 二分查找算法的评价 查找效率：高 限制条件 元素必须有序 只能数组存储 (顺序存储结构) 等概率假设 2019/2/16

练习 ① 给出在递增有序数组 A [1..21] 中二分查找的判定树 ② 求出等概率假设下的 ASL 1 11 5 16 2 8 13 19 4 6 9 12 14 17 20 7 10 15 18 21 2019/2/16

1.基本要求：将线性表中的元素分成若干块，每一块中记录之间是可以有序或无序的，而块之间是按关键字从小到大排列。 9.1.4 索引顺序表的查找（分块查找） 1.基本要求：将线性表中的元素分成若干块，每一块中记录之间是可以有序或无序的，而块之间是按关键字从小到大排列。 13 7 1 86 48 22 53 49 74 58 60 24 38 44 42 33 20 9 8 12

2.基本思想： 3.性能分析 分块查找法是顺序查找法和二分查找法的一种结合，其查找过程分为： 确定待查记录所在的块（顺序/二分查找） 在块中顺序查找待查记录 则分块查找的平均查找长度为ASLbs=ASLb+ASLw 。 3.性能分析 设长度为n的表均匀地分为b块，每块有s个记录，且表中每个记录的查找概率相等，则：

1）若顺序查找确定所在块： 2）若折半查找确定所在块：

小结： 静态查找表 三种查找方法的比较 顺序查找 折半查找 分块查找 平均查找长度 最大 最小 介于二者之间 表结构 有序/无序表 有序表 表中元素逐段有序 存储结构 顺序/链式存储 顺序存储

几种查找表的特性 查找 插入 删除 无序顺序表 无序线性链表 有序顺序表 有序线性链表 (n) (logn) (1) (n) 查找 插入 删除 无序顺序表 无序线性链表 有序顺序表 有序线性链表 (n) (logn) (1) (n) (n) (1)

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

9.2.1 二叉排序树和平衡二叉树 一、二叉排序树的定义与查找过程 1.定义 二叉排序树或者是一棵空树，或是具有下列性质的二叉树： 2.特点 若左子树非空，则左子树上所有结点的值均小于它的根结点的值。 若右子树非空，则右子树上所有结点的值均大于它的根结点的值。 它的左右子树也分别为二叉排序树。 2.特点

3.构造过程: 例：输入序列{45，12，37，3，53，100，24} 45 12 53 3 37 100 24

3.查找过程 算法9.5-a 递归过程 BiTree SearchBST(BiTree T,KeyType key){ if ((!T) || (key==T->data.key)) return T; else if (key<T->data.key) return(SearchBST(T->lchild,key)); else return(SearchBST(T->rchild,key)); }// SearchBST

非递归查找过程 BiTree SearchBST(BiTree T,KeyType key){ BiTree p=T; while (p && !( (key==p->data.key)) if (key<p->data.key) p=p->lchild; else p=p->rchild; return p; }// SearchBST

二、二叉查找树的插入 新插入结点一定是一个新添加的叶子结点，并且是在查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。 下图演示了将关键字值e、b、d、f、a、g、c依次插入到一棵初始为空树的二叉查找树的构建过程。

二、二叉查找树的插入 BiTree InsertBST（BiTree T，BiTreeNode *newnode）{ //在已存在的头指针为T的二叉查找树中插入新结点newnode if(!T) { T = newnode; T->left = T->right = NULL； } else if(newnode->data.key<T->data.key) T->left = InsertBST(T->left，newnode); T->right = InsertBST(T->right，newnode); return(T); 算法: 二叉查找树的递归插入算法 山东大学管理学院 戚桂杰 2019/2/16

二、二叉查找树的插入 BiTree InsertBST（BiTree T，BiTreeNode *newnode）{ //在已存在的头指针为T的二叉查找树中插入新结点newnode BiTreeNode *p； if(!T){ T = newnode; T->left = T->right = NULL； } p = T； while(p) { if（newnode->data.key == p->data.key）p = NULL； else if(p->data.key＞newnode->data.key && p->left) p = p->left; else if (!p->left) { p->left = newnode；p= NULL；} else if(!p->right) p = p->right； else { p->right = newnode；p= NULL；} } //end while return(T); } 算法 二叉查找树的非递归插入算法

f p 三、二叉排序树的删除 设待删结点指针为p，p的双亲结点指针为f，不失一般性，设p为f的左子女（若为右子女，类似）。 二叉排序树的删除算法分析 设待删结点指针为p，p的双亲结点指针为f，不失一般性，设p为f的左子女（若为右子女，类似）。 情况1：p为叶结点 F f P p f->lchild=NULL； free(p);

f p f f p f 情况2：P只有左子树PL或只有右子树PR F P PL F PL F P PR F PR f->lchild=p->lchild； free(p); f->lchild=p->rchild； free(p);

F P PR PL PR F P C CL Q QL S SL F C CL Q QL S SL PR 方法① PR作为s的右子女: s->rchild=p->rchild; c作为f的左子女： f->lchild=p->lchild; 删除p: free(p);

方法② f f F F p p P c S c PR C PR C q CL q CL Q s Q QL QL S SL SL 以前驱S代替P,然后删除s: p->data=s->data; SL作为Q的右子女: q->rchild=s->lchild; 释放结点s: free(s); 同时产生第三种方法：用P的后继代替P

算法9.7 Status DeleteBST(BiTree &T,keyType key){ if (!T) return FALSE; else { if (key==T->data.key) Delete(T); else if (key<T->data.key) DeleteBST(T->lchild,key); else DeleteBST(T->rchild,key) return TRUE;} } }// DeleteBST

算法9.8 void Delete(BiTree &p){ if (!p->rchild){q=p;p=p->lchild;free(q);} else if (!p->lchild) {q=p; p=p->rchild;free(q); } else {q=p; s=p->lchild; while (s->rchild) {q=s;s=s->rchild); p->data=s->data; if (q!=p) q->rchild=s->lchild; else q->lchild=s->lchild; } }//Delete

四、二叉排序树的查找分析 (b) (a) ASL(a)＝1/6(1+2+2+3+3+3)＝14/6 含有n个结点的二叉树的平均查找长度和树的形状有关。 45 24 53 12 37 93 (a) 12 24 37 45 93 53 (b) ASL(a)＝1/6(1+2+2+3+3+3)＝14/6 ASL(b)＝1/6(1+2+3+4+5+6)＝21/6

最好的情况 最坏的情况 一般的情况 二叉排序树的形态同折半查找的判定树 ASL＝O(㏒2n) 二叉排序树的形态为一棵单支树 ASL＝1/n(1＋2＋3＋……＋n)＝(n＋1)/2 一般的情况 ASL＝O(㏒2n)

练习 50 在如下二叉排序树中，依次删除两个元素 50, 60 80 50 120 60 110 150 55 70 53 80 60 在如下二叉排序树中，依次删除两个元素 50, 60 80 50 120 60 110 150 55 70 53 80 60 120 110 150 55 70 53 50 删除 50 2019/2/16

练习 60 在如下二叉排序树中，依次删除两个元素 50, 60 80 120 110 150 55 70 53 直接后继代替 80 60 在如下二叉排序树中，依次删除两个元素 50, 60 80 120 110 150 55 70 53 直接后继代替 80 60 120 110 150 55 70 53 60 删除 60 删除 60 80 55 120 110 150 53 70 直接前驱代替 2019/2/16

练习 10 在如下二叉排序树中，依次删除两个元素 10, 6 10 4 25 8 13 6 5 13 4 25 8 6 5 直接后继代替 8 在如下二叉排序树中，依次删除两个元素 10, 6 10 4 25 8 13 6 5 10 13 4 25 8 6 5 直接后继代替 删除 10 删除 10 8 4 25 6 13 5 直接前驱代替 2019/2/16

练习 6 6 在如下二叉排序树中，依次删除两个元素 10, 6 13 4 25 8 6 5 直接后继代替 13 4 25 8 5 8 4 在如下二叉排序树中，依次删除两个元素 10, 6 13 4 25 8 6 5 直接后继代替 13 4 25 8 5 删除 6 6 8 4 25 6 13 5 直接前驱代替 8 4 25 5 13 删除 6 6 2019/2/16

9.2 动态查找表 删除结点后必须保持二叉排序树 “左小右大” 情况1：被删结点是叶子 9.2 动态查找表 删除结点后必须保持二叉排序树 “左小右大” 情况1：被删结点是叶子 ① 删除该结点；② 父结点对应指针=NULL 情况 2 ：被删结点只有单子树 (被删结点本身是个左/右孩子) ① 删除该结点；② 该结点的单子树成为其父亲的左/右孩子 情况3：被删结点有双子树 ① 删除该结点；② 用中序遍历序列中被删结点的直接后继或前驱代替它 2019/2/16

四、平衡二叉树 定义 1.平衡二叉树（AVL树） 或者是一棵空树，或者是具有如下性质的二叉树： 1）它的左子树和右子树深度之差的绝对值不超过1 2）左子树和右子树的都是AVL树。 2.结点的平衡因子（BF） 3.平衡二叉排序树

图8.4 平衡二叉树与非平衡二叉树 (a) 平衡二叉树；(b) 非平衡二叉树

2) 动态平衡技术 如何构造出一棵平衡二叉排序树呢？Adelson-Velskii和Landis提出了一个动态地保持二叉排序树平衡的方法，其基本思想是：在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。通常将这样得到的平衡二叉排序树简称为AVL树。

所谓最小不平衡子树是指以离插入结点最近、且平衡因子绝对值大于1的结点作根结点的子树。为了简化讨论，不妨假设二叉排序树的最小不平衡子树的根结点为A，则调整该子树的规律可归纳为下列四种情况： (1)  LL型：新结点X插在A的左孩子的左子树里。调整方法见图8.5(a)。图中以B为轴心，将A结点从B的右上方转到B的右下侧，使A成为B的右孩子。 (2)  RR型：新结点X插在A的右孩子的右子树里。调整方法见图8.5(b)。图中以B为轴心，将A结点从B的左上方转到B的左下侧，使A成为B的左孩子。

(3) LR型：新结点X插在A的左孩子的右子树里。调整方法见图8 (3)  LR型：新结点X插在A的左孩子的右子树里。调整方法见图8.5(c)。分为两步进行：第一步以X为轴心，将B从X的左上方转到X的左下侧，使B成为X的左孩子，X成为A的左孩子。第二步跟LL型一样处理(应以X为轴心)。 (4)  RL型：新结点X插在A的右孩子的左子树里。调整方法见图8.5(d)。分为两步进行：第一步以X为轴心，将B从X的右上方转到X的右下侧，使B成为X的右孩子，X成为A的右孩子。第二步跟RR型一样处理(应以X为轴心)。

图8.5 平衡调整的四种基本类型(结点旁的数字是平衡因子) (a) LL型；(b) RR型；(c) LR型；(d) RL型 图8.5 平衡调整的四种基本类型(结点旁的数字是平衡因子) (a) LL型；(b) RR型；(c) LR型；(d) RL型

实际的插入情况可能比图8.5要复杂，因为A、B结点可能还会有子树。现举一例说明，设一组记录的关键字按以下次序进行插入：4、5、7、2、1、3、6，其生成及调整成二叉平衡树的过程示于图8.6。 在图8.6中，当插入关键字为3的结点后，由于离结点3最近的平衡因子为2的祖先是根结点5，因此第一次旋转应以结点4为轴心，把结点2从结点4的左上方转到左下侧，从而结点5的左孩子是结点4，结点4的左孩子是结点2，原结点4的左孩子变成了结点2的右孩子。第二步再以结点4为轴心，按LL类型进行转换。这种插入与调整平衡的方法可以编成算法和程序，这里就不再讨论了。

二叉平衡树插入结点(结点旁的数字为其平衡因子)

问题：如何使构造的二叉排序树成为AVL树？ 插入/删除结点通常会影响从根结点到插入结点的路径上的某些结点。 1）以某些结点为根的子树的深度发生变化； 2）某些结点的平衡因子发生变化； 3）某些结点失去平衡。

A B D C E A B D C E 1. 右单旋 h A C D B E A C E D B 2. 左单旋

左单旋 右单旋 A B D C F E h h-1 G 3. A E B D C F G A B D C F E G

4. D A C B E F h h-1 G 右单旋 左单旋 A C B E F G D A C B E F G D

9.2.2 B_树和B+树 一、B－树及其查找 1.定义：一棵m阶的B－树，或为一棵空树，或为满足下列条件的m叉树： 若根结点不是叶结点，则至少2棵子树； 除根以外的所有非终端结点至少有┌m/2 ┐棵子树； 所有非终端结点中包含下列信息数据：（A0,K1,A1,K2,A2,…，Kn,An)　 叶结点位于同一层次（外部结点/失败点）

2. 示例（一棵4阶B－树及查找过程） F a b c d e f g h T 查找时间取决因素 35 1 18 78 43 2 11 27 39 64 47 53 3 99 F a b c d e f g h T 查找时间取决因素 （1）等于给定值的关键字所在结点的层次； （2）结点中关键字的个数。

顺指针查找结点和在结点的关键字中顺序查找交叉进行的过程。具体方法： 3.查找过程： 顺指针查找结点和在结点的关键字中顺序查找交叉进行的过程。具体方法： 从根结点开始，将key与根结点中的各个关键字k1, k2,……， kj进行比较，由于该关键字序列有序，可采用顺序/二分查找方法。 若key= ki,(1≤i≤j),则查找成功； 若key< k1,则沿指针A0所指的子树中继续查找； 若ki<key<ki+1,则沿指针Ai所指的子树中继续查找； 若key>kj,则沿指针Aj所指的子树中继续查找。 在自上向下的查找过程中，若直到叶结点也没有找到值为key的关键字，则查找失败。

9.2.2 B_树和B+树 二、B＋树（B－的变型树） 1.定义：一棵m阶的B＋ 树与B－树的区别在于： 有n棵子树的结点中含有n个关键字； 所有的叶结点包含了全部关键字的信息，及指向这些关键字记录的指针，且叶结点本身依关键字从小到大排列。 所有的非终端结点可看成是索引部分，结点中仅含有其子树中根结点的最大/最小关键字。

2. 示例（一棵3阶B＋树及查找过程） 59 97 15 44 59 72 97 10 15 21 37 44 51 59 62 72 85 91 97 root sqt