[数据结构与算法]算法——查找

一. 基本概念和评价

1. 相关概念

2. 查找表

2.1 常见操作

2.2 分类

• 静态查找表
• 动态查找表

3. 查找算法的评价指标

• ASL的数量级反应了查找算法时间复杂度

查找成功的平均查找长度

查找失败的平均查找长度

二. 线性结构查找

1. 顺序查找算法

1.1 定义

1.2 算法思想

1.3 特点

1.4 分类

1）无哨兵的无序线性表的顺序查找

2）有哨兵的无序线性表的顺序查找

优点：无需判断是否越界，效率更高

3）对有序表进行顺序查找

优点：查找失败时ASL更少

• 查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度

4）各关键字被查概率不同

优点：查找成功时ASL更少

1.5 查找判定树

对有序表用查找判定树分析ASL

• 树中的圆形结点表示有序线性表中存在的元素；树中的矩形结点称为失败结点(若有n个结点，则相应地有n+1个查找失败结点)，它描述的是那些不在表中的数据值的集合。若查找到失败结点，则说明查找不成功

1.6 查找效率分析（ASL）

2. 折半查找算法

2.1 算法思想

特点：

• 因为折半查找需要方便地定位查找区域，所以它要求线性表必须具有随机存取的特性。因此,该查找法仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列

2.2 算法实现

2.3 查找判定树

1）定义

用来描述折半查找过程的二叉树，称为判定树

• 树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找不成功的情况。
• 从判定树可以看出，查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数；
• 每个结点值均大于其左子结点值，且均小于于其右子结点值

2）构造

3）特性

性质1：

• 用折半查找法查找到给定值的比较次数最多不会超过树的高度

性质2：

2.4 查找效率分析（ASL）

三. 树形结构查找

1. 二叉排序树（二叉查找树/BST）

1.1 相关概念

1.2 基本操作

1）查找操作

2）插入操作

3）构造二叉排序树、

• 二叉排序树作为一种动态树表，其特点是树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字值等于给定值的结点时再进行插入的

4）删除操作

• 在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下
• 将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失

1.3 查找效率分析（ASL）

• 二叉排序树的查找效率，主要取决于树的高度

1）查找成功

2）查找失败

3）二叉排序树与二分查找的比较

2. 二叉平衡树（AVL）

2.1 相关概念

1）为什么需要平衡二叉树

为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过1

2）定义

2.2 基本操作

1）插入

• 每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树

2）调整最小不平衡子树

1. LL：调整A的左孩子节点右上旋
   

2. RR：调整A的右孩子节点左上旋
   
   

3. LR：调整A的左孩子的右孩子，先左上旋再右上旋
   
   

• LR和RL旋转时，新结点究竟是插入C的左子树还是插入C的右子树不影响旋转过程

4. RL：调整A的右孩子的左孩子，先右上旋后左上旋
   
   
   

2.3 查找效率分析（ASL）

3. B树（多路平衡查找树）

3.1 基本概念

1）来源

如何进行查找？

2）如何保证查找效率

策略1：

策略2：

4）B树定义

5）m阶B树的核心特性

3.2 B树的高度

3.3 B树的基本操作

1）B树的查找

• 在B树上进行查找与二叉查找树很相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定

2）B树的插入

easy，见笔记

3）B树的删除

easy，见笔记

4. B+树

4.1 基本概念

4.2 基本操作

1）B+树的查找

见笔记

4.3 B树和B+树的区别

见笔记

5. 红黑树

见笔记

四. 索引结构查找

1. 分块查找（索引顺序查找）算法

1.1 算法思想

特点

• 它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找

算法基本思想：

1）用折半查找查索引

见笔记

2）用顺序查找查索引

见笔记

1.2 查找效率分析（ASL）

五. 散列结构（哈希结构）查找

散列查找：基于散列表的数据结构，通过 哈希函数建立关键字与存储地址的联系

1. 基本概念

在前面介绍的线性表和树表的查找中，记录在表中的位置与记录的关键字之间不存在确定关系，因此，在这些表中查找记录时需进行一系列的关键字比较。这类查找方法建立在“比较”的基础上，查找的效率取决于比较的次数

散列函数：

• 一个把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr (这里的地址可以是数组下标、索引或内存地址等)。

散列表：

• 根据关键字而直接进行访问的数据结构。也就是说，散列表建立了关键字和存储地址之间的一种直接映射关系

2. 哈希函数 (散列函数) 的构造方法

2.1 概述

对于一个给定的关键字key,根据散列函数可以计算出其散列地址，执行步骤如下：

• 散列函数是典型的用空间换时间的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低

2.2 常见的散列函数

设计目标：让不同关键字的冲突尽可能少

1）除留余数法

2）直接定址法

3）数字分析法

4）平方取中法

3. 处理冲突的方法

• 任何设计出来的散列函数都不可能绝对地避免冲突。为此，必须考虑在发生冲突时应该如何处理，即为产生冲突的关键字寻找下一个“空”的Hash地址

3.1 拉链法

3.2 开放定址法

1）线性探测法

线性探测的缺点：

2）平方探测法

3）伪随机序列法

3.3 再散列法

4. 散列查找操作步骤

4.1 拉链法查找步骤

4.1 线性探测法查找操作

4.2 线性探测法删除操作

5. 散列查找的性能分析

5.1 概述

• 散列表的查找过程与构造散列表的过程基本一致
• 对同一组关键字，设定相同的散列函数，则不同的处理冲突的方法得到的散列表不同，它们的平均查找长度也不同
• 虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需要以平均查找长度作为衡量散列表的查找效率的度量

散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子

• 散列表的平均查找长度依赖于散列表的装填因子a,而不直接依赖于”或刃

5.2 拉链法性能分析

5.3 线性探测法性能分析

参考文献：王道数据结构