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

Slides:



Advertisements
Similar presentations
二叉树在树结构的应用中起着非常重要的作用,因为对二叉树的许多操作算法简单,而任何树都可以与二叉树 相互转换,这样就解决了树的
Advertisements

第 9 章 查找.
主讲:计算机工程学院 李兰 答疑地点:主教学楼B区213
第九章 查找.
主讲:计算机工程学院 李兰 答疑地点:主教学楼B区213
第 六 章 查找 6.1 静态查找技术 6.2 二叉排序树 6.3 平衡二叉排序树(AVL树) *6.4 红-黑树 *6.5 B-树和B+树
数据结构课程的内容.
数据结构作业及答案 (C语言版).
第6章 树和二叉树 树型结构是一类非常重要的非线性结构。直观地,树型结构是以分支关系定义的层次结构。
助教:李伟力 电子科学与技术系 数据结构第二次习题课 助教:李伟力 电子科学与技术系
第九章. 查找 (Chapter 9. Searching)
第9章 查找 9.1 基本概念和术语 9.2 静态查找表 9.3 动态查找表 9.4 哈希表 9.5 小结 顺序查找
第8章 查找 在英汉字典中查找某个英文单词的中文解释;在新华字典中查找某个汉字的读音、含义;在对数表、平方根表中查找某个数的对数、平方根;邮递员送信件要按收件人的地址确定位置等等。可以说查找是为了得到某个信息而常常进行的工作。 计算机、计算机网络使信息查询更快捷、方便、准确。要从计算机、计算机网络中查找特定的信息,就需要在计算机中存储包含该特定信息的表。如要从计算机中查找英文单词的中文解释,就需要存储类似英汉字典这样的信息表,以及对该表进行的查找操作。本章将讨论的问题即是“信息的存储和查找”。
第八章 查找.
第8章 查找 8.1 静态查找表 8.2 动态查找表 8.3 哈希表.
第九章 查找 £9.1 概述 £9.2 静态查找表 £9.3 动态查找表 £9.4 哈希表 £9.1.1 查找表 £9.2.1 概述
第六章 二叉树和树 6.1 二叉树 6.2 二叉树的基本操作与存储实现 6.3 二叉树的遍历 6.4 线索二叉树 6.5 树和森林
第九章 查找.
第8章 查找 数据结构(C++描述).
树(三) 2012初赛知识点梳理.
第7章 查找 丽水学院工学院.
其他类型的链表主要内容 静态链表 循环链表 双向链表.
第九章查找.
第11章 查找 主要知识点 查找的基本概念 静态查找表 动态查找表 哈希表.
第七章 搜索结构 静态搜索结构 二叉搜索树 AVL树.
第八章 查找表 8.1概述 8.2静态查找表 8.3动态查找表 8.4哈希表及其查找.
第12章 樹狀搜尋結構 (Search Trees)
9.1-1 按照竞争树的办法求最小值需n-1次比较,然后在lgn个与最小值比较过的元素中求出最小值即为原来n个元素的次小值,需lgn-1次比较,所以共需n+lgn-2次比较 题目是要证明3n/2-2是最少的比较次数,而不是要构造出这样的算法。我们把某个元素与其它元素间的大小关系称作一条信息,那么最大元素包含n-1条信息(这个元素比其它n-1个元素都大),同样,最小元素也包含n-1条信息,同时求出最大和最小元素就需要获得2n-2条信息。未比较过的元素记为N,比较后较小的元素记为S,较大的元素记为
第九章 查找 2018/12/9.
第八章 查找表 8.1概述 8.2静态查找表 8.3动态查找表 8.4哈希表及其查找.
本章重点难点 重点:顺序查找、二分查找、二叉排序树查找以及散列表查找的基本思想和算法实现。
第六章 树和二叉树.
第7章 查找 北京师范大学 教育技术学院 杨开城.
第九章 查找(Search) 9.1 基本概念 9.2 静态查找表 9.3 动态查找表 9.4 Hash表.
何谓查找表 ? 查找表是由同一类型的数据元素(或记录)构成的集合。
第7章 查找 本章中介绍下列主要内容: 静态查找表及查找算法:顺序查找、折半查找 动态查找表及查找算法:二叉排序树 哈希表及查找算法.
第5章 树和二叉树 5.1树 5.2二叉树 5.3二叉树的遍历 5.4线索二叉树 5.5树、森林与二叉树的转换 5.6哈夫曼树.
第11讲 树和二叉树(二).
图内容回顾 图 Dijkstra算法 最短路径 Floyd算法 拓扑排序 邻接矩阵 有向图的应用 DAG图 关键路径 邻 接 表 存储结构
报告人:陈思同 数据结构与数据库习题课 报告人:陈思同
第五章 树 5.1 树的定义 树是一类重要的非线性数据结构,是以分支关系定义的层次结构 定义
第9章 内部排序 9.1 概述 9.2 插入排序 9.3 快速排序 9.4 选择排序 9.5 归并排序 9.6 基数排序
Ch.9 查找 查找和排序是两个重要的运算 §9.1 基本概念
数据结构 第9章 查找 什么是查找?? 静态查找 动态查找 哈希表 数据结构.
第九章 查找表 9.1静态查找表 9.2动态查找表 9.3哈希表及其查找.
第九章 查找 2019/2/16.
顺序表的插入.
无向树和根树.
计算机软件技术基础 数据结构与算法(5).
顺序表的删除.
第六章 树和二叉树 学习要点 理解树的定义和基本术语,重点了解二叉树的定义、性质、存储结构; 掌握二叉树遍历的递归算法及它的典型运算;
9.1 基本概念 9.2 线性表的查找 9.3 树表的查找 9.4 哈希表的查找 9.5 各种查找方法的比较
顺序查找.
Ch.9 查找 §9.1 基本概念 查找和排序是两个重要的运算
第 四 讲 线性表(二).
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
1.设A和B是集合,证明:A=B当且仅当A∩B=A∪B
树和图 tree and graph 蔡亚星.
#define RBTREE_RED 0 #define RBTREE_BLACK 1 typedef int dataType; typedef struct treeNode{ dataType key; int color; //red:0.
实验目的:掌握数据的顺序存储结构及它们在计算机中的操作。 实验内容:
第8章 查找 预备知识 8.1 静态查找表 8.2 动态查找表 8.3 哈希表.
第9章 查找 静态查找表 二叉排序树 平衡二叉树(AVL树) 小结 B树 哈希表.
插入排序的正确性证明 以及各种改进方法.
第七章 搜索结构 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
本节内容 1.二叉排序树的定义 2.二叉排序树的查找操作 3.二叉排序树的插入操作 4.二叉排序树的删除操作 5.二叉排序树的总结
第9章 查找 9.1 查找的基本概念 9.2 线性表的查找 9.3 树表的查找 9.4 哈希表查找.
本节内容 1. 平衡二叉树的定义 2.平衡化旋转 3.平衡二叉排序树的插入操作 昆山爱达人信息技术有限公司
第二章 线性表 东南大学计算机学院 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件.
最小生成树 最优二叉树.
§2 自由代数 定义19.7:设X是集合,G是一个T-代数,为X到G的函数,若对每个T-代数A和X到A的函数,都存在唯一的G到A的同态映射,使得=,则称G(更严格的说是(G,))是生成集X上的自由T-代数。X中的元素称为生成元。 A变, 变 变, 也变 对给定的 和A,是唯一的.
Presentation transcript:

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

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

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

§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,则失败 }

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

§ 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和中间点元素,若查找成功则返回;否则当前查找区间缩小一半,直至当前查找区间为空时查找失败。

§ 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; //当前查找区间为空时失败 }

查找过程 判定(比较)树:分析查找过程的二叉树,形态只与结点数相关,与输入实例的取值无关(为什么?)。例如n=11的形态如下图所示。 1 2 3 4 5 6 7 8 9 10 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

时间分析 比较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 = > <

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

§ 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

§ 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

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

§ 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

§ 9.3.1 二叉查找树(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 ); //查找右子树 }

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)

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

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)

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;// 返回根指针

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

不同的输入实例(数据集不同、或排列不同),生成的树的形态一般不同。对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倍,因此它并不适合排序。

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只有右孩子

①找到*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

②令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的中序后继就是其右孩子

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);

//现在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)

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

Ex. 9.9, 9.11, 9.31