数据结构笔记——查找、排序（王道408）

数据结构笔记——查找、排序（王道408）"/>

数据结构笔记——查找、排序（王道408）

文章目录

• 查找
• • 基本概念
  • 线性表查找
  • • 顺序查找
    • 折半查找（二分）
    • 分块查找
  • 树查找
  • • 二叉排序树（BST）
    • 平衡二叉树（AVL）的插入
    • • 平衡化
      • 复杂度分析
    • 平衡二叉树的删除
  • 红黑树
  • • 红黑树的定义和性质
    • • 红黑树定义
      • 红黑树性质
    • 红黑树的插入
    • 红黑树的删除
  • B树
  • • B树基础
    • B树插入和删除
    • • 裂变插入法
      • 流动删除法
    • B+树
    • • 定义和特性
      • B+树查找
      • B+树对比B树
      • 与OS的联系
  • 散列查找

查找

基本概念

查找表，其实就类似于数据库的数据表。
所谓的数据项，就是数据库的一列，而关键字就是key，是唯一的。

查找长度（SL）即key的比较次数，ASL是Average SL

线性表查找

顺序查找

基本的查找算法，如果不会写就废了，注意循环跳出条件：key匹配则跳出

哨兵可以简化代码，本质在于，哨兵和普通元素的逻辑是一致的，但是可以发挥出终止的效果
因此，for循环不需要考虑越界，最后return的时候也不需要判断是否查找成功（哨兵本身的0下标就代表失败）

其实链表里的头结点也是一种哨兵。

查找的优化思路有二：

1. 有序情况下（假定顺序），如果key已经大于目标key了，那么后面也就没必要继续扫了，即提前终止，可以减少失败ASL
2. 如果已知查找到的概率，那么可以将高概率的排在前面，即提前成功，可以减少成功ASL

分析ASL的时候可以用判定树来分析，将判定逻辑写成树，分析ASL的思路如下：

1. 成功的ASL，就把n个成功节点加权和，而失败的ASL，就把n+1个失败节点加权和
2. 单个成功节点的SL=高度，而失败节点的SL=父节点高度

折半查找（二分）

前提是有序。

low和high构成一个闭区间，目标元素只可能在闭区间内，每次要和mid对比。

和mid对比，情况有两大类：

1. 等，则成功
2. 不等，则代表只能在两侧区域，不包括mid，因此边界要调整为mid-1（小），mid+1（大）

此时你可能会怀疑，最后能不能收敛，如果你是以mid为新边界，下面这种情况可能就无法收敛了，但是如果你去掉mid，即以mid+1为新边界，假设能查到，最坏的情况也一定会收敛到具体的一个点上（此时low==high）

假设查不到，在收敛到具体的一个点后，low和high就要错开，构成low>high的情景，此时直接报错

整体来看这个算法，过程如下：

1. 考察区域从全部收敛到-1
   • 极限情况：low≤high
   • 一定会不断收缩，一定可以判定完最后一个点
   • 之后继续走的话，low和high会交错，退出循环
2. 在收敛过程中，如果成功则提前退出循环

因此这个算法是完美无缺的，可以全覆盖所有可能。

分析效率继续用判定树，这个判定树是非常的神奇好用，把成功节点（mid）逐层展开，再补上失败节点就如下图

需要注意的是，假如总结点数量为偶数个，那么考虑到mid是向下取整，就会出现右子树=左子树+1的现象，不可能更多了，也就是说，右子树-左子树=0或1，只有这两种可能。

反过来，如果mid向上取整，自然就是左-右=0或1

无论哪种方式，折半查找判定树是平衡二叉树，而且只可能有最下面一层不满，那么树高就可以用完全二叉树的算法去算，即log（n+1）向下取整

分块查找

其实分块的最佳储存结构是索引数组+n条链表，操作系统里也会有类似结构出现（比如文件索引）

分块查找=索引+顺序，索引用来缩减范围，进而使得顺序查找次数更少

值得讨论的是查找索引的过程。

首先要明白，索引中的maxValue代表索引中最大的值（包括最大），这是后面讨论的基础：

