Ch.9 查找 §9.1 基本概念 查找和排序是两个重要的运算

Presentation on theme: "Ch.9 查找 §9.1 基本概念 查找和排序是两个重要的运算"— Presentation transcript:

1 Ch.9 查找 §9.1 基本概念 查找和排序是两个重要的运算
对象：表、文件等。其中每个结点（记录）由多个数据项构成，假设每个结点有1个能唯一标识该结点的key。 定义：给定1个值K，在含有n个结点的表中找出关键字等于K的结点，若找到（查找成功），则返回该结点信息或它在表中的位置；否则（查找失败），返回相关指示信息。 分类： 查找过程中是否修改表？动态查找、静态查找 查找过程是否均在内存中进行？内部查找、外部查找

2 §9.1 基本概念 效率：与存储结构、文件状态（有序、无序）有关 平均查找长度(ASL)，即平均的比较次数，作为衡量查找效率的标准： Pi：查找第i个结点的概率 Ci：查找第i个结点的比较次数 设Pi＝1/n, 1≤i≤n 约定：typedef int KeyType;

3 § 9.2 线性表的查找 §9.2.1 顺序查找 对象：用线性表作为表的组织形式。 分类：静态查找、内部查找
方式：顺序查找、二分查找、分块查找 ＃define n 100// §9.2.1 顺序查找 基本思想 从表的一端开始，顺序扫描线性表，依次将扫描到的结点的Key与给定值K进行比较，若当前扫描到结点Key＝K，则查找成功返回；若扫描完整个表后，仍未找到，则查找失败。 适用范围：顺序表、链表 算法：

4 §9.2.1 顺序查找 typedef struct{ KeyType key; InfoType otherinfo; //应用相关
}NodeType, SeqList[n+1]; //0号单元作为哨兵 int SeqSearch( SeqList R, KeyType K) { //在R[1..n]中查找，成功时返回结点位置，失败时返回0 int n; R[0].key=K; //设置哨兵 for ( i=n; R[i].key != K; i-- ); //从后往前找 return i; //若i为0，则失败 }

5 §9.2.1 顺序查找 哨兵的作用 for中省略了下标越界i>=1判定,节约了约一半时间 时间分析 优缺点
成功：ASLss=(n+1)/2，key的平均比较次数约为表长的一半 失败：n+1次比较 优缺点 优点：简单，对存储结构、Key之间的关系均无特殊要求 缺点：效率低，当n较大时不宜用

6 § 9.2.2 二分（折半）查找 适用范围：顺序表、有序 基本思想（分治法）
（1）设R[low..high] 是当前查找区间，首先确定该区间的中点 位置：mid= (low+high)/2 //整除 （2）将待查的K值与R[mid]比较， ① K＝R[mid].key：查找成功，返回位置mid ② K＜R[mid].key：则左子表R[low..mid-1]是新的查找区间 ③ K＞R[mid],key：则右子表R[mid+1..high]是新的查找区间 初始的查找区间是R[1..n]，每次查找比较K和中间点元素，若查找成功则返回；否则当前查找区间缩小一半，直至当前查找区间为空时查找失败。

