当前位置：文档之家 › 静态查找表动态查找表二叉搜索树AVL树哈希表(Hash)

静态查找表动态查找表二叉搜索树AVL树哈希表(Hash)

  • 格式：ppt
  • 大小：652.50 KB
  • 文档页数：53

下载文档原格式

  / 53

合集下载

c语言数据结构查找算法大全

c语言数据结构查找算法大全

printf("This number does not exist in this array.\n");
else
printf("a[%d]=%d\n",p,x);
}
9.2.2 折半查找(二分查找)
使用折半查找必须具备两个前提条件:
（1）要求查找表中的记录按关键字有序(设,从小到大有序) （2）只能适用于顺序存储结构
}
※折半查找算法性能分析:
在折半查找的过程中，每经过一次比较，查找范围都要缩小一半，所 以折半查找的最大查找长度为
MSL=[log2 n]+1
当n足够大时，可近似的表示为log2(n)。可见在查找速度上，折半查找 比顺序查找速度要快的多，这是它的主要优点。
结论：折半查找要求查找表按关键字有序，而排序是一 种很费时的运算；另外，折半查找要求表是顺序存储的，为 保持表的有序性，在进行插入和删除操作时，都必须移动大 量记录。因此，折半查找的高查找效率是以牺牲排序为代价 的，它特别适合于一经建立就很少移动、而又经常需要查找 的线性表。
查找技术分为： 1 静态查找表技术 顺序查找、折半查找、索引顺序查找 2 动态查找表技术 二叉查找树 3哈希表技术 哈希表技术
※查找算法的衡量指标
在查找一个记录时所做的主要操作是关键字的比较， 所以通常把查找过程中对关键字的平均比较次数作为衡量 一个查找算法效率优劣的标准，并称平均比较次数为平均 查找长度（Average Search Length）。平均查找长度的 定义为：
high2=N-1;
/*N为查找表的长度，high2为块在表中的末地址*/
else
high2=ID[low1+1].addr-1;

数据结构第九章--查找-习题及答案

数据结构第九章--查找-习题及答案

第九章查找一、选择题1•若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL 为()。

A ．(n-1)/2B.n/2C.(n+1)/2D.n 2. 下面关于二分查找的叙述正确的是()A. 表必须有序，表可以顺序方式存储，也可以链表方式存储C.表必须有序，而且只能从小到大排列B. 表必须有序且表中数据必须是整型，实型或字符型D.表必须有序，且表只 能以顺序方式存储3. 用二分(对半)查找表的元素的速度比用顺序法() A. 必然快B.必然慢C.相等D.不能确定4. 具有12个关键字的有序表，折半查找的平均查找长度()A.3.1B.4C.2.5D.55．当采用分块查找时，数据的组织方式为()A. 数据分成若干块，每块内数据有序B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D. 数据分成若干块，每块(除最后一块外)中数据个数需相同6. 二叉查找树的查找效率与二叉树的((1))有关,在((2))时其查找效率最低(1) ：A.高度B.结点的多少C.树型D.结点的位置(2) :A.结点太多B.完全二叉树C.呈单枝树D.结点太复杂。

7. 对大小均为n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找失败,它们的平均查找长度是((1)),对于查找成功,他们的平均查找长度是((2))供选择的答案:A.相同的B.不同的9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是()A ．(100，80，90，60，120，110，130)B.(100，120，110，130，80，60，90) C. (100，60，80，90，120，110，130)D.(100，80，60，90，120，130，110)10. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A 的左孩子的平衡因子为0右孩子的平衡因子为1，则应作()型调整以使其平衡。

c语言中常用的查找

c语言中常用的查找

c语言中常用的查找C语言中常用的查找引言：在编程中，查找是一项非常常见且重要的操作。

无论是在数组、链表、树还是图等数据结构中，都需要进行查找操作来寻找特定的数据或者确定某个元素的存在与否。

C语言提供了多种查找算法和数据结构，本文将介绍C语言中常用的查找方法。