1. mid=key，这种情况其实比较少见
2. mid≠key，则最终一定会停在low上
   • 最终high在左，low在右
   • 因为low左边都是小于目标key的，根据前面maxValue的意义，索引的值都小于key了，那必然不存在，所以low左边是不可能的（太小），而low右边又太大了，那么最后就会卡在low上
   • 假如low越界，代表所有索引对应的块都不可能存在目标key
     

对于每一个节点，其SL=索引查找次数+顺序查找次数

需要注意折半情况下的索引查找次数，分析起来比较复杂，假如key≠mid，那么最后就要反复调整直到high<low的时候，这才是真正的索引次数。

因为SL有两部分，而且相关联，所以算ASL比较麻烦，为了便于分析，直接把数组等分，那么这两部分的关联性就打破了，可以分别计算ASL1和ASL2，最后相加。

具体分析，顺序情况下，n=sb，因此把b=n/s带进去ASL就可以得到一个式子，进而求得极限情况的ASL

其实这才是最完美的索引顺序结构。

树查找

二叉排序树可以说是，带有伸缩功能的顺序数组，只是说不平衡会导致其效率退化
而进一步的AVL树，弥补了不平衡的问题，在保证伸缩性的前提下，最大化逼近数组的效率
可以说是比较完美的结构了。

二叉排序树（BST）

递归和循环的思路一样：

1. 退出条件：空，或者匹配到
2. 否则就查左/右子树

插入，就是要找到插入点位：

1. 有一样的，失败
2. 没有一样的，生成新节点，令父节点链域指向该节点。
   • 父节点指针从何而来？需要注意BSTree &T，也就是说，在最后T==0的时候，这个T不仅仅是空指针，其本身还是父节点的孩子链域，因此我们直接把T指向新节点就可以了，在第一步就完成了。
   • 记得初始化左右孩子为NULL

有了插入后，给定一个T=NULL的初始链域，就可以反复插入，形成二叉树。

删除节点，这个涉及到树结构的重构，比较复杂：

1. 叶子结点
2. 只有单边孩子
3. 有双边孩子，按照中序序列，上层是左根右，展开后变为（左根右）根（左根右），删去根后有两种顶替思路
   • 以右子树最左边的节点顶替根（大中最小），那么拆掉的这个节点又该怎么补呢？恰好最左边的节点，一定不可能有左子树，这就划归到了2情况
   • 左侧情况反过来就行
     

查找效率用ASL评估，这俩在查找中是等价的。

给定具体的一个例子，成功的ASL则要去计算n个成功节点的加权，而失败则要补n+1个失败节点，再加权

下图表示，二叉树查找的平均效率与其高度成正比，那么理想情况是把高度压制成平衡二叉树，这就是后面的内容了。

平衡二叉树（AVL）的插入

平衡化

平衡二叉树，任一节点的平衡因子（左-右）都只可能是-1,0，1，如果添加节点导致破坏平衡性，就要找到最小不平衡树，进行平衡化修正

以最小不平衡树根节点为A，则不平衡无非就是四种情况，LL，LR，RL，RR，这四种情况的记忆方法如下：

1. 第一个字母代表A的左右子树
2. 第二个字母代表子树的左右孩子

因此LL就是左子树左孩子插入，导致不平衡，到时候自己画图就好。

首先要说明，三个子树都是H高度，这个是铁定的，否则插入就不会破坏平衡性。

LL和RR比较简单，本质在于让B当根节点，因此转一下就行

看下操作，实际上是要让B当根，A当孩子，因此分三步，写旋转代码要按这三个步骤来：

1. 替换A的左孩子，此时A成为一颗可以随意挪动的树
2. 让A成为B的孩子
3. 让B成为根节点

LR和RL复杂一些，对于LR，具体还要把L子树的R孩子（高度为H+1）继续展开，以便于分析，但是实际上，这两种情况是一样的，因此假定是下图情况。

但是实际上本质不变，最终的目标是让C当根节点，BA分别为左右，那么C就要转两下，先和B在和A，这样C就可以变成根节点，两次旋转沿用前面的思路即可。

RL也是如此，最终要让C当根节点。

最后再整体总结一下，你会发现4类情况，最小不平衡子树本来都是H+2高度，然后插入新节点变成H+3，破坏平衡性，调整以后重归H+2，同时平衡性保持住了

