数据结构 检索方法
- 格式：ppt
- 大小：188.00 KB
- 文档页数：10
下载文档原格式
合集下载
es查询索引数据结构
es查询索引数据结构Elasticsearch是一个开源的分布式搜索和分析引擎，它使用了一种称为倒排索引的数据结构来加速搜索操作。
在Elasticsearch中，倒排索引是其核心数据结构之一，它提供了高性能的数据检索和全文搜索功能。
倒排索引是一种在实现全文搜索中常用的数据结构，它的设计目标是快速定位包含特定词项的文档。
与传统的索引方法不同，倒排索引将词项映射到包含该词项的文档列表。
这种结构使得我们可以通过将搜索词与倒排索引相匹配来快速定位包含该词项的文档，并以此对搜索结果进行排序。
在Elasticsearch中，每个索引都包含一个或多个分片，每个分片都是一个独立的倒排索引。
每个分片由多个段组成，每个段代表一个不可变的倒排索引，这个设计使得Elasticsearch可以快速添加、删除或合并索引数据。
每个段又由多个倒排索引组成，每个倒排索引包含一系列词项和文档列表。
词项是被索引的文档中的一个单词或短语。
文档列表是一个按文档ID排序的数组，其中每个文档的ID记录了包含该词项的文档。
在一个倒排索引中，词项被分解成不同的标记或标识符，这个过程称为分词。
分词是一个重要的步骤，用于将输入的文本拆分成可搜索的单词或短语。
Elasticsearch使用各种分析器来处理不同的语言和文本类型，并生成标记流，然后将它们存储在倒排索引中。
倒排索引的好处在于它可以在O(1)的时间复杂度内定位到包含特定词项的文档。
当进行搜索操作时，Elasticsearch会将搜索词与倒排索引进行匹配，并返回匹配的文档列表。
然后，它可以按照各种因素对文档进行排序，例如匹配度、得分和其他自定义的评分因素。
为了提高查询性能，Elasticsearch在内存中缓存了经常访问的倒排索引段。
这些缓存可以加速搜索操作，尤其是对于经常访问的查询。
此外，Elasticsearch还支持分布式搜索和并行查询，通过将搜索操作分布到多个节点上，可以大大提高搜索速度和吞吐量。
数据结构教案第9章 查找
●性能分析 定义：为了确定记录在查找表中的位置，需和给定值进行比 较的关键字个数的期望值称为查找算法在查找成功时的平均查找 长度。
ASL = ∑ Pi C i
i =1
n
其中：Pi为查找表中第i个记录的概率；Ci为找到第i个记 录的比较次数； 查找成功的平均查找长度：
1 n n +1 ASL = ∑ (n − i + 1) = 2 n i =1
索引表 最大关键字 起始地址
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动态查找表 特点：表结构本身是在查找过程中动态生 成的，即对于给定值key，若表中存在其关键 字等于key的记录，则查找成功返回；否则插 入关键字等于key的记录。
10 10 9 15 9 17 17 15
a
16
作业：(P55)9.9, 9. 33
9．3哈希表 9．3．1什么是哈希表 哈希函数：在记录的关键字和它的存储位置之间建立 一个确定的对应关系f，使每个关键字和结构中一个 唯一的存储位置相对应，称对应关系f为哈希(Hash) 函数。 哈希表：按哈希函数建立的表称为哈希表。
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; \*q！=p正常情况 else q->lchile= s->lchild; \* q=p意外者，p的左子树的根没有右子树 free(s); }\\else }
数据存储与检索在信息技术基础模块中的原理与方法
数据存储与检索在信息技术基础模块中的原理与方法数据存储与检索是信息技术基础模块中的重要内容，它涉及到如何高效地存储和管理大量数据，以及如何快速地检索和获取所需信息。
在这篇文章中，我将详细介绍数据存储与检索的原理和方法。
首先，我们来讨论数据存储的原理与方法。
数据存储是指将数据按照一定的结构和规则存放在存储介质中，以便日后进行读取和使用。
现代信息技术中常用的数据存储介质包括硬盘、闪存、内存等。
数据存储的基本原理是将数据以二进制位的形式存储在介质中。
在计算机中，数据以字节为单位进行存储。
每个字节由8个二进制位组成，可以表示256种不同的状态，包括数字、字符、图像等各种类型的数据。
对于大量数据的存储，我们需要使用数据结构来进行组织和管理。
常见的数据结构包括数组、链表、栈、队列、树和图等。
不同的数据结构适用于不同的存储需求。
例如，数组适用于一维数据的存储，链表适用于动态数据的存储。
另外，数据存储还涉及到数据的持久性和安全性。
持久性是指数据在断电或系统崩溃等异常情况下的保存能力。
为了保证数据的持久性，我们需要将数据写入非易失性存储介质中，如硬盘等。
而安全性是指数据的保密性和完整性。
为了保证数据的安全性，我们可以使用加密技术和备份技术。
接下来，我们探讨数据检索的原理与方法。
数据检索是指根据特定的需求从存储介质中查找和获取数据的过程。
常见的数据检索方法包括线性查找、二分查找、哈希查找和索引查找等。
线性查找是一种最简单的数据检索方法，它从存储介质的头部开始逐个比较数据，直到找到目标数据或遍历完所有数据。
线性查找的时间复杂度为O(n)，其中n 为数据的总个数。
二分查找是一种基于有序数据的查找方法。
它通过将目标数据与中间数据进行比较，然后根据比较结果确定下一次查找的范围，从而缩小查找范围。
二分查找的时间复杂度为O(logn)，其中n为数据的总个数。
哈希查找是一种利用哈希函数将数据映射到固定位置的查找方法。
它通过将目标数据计算哈希值，然后根据哈希值找到对应的存储位置，从而快速地定位目标数据。
数据结构_查找原理及典型的查找算法
无法实现！因全部元素的定位只能从头指针head开 始，是一种非随机存取结构。
3.对非线性(树)结构如何进行折半查找？ 可借助二叉排序树来查找（属动态查找表形式）。
9.1.2 有序表的查找
折半查找过程可以描述为一棵二叉树
折半查找的判定树 如：（a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11）
总之：
二叉排序树既有类似于折半查找的特性，又采用了链 表存储，它是动态查找表的一种适宜表示。
一、二叉排序树
（3）构造过程: 例：输入序列{45，12，37，3，53，100，24}
45
12
53
3
37
100
24
一、二叉排序树
（2）非递归查找过程 BiTree SearchBST(BiTree T,KeyType key){
CH9 查找
查找的基本概念 9.1 静态查找表
9.1.1 顺序查找 9.1.2 有序表的查找 9.1.3 索引顺序表的查找
9.2 动态查找表
9.2.1 二叉排序树和平衡二叉树 9.2.2 B－和B＋树
9.3 哈希表
查找的基本概念
1.查找表 2.查找
关键字 主关键字 次关键字
}
9.2.1 二叉排序树和平衡二叉树
一、二叉排序树 二、平衡二叉树
一、二叉排序树
1.定义、特点、构造过程
（1）定义 二叉排序树或者是一棵空树，或是具有下列性质的二叉树：
若左子树非空，则左子树上所有结点的值均小于它的 根结点的值。
若右子树非空，则右子树上所有结点的值均大于它的 根结点的值。
有序/无序表 有序表
顺序/链式存 储
顺序存储
分块查找 介于二者之间 表中元素逐段有序 顺序/链式存储
3.对非线性(树)结构如何进行折半查找？ 可借助二叉排序树来查找（属动态查找表形式）。
9.1.2 有序表的查找
折半查找过程可以描述为一棵二叉树
折半查找的判定树 如：（a1, a2, a3, a4, a5, a6, a7, a8, a9, a10, a11）
总之：
二叉排序树既有类似于折半查找的特性，又采用了链 表存储，它是动态查找表的一种适宜表示。
一、二叉排序树
（3）构造过程: 例：输入序列{45，12，37，3，53，100，24}
45
12
53
3
37
100
24
一、二叉排序树
（2）非递归查找过程 BiTree SearchBST(BiTree T,KeyType key){
CH9 查找
查找的基本概念 9.1 静态查找表
9.1.1 顺序查找 9.1.2 有序表的查找 9.1.3 索引顺序表的查找
9.2 动态查找表
9.2.1 二叉排序树和平衡二叉树 9.2.2 B－和B＋树
9.3 哈希表
查找的基本概念
1.查找表 2.查找
关键字 主关键字 次关键字
}
9.2.1 二叉排序树和平衡二叉树
一、二叉排序树 二、平衡二叉树
一、二叉排序树
1.定义、特点、构造过程
（1）定义 二叉排序树或者是一棵空树，或是具有下列性质的二叉树：
若左子树非空，则左子树上所有结点的值均小于它的 根结点的值。
若右子树非空，则右子树上所有结点的值均大于它的 根结点的值。
有序/无序表 有序表
顺序/链式存 储
顺序存储
分块查找 介于二者之间 表中元素逐段有序 顺序/链式存储
数据结构查找表
如何进行查找
在一个结构中查找某个数据元素的过程，依赖于数据 元素在结构中的地位，即依赖于数据元素的组织关系 （人为的）。
在计算机中进行查找的方法随数据结构不同而不同。 即随查找表的不同而不同。
9.1 静态查找表
顺序表的查找 有序表的查找 静态树表的查找
查找表的结构 查找过程描述 查找性能分析 查找方法比较
n ASLbs log 2 ( 1) 1 s
9.2 动态查找表
动态查找表的ADT
动态查找表的特点是，表结构本身是在查找过程中动态生成的。即， 对于给定值key，若表中存在其关键字等于key的记录，则查找成 功返回；否则，插入关键字等于key的记录。
P226: SearchDSTable(DT，key )； InsertDSTable(&DT，e )； DeleteDSTable(&DT, e )；
给定值进行比较的关键字个数最多也不超过log2 n 1
折半查找的ASL
假设有序表的长度为n=2h-1，则描述折半查找的判定树是深度 为h的满二叉树。 该树中层次为1的结点有1个，层次为2的结点有2个，…，层次 为h的结点有2h-1个。 假设有序表中每个记录的查找概率相等(Pi = 1/n)。
05 low 13 19 21 37 56 64 75 80 88 92 high
mid
high low
mid (low high) / 2
例子
给定值key = 21的查找过程: 给定值key = 85的查找过程:
下界low>上界high，查找不成功。
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; }
数据结构(八)查找
122
99
250
110
300
280
类C程序实现： void InsertBST(*&t，key) //在二叉排序树中插入查找关键字key { if(t= = NULL){ t=new BiTree; t->lchild=t->rchild=NULL; t->data=key; return; } if(key<t->data ) InsertBST(t->lchild,key); else InsertBST (t->rchild, key ); } void CreateBiTree(tree,d[ ],n） //n个数据在数组d中，tree为二叉排序树根 { tree=NULL; for(i=0;i<n;i++) InsertBST(tree,d[i]); }
p q
void delete(*&p) { if(p->rchild = = NULL) { q=p; p=p->lchild; delete q; } else if(p->lchild= =NULL) { q=p; p=p->rchild; delete q; } else { q=p; s=p->lchild; while(s->rchild!=NULL) {q=s; s=s->rchild;} p->data=s->data; if(q!=p) q->rchild=s->lchild; else q->lchild=s->lchild; } delete s; }
在xL中选值最大的代替x，该数据按二叉排序树的性质应在 最右边。
f x f s c
99
250
110
300
280
类C程序实现： void InsertBST(*&t，key) //在二叉排序树中插入查找关键字key { if(t= = NULL){ t=new BiTree; t->lchild=t->rchild=NULL; t->data=key; return; } if(key<t->data ) InsertBST(t->lchild,key); else InsertBST (t->rchild, key ); } void CreateBiTree(tree,d[ ],n） //n个数据在数组d中，tree为二叉排序树根 { tree=NULL; for(i=0;i<n;i++) InsertBST(tree,d[i]); }
p q
void delete(*&p) { if(p->rchild = = NULL) { q=p; p=p->lchild; delete q; } else if(p->lchild= =NULL) { q=p; p=p->rchild; delete q; } else { q=p; s=p->lchild; while(s->rchild!=NULL) {q=s; s=s->rchild;} p->data=s->data; if(q!=p) q->rchild=s->lchild; else q->lchild=s->lchild; } delete s; }
在xL中选值最大的代替x，该数据按二叉排序树的性质应在 最右边。
f x f s c
数据结构-查找分析
第八章查找一、填空题1.线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。
设有100个结点，用二分法查找时，最大比较次数是。
2．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。
3. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。
4、对线性表进行二分查找时，要求线性表必须以方式存储，且结点按关键字排列。
5．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为_ __次；当使用监视哨时，若查找失败，则比较关键字的次数为__ 。
6．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为____ _____。
7. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是_8. 已知二叉排序树的左右子树均不为空，则_______上所有结点的值均小于它的根结点值，________上所有结点的值均大于它的根结点的值。
9、中序遍历二叉排序树得到的序列是序列（填有序或无序）。
10、从有序表(10，16，25，40，61，28，80，93)中依次二分查找40和61元素时，其查找长度分别为和。
二、单项选择题（）1．在表长为ｎ的链表中进行顺序查找，它的平均查找长度为Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;Ｃ. ＡＳＬ＝n＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１（）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。
若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。
A．20，70，30，50 B．30，88，70，50C．20，50 D．30，88，50（）3．对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。
数据结构——第五章查找：01静态查找表和动态查找表
数据结构——第五章查找：01静态查找表和动态查找表1.查找表可分为两类：（1）静态查找表：仅做查询和检索操作的查找表。
（2）动态查找表：在查询之后，还需要将查询结果为不在查找表中的数据元素插⼊到查找表中；或者，从查找表中删除其查询结果为在查找表中的数据元素。
2.查找的⽅法取决于查找表的结构：由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。
为了提⾼查找效率，需要在查找表中的元素之间⼈为地附加某种确定的关系，⽤另外⼀种结构来表⽰查找表。
3.顺序查找表：以顺序表或线性链表表⽰静态查找表，假设数组0号单元留空。
算法如下：int location(SqList L, ElemType &elem){ i = 1; p = L.elem; while (i <= L.length && *(p++)!= e) { i++; } if (i <= L.length) { return i; } else { return 0; }}此算法每次循环都要判断数组下标是否越界，改进⽅法：加⼊哨兵，将⽬标值赋给数组下标为0的元素，并从后向前查找。
改进后算法如下：int Search_Seq(SSTable ST, KeyType kval) //在顺序表ST中顺序查找其关键字等于key的数据元素。
若找到，则函数值为该元素在表中的位置，否则为0。
{ ST.elem[0].key = kval; //设置哨兵 for (i = ST.length; ST.elem[i].key != kval; i--) //从后往前找，找不到则返回0 { } return 0;}4.顺序表查找的平均查找长度为：(n+1)/2。
5.上述顺序查找表的查找算法简单，但平均查找长度较⼤，不适⽤于表长较⼤的查找表。
若以有序表表⽰静态查找表，则查找过程可以基于折半进⾏。
算法如下：int Search_Bin(SSTable ST, KeyType kval){ low = 1; high = ST.length; //置区间初值 while (low <= high) { mid = (low + high) / 2; if (kval == ST.elem[mid].key) { return mid; //找到待查元素 } else if (kval < ST.elem[mid].key) { high = mid - 1; //继续在前半区间查找 } else { low = mid + 1; //继续在后半区间查找 } } return 0; //顺序表中不存在待查元素} //表长为n的折半查找的判定树的深度和含有n个结点的完全⼆叉树的深度相同6.⼏种查找表的时间复杂度：（1）从查找性能看，最好情况能达到O(logn)，此时要求表有序；（2）从插⼊和删除性能看，最好情况能达到O(1)，此时要求存储结构是链表。
c语言检索方法
c语言检索方法C语言检索方法引言：C语言是一门广泛应用于软件开发领域的高级编程语言，因其简洁、高效和可移植性而备受青睐。
在大型软件项目中，对数据的检索是非常常见的需求。
本文将介绍几种常用的C语言检索方法，帮助读者更好地理解和应用这些方法。
一、线性查找线性查找是最简单、最直接的一种检索方法。
它的基本思想是从数据集合的第一个元素开始逐个比较，直到找到目标元素或遍历完整个集合。
如果目标元素存在于集合中，线性查找的时间复杂度为O(n)，其中n为集合的大小。
二、二分查找二分查找也称为折半查找，它是一种基于有序数据集合的检索方法。
二分查找的关键思想是通过与数据集合中间元素的比较，将待查找的数据集合一分为二，然后继续在其中一部分进行查找，直到找到目标元素或确定目标元素不存在。
二分查找的时间复杂度为O(log n)，其中n为集合的大小。
但要注意，二分查找只适用于有序数据集合。
三、哈希查找哈希查找是一种基于哈希表的检索方法。
哈希表是一种以键-值对形式存储数据的数据结构，通过将键映射到哈希表中的位置来实现快速检索。
在哈希查找中，首先需要将数据集合中的元素通过哈希函数映射到哈希表的位置，然后根据目标元素的键在哈希表中进行查找。
哈希查找的平均时间复杂度为O(1)，但在最坏情况下可能达到O(n)。
四、二叉搜索树二叉搜索树（Binary Search Tree，简称BST）是一种基于树结构的检索方法。
它具有以下性质：左子树中的所有节点的键值小于根节点的键值，右子树中的所有节点的键值大于根节点的键值。
通过利用这种有序性，可以在二叉搜索树中快速查找目标元素。
二叉搜索树的平均查找时间复杂度为O(log n)，但在最坏情况下可能达到O(n)。
五、B树和B+树B树和B+树是一种常用的多叉平衡查找树。
相比于二叉搜索树，B 树和B+树可以在每个节点中存储多个键值，从而提高了数据的检索效率。
B树和B+树通常用于磁盘存储系统中，可以有效地降低磁盘I/O的次数，提高数据的访问速度。
数据结构 查找
生成二叉排序树过程。
10 3 2 7 8 18 12
注：二叉排序树与关键字排列顺序有关，排列顺 序不一样，得到的二叉排序树也不一样。
二叉排序树的建立的算法
反复调用二叉排序树的插入算法即可 Bitree Creat (int n) { //建立含有n个结点的二叉排序树
Bitree T= NULL;
for ( int i=1; i<=n; i++) {
else if LT(key,p->key) p->lchild=s;
else p->rchild=s
return TRUE； }
//被插结点*s为右孩子
else return FALSE;
}// Insert BST
//树中已有关键字相同的结点，不再插入
4）二叉排序树的建立
例：关键字序列{ 10、18、3、8、12、2、7、3 }
5）二叉排序树上的删除
对于二叉排序树，删去树上一个结点相当于删去有序 序列中的一个记录，在删除某个结点之后依旧要保持二叉 排序树的特性。
如何在二叉排序树上删去一个结点呢?
设在二叉排序树上被删结点为*p（指向结点的指针为 p)，其双亲结点为*f，设*p是*f的左孩子。 f F p P c PR C q Q s CL S QL SL
low
( 08,
( 08,
mid
14,
14,
high
55, 68, 79,
79,
23,
23,
37,
37,
46,
46,
91 )
low
55,
mid
68,
high
91 )
low mid
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
顺序查找
1．顺序查找的基本思想 ． 顺序查找是一种最简单的查找方法，它的基本思想是： 顺序查找是一种最简单的查找方法，它的基本思想是：从 表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字 表的一端开始， 顺序扫描线性表， 和待找的值Ｋ相比较，若相等，则查找成功， 和待找的值Ｋ相比较，若相等，则查找成功，若整个表扫描完 仍末找到关键字等于Ｋ的元素，则查找失败。 毕，仍末找到关键字等于Ｋ的元素，则查找失败。 顺序查找既适用于顺序表，也适用于链表。若用顺序表， 顺序查找既适用于顺序表，也适用于链表。若用顺序表， 既适用于顺序表 查找可从前往后扫描，也可从后往前扫描，但若采用单链表， 查找可从前往后扫描，也可从后往前扫描，但若采用单链表， 则只能从前往后扫描。另外， 则只能从前往后扫描。另外，顺序查找的表中元素可以是无序 的。 衡量一个查找算法性能优劣的标准是平均查找长度， 衡量一个查找算法性能优劣的标准是平均查找长度，即在 查找成功的情况下所需的平均比较次数。对于等概率顺序查找， 查找成功的情况下所需的平均比较次数。对于等概率顺序查找， 它的平均查找长度为： 它的平均查找长度为 ： （ n+1） /2。 若失败 ， 平均比较结点个 ） 。 若失败， 数为n+1。 。 数为
查找 K=21 的示意图
0
05
1
13
2
19 [
3
21
4
37
5
] 56
6
64
7
74
8
80
9 10
88 92
mid low hig (d ) 经过三次比较后的情形 图 8-1 (array[mid].key=21)
查找成功) 查找 K=21 的示意图 (查找成功 查找成功
0 0 [ 05
1 1 13
2 2 19
二分查找 1.二分查找的基本思想 二分查找的基本思想 二分查找，也称折半查找，是一种高效率的查找方法。 二分查找，也称折半查找，是一种高效率的查找方法。 但要求表中元素必须按关键字有序(升序或降序 升序或降序)。 但要求表中元素必须按关键字有序 升序或降序 。不妨假 设表中元素为升序排列。二分查找的基本思想是： 设表中元素为升序排列。二分查找的基本思想是：首先将 待查值K与有序表 与有序表array[0]到array[n-1]的中点 的中点mid上的关 待查值 与有序表 到 的中点 上的关 键字array[mid].key进行比较，若相等，则查找成功；否 进行比较， 键字 进行比较 若相等，则查找成功； 则在array[1]到array[mid-1] 则，若array[mid].key>k ， 则在 到 中继续查找，若有array[mid].key<k ， 则在 则在array[mid+1] 中继续查找，若有 中继续查找。 到array[n-1]中继续查找。每通过一次关键字的比较，区 中继续查找 每通过一次关键字的比较， 间的长度就缩小一半，区间的个数就增加一倍， 间的长度就缩小一半，区间的个数就增加一倍，如此不断 进行下去，直到找到关键字为K的元素 的元素； 进行下去，直到找到关键字为 的元素；若当前的查找区 间为空(表示查找失败 表示查找失败)。 间为空 表示查找失败 。
二叉排序树查找 二叉排序树（ 二叉排序树（Binary Sorting Tree），它或者是一棵空树， ） 它或者是一棵空树， 或者是一棵具有如下特征的非空二叉树： 或者是一棵具有如下特征的非空二叉树： (1)若它的左子树非空， 则左子树上所有结点的关键字均小于 若它的左子树非空， 若它的左子树非空 根结点的关键字； 根结点的关键字； (2)若它的右子树非空， 则右子树上所有结点的关键字均大于 若它的右子树非空， 若它的右子树非空 等于根结点的关键字； 等于根结点的关键字； (3)左、右子树本身又都是一棵二叉排序树。 左 右子树本身又都是一棵二叉排序树。 二叉排序 树的查找思想 若二叉排树为空， 失败，否则， 若二叉排树为空，则查找 失败，否则，先拿根结点值与待查 值进行比较，若相等，则查找成功，若根结点值大于待查值， 值进行比较，若相等，则查找成功，若根结点值大于待查值， 则进入左子树重复此步骤，否则，进入右子树重复此步骤， 则进入左子树重复此步骤，否则，进入右子树重复此步骤， 若在查找过程中遇到二叉排序树的叶子结点时， 若在查找过程中遇到二叉排序树的叶子结点时，还没有找到 待找结点，则查找不成功。 待找结点，则查找不成功。
6
64
7
74
8
80
9 10
88 92 ]
low (c)
mid
hig
经过二次比较后的情形
0
05
1
13
2
19
3
21
4
37
5
56
6
64
7
74880 [源自9 1088 92 ]
low (d) 经过三次比较后的情形
mid hig
0
05
1
13
2
19
3
21
4
37
5
56
6
64
7
74
8
80
9 10
88 92 ]
hig (e) 经过四次比较后的情形(hig<low) 经过四次比较后的情形
low (a) 初始情形
hig
0
[ 05
1
13
2
19
3
21
4
37 ]
5
56
6
64
7
74
8 9 10
80 88 92
low (b)
hig
mid
经过一次比较后的情形
0
[05
1
13
2
19
3
21
4
37
5
] 56
6
64
7
74
8 9 10
80 88 92
low
mid
hig (c ) 经过二次比较后的情形 图 8-1 (array[mid].key=19)
例 如 ， 假 设 给 定 有 序 表 中 关 键 字 为 05,13,19,21,37,56,64,74,80,88,92 将 查 找 K=21 和 K=85的情况描述为图8-1及图8-2形式。
0 0 11 22 33 4 4 5 5 6 6 7 7 88 9 9 1010 [ 05 13 19 21 37 56 64 74 80 88 92 ]
low
图8-2 查找 查找K=85 的示意图 (查找不成功 查找不成功) 查找不成功
二分查找需事先对数据元素进行排序， 二分查找需事先对数据元素进行排序，并且 只适用于顺序存储结构的线性表， 只适用于顺序存储结构的线性表，无法灵活的适 应动态变化的要求。因为若插入新元素， 应动态变化的要求。因为若插入新元素，则需将 序列从新排序，若删除元素， 序列从新排序，若删除元素，则需移动该元素后 的所有元素。但它具有比较次数少、 的所有元素。但它具有比较次数少、查找时间短 的特点。 的特点。 若二分查找成功， 若二分查找成功，则给定值最多与 「㏒2 」 个关键字进行比较 个关键字进行比较。 「㏒ n」+1个关键字进行比较。
3 7 3 44 55 66 7 21 37 56 64 74
8 10 8 99 10 80 88 92 ]
low (a) 初始情形
hig
0
05
1
13
2
19
3
21
4
37
5
56 [
6
64
7
74
8
80
9 10
88 92 ]
mid (b)
low
hig
经过一次比较后的情形
0
05
1
13
2
19
3
21
4
37
5
56 [
第5章 检索方法
检索的定义:在特定的数据元素集合中寻找关键字与给定值相 检索的定义 在特定的数据元素集合中寻找关键字与给定值相 查找， 检索。 等的元素并输出寻找结果的过程称为查找 也叫检索 等的元素并输出寻找结果的过程称为查找，也叫检索。 关键字:指的是数据元素中用以标识该数据元素的某个数据项 关键字 指的是数据元素中用以标识该数据元素的某个数据项 的值，如学生成绩表中，学生可以同名，同分等， 的值，如学生成绩表中，学生可以同名，同分等，只有学号是各 不相同的，一个学号就对应一个学生，所以学号是关键字。 不相同的，一个学号就对应一个学生，所以学号是关键字。如果 某数据元素只有一个数据项，那么该数据元素的值就是关键字。 某数据元素只有一个数据项，那么该数据元素的值就是关键字。 检索方法包括：顺序查找；二分查找（又称折半查找）；索 检索方法包括：顺序查找；二分查找（又称折半查找）；索 ）； 引查找（又称分块查找）； ）；Hash查找（哈希表，散列表）。 查找（ 引查找（又称分块查找）； 查找 哈希表，散列表）。