常见查找算法分析

博主： wmicheng
发布时间：2025 年 02 月 11 日
29 次浏览
暂无评论
11721字数
分类：数据结构

## 查找

> #### 基本概念

- `查找`： 在数据集合中寻找满足某种条件的数据元素的过程称为查找
- `查找表`（**查找结构**）：用于查找的数据集合称为查找表，它由同一类型的数据元素（或**记录**）组成
- `关键字`： 数据元素中**唯一标识**该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。

![查找基本概念](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念.png)

![查找基本概念1](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念1.png)

> #### 对查找表的常见操作

查找符合条件的数据元素

- 静态查找表
- 仅关注查找速度即可

插入、删除某个数据元素

- 动态查找表
- 除了查找速度，也要关注插/删操作是否方便实现

![查找基本概念2](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念2.png)

> #### 查找算法的评价指标

`查找长度`：在查找运算中，需要对比关键字的次数称为查找长度

`平均查找长度`（ASL, Average Search Length ）：所有查找过程中进行关键字的比较次数的平均值

![查找基本概念3](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念3.png)

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

`评价一个查找算法的效率时，通常考虑查找成功、查找失败两种情况的ASL`

![查找基本概念4](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念4.png)

![查找基本概念5](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念5.png)

![查找基本概念6](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念6.png)

## 顺序查找

> #### 定义

**顺序查找**，又叫“**线性查找**”，通常用于线性表。

**算法思想**：从头到`jio`依次往后找(反过来也OK)

> #### 顺序查找的实现