之所以只调整最小不平衡树就可以保证整体平衡性，是因为这一通调整将多出来的高度抹平了，更上面的节点的平衡因子自然就退回到平衡状态了。

我们把眼光落实在做题上：你要盯一眼，从下往上找到第一个不平衡的节点，代表最小不平衡树的根节点，然后回忆4种情况，标上ABC，剩下步骤就很简单了，如此就秒杀了。

复杂度分析

无论是插入还是删除，费时间的其实还是查找目标位置，说白了ASL和查找是一样的，调平衡度不影响。

再有就是复杂度分析，ASL=层数，即O（h）效率，关键在于如何通过节点数量n计算h的上界（或者通过h计算n的下界）

这是个数学问题，根本在于AVL的特性，即平衡因子最多为1，那么极限情况就是高度为h的树，一颗子树高度为h-1，另一颗为h-2，因此这颗树的节点数 n h = n h − 1 + n h − 2 + 1 n_h=n_{h-1}+n{h-2}+1 nh​=nh−1​+nh−2+1=左子树+右子树+根

考虑初始情况，高度为012，最少节点也是012，按照递推就可以计算出任何高度的节点数下界。
反过来，已知n，就可以知道h上界
最后算ASL，经过一通推导，结果就是O（logN）

平衡二叉树的删除

第一步是按照二叉排序树删除，这一步本身就挺麻烦

先看一个简单的例子，熟悉流程

1. 从删去点向上找，找到第一个不平衡节点，这就是最小不平衡树的根
2. 从根开始，找个头最高的儿子和孙子，其实就是从上往下，找到不平衡的传导链条
3. 判断4类不平衡情况，进行旋转
   • 这一步可以使得不平衡部分的H减小1，这样可能会导致树的另一侧过高失衡，要二次调整，回到1步开始

接下来举一个需要二次平衡的例子，下图进行第一次平衡后，右子树高度减一，导致左子树太高。

跳回到1步：

1. 从调整点位开始向上找，找到第一个不平衡点，即33
2. 然后从根节点开始向下找不平衡链条，为33-10-20
3. 进行翻转，即可平衡

有没有可能出现第三次不平衡？有可能，因为我们这次找到根恰好也是整个树的根，因此一步到位，假设我们找到的根上面还有东西，那么这一层降低高度后还有可能导致另一侧失衡，总之是一定要向上找是否失衡

考试中可能出现的最极限的情况是，删除的节点同时有左右孩子，那么这个时候就有两种删除方案。
后面仍然按照我们的流程来进行调整

但是这其实就有歧义了，408不太可能出这种，最后提一嘴，复杂度同查找，O（logN）

红黑树

红黑树的定义和性质

虽说AVL的复杂度是logN，但是实际上，每次找最小不平衡树比较费时间，实际消耗时间会有一个常数级别的放大，如果要频繁改变结构，就比较慢，红黑树应运而生。

首先明白，红黑树是从BST，AVL一脉相承过来的，所以本身也具有BST性质：左＜根＜右
或者说，AVL和红黑树都是BST的改进，AVL和红黑树严格来说是并列关系，但是性能是要碾压的

红黑树相比于BST来说，有两点改变：

1. 使用三叉链表结构
2. 增加了节点的红黑特性（对标AVL的平衡因子，但是有所不同）

红黑树定义

多出来的两个信息，可以为操作带来诸多方便，理解一下下面的规律：

1. 左根右。这告诉我们红黑树的本质还是BST
2. 根叶黑。根节点和叶节点都是黑色的
   • 叶节点并不是我们传统意义上的叶节点，而是代表（外部，NULL，失败），这三个说法是等同的，也就是我们之前判定树计算失败ASL时补上的节点。
   • 与叶节点对应的就是内部节点，就是有具体意义的节点，可以成功的节点。
3. 不红红。不存在相邻的红节点
   • 这是对红节点的限制，但是黑节点无所谓，可以相邻
4. 黑路同。任意节点（不一定只是根节点）到任一叶节点的通路上，路过的黑节点数量相同
   • 这是对黑节点的限制，同理红节点无所谓

一个基本功就是判断红黑树是否符合定义，大致思路如下：