一、线性查找线性查找是最简单的查找方法之一，也称为顺序查找。

其基本思想是从数据集合的起始位置开始逐个比较待查找元素与集合中的元素，直到找到目标元素或者遍历完整个集合。

在C语言中，可以使用for循环或者while循环实现线性查找。

线性查找的时间复杂度为O(n)，其中n为数据集合中元素的个数。

二、二分查找二分查找又称为折半查找，是一种高效的查找算法，但要求数据集合必须是有序的。

其基本思想是将数据集合分为两部分，然后通过与目标元素的比较来确定目标元素在哪个部分中，从而缩小查找范围。

重复这个过程直到找到目标元素或者确定目标元素不存在于数据集合中。

二分查找的时间复杂度为O(logn)，其中n为数据集合中元素的个数。

三、哈希表查找哈希表是一种通过哈希函数将关键字映射到存储位置的数据结构，它能够以常数时间复杂度O(1)进行查找操作。

在C语言中，可以使用数组和链表的结合来实现哈希表。

哈希表的关键之处在于哈希函数的设计，良好的哈希函数能够将关键字均匀地映射到不同的存储位置，从而提高查找效率。

四、二叉搜索树查找二叉搜索树是一种常用的数据结构，它满足以下性质：对于任意节点，其左子树中的所有节点的值都小于该节点的值，而右子树中的所有节点的值都大于该节点的值。

在C语言中，可以使用指针和递归的方式来实现二叉搜索树。

通过比较目标值与当前节点的值，可以确定目标值位于左子树还是右子树中，从而缩小查找范围。

五、图的遍历在图的数据结构中，查找操作通常是指遍历操作。

图的遍历有两种方式：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索通过递归的方式依次访问图中的每个节点，直到找到目标节点或者遍历完整个图。

数据结构-动态查找表

数据结构-动态查找表

数据结构-动态查找表⼀、动态查找的概念：动态查找表：表结构在查找过程中动态⽣成。

要求：对于给定值key, 若表中存在其关键字等于key的记录，则查找成功返回（或者删除之）；否则插⼊关键字等于key 的记录。

⼆、动态查找表1. 1. ⼆叉排序树的定义⼆叉排序树的定义（Binary Sort Tree或Binary Search Tree）：⼆叉排序树或者是⼀棵空树，或者是满⾜下列性质的⼆叉树：（1）若左⼦树不为空，则左⼦树上的所有结点的值（关键字）都⼩于根节点的值；（2）若右⼦树不为空，则右⼦树上的所有结点的值（关键字）都⼤于根节点的值；（3）左、右⼦树都分别为⼆叉排序树。

如下图15-1所⽰，该图中的树就是⼀棵⼆叉排序树。

任何⼀个⾮叶⼦结点的左⼦树上的结点值都⼩于根结点，右⼦树上的结点值都⼤于根结点的值。

图1中，⼆叉树的结点值中序遍历的结果为：3,12,24,37,45,53,61,78,90,100。

结论：若按中序遍历⼀棵⼆叉排序树，所得到的结点序列是⼀个递增序列。

1. 1. ⼆叉排序树（BST树）的查找思想BST树的查找思想:（1）⾸先将给定的K值与⼆叉排序树的根节点的关键字进⾏⽐较：若相等，则查找成功；（2）若给定的K值⼩于BST树的根节点的关键字：继续在该节点的左⼦树上进⾏查找；（3）若给定的K值⼤于BST树的根节点的关键字：继续在该节点的右⼦树上进⾏查找。

1. 2. ⼆叉排序树总结（1）查找过程与顺序结构有序表中的折半查找相似，查找效率⾼；（2）中序遍历此⼆叉树，将会得到⼀个关键字的有序序列（即实现了排序运算）；（3）如果查找不成功，能够⽅便地将被查元素插⼊到⼆叉树的叶⼦结点上，⽽且插⼊或删除时只需修改指针⽽不需移动元素。

