Loading... ## 基本概念 - 查找：再数据集合种寻找满足某种条件的数据元素的过程称之为查找 - 查找表 (查找结构) ：用于查找的数据集合称为查找表，它由同一类型的数据元素组成。 > 查找表不是特定的数据结构。 - 关键字：数据元素中**唯一**标识该元素的某个数据项的值。 ### 常见操作 - 查找符合条件的数据元素。 - 插入或删除某个数据元素。 静态查找表：只进行查找操作，所以仅关注查找速度即可。 动态查找表：需要进行上面两种操作，所以也需要关注插入删除操作是否方便实现。 ### 查找算法的评价指标 - 查找长度：在查找运算中，需要对比关键字的次数称为查找长度。 - 平均查找长度 (ASL, Average Search Length) ：所有查找过程中进行关键字的比较次数的平均值。 > ASL 的数量级反映了查找算法的时间复杂度。评价一个查找算法的效率时，通常考虑查找成功和查找失败两种情况的 ASL 。 ## 顺序查找 顺序查找又叫**线性查找**，常见于线性表，从头到尾遍历一遍查找即可。 - $ASL_{success} = \frac{1 + 2 + 3 + ... + n}{2} = \frac{n + 1}{2}$ 。 - $ASL_{fail} = n + 1$ 。 因此顺序查找的时间复杂度为 $O(n)$ 。 ### 优化 如果线性表有序，那么此时就可以提前结束查找。此时的 ASL 可以用查找判定树来分析： ![image-20240607005439618.png][1] 如果被查找的概率不相等，那么可以把概率高的数放在前面。 ## 二分查找 仅适用于有序顺序表的查找算法。 ![image-20240607005859860.png][2] ### 二分查找判定树的构造 - 如果 `left` 和 `right` 中有奇数个元素，则 `mid` 分隔后，左右两部分元素个数相同。 - 如果 `left` 和 `right` 中有偶数个元素，则 `mid` 分隔后，左半部分比右半部分少一个元素。 - 二分查找的判定树中，若 $mid = \lfloor (low + high) / 2 \rfloor$ ，则对于任何一个节点，必有**右子树节点数 - 左子树节点数 = 0 或 1** 。 ![image-20240607010444272][3] 判定树一定为平衡二叉树，树高为 $\lceil log_2(n + 1) \rceil$ 。 ### 时间复杂度 判定树树高最大为 $\lceil log_2(n + 1) \rceil$ ，查找成功和失败的 ASL 必定小于等于树高，因此二分查找的时间复杂度为 $O(log_2n)$ 。 ## 分块查找 分块查找，又称**索引顺序查找**，特点是数组中元素在块内无序，块间有序。 ![image-20240627210729897.png][4] ### 算法过程 1. 在索引白哦中确定待查元素所属的分块；(可以使用顺序查找或者二分查找) 2. 在块内使用顺序查找。 ### 考点 主要存在于选择题。 - 查找成功的 ASL ![image-20240627211706684.png][5] 计算出查找到各个元素的次数，然后乘以概率即可。二分查找的分析流程也类似。 查找失败一般不考察。 - 均分的情况 ![image-20240627212222254.png][6] 二分查找的情况下 $ASL = \lceil log_2(b + 1) \rceil + \frac{s + 1}{2}$ 。 ## 二叉搜索树 BST (Binary Search Tree) ：一颗空二叉树或者具有以下性质的二叉树 - 左子树上所有节点的关键字均小于根节点的关键字； - 右子树上所有节点的关键字均大于根节点的关键字； - 左子树和右子树各是一棵二叉排序树。 > 对二叉搜索树进行中序遍历，可以得到一个递增的有序序列。 ### 基本操作 - 查找 若树非空，则将目标值和根节点的值比较，若相等则查找成功。 若小于根节点，则往左子树上查询；大于根节点则在右子树上查询。 - 插入 - 构造 不同的关键字序列可能得到相同的二叉搜索树。 - 删除 若被删除的节点 $z$ 没有子树，直接删除即可。 若节点 $z$ 只有一棵子树，则直接让 $z$ 的子树成为 $z$ 父节点的子树即可。 若节点 $z$ 有两棵子树，则令 $z$ 的直接后继 (或直接前驱) 替代 $z$ ，然后从二叉排序树中删除这个直接后继 (或直接前驱) ，此时就转化为前面情况，使用对应的方法处理即可。 > $z$ 的前驱：$z$ 的左子树中最右下的节点，也就是小于 $z$ 的值中最大的一个。 > > $z$ 的后继：$z$ 的右子树中最左下的节点，也就是大于 $z$ 的值中最小的一个。 ### 查找效率 查找成功的情况： ![image-20240629203055657.png][7] 查找失败的情况：(需要补充失败节点) ![image-20240629203122571.png][8] ## 平衡二叉树 平衡二叉树 (Balanced Binary Tree) ，简称 AVL 树 (来自于发明者 G. M. Adeleson-Velsky 和 E. M. Landis) 。树上任一节点的左子树和右子树的高度之差不超过 1 。 节点的**平衡因子**：左子树高 - 右子树高。 - 平衡二叉树的平衡因子只可能是 -1, 0, 1 。 - 一棵高度为 $k$ 的平衡二叉树在节点最少的情况下，其所有非叶节点的平衡因子都为 1 。可通过以下递推式计算出此时的节点数：$F(k) = F(k - 1) + F(k - 2) + 1$ ，其中 $F(2) = 2, F(1) = 1$ 。 ### 基本操作 #### 插入 插入一个元素会要保持二叉搜索树的特性不变。若插入导致平衡二叉树不平衡，这时候需要调整**最小不平衡子树**。 ![image-20240629203726545.png][9] - 左孩子的左子树中插入导致不平衡 (LL) 将失衡节点进行一次向右旋转即可。 ![image-20240701014411124.png][10] - 右孩子的右子树中插入导致不平衡 (RR) 与 LL 同理，进行一次左旋即可。 ![image-20240701014455116.png][11] - 左孩子的右子树中插入导致不平衡 (LR) 先对左子树进行一次左旋，再对失衡节点进行一次右旋。 ![image-20240701014617378.png][12] - 右孩子的左子树中插入导致不平衡 (RL) 先对右子树进行一次右旋，再对失衡节点进行一次左旋。 ![image-20240701014714661.png][13] #### 查找 若树高为 $h$ ，则最坏情况下查找一个关键字最多需要对比 $h$ 次，即查找时间复杂度最大为 $O(h)$ 。 设深度为 $h$ 的平衡树中含有的最少节点数为 $n_h$ ，易知 $n_0 = 0, n_1 = 1, n_2 = 2$ ，并且可以推出 $n_h = n_{h - 1} + n_{h - 2} + 1$ 。因此 $n$ 个节点的平衡二叉树的最大深度为 $O(log_2 n)$ ，也就是平衡二叉树的平均查找长度为 $O(log_2 n)$ 。 > 证明方法见 《An algorithm for the organiza on of informa on》——G.M. Adelson Velsky 和 E.M. Landis ,1962 #### 删除 删除操作和插入操作类似，但由于删除节点可能会减少当前子树的高度，所以不平衡可能会向上传导。 删除节点的步骤： 1. 删除节点，操作同二叉搜索树。 - 叶子节点直接删除； - 有一颗子树则直接用子节点代替该节点； - 两颗子树则用其直接前驱 (直接后继) 代替该节点，然后删除其前驱 (后继) 。 2. 向上搜索找到最小不平衡子树，若不存在则结束。 3. 找到最小不平衡子树的高度最高的儿子节点和孙子节点。 4. 根据儿子节点和孙子节点的位置关系，调整平衡，方法同插入情况。(LL, RR, LR, RL) 5. 如果不平衡向上传导，也就是还存在不平衡的情况，则回到 2 继续执行。 ![image-20240702203118149.png][14] ![image-20240702203133157.png][15] **时间复杂度**：$O(log_2n)$ 。 ## 红黑树 **平衡二叉树**插入或删除节点很容易破坏平衡，**需要频繁调整**树的形态。每次调整需要先计算平衡因子，找到最小不平衡子树 (时间消耗较大) ，然后再进行旋转调整。 **红黑树**的插入和删除操作一般不会破坏 "红黑" 的特性，无需频繁调整。即使需要调整，通常情况下都可以在**常数级时间内完成**。 因此平衡二叉树适用于以查找为主，插入删除较少的场景；红黑树适合频繁插入删除的场景，实用性较长。 ### 定义 红黑树也是一种二叉搜索树，所以也满足二叉搜索树的定义，即 左子树节点值 $\leq$ 根节点值 $\leq$ 右子树节点值。 此外，还有一些额外的要求： - 每个节点都是红色或黑色的； - 根节点是黑色的； - 叶节点 (又称外部节点，失败节点等) 均是黑色的； 注意红黑树的叶节点和一般说的叶节点不一样，指的是二叉树的空链域。 - 不存在两个相邻的红节点； 即任意红节点的父节点和子节点都一定是黑色的，兄弟节点不算相邻。 - 对于每个节点，从该节点到其任意一个叶节点的简单路径上，所包含的黑节点数量相同。 ```c++ struct RBnode { int key; RBnode* parent; RBnode* lChild; RBnode* rChild; int color; // 节点颜色 }; ``` **黑高 (bh)**：从某节点出发 (不含该节点) 到达其任一叶节点的路径上的黑节点总数。 ### 性质 1. 从根节点到叶节点的最长路径不大于最短路径的两倍。 2. 有 $n$ 个内部节点的红黑树高度 $h \leq 2log_2(n + 1)$ 。 因此红黑树的查找时间复杂度为 $O(log_2n)$ 。 ### 基本操作 #### 插入 1. 先查找，确定插入位置。红黑树也是一棵二叉搜索树，因此按照二叉搜索树的方式插入新节点。 2. 若新节点是根节点，则将其染为黑色；若不是根节点则染为红色。 3. 若插入新节点后仍然满足红黑树的定义，则结束插入。若不满足，则需要调整使其重新满足红黑树的定义： 根据其叔节点 (父节点的兄弟节点) 的颜色，有不同的操作方法。 - 若叔节点为黑色，则需要进行旋转和染色。 旋转参考平衡二叉树的旋转，也是四种情况。在此基础上还需要增加一个染色操作，具体为将原先的父节点和爷节点的颜色进行取反。 - 若树节点为红色，则需要染色，并且对爷节点再次进行判断。 这里的染色是将叔节点，父节点，爷节点的颜色全部进行取反，并且对爷节点再进行一次步骤 3 的判断。 #### 删除 - 红黑树删除的时间复杂度是 $O(log_2n)$ 。 - 红黑树中删除节点的操作和二叉排序树的删除一样。但删除后可能会破坏红黑的特性，需要调整节点的颜色。 - 22 年才加入，大概率不考，主要复习前两个操作。 ## B 树 ### 定义和性质 B 树，又称多路平衡查找树。B 树种所被允许的孩子个数的最大值成为 **B 树的阶**，通常用 $m$ 表示。一棵 $m$ 阶的 B 树要么是空树，要么是满足以下特性的 $m$ 叉树： 1. 树中每个节点至多有 $m$ 棵子树，即至多含有 $m - 1$ 个关键字。 2. 若根节点不是终端节点，则至少有两棵子树。(要保证绝对平衡) 3. 除了根节点外的所有非叶节点至少有 $\lceil m / 2 \rceil$ 棵子树，即至少含有 $\lceil m / 2 \rceil - 1$ 个关键字。 4. 所有非叶节点的结构如下： ![image-20240705144450662.png][16] 其中 $K_i \ (i = 1, 2, ... , n)$ 为节点的关键字，且满足 $K_1 < K_2 < ... < K_n$ ；$P_i \ (i = 0, 1, ... , n)$ 为指向子树根节点的指针，且指针 $P_{i - 1}$ 所指向的子树中所有节点的关键字均小于 $K_i$ ，$P_{i}$ 所指向的子树中所有节点的关键字均大于 $K_i$ 。$n$ 为节点中关键字的个数，其范围为 $\lceil m / 2 \rceil - 1 \leq n \leq m - 1$ 。 5. 所有**叶节点 (失败节点)** 都出现在同一层次上，且不带信息。 ![image-20240705210842663.png][17] **$m$ 阶 B 树的核心特性**： 1. 根节点的子树数 $\in [2, m]$ ，关键字数 $\in [1, m - 1]$ 。 其他节点的子树数 $\in [\lceil m / 2 \rceil , m]$ ，关键字数 $\in [\lceil m / 2 \rceil - 1 , m - 1]$ 。 (尽可能满) 2. 对于任一节点，其所有子树的高度都相同。 (尽可能平衡) 3. 关键字的值：子树 0 < 关键字 1 < 子树 1 < 关键字 2 ... - 含有 $n$ 个关键字的 $m$ 阶 B 树，**最小高度**为 $log_m(n + 1)$ 。 高度最小意味着需要让每个节点尽可能地满，有 $m - 1$ 个关键字，$m$ 个分叉。因此有 $n \leq (m - 1)(1 + m + m^2 + ... + m^{h - 1}) = m^h - 1$ ，化简得 $h \geq log_m(n + 1)$ 。 - **最大高度**为 $h \leq log_{\lceil m / 2 \rceil} \frac{n + 1}{2} + 1$ 。 高度最大则需要让各层地分叉尽可能少，即根节点只有两个分叉，其他节点各有 $\lceil m / 2 \rceil$ 个分叉。 ### 基本操作 B 树实际上是一个 $m$ 叉搜索树，因此查找操作直接参考二叉搜索树即可，不多赘述。 #### 插入 **核心要求：** 1. 对 $m$ 阶 B 树，除根节点外节点的关键字个数 $n$ 满足 $\lceil m / 2 \rceil - 1 \leq n \leq m - 1$ 。 2. 子树 0 < 关键字 1 < 子树 1 < 关键字 2 ... 新元素一定是插入到最底层的 "终端节点" ，需要查找来确定插入的位置。 ![image-20240705212055019.png][18] 在插入 key 后，若导致源节点的关键字数超过上限，则从中间位置 ($\lceil m / 2 \rceil$) 将其中的关键字**分为两部分**，左边部分包含的关键字放在原节点中，右边部分包含的关键字放到新节点中，中间位置的节点插入原节点的父节点中 (注意保持有序) 。 ![image-20240705212301290.png][19] 若经过上述处理后导致父节点的关键字个数也超过了上限： ![image-20240705212426941.png][20] 则继续执行这种分裂操作，直到这个过程传导到根节点为止。此时将导致 B 树的高度增加 1 。 ![image-20240705212525625.png][21] #### 删除 若被删除的关键字在**非终端节点**，则用其**直接前驱 (后继) **来替代被删除的关键字，然后删除其直接前驱 (后继) 。这样就将非终端节点的删除**转化为终端节点的删除**。 若删除的节点在终端节点，那么分为以下几种情况： - 节点中关键字个数大于 $\lceil m / 2 \rceil - 1$ ，直接删除即可。 - 删除元素后节点内关键字个数小于 $\lceil m / 2 \rceil - 1$ ，此时需要观察其左右兄弟的情况： - 若其左右兄弟中存在关键字个数大于 $\lceil m / 2 \rceil - 1$ 的，则进行一个 "左旋" (或 "右旋") 的操作； ![image-20240705214207015.png][22] ![image-20240705214224736.png][23] - 若其左右兄弟关键字个数均不大于 $\lceil m / 2 \rceil - 1$ ，则将删除元素后的该节点和**其左 (或右) 兄弟节点**，以及**父节点中的关键字**进行**合并**。 ![image-20240705214604586.png][24] ![image-20240705214626230.png][25] 若合并后父节点中关键字个数也小于 $\lceil m / 2 \rceil - 1$ ，则需要继续判断，直至符合 B 树的要求为止。 ![image-20240705214830365.png][26] ## B+ 树 ### 定义 一棵 $m$ 阶的 B+ 树需要满足下列条件： 1. 每个分支节点最多有 $m$ 棵子树 2. 非叶根节点至少有两棵子树，其他每个分支节点至少有 $\lceil m / 2 \rceil$ 棵子树。(为了追求绝对平衡) 3. **节点的子树个数与关键字个数相同**。(与 B 树不同) 4. 所有叶节点**包含全部关键字**及指向相应记录的指针，叶节点中将关键字按大小顺序排列，并且**相邻叶节点按照大小顺序连接起来**。 > 意味着 B+ 树支持顺序查找 5. 所有**分支节点**中仅包含它的各个子节点中**关键字的最大值**及指向其子节点的指针。 ![image-20240705225810778.png][27] ### 查找 可以按照树的查找进行查找，也可按照分块查找的方式进行顺序查找，不多赘述。 ### B 树 V.S. B+ 树 | B 树 | B+ 树 | | ------------------------------------------------------------ | ------------------------------------------------------------ | | $m$ 叉搜索树 | 多级分块查找 | | 节点中 $n$ 个关键字对应 $n + 1$ 棵子树。 | 节点中 $n$ 个关键字对应 $n$ 棵子树。 | | 根节点的子树数 $\in [2, m]$ ，关键字数 $\in [1, m - 1]$ 。 <br>其他节点的子树数 $\in [\lceil m / 2 \rceil , m]$ ，关键字数 $\in [\lceil m / 2 \rceil - 1 , m - 1]$ 。 | 根节点的子树数 $\in [1, m]$ ，关键字数 $\in [1, m]$ 。 <br/>其他节点的子树数 $\in [\lceil m / 2 \rceil , m]$ ，关键字数 $\in [\lceil m / 2 \rceil , m]$ 。 | | 各节点中包含的关键字是不重复的。 | 叶节点包含所有的关键字，非叶节点出现过的关键字也会出现在叶节点中。 | | 所有节点中都包含记录的信息。 | 只有叶节点包含信息，非叶节点仅起索引作用。<br>非叶节点中的每个索引项仅含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。 | | 不支持顺序查找。查找成功时可能停留在任意一层的节点，查找速度 "不稳定" 。 | 支持顺序查找。查找成功或者失败都会到达最下一层的叶节点，查找速度 "稳定" 。 | > B+ 树的非叶节点不含有该关键字对应记录的存储地址。这么设计可以使一个磁盘块能存储更多的关键字，使得 B+ 树的阶更大，树高更矮。从而使读磁盘次数更少，查找更快。 ## 哈希表 ### 定义 **哈希表** (Hash Table) ：也可叫散列表，是一种数据结构，特点是**可以根据数据元素的关键字计算出它在哈希表中的存储地址**。 **哈希函数** ：建立了 `关键字 -> 存储地址` 的映射关系的函数。 **冲突 (碰撞)** ：在哈希表中插入一个数据元素时，若根据哈希函数计算出的地址已经存储了其他元素，则称这种情况为**哈希冲突**。 **同义词** ：若不同的关键字通过哈希函数映射到同一个存储地址，则称它们为**同义词**。 理想情况下，哈希表中查找一个元素的时间复杂度为 $O(1)$ 。 ### 哈希函数的设计 - 定义域必须涵盖所有可能出现的关键字。 > 反例：$H(key) = \sqrt{key} % 13$ ，该哈希函数不支持负关键字。 - 值域不能超出哈希表的地址范围。 - 尽可能减少冲突。哈希函数计算出来的地址应尽可能均匀地分布在整个地址空间。 - 哈希函数应该尽可能简单，能够快速计算出任意一个关键字对应的地址。 #### 除留余数法 $$ H(key) = key \% p $$ 设哈希表表长为 $m$ ，则 $p$ 应该取一个不大于 $m$ 但最接近或等于 $m$ 的**质数**。 > 选取质数的原因是对质数取余可以分布的更均匀，从而减少冲突。具体证明可以研究数论。 #### 直接定址法 $$ H(key) = key \ 或 \ H(key) = a \times key + b $$ 其中 $a, b$ 为常数。这种方法计算最简单，并且不会产生冲突。若关键字分布不连续，空位较多，则会造成存储空间的浪费。 **适用场景**：关键字分布基本连续的场景。 #### 数字分析法 选取数码分布较为均匀的若干位作为哈希地址。 设关键字是 $r$ 进制数 (如十进制数) ，而 $r$ 个数码在各位上唇线的频率不一定相同，可能在某些位上的分布均匀一些，而在某些位上分布不均匀。此时可以选择数码分布较为均匀的若干位作为哈希地址。 **适用场景**：关键字即可已知，且关键字中有部分数码位分布均匀。 例如：将手机号码存入哈希表中。已知手机号码前三位是运营商号，中间四位是地区区号，最后四位是随机的。因此手机号最后四位是分布较为均匀的数码，可以选择这四位作为哈希地址。 #### 平方取中法 取关键字的平方值的中间几位作为哈希地址。 具体取多少位视情况而定。这种方法得到的哈希地址与关键字的每位都有关系，因此使得哈希地址的分布比较均匀。 **适用场景**：关键字的每位取值都不够均匀。 ![image-20240708011001513.png][28] ### 哈希冲突的处理 #### 链地址法 把所有**同义词**存储在一个链表中。 #### 开放定址法 如果发生冲突，则寻找另一个空闲的位置来存储新元素。 $$ H_i = (H(key) + d_i) \% m $$ 其中 $H_i$ 为发生第 $i$ 次冲突时候的哈希地址；$H(key)$ 为初始哈希地址；$d_i$ 为偏移量；$m$ wei哈希表表长。 常用的探测序列构造法： - 线性探测法：$d_i = 0, 1, 2, ... , m - 1$ ； - 平方探测法：$d_i = 0^2, 1^2, -1^2, 2^2, -2^2, ... , k^2, -k^2$ ，其中 $k \leq m /2$ ； - 双哈希法 (双散列法)：$d_i = i \times hash_2(key)$ ，其中 $hash_2(key)$ 为另一个哈希函数； - 伪随机序列法：$d_i$ 是一个伪随机序列，如 $d_i = 0, 5, 3, 11, ...$ 。 > 注意删除的时候需要使用软删除，否则会影响开放定址法的搜索。 [1]: https://blog.domineto.top/usr/uploads/2024/07/2470022375.png [2]: https://blog.domineto.top/usr/uploads/2024/07/885614655.png [3]: https://blog.domineto.top/usr/uploads/2024/07/1653007331.png [4]: https://blog.domineto.top/usr/uploads/2024/07/1986754684.png [5]: https://blog.domineto.top/usr/uploads/2024/07/1130843710.png [6]: https://blog.domineto.top/usr/uploads/2024/07/2114987946.png [7]: https://blog.domineto.top/usr/uploads/2024/07/2843275658.png [8]: https://blog.domineto.top/usr/uploads/2024/07/1968227139.png [9]: https://blog.domineto.top/usr/uploads/2024/07/4244069529.png [10]: https://blog.domineto.top/usr/uploads/2024/07/4231966530.png [11]: https://blog.domineto.top/usr/uploads/2024/07/1108595936.png [12]: https://blog.domineto.top/usr/uploads/2024/07/160643208.png [13]: https://blog.domineto.top/usr/uploads/2024/07/4010489202.png [14]: https://blog.domineto.top/usr/uploads/2024/07/2280847502.png [15]: https://blog.domineto.top/usr/uploads/2024/07/256406811.png [16]: https://blog.domineto.top/usr/uploads/2024/07/1289616943.png [17]: https://blog.domineto.top/usr/uploads/2024/07/2012878682.png [18]: https://blog.domineto.top/usr/uploads/2024/07/3727690265.png [19]: https://blog.domineto.top/usr/uploads/2024/07/1313518045.png [20]: https://blog.domineto.top/usr/uploads/2024/07/3471524100.png [21]: https://blog.domineto.top/usr/uploads/2024/07/1396446654.png [22]: https://blog.domineto.top/usr/uploads/2024/07/2910023541.png [23]: https://blog.domineto.top/usr/uploads/2024/07/3659378035.png [24]: https://blog.domineto.top/usr/uploads/2024/07/789304039.png [25]: https://blog.domineto.top/usr/uploads/2024/07/1377721080.png [26]: https://blog.domineto.top/usr/uploads/2024/07/195335907.png [27]: https://blog.domineto.top/usr/uploads/2024/07/1039054063.png [28]: https://blog.domineto.top/usr/uploads/2024/07/3159207278.png 最后修改：2024 年 11 月 20 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