1. 根叶黑。先看根节点和叶节点
2. 不红红。扫一眼看看有没有红节点相邻
3. 黑路同。这个就比较复杂了，你在看一眼黑色聚集的比较多的地方，那些地方极有可能会出现黑色路径过长，黑节点太多的问题
4. 左根右。这个也容易埋坑，你要知道红黑树首先是一颗BST，所以如果出题很阴，会出在这里。

下面这道题很阴，看哪个7，好在这种情况一般是出现在前三条都失效的时候，此时选择题里估计最多剩俩选项，硬着头皮细心对比就行

红黑树性质

性质清单：

1. 黑高定义，h
2. 给定h，内部节点下界
3. 给定h，内部节点上界（红节点上界）
4. 最长路径最多是最短路径的两倍
5. 给定n，设H为总高度（非黑高），则高度上界 H ≤ 2 l o g 2 ( n + 1 ) H≤2log_2(n+1) H≤2log2​(n+1)

前面铺垫一大堆，都是规定，通过这些复杂的规定，可以产生很多有趣的性质，这才是红黑树高效率的开始。

首先从“黑路同”里衍生一个概念：

黑高，即从这个节点开始，走到任意一个叶节点经过的黑节点个数（不包括自己）
根据黑路同逻辑，一个节点的黑高一定是一个具体的值，从一个特定节点开始，无论是从那条路走，黑高都是一致的，因此用统一的值描述。

其实我们更深地考虑一下，黑路同这个特性很好玩，如果不考虑红节点的话，纯黑情况下一定是满二叉树，黑高就是内部节点的层数，因此黑高为h的红黑树，内部节点至少是 2 h − 1 2^h-1 2h−1

而红黑树是什么东西呢？其实就是在一个满二叉黑树之间，尽可能塞入不重复的红节点，那么给定黑高为h，极限情况下，可以塞入 2 h + 1 − 2 2^{h+1}-2 2h+1−2个红节点，

这个的计算如下图，给定h为黑高，算上最顶上的那个×，总共可以塞h+1层红节点，即 2 h + 1 − 1 2^{h+1}-1 2h+1−1个，然后你再去掉顶部×这个不能加的节点，因此就是-2

其次再论两个性质：

1. 根节点到叶节点的极限路径长，最多为两倍关系
   • 最短路径为纯黑
   • 最长路径为从黑（根节点）开始：红-黑-红-黑，实际上路径就是一红一黑，插入尽可能多的红节点，也就是最短路径的两倍
2. 给定内部节点N，则极限高度为2log（N+1），因此查找操作的ASL和AVL一致
   

红黑树的插入

如何构建一颗红黑树？
或者说如何在插入的时候保持红黑特性？
这就是本章研究的问题

插入一个节点操作如下：

1. 根节点染黑，根叶黑
2. 非根节点染红，能够保证黑路同
   • 可能不平衡，1,2条可以保证根叶黑，黑路同，而找节点的过程也满足BST特性，因此唯一可能不满足定义的地方就是红节点连续，而且不平衡只可能在非根节点时候发生
   • 因此不平衡=红节点连续，调整要看叔
   • 叔黑，旋转+染色
     • 首先要找到旋转的极大不平衡根节点，从下面插入的儿往上，上层为父，上上层为爷，爷其实就对应AVL里面极大不平衡树的根节点
     • 对于LL，RR型，父爷换，之后令交换的两个节点反色
     • 对于LR，RL型，把儿换到爷位，之后令交换的两个节点（爷儿）反色，父节点不反色
   • 叔红，反色+判新（不用调整结构）
     • 反色部分为父叔爷，其实就是把上面两层反色
     • 判新，指把爷当做新节点，跳到第1步

下面这个例子是：不平衡+黑叔+LL/RR型，先单旋再反色

下面这个例子是：不平衡+红叔，则反色上两层

然后以爷为新节点，再判断一轮，此时为：根，染黑

当红黑树逐渐变大，你会发现红黑树有一个有趣的特性，就是大部分情况下是不需要调整的（其实AVL和红黑树的最终目标都是平衡，那么AVL其实也差不了太多，关键在于AVL需要去向上找最大不平衡根，而红黑树的爷就是最大不平衡根，寻根效率更高，这才是红黑树碾压AVL的本质）