三、红⿊树1. 1. 红⿊树的定义红⿊树（Red Black Tree）是⼀种⾃平衡⼆叉查找树，是在计算机科学中⽤到的⼀种数据结构，典型的⽤途是实现关联数组。

它是在1972年由Rudolf Bayer发明的，当时被称为平衡⼆叉B树（symmetric binary B-trees）。

第章查找A

第章查找A
• 折半查找在查找成功时关键字比较次数 不超过树的深度,即: log2n + 1
假设 n=2h-1 并且查找概率相等
则
ASLbs

1 n
n i1
Ci

1 n

h j1
j

2
j1



n
n
1
log
2
(n

1)

1
在n>50时，可得近似结果
ASLbs log2(n 1) 1
若此关键字能识别若干记录，则称
之谓“次关键字”。
查找（搜索 、 Search)
所谓查找，就是在数据集合中寻找满足某种条 件的数据对象。
查找的结果通常有两种可能： 查找成功，即找到满足条件的数据对象。这 时，作为结果，可报告该对象在结构中的位置， 还可进一步给出该对象中的具体信息。 查找不成功，或搜索失败。作为结果，也应 报告一些信息，如失败标志、失败位置等。
• 分块有序原则：第二个子表的所有记录的关键字均 大于第一个字表中的最大关键字，……，依此类推。
索引顺序表的查找过程：
1）由索引确定记录所在块（子表）； 2）在顺序表的某个块内进行顺序查找。
可见， 索引顺序查找的过程也是一个
“缩小区间”的查找过程。
注意：索引可以根据查找表的特点来构造。
因为索引表中的 索引项是按关键字有 序排列的，因此可用顺序查找，也可用 折半查找；而块（子表）中的记录是任 意排列的，只能用顺序查找的方法。
for (i=ST.length; ST.elem[i].key!=key; --i);
// 从后往前找
return i ;

电子科技大学820计算机基础考试大纲

电子科技大学820计算机基础考试大纲

本科目包括《数据结构》与《计算机操作系统》两门课程，总分1 50分,两门课程各占75分《数据结构》。

了解:磁盘容错技术与数据一致性控制。

第七章操作系统接口。

理解与掌握:联机命令接口、系统调用、图形用户接口元素、图形用户接口元素得基本操作。