![顺序查找](https://wmicheng.top/images/note/img_Search_Sort/顺序查找.png)

> #### 顺序查找的实现（哨兵）

![顺序查找2](https://wmicheng.top/images/note/img_Search_Sort/顺序查找2.png)

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

> #### 顺序查找效率分析

$$
\mathbf{A S L}=\sum_{i=1}^{n} P_{i} C_{i}
$$

$$
\mathbf{A S L}_{\text {成功 }}=\frac{1+2+3+\ldots+n}{n}=\frac{n+1}{2}
$$

$$
\mathbf{A S L}_{\text {失败 }}=\mathrm{n}+1
$$

> #### 顺序查找的优化（对有序表）

![顺序查找3](https://wmicheng.top/images/note/img_Search_Sort/顺序查找3.png)

> #### 用查找判定树分析`ASL`

- 一个成功结点的查找长度 = 自身所在层数
- 一个失败结点的查找长度 = 其父结点所在层数
- 默认情况下，各种失败情况或成功情况都等概率发生

![顺序查找4](https://wmicheng.top/images/note/img_Search_Sort/顺序查找4.png)

> #### 顺序查找的优化（被查概率不相等）

![顺序查找5](https://wmicheng.top/images/note/img_Search_Sort/顺序查找5.png)

![顺序查找6](https://wmicheng.top/images/note/img_Search_Sort/顺序查找6.png)

## 折半查找

> #### 算法思想

折半查找，又称“二分查找”，仅适用于`有序`的`顺序表`。

![折半查找](https://wmicheng.top/images/note/img_Search_Sort/折半查找.png)

> #### 代码实现

![折半查找2](https://wmicheng.top/images/note/img_Search_Sort/折半查找2.png)

> #### 查找效率分析

![折半查找3](https://wmicheng.top/images/note/img_Search_Sort/折半查找3.gif)

> #### 折半查找判定树的构造

![折半查找4](https://wmicheng.top/images/note/img_Search_Sort/折半查找4.png)

如果当前low和high之间有`偶数`个元素，则 mid 分隔后，**左半部分比右半部分少一个元素**

如果当前low和high之间有`奇数`个元素，则 mid 分隔后，**左右两部分元素个数相等**

折半查找的判定树中,**mid** = `[(low + high)/2]`则对于任何一个结点，必有：**右树结点数-左子树结点数=0或1**

折半查找的判定树`一定是平衡二叉树`

折半查找的判定树中，`只有最下面一层是不满的`因此，元素个数为n时树高$h=\left\lceil\log _{2}(n+1)\right\rceil$（该树高不包含失败节点）

判定树结点关键字：`左<中<右`，满足二叉排序树的定义

`失败结点：n+1个`（等于成功结点的空链域数量）

`折半查找的时间复杂度`:$O(log_2n)$

![折半查找3](https://wmicheng.top/images/note/img_Search_Sort/折半查找3.png)

## 分块查找

> #### 算法思想

![分块查找](https://wmicheng.top/images/note/img_Search_Sort/分块查找.png)

`特点`：块内无序、块间有序

**分块查找**，又称`索引`顺序查找**，算法过程如下：

- 在索引表中确定待查记录所属的分块（可顺序、可折半）
- 在块内顺序查找

> #### 用折半查找查索引

**查找目标与索引表值相同**

![分块查找5](https://wmicheng.top/images/note/img_Search_Sort/分块查找5.png)

**查找目标与索引值不同**

![分块查找4](https://wmicheng.top/images/note/img_Search_Sort/分块查找4.png)

**查找失败**

![分块查找6](https://wmicheng.top/images/note/img_Search_Sort/分块查找6.png)

> #### 查找效率分析

![分块查找1](https://wmicheng.top/images/note/img_Search_Sort/分块查找1.png)

![分块查找2](https://wmicheng.top/images/note/img_Search_Sort/分块查找2.png)

![分块查找3](https://wmicheng.top/images/note/img_Search_Sort/分块查找3.png)

## 二叉排序树

> #### 定义

![二叉排序树](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树.png)

> #### 二叉排序树查找

![二叉排序树1](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树1.png)

| 非递归实现                                      | 递归实现                                        |
| ----------------------------------------------- | ----------------------------------------------- |
| ![二叉排序树2](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树2.png) | ![二叉排序树3](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树3.png) |

> #### 二叉排序树插入

![二叉排序树4](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树4.png)

> #### 二叉排序树构造

|                                                 |                                                 |
| ----------------------------------------------- | ----------------------------------------------- |
| ![二叉排序树5](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树5.png) | ![二叉排序树6](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树6.png) |

> #### 二叉排序树删除

先搜索找到目标结点：

1. 若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质
2. 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
3. 若结点z有左、右两棵子树，则令z的直接后继 （或直接前驱）替代z，然后从二叉排序树中删去这 个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

![二叉排序树7](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树7.png)

> #### 查找效率分析

![二叉排序树8](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树8.png)

![二叉排序树9](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树9.png)

| 查找成功的平均查找长度ASL                                    | 查找失败的平均查找长度ASL                                    |
| ------------------------------------------------------------ | ------------------------------------------------------------ |
| `最好情况：`$ASL = (1*1 + 2*2 + 3*4 + 4*1)/8 = 2.625 $`最坏情况：`$ASL=(1*1+2*2 +3*1 +4*1 +5*1 +6*1+ 7*1)/8 =3.75$ | `最好情况：`$ASL = (3*7 + 4*2)/9 = 3.22$ `最坏情况：`$ASL = (2*3 +3+4+5+6+7*2)/9 = 4.22$ |

![二叉排序树10](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树10.png)

## 平衡二叉树

> #### 定义

![平衡二叉树](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树.png)

> #### 平衡二叉树

|                                                 |                                                 |
| ----------------------------------------------- | ----------------------------------------------- |
| ![平衡二叉树1](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树1.png) | ![平衡二叉树2](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树2.png) |

> #### `调整平衡二叉树★★★`

![平衡二叉树3](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树3.png)

> #### 调整最小不平衡子树LL&RR

|                                                 |                                                 |
| ----------------------------------------------- | ----------------------------------------------- |
| ![平衡二叉树4](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树4.png) | ![平衡二叉树5](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树5.png) |

![平衡二叉树6](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树6.png)

> #### 调整最小不平衡子树LR&RL

|                                                 |                                                    |
| ----------------------------------------------- | -------------------------------------------------- |
| ![平衡二叉树7](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树7.png) | ![平衡二叉树10](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树10.png)1 |
| ![平衡二叉树8](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树8.png) | ![平衡二叉树11](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树11.png)  |
| ![平衡二叉树9](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树9.png) | ![平衡二叉树12](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树12.png)  |

![平衡二叉树13](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树13.png)

### 平衡二叉树插入&删除

> ##### 平衡二又树的`插入`操作：

- `插入`新结点后，要`保持二叉排序树的特性不变` （左<中<右）
- 若插入新结点导致`不平衡`，则需要`调整平衡`

> ##### 平衡二叉树的`删除`操作：

- `删除`新结点后，要`保持二叉排序树的特性不变` （左<中<右）
- 若`删除`新结点导致`不平衡`，则需要`调整平衡`

> ##### 平衡二叉树的`删除`操作具体步骤：

1. 删除结点（方法同“二叉排序树”）
   若删除的结点是叶子，直接删。
   若删除的结点只有一个子树，用子树顶替删除位置
   若删除的结点有两棵子树，用前驱（或后继）结点顶替，并转换为对前驱（或后继）结点的删除
2. `一路向北找到最小不平衡子树`，找不到就完结撒花
3. 找最小不平衡子树下，`“个头”最高的儿子、孙子`
4. 根据孙子的位置，调整平衡（LL/RR/LR/RL)
   孙子在LL：儿子右单旋
   孙子在RR：儿子左单旋
   孙子在LR：孙子先左旋，再右旋
   孙子在RL：孙子先右旋，再左旋
5. 如果不平衡向上传导，继续2.
   对最小不平衡子树的`旋转可能导致树变矮`，从而导致上层祖先不平衡 （不平衡向上传递）

> ##### 平衡二叉树删除操作`时间复杂度`$=O\left(\log _{2} n\right)$

## 红黑树

![红黑树2](https://wmicheng.top/images/note/img_Search_Sort/红黑树2.png)

> #### 定义

**平衡二叉树AVL**：插入/删除很容易破坏“平衡”特性，需要频繁调整树的形态。如：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大），再进行LL/RR/LR/RL调整

| 违反“不红红”                            | 违反“根叶黑”                            |
| --------------------------------------- | --------------------------------------- |
| ![红黑树3](https://wmicheng.top/images/note/img_Search_Sort/红黑树3.png) | ![红黑树4](https://wmicheng.top/images/note/img_Search_Sort/红黑树4.png) |

| 违反“黑路同”                            | 违反“左根右”                            |
| --------------------------------------- | --------------------------------------- |
| ![红黑树5](https://wmicheng.top/images/note/img_Search_Sort/红黑树5.png) | ![红黑树6](https://wmicheng.top/images/note/img_Search_Sort/红黑树6.png) |

`性质1`: 从根节点到叶结点的最长路径不大于最短路径的2倍

`性质2`: 有 ${\mathrm{n}}$ 个内部节点的红黑树高度 ${\mathrm{h} \leq 2 \log _{2}(n+1)}$

红黑树`查找`操作`时间复杂度` $=O\left(\log _{2} n\right)$——(查找效率与AVL树同等数量级)

> #### `红`黑树查找

与 BST、AVL 相同，从根出发，左小右大，若查找到一个空叶节点，则查找失败

### `红`黑树的插入

从一棵空的红黑树开始，插入：20,10,5,30,40,57,3,2,4,35,25,18,22,23,24,19,18

![红黑树7](https://wmicheng.top/images/note/img_Search_Sort/红黑树7.png)

![红黑树8](https://wmicheng.top/images/note/img_Search_Sort/红黑树8.png)

**性质1证明：任何一条查找失败路径上黑结点数量都相同，而路径上不能连续出现两个红结点，即红结点只能穿插在各个黑结点中间**

**性质2证明: 若红黑树总高度 =h 则根节点黑高 $\geq h / 2$n , 因此内部结点数$n\geq 2^{h / 2}-1$, 由此推出 $ h\leq 2 \log _{2}(n+1)$**

![红黑树9](https://wmicheng.top/images/note/img_Search_Sort/红黑树9.png)

结点的**黑高** `bh`一一从某结点出发（不含该结点）到达任一叶结点的路径上黑结点总数

`思考`：根节点黑高为h的红黑树，内部结点数（关键字）`至多`有多少个？

`回答`：内部结点数`最多`的情况一一h层黑结点，每一层黑结点下面都铺满一层红结点。共**2h**层的满树形态

`结论`：**若根节点黑高为h，内部结点数（关键字）最多有**$2^{2h}-1$**个**

### `红`黑树的删除

![红黑树10](https://wmicheng.top/images/note/img_Search_Sort/红黑树10.png)

## B树

> #### m叉查找树：

- 实际上就是二叉查找树的拓展，结点多少有多少个分叉就是多少叉查找树
- 每个结点关键字的查找可以用顺序查找也可以用折半查找

![B树](https://wmicheng.top/images/note/img_Search_Sort/B树.png)

**如何保证查找效率：**

- 若每个结点内关键字太少，导致树变高，要查更多层结点，效率低
  
  - 策略：m叉查找树中，规定`除了根结点外`，任何结点`至少有⌈m/2⌉个分叉`，即至少含有`⌈m/2⌉ − 1 个关键字`
  - 为什么不能保证根结点至少有⌈m/2⌉个分叉：如果整个树只有1个元素，根结点只能有两个分叉
- 不够“平衡”，树会很高，要查很多层结点
  
  - 策略：m叉查找树中，规定对于`任何一个结点，其所有子树的高度都要相同`。

> #### B树的定义

![B树1](https://wmicheng.top/images/note/img_Search_Sort/B树1.png)

`B树`，又称`多路平衡查找树`，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵`m阶B树`或为空树，或为满足如下特性的m叉树：

- 树中每个结点至多有m棵子树，即至多含有m-1个关键字。
- 若根结点不是终端结点，则至少有两棵子树。
- `除根结点外`的所有非叶结点`至少有⌈m/2⌉棵子树`，即至少含有 `⌈m/2⌉-1个关键字`。
- 所有非叶结点的结构如下：
  
  - ![B树2](https://wmicheng.top/images/note/img_Search_Sort/B树2.png)
  - 其中，Ki（i = 1, 2,…, n）为结点的关键字，且满足`K1 < K2 <…< Kn`；Pi（i = 0, 1,…, n）为指向子树根结点的指针，且指针`Pi-1所指子树中所有结点的关键字均小于Ki，Pi所指子树中所有结点的关键字均大于Ki`，n（⌈m/2⌉- 1≤n≤m - 1）为结点中关键字的个数。
- 所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。

> #### `m阶B树`核心特性

1) 根节点的子树数 ${\in[2, \mathrm{m}]}$, 关键字数 ${\in[1, m-1]}$ 。 其他结点的子树数 ${\in[[m / 2], \mathrm{m}]}$; 关键字数 ${\in[[m / 2]-1, \mathrm{m}-1]}$ （尽可能“满”）
2) 对任一结点, 其所有子树高度都相同 （尽可能“平衡”）
3) 关键字的值: 子树 ${0<}$ 关键字 ${1<子}$ 树 ${1<}$ 关键字 ${2<子}$ 树 ${2<\ldots}$ (类比二叉查找树 左<中<右)

> #### B树的高度

![B树3](https://wmicheng.top/images/note/img_Search_Sort/B树3.png)

$$
\text { 含 } \mathrm{n} \text { 个关键字的 } \mathrm{m} 叉\mathrm{B} \text { 树, } \log _{m}(n+1) \leq h \leq \log _{[m / 2]} \frac{n+1}{2}+1
$$

### `B树的插入删除`

> #### B树的插入：

- 新元素一定是插入到最底层“终端结点”，用“查找”来确定插入位置
- 在插入key后，若导致原结点关键字数超过上限，则从中间位置（⌈m/2⌉）将其中的关键字分为两部分
- 左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（⌈m/2⌉）的结点插入原结点的父结点
- 若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致B树高度增1。

> #### B树的删除

- 若被删除关键字在终端结点，则直接删除该关键字（要注意结点关键字个数是否低于下限 ⌈m/2⌉ − 1）
- 若被删除关键字在非终端结点，则用直接前驱或直接后继来替代被删除的关键字
  
  - 直接前驱：当前关键字左侧指针所指子树中“最右下”的元素
  - 直接后继：当前关键字右侧指针所指子树中“最左下”的元素
- 若被删除关键字所在结点删除前的关键字个数低于下限，且与此结点右（或左）兄弟结点的关键字个数还很宽裕，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法）
  
  - 当右兄弟很宽裕时，用当前结点的后继（比当前结点大一位）、后继的后继（比当前结点大两位）来填补空缺
  - 当左兄弟很宽裕时，用当前结点的前驱（比当前结点小一位）、前驱的前驱（比当前结点小两位）来填补空缺
- 若被删除关键字所在结点删除前的关键字个数低于下限，且此时与该结点相邻的左、右兄弟结点的关键字个数均=⌈m/2⌉ − 1，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并

![B树5](https://wmicheng.top/images/note/img_Search_Sort/B树5.png)

## B+树

![B+树](https://wmicheng.top/images/note/img_Search_Sort/B+树.png)

> #### 定义和性质

一棵`m阶的B+树`需满足下列条件：

1. 每个分支结点最多有m棵子树（孩子结点）。
2. 非叶根结点至少有两棵子树，其他每个分支结点至少有⌈m/2⌉棵子树。
   
   - （可以理解为：要追求“绝对平衡”，即所有子树高度要相同）
3. `结点的子树个数与关键字个数相等`。
4. 所有`叶结点包含全部关键字`及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且`相邻叶结点按大小顺序相互链接起来`（**支持顺序查找**）。
5. 所有`分支结点`中仅包含它的各个子结点中`关键字的最大值`及指向其子结点的指针。

**B+树的查找：**

B+树中，无论查找成功与否，最终一定都要走到最下面一层结点，因为只有叶子结点才有关键字对应的记录

**B+树和B树区别：**

| B树                                 | B+树                                |
| ----------------------------------- | ----------------------------------- |
| ![B+树2](https://wmicheng.top/images/note/img_Search_Sort/B+树2.png) | ![B+树3](https://wmicheng.top/images/note/img_Search_Sort/B+树3.png) |

- 典型应用：关系型数据库的“索引”（如MySQL）
- 在B+树中，`非叶结点不含有该关键字对应记录的存储地址`。
- 可以使一个磁盘块可以包含更多个关键字，使得B+树的阶更大，`树高更矮`，`读磁盘次数更少`，查找更快

![B+树1](https://wmicheng.top/images/note/img_Search_Sort/B+树1.png)

## 散列（哈希）查找

![散列表](https://wmicheng.top/images/note/img_Search_Sort/散列表.png)

> #### 定义

- `散列表`（`Hash Table`），又称哈希表
- 是一种数据结构，特点是：**数据元素的关键字与其存储地址直接相关**
- 通过哈希函数建立关键字和存储地址的联系
- 若不同的关键字通过散列函数映射到同一个值，则称它们为“`同义词`”
- 通过散列函数确定的位置已经存放了其他元素，则称这种情况为“`冲突`”

> #### 处理冲突的方法——拉链法

![散列表1](https://wmicheng.top/images/note/img_Search_Sort/散列表1.png)

| 查找27                                  | 查找20                                  |
| --------------------------------------- | --------------------------------------- |
| ![散列表2](https://wmicheng.top/images/note/img_Search_Sort/散列表2.png) | ![散列表3](https://wmicheng.top/images/note/img_Search_Sort/散列表3.png) |

- 用`拉链法`（`又称链接法、链地址法`）处理“冲突”：把所有“同义词”存储在一个链表中
- 最理想情况：散列查找时间复杂度可到达$O(1)$
- “冲突”越多，查找效率越低
- 实际上就是顺序表和链表的结合结合两者优点，比如顺序表的随机存取，然后用链表的解决冲突问题，又规避了顺序表的一系列缺点
- 在插入新元素时，保持关键字有序，可微微提高查找效率

> #### 常见的散列函数

`散列函数的设计目的`：

- 让不同关键字的冲突尽可能的少
- 散列查找是典型的“用空间换时间”的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。

**除留余数法**：$H(key) = key % p$

- 散列表表长为m，取一个不大于m但最接近或等于m的质数p
- 质数又称素数。指除了1和此整数自身外,不能被其他自然数整除的数

![散列表4](https://wmicheng.top/images/note/img_Search_Sort/散列表4.png)

**直接定址法** ： H(key) = key 或 H(key) = a\*key + b

- 其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

![散列表5](https://wmicheng.top/images/note/img_Search_Sort/散列表5.png)

**数字分析法**：选取数码分布较为均匀的若干位作为散列地址

- 设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；
- 而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

![散列表6](https://wmicheng.top/images/note/img_Search_Sort/散列表6.png)

**平方取中法**：取关键字的平方值的中间几位作为散列地址。

- 具体取多少位要视实际情况而定。
- 这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
- $$
  \begin{array}{l} 1310^{2}=1,716,100 \\ 1110^{2}=1,232,100 \\ 1300^{2}=1,690,000 \\ 1210^{2}=1,464,100 \\ 1200^{2}=1,440,000 \end{array}
  $$

![散列表7](https://wmicheng.top/images/note/img_Search_Sort/散列表7.png)

![散列表8](https://wmicheng.top/images/note/img_Search_Sort/散列表8.png)

> #### 处理冲突的方法——开放定址法

![散列表9](https://wmicheng.top/images/note/img_Search_Sort/散列表9.png)

**线性探测法**

- di = 0, 1, 2, 3, …, m-1；即发生冲突时，每次往后探测相邻的下一个单元是否为空，为空则可以插入数值
- 查找也是类似，先通过公式得到Hi再依次往后查找，若遇到空的位置则说明查找失败，所以越早遇到空位置，就可以越早确定查找失败
- 删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径，可以做一个“删除标记”，进行逻辑删除
- 线性探测法由于冲突后再探测一定是放在某个连续的位置，很容易造成同义词、非同义词的“聚集（堆积）”现象，严重影响查找效率

**平方探测法**

- 当$di = 0^2, 1^2, -1^2, 2^2, -2^2, …, k^2, -k^2$时，称为平方探测法，又称`二次探测法`，其中$k≤m/2$
- 比起线性探测法更不易产生“聚集（堆积）”问题
- 注意：负数的模运算，(-3)%27 = 24，而不是3
- 模运算的规则：`a MOD m == (a+km) MOD m` , 其中，k为任意整数
- 散列表长度m必须是一个可以表示成4j + 3的素数，才能探测到所有位置

**伪随机序列法**

- $di$ 是一个伪随机序列，如 $di= 0, 5, 24, 11, …$

**处理冲突的方法——再散列法：**

- 除了原始的散列函数 H(key) 之外，多准备几个散列函数
- 当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止：
- $Hi = RHi(Key)$
- $i=1,2,3….,k$

![散列表10](https://wmicheng.top/images/note/img_Search_Sort/散列表10.png)

---

最后修改：2025 年 02 月 11 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

常见查找算法分析

wmicheng • 2025 年 02 月 11 日

## 查找

> #### 基本概念

![查找基本概念](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念.png)

![查找基本概念1](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念1.png)

> #### 对查找表的常见操作

查找符合条件的数据元素

- 静态查找表
- 仅关注查找速度即可

插入、删除某个数据元素

- 动态查找表
- 除了查找速度，也要关注插/删操作是否方便实现

![查找基本概念2](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念2.png)

> #### 查找算法的评价指标

`查找长度`：在查找运算中，需要对比关键字的次数称为查找长度

`平均查找长度`（ASL, Average Search Length ）：所有查找过程中进行关键字的比较次数的平均值

![查找基本概念3](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念3.png)

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

`评价一个查找算法的效率时，通常考虑查找成功、查找失败两种情况的ASL`

![查找基本概念4](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念4.png)

![查找基本概念5](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念5.png)

![查找基本概念6](https://wmicheng.top/images/note/img_Search_Sort/查找基本概念6.png)

## 顺序查找

> #### 定义

**顺序查找**，又叫“**线性查找**”，通常用于线性表。

**算法思想**：从头到`jio`依次往后找(反过来也OK)

> #### 顺序查找的实现

![顺序查找](https://wmicheng.top/images/note/img_Search_Sort/顺序查找.png)

> #### 顺序查找的实现（哨兵）

![顺序查找2](https://wmicheng.top/images/note/img_Search_Sort/顺序查找2.png)

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

> #### 顺序查找效率分析

$$
\mathbf{A S L}=\sum_{i=1}^{n} P_{i} C_{i}
$$

$$
\mathbf{A S L}_{\text {成功 }}=\frac{1+2+3+\ldots+n}{n}=\frac{n+1}{2}
$$

$$
\mathbf{A S L}_{\text {失败 }}=\mathrm{n}+1
$$

> #### 顺序查找的优化（对有序表）

![顺序查找3](https://wmicheng.top/images/note/img_Search_Sort/顺序查找3.png)

> #### 用查找判定树分析`ASL`

- 一个成功结点的查找长度 = 自身所在层数
- 一个失败结点的查找长度 = 其父结点所在层数
- 默认情况下，各种失败情况或成功情况都等概率发生

![顺序查找4](https://wmicheng.top/images/note/img_Search_Sort/顺序查找4.png)

> #### 顺序查找的优化（被查概率不相等）

![顺序查找5](https://wmicheng.top/images/note/img_Search_Sort/顺序查找5.png)

![顺序查找6](https://wmicheng.top/images/note/img_Search_Sort/顺序查找6.png)

## 折半查找

> #### 算法思想

折半查找，又称“二分查找”，仅适用于`有序`的`顺序表`。

![折半查找](https://wmicheng.top/images/note/img_Search_Sort/折半查找.png)

> #### 代码实现

![折半查找2](https://wmicheng.top/images/note/img_Search_Sort/折半查找2.png)

> #### 查找效率分析

![折半查找3](https://wmicheng.top/images/note/img_Search_Sort/折半查找3.gif)

> #### 折半查找判定树的构造

![折半查找4](https://wmicheng.top/images/note/img_Search_Sort/折半查找4.png)

如果当前low和high之间有`偶数`个元素，则 mid 分隔后，**左半部分比右半部分少一个元素**

如果当前low和high之间有`奇数`个元素，则 mid 分隔后，**左右两部分元素个数相等**

折半查找的判定树中,**mid** = `[(low + high)/2]`则对于任何一个结点，必有：**右树结点数-左子树结点数=0或1**

折半查找的判定树`一定是平衡二叉树`

折半查找的判定树中，`只有最下面一层是不满的`因此，元素个数为n时树高$h=\left\lceil\log _{2}(n+1)\right\rceil$（该树高不包含失败节点）

判定树结点关键字：`左<中<右`，满足二叉排序树的定义

`失败结点：n+1个`（等于成功结点的空链域数量）

`折半查找的时间复杂度`:$O(log_2n)$

![折半查找3](https://wmicheng.top/images/note/img_Search_Sort/折半查找3.png)

## 分块查找

> #### 算法思想

![分块查找](https://wmicheng.top/images/note/img_Search_Sort/分块查找.png)

`特点`：块内无序、块间有序

**分块查找**，又称`索引`顺序查找**，算法过程如下：

- 在索引表中确定待查记录所属的分块（可顺序、可折半）
- 在块内顺序查找

> #### 用折半查找查索引

**查找目标与索引表值相同**

![分块查找5](https://wmicheng.top/images/note/img_Search_Sort/分块查找5.png)

**查找目标与索引值不同**

![分块查找4](https://wmicheng.top/images/note/img_Search_Sort/分块查找4.png)

**查找失败**

![分块查找6](https://wmicheng.top/images/note/img_Search_Sort/分块查找6.png)

> #### 查找效率分析

![分块查找1](https://wmicheng.top/images/note/img_Search_Sort/分块查找1.png)

![分块查找2](https://wmicheng.top/images/note/img_Search_Sort/分块查找2.png)

![分块查找3](https://wmicheng.top/images/note/img_Search_Sort/分块查找3.png)

## 二叉排序树

> #### 定义

![二叉排序树](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树.png)

> #### 二叉排序树查找

![二叉排序树1](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树1.png)

> #### 二叉排序树插入

![二叉排序树4](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树4.png)

> #### 二叉排序树构造

> #### 二叉排序树删除

先搜索找到目标结点：

![二叉排序树7](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树7.png)

> #### 查找效率分析

![二叉排序树8](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树8.png)

![二叉排序树9](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树9.png)

![二叉排序树10](https://wmicheng.top/images/note/img_Search_Sort/二叉排序树10.png)

## 平衡二叉树

> #### 定义

![平衡二叉树](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树.png)

> #### 平衡二叉树

> #### `调整平衡二叉树★★★`

![平衡二叉树3](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树3.png)

> #### 调整最小不平衡子树LL&RR

![平衡二叉树6](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树6.png)

> #### 调整最小不平衡子树LR&RL

![平衡二叉树13](https://wmicheng.top/images/note/img_Search_Sort/平衡二叉树13.png)

### 平衡二叉树插入&删除

> ##### 平衡二又树的`插入`操作：

- `插入`新结点后，要`保持二叉排序树的特性不变` （左<中<右）
- 若插入新结点导致`不平衡`，则需要`调整平衡`

> ##### 平衡二叉树的`删除`操作：

- `删除`新结点后，要`保持二叉排序树的特性不变` （左<中<右）
- 若`删除`新结点导致`不平衡`，则需要`调整平衡`

> ##### 平衡二叉树的`删除`操作具体步骤：

> ##### 平衡二叉树删除操作`时间复杂度`$=O\left(\log _{2} n\right)$

## 红黑树

![红黑树2](https://wmicheng.top/images/note/img_Search_Sort/红黑树2.png)

> #### 定义

`性质1`: 从根节点到叶结点的最长路径不大于最短路径的2倍

`性质2`: 有 ${\mathrm{n}}$ 个内部节点的红黑树高度 ${\mathrm{h} \leq 2 \log _{2}(n+1)}$

红黑树`查找`操作`时间复杂度` $=O\left(\log _{2} n\right)$——(查找效率与AVL树同等数量级)

> #### `红`黑树查找

与 BST、AVL 相同，从根出发，左小右大，若查找到一个空叶节点，则查找失败

### `红`黑树的插入

从一棵空的红黑树开始，插入：20,10,5,30,40,57,3,2,4,35,25,18,22,23,24,19,18

![红黑树7](https://wmicheng.top/images/note/img_Search_Sort/红黑树7.png)

![红黑树8](https://wmicheng.top/images/note/img_Search_Sort/红黑树8.png)

**性质1证明：任何一条查找失败路径上黑结点数量都相同，而路径上不能连续出现两个红结点，即红结点只能穿插在各个黑结点中间**

**性质2证明: 若红黑树总高度 =h 则根节点黑高 $\geq h / 2$n , 因此内部结点数$n\geq 2^{h / 2}-1$, 由此推出 $ h\leq 2 \log _{2}(n+1)$**

![红黑树9](https://wmicheng.top/images/note/img_Search_Sort/红黑树9.png)

结点的**黑高** `bh`一一从某结点出发（不含该结点）到达任一叶结点的路径上黑结点总数

`思考`：根节点黑高为h的红黑树，内部结点数（关键字）`至多`有多少个？

`回答`：内部结点数`最多`的情况一一h层黑结点，每一层黑结点下面都铺满一层红结点。共**2h**层的满树形态

`结论`：**若根节点黑高为h，内部结点数（关键字）最多有**$2^{2h}-1$**个**

### `红`黑树的删除

![红黑树10](https://wmicheng.top/images/note/img_Search_Sort/红黑树10.png)

## B树

> #### m叉查找树：

- 实际上就是二叉查找树的拓展，结点多少有多少个分叉就是多少叉查找树
- 每个结点关键字的查找可以用顺序查找也可以用折半查找

![B树](https://wmicheng.top/images/note/img_Search_Sort/B树.png)

**如何保证查找效率：**

> #### B树的定义

![B树1](https://wmicheng.top/images/note/img_Search_Sort/B树1.png)

`B树`，又称`多路平衡查找树`，B树中所有结点的孩子个数的最大值称为B树的阶，通常用m表示。一棵`m阶B树`或为空树，或为满足如下特性的m叉树：

> #### `m阶B树`核心特性

> #### B树的高度

![B树3](https://wmicheng.top/images/note/img_Search_Sort/B树3.png)

$$
\text { 含 } \mathrm{n} \text { 个关键字的 } \mathrm{m} 叉\mathrm{B} \text { 树, } \log _{m}(n+1) \leq h \leq \log _{[m / 2]} \frac{n+1}{2}+1
$$

### `B树的插入删除`

> #### B树的插入：

> #### B树的删除

![B树5](https://wmicheng.top/images/note/img_Search_Sort/B树5.png)

## B+树

![B+树](https://wmicheng.top/images/note/img_Search_Sort/B+树.png)

> #### 定义和性质

一棵`m阶的B+树`需满足下列条件：

**B+树的查找：**

B+树中，无论查找成功与否，最终一定都要走到最下面一层结点，因为只有叶子结点才有关键字对应的记录

**B+树和B树区别：**

![B+树1](https://wmicheng.top/images/note/img_Search_Sort/B+树1.png)

## 散列（哈希）查找

![散列表](https://wmicheng.top/images/note/img_Search_Sort/散列表.png)

> #### 定义

> #### 处理冲突的方法——拉链法

![散列表1](https://wmicheng.top/images/note/img_Search_Sort/散列表1.png)

> #### 常见的散列函数

`散列函数的设计目的`：

- 让不同关键字的冲突尽可能的少
- 散列查找是典型的“用空间换时间”的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。

**除留余数法**：$H(key) = key % p$

- 散列表表长为m，取一个不大于m但最接近或等于m的质数p
- 质数又称素数。指除了1和此整数自身外,不能被其他自然数整除的数

![散列表4](https://wmicheng.top/images/note/img_Search_Sort/散列表4.png)

**直接定址法** ： H(key) = key 或 H(key) = a\*key + b

![散列表5](https://wmicheng.top/images/note/img_Search_Sort/散列表5.png)

**数字分析法**：选取数码分布较为均匀的若干位作为散列地址

![散列表6](https://wmicheng.top/images/note/img_Search_Sort/散列表6.png)

**平方取中法**：取关键字的平方值的中间几位作为散列地址。

![散列表7](https://wmicheng.top/images/note/img_Search_Sort/散列表7.png)

![散列表8](https://wmicheng.top/images/note/img_Search_Sort/散列表8.png)

> #### 处理冲突的方法——开放定址法

![散列表9](https://wmicheng.top/images/note/img_Search_Sort/散列表9.png)

**线性探测法**

**平方探测法**

**伪随机序列法**

- $di$ 是一个伪随机序列，如 $di= 0, 5, 24, 11, …$

**处理冲突的方法——再散列法：**

![散列表10](https://wmicheng.top/images/note/img_Search_Sort/散列表10.png)

---

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

常见查找算法分析

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款