下图是一种连锁反应，这种连锁反应只可能在不平衡+红叔时发生，因为爷要当做新节点，跳回1，会触发连锁反应。

再来看一个LR的例子：不平衡+黑叔+LR=旋转+反色

1. 先旋转两下
2. 然后进行反色，注意只反爷儿，父不管

红黑树的删除

虽然视频没说，但是我脑子里已经有一个大致的思路了，因为删除的思路和插入其实一样。

首先按照BST删除思路，进行删除
之后必然面对结构破坏的问题，就要进行调整，我们可以利用一个逆向思维，假设自己是在进行插入操作，就当他是插入操作导致的结构破坏，然后我们用插入的思路来调整结构。

而这个思路的关键在于，你要明确儿子节点到底是哪个，又或者干脆就利用红黑树定义去修改颜色和位置

到时候凭感觉就行了，真考出来咱们就大难临头各自飞，我自己也不知道（乐）

B树

B树基础

B数是BST的升级版，仍然保留了顺序性，如下图：

m阶B树，指的是m叉B树，其中有m个链域，m-1个关键字（BST实际上就是1个关键字，2个链域的B树）

要区分关键字和节点，一个节点里面可以有多个关键字，关键字=隔板

如何找一个key呢？

1. 顺序匹配关键词，如果匹配到那就是相等
2. 否则就要去找到两个隔板中间的一个链域，去找孩子
3. 找到了就停，如果最后都没找到，即找到了NULL，就算失败。

每个关键字节点都是有序的，因此可以采用折半查找，我们这里都是用顺序去理解。

为了提高效率，B树强行规定了两个核心特色：

1. 满，至少一半以上的链域
2. 绝对平衡。这个绝对平衡，要求所有子树高度一样，不能有高度差

根据这两点，可以将节点分为四类：

1. 根节点
2. 普通节点，上有老下有小
3. 终端节点，下面只有失败情况，只会出现在倒数第二层
4. 叶子结点，失败，叶子只会出现在最后一层

叶子结点严格来说不是节点，只是臆想出来的，因此实际计算B树高度，是只考虑到终端节点的。

结合下面列出的核心特性，还可以引出一些具体的特色：

1. 子树不可能只有一颗，非0情况下至少为2
   • 因为要绝对平衡，一颗子树是不平衡的
2. 非根节点的子树要求更高，非0情况下至少为m/2向上取整
   • 结合1来看，以m=5举例，根节点要么为0，要么从2开始取，而非根要么0，要么从3开始取
3. n个关键字，至少有n+1个叶子结点
   • n个关键字，本质上是把总区间分割成n+1份，如果落在这n+1份区间内而不是隔板上，就是失败

设n为关键字数量，已知n，计算计算高度h的上下界：

注意，h下界是用的关键字数量计算，而h上界用的是节点数量（通过规则将关键字数量转化成了叶节点数量）

1. 最小高度：尽可能满，n≤关键字最大数量
   • 首先n是指总关键字个数，也就是key的个数（隔板的个数）
   • 每个节点，最多有（m-1）个key，然后右边（1+···+ m h − 1 m^{h-1} mh−1）是总共的节点数 ，化简就是右式
     
2. 最大高度：尽可能分叉少，叶节点个数n+1≥叶子层最少节点数
   • 分叉，根节点为2，非根为k=m/2向上取整
   • 先推第h层最少节点数，第一层1，从2开始，则为 2 k h − 2 2k^{h-2} 2kh−2
   • 因为n个关键字，叶节点为n+1个节点，所以n+1≥
     

B树插入和删除

裂变插入法

我们前面说的BST，都是从上往下插，补在末端，但是B树反其道而行之，插到下面，然后通过裂变的思路裂出父节点，具体如下：

1. 插入只能往终端节点插（刚开始根节点就是终端）
   • 插入的时候，在一个节点内部，是顺序储存，因此插入方法也是顺序插入
   • 可能要进行挪动节点，同时还要挪动链域，所以为了方便整体挪动，B树的关键字和链域是混在一起存的
2. 任何节点，只要满了就裂变，分为左，中，右
   • 左右分别变成两个节点
   • 中关键字上提，如果有父节点就插入父节点（可能要挪动），如果没有父节点，则成为父节点
   • 上提可能会引发连锁裂变反应，从下往上顺着裂就行，当分裂传递到根节点，则高度+1