了解：对UNIX得SHELL与UNIX得系统调用作一般了解三、考试题型及分值选择题:20弔填空题:30%简答题：4 0%计算题：1 0%电子科技大学2011年攻读硕士学位研究生入学试题考试科目：820计算机专业基础注：所有答案必须写在答題纸上.做在试卷或草稿纸上无效数据结构75分一、选择题(每小题1分，共8分)1.若结点的存储地址与其关健字值之间存在某种对应关系，则称这种存储结构为( )A.顺序存错结构B.链式存储结枸C.索引存储结构D.散列存储结构2.能在0(1)时间内访何线性表的第i个元素的结构是()A.顺序茨B.单链茨C.单向循环链表D.双向链表3.—个nxn的对称矩阵.如果以行主序存储，每个元素占一个单元，则其需要的最犬存储空间为()Xn^n B n x rv2 C (n+l>n/2 D (n 十l"(n+l)/24.已知一稀疏矩阵的三元组表为『(L 2, 3), (b 6, 1), (3, 1. 5). (3. 2, ・】)，(4, 5, 4), (5,1, -3),则其转宜矩阵的三元组农中第3个三元组为( )A・(2, 1. 3) B・(3, 1, 5) C・(3, 2, -1) D.(2, 3, -1)5.在有n个结点的二叉链表中，值为空的链域的个数为( )A. n-1 B・n十 1 C. 2n-l D. 2n+l6.对于一个具有n个顶点的无向图，若采用邻接表表示，则存放表头结点的数组的大小为( )A.nB.n+1C.n-1D.n+1 边数7.下图所示的二叉树是( )A.二叉判定树B.二叉排序树C.二叉平衡树D.堆&用某种排序方法对关健字序列(25, 84, 21, 47, 15. 27, 68, 35, 20)进行排学时.序列的变化情况如下：20, 15, 21, 25, 47, 27. 68, 35. 8415, 20, 21, 25, 35, 27, 47, 68, 8415. 20. 21, 25, 27, 35. 47, 68, 84则所采用的排序方法是()A.选择排序B.希尔排序C.归并排序D・快連排序二、填空题(每小题1分，共8分)1.若一个算法中的语句頻度之和为T(n)-3720n4-4nlogn,则算法的时间尖杂度为 _______ •2.在长度为n的顺序表的笫i(l<i<n+l)个位置上插入一个元索，元素的移动次数为 _______ ■3.一个队列的入队序列是a、b、s d,则队列的输出序列为_____________ •4.广义表A=Ka,(b)O(c,d,e))的长度为 _________ ,5.在有n个结点的哈夫曼树中，其叶子结点数是________________ .6.已知某二叉树的先序序列为AI3DECF,中序序列为DBEAFC.則其后序序列为 ______________ •7.在含n个顶点和e条边的无向图的邻接矩阵中.零元素的个数为—o&在以｛4,5,6,7,8｝作为叶子结点权值构造的二叉树中，其帝权路径长皮嚴小三、简答题(每小题6分，共36分)1.已知一棵完全二叉树共有893个结点，试求:(1)树的高度；(2)叶子结点数目•2.用Dijkstra算法求岀下图中从顶点vl到其余各顶点的最短路径，按求解过程依次写出各条最短路径及其路径长度.3.己知关键字序列在a[l・・8]中的初始状态为I 2 3 4 5 ,6 7 8a | 48 | 70 | 33 丨65 | 24 | 56 | 12 [ 92写岀将其调整为大根堆的过程中毎一次筛选后a的状态。

数据结构大纲知识点

数据结构大纲知识点一、绪论。

1. 数据结构的基本概念。

- 数据、数据元素、数据项。

- 数据结构的定义（逻辑结构、存储结构、数据的运算）- 数据结构的三要素之间的关系。

2. 算法的基本概念。

- 算法的定义、特性（有穷性、确定性、可行性、输入、输出）- 算法的评价指标（时间复杂度、空间复杂度的计算方法）二、线性表。

1. 线性表的定义和基本操作。

- 线性表的逻辑结构特点（线性关系）- 线性表的基本操作（如初始化、插入、删除、查找等操作的定义）2. 顺序存储结构。

- 顺序表的定义（用数组实现线性表）- 顺序表的基本操作实现（插入、删除操作的时间复杂度分析）- 顺序表的优缺点。

3. 链式存储结构。

- 单链表的定义（结点结构，头指针、头结点的概念）- 单链表的基本操作实现（建立单链表、插入、删除、查找等操作的代码实现及时间复杂度分析）- 循环链表（与单链表的区别，操作特点）- 双向链表（结点结构，基本操作的实现及特点）三、栈和队列。

1. 栈。

- 栈的定义（后进先出的线性表）- 栈的基本操作（入栈、出栈、取栈顶元素等操作的定义）- 顺序栈的实现（存储结构，基本操作的代码实现）- 链栈的实现（与单链表的联系，基本操作的实现）- 栈的应用（表达式求值、函数调用栈等）2. 队列。

- 队列的定义（先进先出的线性表）- 队列的基本操作（入队、出队、取队头元素等操作的定义）- 顺序队列（存在的问题，如假溢出）- 循环队列的实现（存储结构，基本操作的代码实现，队空和队满的判断条件）- 链队列的实现（结点结构，基本操作的实现）- 队列的应用（如操作系统中的进程调度等）四、串。

1. 串的定义和基本操作。

- 串的概念（字符序列）- 串的基本操作（如连接、求子串、比较等操作的定义）2. 串的存储结构。

- 顺序存储结构（定长顺序存储和堆分配存储）- 链式存储结构（块链存储结构）3. 串的模式匹配算法。

- 简单的模式匹配算法（Brute - Force算法）的实现及时间复杂度分析。

数据结构_查找原理及典型的查找算法

无法实现！因全部元素的定位只能从头指针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）定义 二叉排序树或者是一棵空树，或是具有下列性质的二叉树：
若左子树非空，则左子树上所有结点的值均小于它的 根结点的值。
若右子树非空，则右子树上所有结点的值均大于它的 根结点的值。
有序/无序表 有序表
顺序/链式存 储
顺序存储
分块查找 介于二者之间 表中元素逐段有序 顺序/链式存储

大学数据结构课件--第9章 查找

——这种既查找又插入的过程称为动态查找。
二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态 查找表的一种适宜表示。
注：若数据元素的输入顺序不同，则得到的二叉排序树形态 也不同！
17
二、二叉树的插入和删除操作
1、二叉排序树的插入和查找操作
例：输入待查找的关键字序列=（45，24，53，12，90）
折半查找举例：
已知如下11个元素的有序表：
（05 13 19 21 37 56 64 75 80 88 92）, 请查找关键字为21和85的数据元素。
Low指向待查元 素所在区间的下 界
mid指向待查元素所在 high指向待查元素所
区间的中间位置
在区间的上界
8
9.1.2 折半查找（又称二分查找或对分查找）
balance。这样，可以得到AVL树的其它性质：
❖ 任一结点的平衡因子只能取：-1、0 或 1；如果树中任 意一个结点的平衡因子的绝对值大于1，则这棵二叉树 就失去平衡，不再是AVL树；
24
三、平衡二叉树
例：判断下列二叉树是否AVL树？
-1
1
-1
0
0
1
0
(a) 平衡树
2
-1
0
0
1
0
(b) 不是平衡树
（1）p为叶子结点，只需修改p双亲f的指针f->lchild=NULL或 f->rchild=NULL
（2）P只有左子树或右子树 ❖ P只有左子树，用P的左孩子代替P ❖ P只有右子树，用P的右孩子代替P
（3）P左、右子树均非空 （P左子树的根C的右子树分支找到S，S的右子树为空） ❖ P的左子树成为双亲f的左子树，P的右子树成为S的右子树 ❖ S的左子树成为S的双亲Q的右子树，用S取代p； 若C无右子树，用C取代p

数据结构7

搜索不成功: 树中原来没有关键码等于给 定值的结点，把新元素加到搜索操作停止 的地方。
递归的二叉搜索树插入算法
template <class Type> void BST<Type> ::
Insert ( Type x, BstNode<Type> * & ptr) {
if ( ptr == NULL ) {
BstNode<Type> *& ptr );
//删除
void PrintTree ( BstNode<Type> * ptr ) const;
BstNode<Type> *Copy
( const BstNode<Type> * ptr ); //复制
BstNode<Type> *Find ( Type x,
void setData ( Type d ) { data = d; }
Type GetData ( ) { return data; }
~BstNode ( ) { }
//析构函数
};
template <class Type> class BST
: public BinaryTree<Type> {
Chapter 7 搜索结构
静态搜索结构 二叉搜索树 AVL树
静静态态搜索搜结索构表
搜索(Search)的概念
。搜索:就是在数据集合中寻找满足某种条件的数 据对象
搜索的结果通常有两种可能： 搜索成功
搜索不成功
通常称用于搜索的数据集合为搜索结构，它是 由同一数据类型的对象(或记录)组成。
在每个对象中有若干属性，其中有一个属性， 其值可唯一地标识这个对象,称为关键码。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

AVL树的高度



设在新结点插入前AVL树的高度为 h，结点个 数为 n，则插入一个新结点的时间是O(h)。对 于AVL树来说，h 多大？ 设 Nh 是高度为 h 的AVL树的最小结点数。根 的一棵子树的高度为 h-1，另一棵子树的高度 为 h-2，这两棵子树也是高度平衡的。因此有 N-1 = 0 (空树) N0 = 1 (仅有根结点) Nh = Nh-1 + Nh-2 +1 , h > 0 可以证明，对于 h 0，有 Nh = Fh+3 -1 成立。
平衡化旋转




如果在一棵平衡的二叉搜索树中插入一个新结点，造 成了不平衡。此时必须调整树的结构，使之平衡化。 平衡化旋转有两类： 单旋转 (左旋和右旋) 双旋转 (左平衡和右平衡) 每插入一个新结点时，AVL树中相关结点的平衡状态 会发生改变。因此，在插入一个新结点后，需要从插 入位置沿通向根的路径回溯，检查各结点的平衡因子 (左、右子树的高度差)。 如果在某一结点发现高度不平衡，停止回溯。
查找算法
int Search_Seq(SSTable ST,KeyType key){ ST.elme[0].key=key; for(i=ST.length; !EQ(ST.elem[i].key,key); --i); return i; }
查找操作的性能分析：
查找算法中的基本操作是将记录的关键字和给定值进 行比较，通常以“其关键字和给定值进行过比较的记 录个数的平均值”作为衡量依据。
于给定值key，若表中存在其关键字等于key的 记录，则查找成功返回，否则插入关键字等于 key的记录

动态查找表允许的操作
创建表、销毁表、关键字查找、记录插入、记
录删除、记录遍历等
动态查找表
ADT DymanicSearchTable{ 数据对象Ｄ：Ｄ是具有相同特性的数据元素的集合。各个 数据元素均含有类型相同，可唯一标识数据元素的关键字 。 数据关系Ｒ：数据元素同属一个集合。 基本操作Ｐ： InitDSTable(&DT); DestroyDSTable(&DT); SearchDSTable(DT,key); InsertDSTable(&DT,e); DeleteDSTable(&DT,key); TraverseDSTable(DT,Visit()); }ADT DynamicSearchTable
平均查找长度 Average Search Length： 为确定记录在查找表中的位置，需用和给定值进行比 较的关键字个数的期望值称为查找算法在查找成功时 的平均查找长度。
其中：Pi为查找表中第i个记录的概率， 且 ； Ci为找到表中其关键字与给定值相等的第i个 记录时，和给定值已进行过比较的关键字个 数。
查找表本身在查找过程中动态生成，即若没有找到，则 插入该元素 对查询表除了创建、销毁、查找、遍历操作外，还能进 行插入和删除操作

对两个关键字的比较约定为如下的宏定义：
对数值型关键字 #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b)) 对字符串型关键字 #define EQ(a,b) (!strcmp((a),(b))) #define LT(a,b) (strcmp((a),(b))<0) #define LQ(a,b) (strcmp((a),(b))<=0)
}
假设查找的关键序列为{45,24,53,45,12,24,90}， 则生成二叉排序树的过程如下图所示：
45
24 b c 53 24
45
24 a
45
45
53 12 d 24
45
53 90 e
12
二叉排序树

二叉排序树的特点
中序遍历二叉排序树可得到一个关键字的有序序
列（即：可以通过输入一个无序序列，而通过构 造二叉排序树后进行遍历的方法实现排序） 二叉排序树的插入过程不需要移动其他记录 具有相同n个结点的二叉排序树会因为构造的时 候关键字插入的顺序不同而不同(下页说明) 二叉排序树的查找算法具有折半查找的特性，同 时又采用了链式存储结构，因此是动态查找表的 适宜表示
动态查找表

二叉排序树 (*) 平衡二叉树
9.2.1 二叉排序树及其查找过程
二叉排序树或者是一棵空树；或者是具有下列性质的二 叉树： １、若它的左子树不空，则左子树上所有结点的值均小 于它的根结点的值； ２、若它的右子树不空，则右子树上所有结点的值均大 于它的根结点的值； ３、它的左、右子树了分别为二叉排序树。
等概率条件下有：
假设查找成功与不成 功的概率相同：
9.1.2静态查找表（二）有序表的查 找
折半查找的查找过程 以有序表表示静态查找表时，Search函数可用折半查找来实现 。 先确定待查记录所在的范围（区间），然后逐步缩小范围直到 找到或找不到该记录为止。
9.1.2静态查找表（二） 有序表的查找
高度不平衡的二叉搜索树
高度平衡的二叉搜索树
结点的平衡因子balance (balance factor)




每个结点附加一个数字，给出该结点右子树的 高度减去左子树的高度所得的高度差。这个数 字即为结点的平衡因子balance 。 根据AVL树的定义，任一结点的平衡因子只能 取 -1，0和 1。 如果一个结点的平衡因子的绝对值大于1，则这 棵二叉搜索树就失去了平衡，不再是AVL树。 如果一棵二叉搜索树是高度平衡的，它就成为 AVL树。如果它有 n 个结点，其高度可保持在 O(log2n)，平均搜索长度也可保持在O(log2n)。

静态查找表 动态查找表
二叉搜索树 AVL树


哈希表 (Hash)
查找的基本概念
备注
概念

查找表

查找操作针对的数据集，由同一类型的数据元素组成
数据元素中某个数据项的值，可唯一标识该数据元素

关键字(key)


关键字和数据元素的类型说明，如
typedef float KeyType; //实型 typedef int KeyType; //整型 typedef char *KeyType; //字符串型 typedef struct { KeyType key; //关键字域 … //其它域 }ElemType;
如：查找的关键序列分别为{27,32,16,14}、 {16,14,27,32}和{14,16,27, 32}, 生成二叉排序树 分别如下：
14
27
16 14 32 14
16
27 32
16 27 32
比较极端的例子还有
二叉排序树的查找分析
最差情况 (n+1)/2 最好情况 log2n 平均性能
9.1 静态表查找

顺序表的查找 有序表的查找 索引顺序表的查找
静态查找表的类型定义：
ADT StaticSearchTable{ 数据对象D：D是具有相同特性的数据元素的集合。各个数据 元素均含有类型相同，可唯一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P：
Create(&ST,n);操作结果：构造一个含n个数据元素的静 态查找表ST。 Destroy(&ST);初始条件：静态查找表ST存在。操作结果 ：销毁表ST。 Search(ST,key);初始条件：静态查找表ST存在，key为和 关键字类型相同的给定值。 操作结果：若ST中在在其关键字等于key的数据元素，则 函数值为该元素的值或在表中的位置，否则为“空”。 Traverse(ST,Visit());初始条件：静态查找表ST存在，Visit 是对元素操作的应用函数。操作结果：按某种次序对ST 的每个元素调用函数visit()一次且仅一次。一旦visit()失败 ，则操作失败。

在二叉排序树中删除一个节点
思考：如何找到某子树上最大值结 点，如何找到最小值结点？
在二叉排序树中删除一个节点 x
如何找到 w ？
平衡二叉树 AVL树
高度平衡的二叉搜索树
一棵AVL树或者是空树，或者是具有下列性质的二叉 搜索树：它的左子树和右子树都是AVL树，且左子树和 右子树的高度之差的绝对值不超过1。
折半查找的查找实现 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;
22 12 13 8 9 20 33 42 44 38 24 44 38 24 48 60 58 74 49 86 53
查找表
(只描述了关键字部分)
(块间有序，块内无序)
索引顺序表查找

分块查找算法
首先，根据关键字值在索引表中查找(顺序或折
半查找)以确定块的范围 然后，在块中根据关键字值做顺序查找



从发生不平衡的结点起，沿刚才回溯的路径取 直接下两层的结点。 如果这三个结点处于一条直线上，则采用单旋 转进行平衡化。单旋转可按其方向分为左单旋 转和右单旋转，其中一个是另一个的镜像，其 方向与不平衡的形状相关。 如果这三个结点处于一条折线上，则采用双旋 转进行平衡化。双旋转分为先左后右和先右后 左两类。
概念