7 § 9.2.2 二分（折半）查找 算法： int BinSearch( SeqList R, KeyType K ) {
int mid, low=1, high=n; while ( low < high ) { //当前查找区间R[low..high]非空 mid= (low+high)/2； //整除 if ( R[mid].key==K ）return mid; //成功返回位置mid if ( K＜R[mid].key ) //两个子问题求解其中的一个 high=mid-1; //在左区间中查找 else low=mid+1；//在右区间中查找 } // endwhile return 0; //当前查找区间为空时失败 }

8 查找过程 判定(比较)树：分析查找过程的二叉树，形态只与结点数相关，与输入实例的取值无关（为什么？）。例如n＝11的形态如下图所示。
（05,13,19,21,37,56,64,75,80, 88, 92），找21成功，找85失败。 内部结点 R[1..11] 6 外部结点 R[1..5] R[7..11] ＝ ＜ ＞ 9 3 R[10..11] R[1..2] R[4..5] R[7..8] 1 7 10 4 R[11..11] Φ R[2..2] R[8..8] Φ R[5..5] Φ Φ 11 2 8 5 9-10 3-4 6-7 -1 Φ Φ Φ Φ Φ Φ Φ Φ 11- 1-2 2-3 4-5 5-6 7-8 8-9 10-11

9 时间分析 比较1次：查找R[6] 比较2次：查找R[3]、R{9] 比较3次：查找R[1]、R[4]、R[7]、R[10] 比较4次：查找R[2]、R[5]、R[8]、R[11] 6 R[1..11] 1 9 4 3 7 10 2 R[1..5] R[7..11] R[10..11] R[5..5] Φ R[11..11] -1 4-5 1-2 2-3 3-4 R[1..2] R[2..2] 5 8 R[4..5] 5-6 6-7 7-8 11 R[7..8] R[8..8] 8-9 9-10 11- 10-11 ＝ ＞ ＜

10 § 9.2.2 二分（折半）查找 时间分析 总结：查找过程走了一条从判定树的根到被查结点的路径。
成功：终止于一个内部结点，所需的Key比较次数恰为该结点在树中的层数; 失败：终止于一个外部结点，所需的Key比较次数为该路径上内部结点总数。（层数－1） 平均查找长度（ASL）： 设n＝2h-1, 则树高h＝lg(n+1) //不计外部结点的满二叉树 第k层上结点数为2k－1，找该层上每个结点的比较次数为k，在等概率假设下： 最坏时间：查找失败，不超过树高 ⌈lg(n+1)⌉ 在链表上可做折半查找吗？

11 § 9.2.3 分块查找（索引顺序查找） 22 48 86 1 7 13 最大关键字 起始地址 存储结构 关键字状态
将R[1..n]均分成b块，前b-1块中结点数为s＝⌈n/b⌉ ，最后一块中的结点数可能小于s，引入索引表标记块。 关键字状态 分块有序：块间有序，块内不一定有序; 例子：n＝18，b＝3，s＝6 22 48 86 1 7 13 最大关键字 起始地址 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 49 86 53

12 § 9.2.3 分块查找（索引顺序查找） 性能分析 EX.9.3, 9.25 查找过程（两步查找）
索引表查找：确定块。n较大时用折半查找，n较小时用顺序查找。 块内查找：只能顺序查找。 性能分析 以折半查找确定块 ASL＝ ASLbs＋ASLss＝lg(b＋1)-1＋(s＋1)/2≈lg(n/s＋1)＋s/2 以顺序查找确定块 ASL＝ ASLss＋ASLss＝(b＋1)/2＋(s＋1)/2＝(s2＋2s＋n)/(2s) 当s＝ 时，ASL取极小值 ＋1 块不一定等分 EX.9.3, 9.25

13 § 9.3 树上的查找（动态查找） 折半查找效率最高，但它不适应插删操作。本节讨论适用于动态查找，即查找过程中动态维护表结构。
§ 二叉查找树（BST） 定义 二叉查找树或是空树，或满足下述BST性质的二叉树： ①若它的左子树非空，则左子树上所有结点的keys均小于根的key ②若它的右子树非空，则右子树上所有结点的keys均大于根的key ③左右子树又都是二叉查找树 Note：性质1或2中，可以将“﹤” 改为“≤”；或“﹥”改为“≥” BST性质 二叉查找树的中序序列是一个递增有序序列

14 § 9.3.1 二叉查找树（BST） 举例 存储结构 5 3 7 2 9 4 typedef struct node {
KeyType key; InfoType otherinfo; struct node *lchild, *rchild; } BSTNode, *BSTree; 5 3 7 2 9 4

15 § 二叉查找树（BST） 5 3 7 2 9 4 1.查找 基本思想 从根结点开始比较，若当前结点的key与待查的key相等，则查找成功，返回该结点的指针；否则在左子树或右子树中继续查找。若树中没有待查结点，则失败于某个空指针上。 算法 BSTNode *SearchBST( BSTree T, KeyType key ){ //在T上查找key=K的节点，成功时返回该节点，否则返回NULL if ( T==NULL || key==T->key ) return T; //若T为空，查找失败；否则成功 if ( key < T->key ) return SearchBST ( T->lchild, key ); //查找左子树 else return SearchBST ( T->rchild, key ); //查找右子树 }

16 5 3 7 2 9 4 § 9.3.1 二叉查找树（BST） 1.查找（续） 时间 若成功，则走了一条从根到待查节点的路径
若失败，则走了一条从根到叶子的路径？（不一定） 上界：O(h) 分析：与树高相关 ①最坏情况：单支树，ASL=(n+1)/2,与顺序查找相同 ②最好情况：ASL≈lgn，形态与折半查找的判定树相似 ③平均情况：假定n个keys所形成的n!种排列是等概率的，则可证明由这n!个序列产生的n!棵BST（其中有的形态相同）的平均高度为O(lgn)，故查找时间仍为O(lgn)

17 2、BST的插入和生成 插入 算法思想 保证新结点插入后满足BST性质，基本思想如下：
若T为空，则为待插入的Key申请一个新结点，并令其为根； 否则，从根开始向下查找插入位置，直到发现树中已有Key，或找到一个空指针为止； 将新结点作为叶子插入空指针的位置。 查找过程是一个关键字的比较过程，易于写出递归或非递归算法，也可以调用查找操作。 算法实现

18 void InsertBST( BSTree *T, KeyType key ) { //*T是根
BSTNode *f, *p=*T; //p指向根结点 while( p ) { //当树非空时，查找插入位置 if ( p->key==key ) return; //树中已有key，不允许重复插入 f＝p；// f和p为父子关系， 循环不变量：*parent为*p的双亲 p＝( key < p->key ) ? p->lchild; p->rchild; } //注意：树为空时，无须查找 p = (BSTNode *) malloc(sizeof(BSTNode)); p->key=key; p->lchild=p->rchild=NULL; //生成新结点 if ( *T ==NULL ) * T=p; //原树为空,新结点为根 else //原树非空, 新结点作为*f的左或右孩子插入 if ( key < f->key ) f->lchild=p; else f->rchild=p; } //时间为O（h）

19 2、BST的插入和生成 生成 } 算法： 从空树开始，每输入一个数据就调用一次插入算法。
算法： 从空树开始，每输入一个数据就调用一次插入算法。 BSTree CreateBST( void ) { BSTree T＝NULL; //初始时T为空 KeyType key; scanf( “%d”, &key ); while( key ) { //假设key＝0表示输入结束 InsertBST ( &T, key ) ; //将key插入树T中 scanf( “%d”, &key )；// 读入下一个关键字 } return T；// 返回根指针

20 2、BST的插入和生成 举例 输入实例 {10， 18， 3， 8， 12， 2， 7， 3} 10 18 3 8 12 2 7

21 不同的输入实例（数据集不同、或排列不同），生成的树的形态一般不同。对n个结点的同一数据集，可生成n！棵BST。 例外情况
一般情况 不同的输入实例（数据集不同、或排列不同），生成的树的形态一般不同。对n个结点的同一数据集，可生成n！棵BST。 例外情况 但有时不同的实例可能生成相同的BST，例如：（2，3，7，8，5，4）和（2，3，7，5，8，4）可构造同一棵BST。 排序树名称的由来 因为BST的中序序列有序，所以对任意关键字序列，构造BST的过程，实际上是对其排序。 生成n个结点的BST的平均时间是O(nlgn), 但它约为堆排序的2－3倍，因此它并不适合排序。

22 3、BST的删除 保证删一结点不能将以该结点为根的子树删去，且仍须满足BST性质。即：删一结点相当于删有序序列中的一个结点。
基本思想 查找待删结点*p，令parent指向其双亲（初值NULL）；若找不到则返回，否则进入下一步。 在删除*p时处理其子树的连接问题，同时保持BST性质不变。 case1:*p是叶子，无须连接子树，只需将*parent中指向*p的指针置空 case2:*p只有1个孩子，只须连接唯一的1棵子树，故可令此孩子取代*p与 其双亲连接（4种状态） parent p child parent p child child parent p parent p child *p只有左孩子 *p只有右孩子

23 ①找到*p 的中序后继(或前驱)*s，用*p的右(或左)子树取代*p与其双亲*parent连接；
case3: *p有2个孩子，有2种处理方式 ①找到*p 的中序后继(或前驱)*s，用*p的右(或左)子树取代*p与其双亲*parent连接； 而*p的左(或右)子树PL则作为*s的左(或右)子树与*s连接。缺点：树高可能增大。 PL sR p parent s pr PL sR s pr parent

24 ②令q=p，找. q的中序后继. p，并令parent指向. p的双亲，将. p的右子树取代. p与其双亲. parent连接。将
②令q=p，找*q的中序后继*p，并令parent指向*p的双亲，将*p的右子树取代*p与其双亲*parent连接。将*p的内容copy到*q中，相当于删去了*q，将删*q的操作转换为删*p的操作。对称地，也可找*q的中序前驱 因为*p最多只有1棵非空的子树，属于case2。实际上case1也是case2的特例。因此，case3采用该方式时，3种情况可以统一处理为case2。 q=p parent p child q=p p child *q的中序后继就是其右孩子

25 3、BST的删除 算法 void DelBSTNode( BSTree *T, KeyType key) { //*T是根
BSTree *q, *child, *parent=NULL, *p=*T; while ( p ) { //找待删结点 if ( p->key ==key ) break; //已找到 parent=p; //循环不变式是*parent为*p的双亲 p＝( key < p->key ) ? p->lchild; p->rchild; } if ( !p ) return; //找不到被删结点，返回 q=p; //q记住被删结点*p if (q->lchild && q->rchild ) //case3，找*q的中序后继 for(parent=q,p=q->rchild; p->lchild; parent=p, p=p->lchild);

26 //现在3种情况已统一到情况2，被删结点*p最多只有1个非空的孩子
child=(p->lchild)？p->lchild; p->rchild; //令child指向*p非空的孩子，仅case1时child为空 If ( !parent ) //*p的双亲为空，说明 *p是根，即删根结点 *T=child; //若是情况1，则树为空；否则*child取代*p成为根 else { //*p非根，它的孩子取代它与*p的双亲连接，即删 *p if ( p==parent->lchild ) parent->lchild=child; else parent->rchild=child; if ( p != q ) //情况3，将*p的数据copy到*q中 q->key=p->key; //若有其他数据亦需copy } free( p ); //删除*p } //时间O(h)

27 3、平衡二叉树和平衡的二叉查找树 平衡二叉树 任一结点的左右子树高度大致相同，即只要二叉树高度为O(lgn)，则可认为它是平衡的。
完全平衡二叉树 任一结点的左右子树高度完全相同（满二叉树） 平衡的二叉查找树 满足BST性质的平衡二叉树 AVL树：任一结点的左右子树的高度之差的绝对值不超过1，h≈1.44lgn 红黑树：h≈2lgn 平衡机制 AVL树：4种旋转 红黑树：2种旋转

28 Ex. 9.9, 9.11, 9.31