裂变的思路，可以保证绝对平衡，子树要么是0，要么就至少满足最小值情况(包括根）

流动删除法

删除，可能是非终端，也可能是终端，但是类似于BST的删除，通过顶替的操作，最终都可以转嫁为终端节点的删除

删除终端分为三种情况：

1. 关键字仍然够
2. 关键字不够，但是兄弟够借
3. 关键字不够，兄弟也不够，那就合并

先看2，框住的区域整体是有序的，因此两个兄弟只需要以父节点为中介，整体流动一下就好
注意这个整体流动是包括父节点的，因此那个70其实是从孩子流到父节点里的，而原有父节点的流到亏空的地方（怎么有种连通器的感觉？）

再看3，这次兄弟没有富裕，因此要合并。

同理，合并其实仍然是一种流动，可以理解为把兄弟的关键字全部流到了不够的节点里面（顺带带走一个父节点的关键字），下图中，70这个关键字被冲了下来。

注意，这种还会引发连锁反应，如果最后借得根节点为空，那么就要删去根节点，此时高度-1

B+树

定义和特性

首先给B+树一个定义，同B树，根节点要么是0子树，要么是2颗以上子树，这本质还是绝对平衡。

B+树和B树整体思想一致，多叉，但是细节差距很大，因为根本目标是不一样的

1. B树是m个链域，m-1个关键字，也就是说关键字起到隔板作用，是要直接去匹配关键字的
   • B树全体都是用来储存key的，叶节点=失败
2. 但是B+树，关键字=链域数量，起到的是类似于分块查找的作用，不会去直接匹配关键字
   • B+树分为两大部分，底部每个叶节点里面有n条记录，上面的所有部分是多级索引
   • B+树其实是加强版的索引顺序储存，而且B+树的顺序部分一定是有序的（索引顺序里是无序的）

解释一下B+树的特性：

1. 子树数量规则略有不同
   • 叶子根节点可以是1个子树
   • 非叶根节点0/2起
   • 非根节点仍然是0/k起
2. B+树实际是加强版索引顺序储存
   • 关键字=链域，为链域内关键字上界（包含）
   • 叶节点内部顺序，且链域指向关键字对应的数据域
   • 叶节点一层整体是可以顺序查找的

B+树查找

来看一下B+树的查找：

首先是类似于索引顺序查找的方式，从左往右（折半太麻烦不讲）扫，不断地递进索引，最后找到叶节点层：

1. 有数据，成功
2. 无数据，失败

无论如何，都到叶节点。

另一种思路是顺序查找，就是直接到叶节点层从头开始找

B+树对比B树

这一部分是对上面的整体总结，考试也爱考这些

1. 两个树的本质不同，B+是索引储存，B是全体储存，因此会有大量的延伸特性
   • 链域和关键字对应不同，B+：m——m，B：m——m-1
   • 数据项内容不同：B+索引中出现的数必然在叶节点中出现，而且叶节点本身还会储存一个指向数据记录的指针，而B出现过的不会再重复，B的节点本身就存着key和数据记录
   • 查找过程不同：B+树一定会查到最后一层，而B树匹配到就停
2. 关键字数量不同
   • B+：为链域下界，即1，k
   • B：为链域下界-1，即1，k-1
   • 注意到，B树链域下界是2，但是B+树链域下界可以是1，这种情况比较特殊，只有叶子根节点才允许，其他情况下界为2/k

与OS的联系

B+树用于磁盘和数据库的储存，MySQL的索引功能就是用B+树实现的

如下图，每个B+树节点都存在一个磁盘块中，下面的3层B+树，每次访问一个数据块实际上要经过4次：

1. 读两次索引
2. 读一次指针
3. 根据指针读数据

之所以要采用索引+指针的方式，是因为要尽可能精简B+树，但是一个磁盘块（对应一个节点）的大小是固定的，因此无论是索引还是叶子结点，里面的关键字都要尽可能多，这才能降低树高，进而减少读磁盘次数，因此要尽可能减小数据项的大小，最后就演变成只储存关键字了（叶节点还有指针）

而B树不适合储存磁盘，因为数据记录+key的空间比较大，一个磁盘块存不了几个key

散列查找