查找

从数据集合中寻找某个数据元素的过程称为查找。查找结果分为:

• 成功: 找到符合的元素
• 失败: 数据集合不存在指定元素

查找的相关概念

• 查找表与静态查找表: 用于查找的集合，通常的操作有插查询与增删，支持增删元素的查找表称为动态查找表，只支持查询元素的查找表称为静态查找表
• 关键字: 用以唯一对应元素的某个数据项的值
• 平均查找长度: 一次查找的长度指中的比较关键字的次数，平均查找长度为对于当前的查找表的查找长度期望

$$\text{ASL} = \sum_{i=1}^n P_iC_i$$

查找方式

顺序查找

顺序查找是对于线性表的查找，可对于关键字有序与无序的线性表进行查找。

一般顺序表的查找

一般顺序表的查找即遍历整个线性表的查找方式。在查找中，逆序查找目标元素，同时人为设定表头为目标元素作为"哨兵"避免越界判断，

struct SSTable{
    ElemType *elem;
    int Len;
}

int Search_seq(SSTable ST,ElemType key){
    int i;
    ST.elem[0] = key;
    for i = ST.Len; ST.elem[i] != key ; i--);
    return i;
}

使用一般顺序表的查找方式的查找成功的平均查找长度为

$$\text{ASL}_\text{成功} = \sum_{i=1}^n (n-i+1)P_i$$

当查找每一个元素为等概率事件时

$$\text{ASL}_\text{成功} = \sum_{i=1}^n \frac{n-i+1}{n} = \frac{n+1}{2}$$

查找失败的平均查找长度为

$$\text{ASL}_\text{失败} = \sum_{i=1}^n (n+1)P_i =n+1$$

时间复杂度显然为$\mathcal{O}(n)$

有序顺序表的查找

有序顺序表相比一般顺序表的遍历方式，可以通过有序条件判断进行二叉决策，可以在查找中就判断出查找失败而不是遍历完全表才查找失败，从而降低失败的平均查找长度。

struct STable {
    ElemType *elem;
    int Len;
};

int Search_seq_for(STable ST, ElemType key) {
    for (int i = 0; i < ST.Len; i++) {
        if (ST.elem[i] == key) {
            return i;
        }
        if (ST.elem[i] > key) {
            return -1; 
        }
    }
    return -1; 
}

我们可以将表元素的间的失败区间视为一个新的“黑“表，因此搜索失败相当于对”黑“表的搜索成功，同时，黑表的最后两项的搜索长度都为n。对于有序线性表的查找失败的平均查找长度为

$$\text{ASL}_\text{失败} = \sum_{i=1}^n (l_i-1)P_i = \frac{1+\cdots+n+n}{n+1} = \frac{n}{2}+\frac{n}{n+1}$$

二分查找

二分查找只适用于关键字有序的顺序表(原理上对于双向链表也适用，但是因为链表遍历的时间开销，整体时间复杂度不会被优化)

int Binary_Search(STable ST, ElemType key){
    int low = 0;
    int high = ST.Len - 1; 
    int mid;
    while(low <= high){
        mid = (low + high) / 2;
        if (ST.elem[mid] == key){
            return mid;
        }
        else if (ST.elem[mid] > key){
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return -1;
}

对于静态的有序顺序表，执行二分查找的过程等价于在一棵平衡的二叉排序树上进行搜索；
对于无序的数据集合，如果想要在不移动大量元素的前提下获得对数级别 $\mathcal{O}(\log n)$ 的查找效率，不能直接使用二分查找，而必须在物理结构上将其构建为一棵平衡二叉排序树。

二分查找的比较次数不超过判定树高度。在等概率查找的条件下满足

$$2^{h-1} - 1 < n \leq 2^{h} - 1$$

$$h = \left \lceil \log_2(n+1) \right \rceil$$

设二叉平衡树的每一层元素个数为$a_h$,则查找成功的平均查找长度为

$$\text{ASL}_\text{成功}= \frac{1}{n}\sum_{i=1}^n l_i = \sum_{j=1}^h\frac{j\times a_j}{n} \overset{\text{满二叉树}}{\simeq} \frac{n+1}{n}\log_2(n+1) -1 \simeq \log_2(n+1)-1$$

查找失败的平均查找长度为

$$\text{ASL}_\text{失败}= \frac{(2a_{h-1}-a_h)(h-1)+2a_{h}h}{n+1}$$

查找失败也只有两种可能性，树的高度与树的高度-1，因此关键词比较次数最多等于树的高度

$$h = \lceil \log_2(n+1)\rceil$$

分块查找

分块查找是将整个大的顺序表分为若干个小块，小块内部可以没有顺序，小块之间有顺序。基于最大关键字与块起始地址建立块间索引。进行分块查找首先查找在哪一个块中，再对子块进行顺序表查找。

分块查找的平均查找长度等于块间索引查找长度与块内查找的长度和

$$\text{ASL} = L_I+L_S$$

如果将分块等分为$b$块,每一块包含$s$个元素，每一个元素被查找遵循等可能原则，则平均查找长度为

$$\text{ASL} = \frac{b+1}{2}+\frac{s+1}{2} = \frac{s^2+2s+n}{2s} = \frac{s}{2} +\frac{n}{2s}+1\geq \sqrt{n}+1$$

当 $s = \sqrt{n}$ 时 $\text{ASL}$取最小

树形查找

二叉排序树(BST)

构建二叉排列树的目的是作为动态查找表，利用其有序结构更加高效的进行动态查找、增删。

二叉排序树的构建满足如下原则：

• 若左子树非空，则左子树的所有结点的关键字均小于左子树根结点
• 若右子树非空，则右子树的所有结点的关键字均大于右子树根结点
• 左右子树也是二叉排序树

二叉排序树中序遍历可以得到一个递增的有序关键字序列。

对于n个结点的有序表构建二叉排序树，二叉排序树的可能数目为Catalan数

$$C_n = \frac{\binom{2n}{n}}{n+1}$$

二叉排序树的查找

二叉排序树的拓扑结构和二分查找的判定树是相似的。二叉排序树的查找是从根结点出发，逐层向下比较并选择左/右子树的过程。当二叉排序树的结构是几乎平衡时，二叉排序树的查找的时间复杂度为 $\mathcal{O}(\log n)$, 当二叉排序树的结构几乎为一条没有分支的树时， 时间复杂度为 $\mathcal{O}(n)$.

二叉排序树的构建

对于一个选定的结点，将比它小的添加在它的左孩子结点，比它大的添加在它的右孩子结点。

平衡二叉树(AVL树)

AVL树是二叉排序树平衡化的结果，它要求任意结点的左右子树高度差绝对值不小于1。

定义结点的左子树与右子树的高度差为平衡因子，平衡二叉树的平衡因子只能是 $\pm 1, 0$

平衡二叉树的旋转

基本旋转为向右旋转与向左旋转两种

LL 平衡旋转

左子树更深的时候，将左子树根结点提升到整树根结点，将原树根结点向右下降为右子树根结点

RR 平衡旋转

右子树更深的时候，将右子树根结点提升到整树根结点，将原树根结点向左下降为左子树根结点

基于这两种旋转的复合，有:

LR平衡旋转

将左子树的右子树的根结点，先向左旋转再向右旋转提升为整树根结点

RL平衡旋转

将右子树的左子树的根结点，先向右旋转再向左旋转提升为整树根结点

平衡二叉树的删除

平衡二叉树的删除和增加的旋转类似，都遵循“哪边子树深度更浅，向哪边旋转的原则”，旋转到平衡为止。

红黑树

AVL树的每一次增删几乎都需要进行平衡性校验与旋转以改变整体拓扑结构，代价较大。红黑树在AVL树的基础上放宽了条件要求。

红黑树满足如下性质:

• 红黑树是二叉排序树
• 红黑树的每一个结点都是红色/黑色的
• 红黑树的根结点是黑色的
• 叶结点(虚构外结点/NULL结点)都是黑色的
• 红结点的父结点与子结点都是黑色的，不存在相邻的红结点
• 每一个结点到任意叶结点的路径的简单路径的黑色结点数量相等。由此性质，定义这样的(不含该结点的)简单路径的黑结点总数为黑高，根结点的黑高称为红黑树的黑高

红黑树的一个黑结点的子结点既可以是红结点，也可以是黑结点，在同一黑结点也可以存在红/黑两个不同色的子结点。且只需要满足左右子树的黑高相等就能构成红黑树。

红黑树的最大深度差为 $bh$

全黑子树的深度为$bh$, 红黑交替的子树的深度最大为$2bh$,因此最大深度差为$2bh-bh = bh$。

而AVL树的最大深度差仅为$1$， 红结点的引入极大松弛了整体拓扑结构。

Corollary: 有$n$个内部结点的红黑树的高度

$$h\leq 2\log_2(n+1)$$

一个简单路径至少一半为黑结点

$$bh\geq \frac{h}{2}$$

因此

$$n\geq 2^{\frac{h}{2}}-1$$

即

$$h\leq 2\log_2(n+1)$$

红黑树的插入

红黑树的插入元素初始化必须为红色结点, 否则插入后必然破坏红黑树的黑高平衡，只会在插入后，其父结点与子结点均为红结点时出现问题，需要进红黑树的旋转。

当插入结点的父结点为红且叔结点为黑时:

LR旋转

与AVL树的LR旋转类似，当左子树的根结点与其右孩子都为红色时，将该右孩子旋转为上一级树的根结点并染黑，将原上一级树的根结点向右旋转并染为红, 保证了左右子树的黑高平衡。

LL旋转

当左子树的根结点与其左孩子都为红色时，旋转该根结点至上一级树的根结点，并染黑，原上一级树的根结点向右旋转并染为红。

当叔结点为红时: 将父结点与叔叔结点都染黑，将祖父结点染红，这样就保证了整体的黑高不变。如果祖父结点为根结点，则先染红再染回默认黑色，因为整体根结点的颜色不会影响黑高平衡。

红黑树的删除

红黑树的优势

红黑树相比AVL树，在大量增删的场景下对于全局拓扑结构的改变次数少， 因此适合大量增删的场景；如果查找操作远多于增删操作，则AVL树更优。

B树

B树是面向大数据量的数据结构，其类似于分块查找，但是分层更深。

B树的每一个结点组成包含指向下一层结点的指针域与关键字域，其中关键字域和指针域是交替的, 因此指针域总比关键字域多1个

一棵$m$ 阶B树满足如下条件:

• $m$ 叉树
• 每个结点至多有$m$ 棵子树，即至多包含$m-1$ 个关键字。
• 根结点最少包含 $2$ 棵子树，最少包含 $1$ 个关键字
• 除了根结点外，所有非叶结点至少有 $\lceil \frac{n}{2}\rceil$ 棵子树，至少包含 $\lceil \frac{n}{2}\rceil -1$ 个关键字 -- 否则，再减少一个元素后，它与它的子树将“崩塌”为一个结点。
• 叶结点出现在同一层，对应指针为NULL，表示查找失败，因此叶 结点只有 $n+1$ ge

B树的高度

B树的拓扑结构相当多样，在每一个结点都可以拓展多一半的空间。它的两个极限情况分别为:

• 每一个结点全部填满为 $m-1$ 个关键字
• 每一个结点只填充 $\lceil \frac{n}{2}\rceil -1$ 个关键字

情况1

$$n \leq (m-1)(1+m+\cdots+m^{h-1}) = m^h-1$$

即

$$h_\text{min}=\log_m(n+1)$$

情况2

由于外部结点总只有$n+1$个，

$$n+1 \geq 2\left(\frac{m}{2}\right)^{h-1}$$

即

$$h_\text{max} = \log_{\lceil \frac{m}{2}\rceil}(\frac{n+1}{2}) +1$$

特殊情况: 对于3阶B树的情况2，每一个结点内的关键字个数为$\lceil \frac{3}{2}\rceil -1 = 1$,相当于一个满二叉树.

B树的构建与插入

B树在大部分时刻插入时，结点都是未填满的状态(即 $\lceil\frac{m}{2} \rceil -1\leq i<m-1$), 此时直接添加不会改变B树的拓扑结构。

当添加时结点处于填满状态($n = m-1$)时，再插入一个元素会导致结点的分裂。将中间的关键字提升到父结点，整个结点的左侧和右侧分裂为两个结点，指向这两个结点的指针在父结点的数据域中排列在提升的关键字的左边与右边。如果父结点仍然满，就将父结点

B树的构建遵循自底而上的原则。先填充满$n = m-1$个关键字的结点，再插入新关键字导致结点分裂，依此规则填满整个B树

B树的删除

删除关键字同样需要保证删除后结点内关键字不少于 $\lceil \frac{m}{2}\rceil-1$, 否则触发结点的借位或合并。

如果删除的关键字属于非终端结点，删除后，相邻子结点的最靠近该关键字的关键字提升到父结点。

如果删除的关键字属于终端结点，则有三种情况:

• 如果删除该关键字后，结点内关键字数量仍然大于 $\lceil \frac{m}{2}\rceil-1$, 则直接删除关键字
• 如果删除结点关键字量为 $\lceil \frac{m}{2}\rceil -1$, 且兄弟结点的关键字数量大于 $\lceil \frac{m}{2}\rceil$, 则将父结点的相邻关键字下降到被删除的关键字的位置，同时将相邻结点的关键字补回原来父结点关键字的位置。
• 如果删除结点关键字量为 $\lceil \frac{m}{2}\rceil -1$, 但是兄弟结点的关键字数量都为 $\lceil \frac{m}{2}\rceil -1$， 删除该关键字后，将两个兄弟结点以父结点中间的关键字合并为一个结点。

B+树

B+树的所有关键字都存储在叶结点中，相邻叶结点间存在指针相连，每一个结点的子树个数等于其关键字个数，关键字作为子结点的索引存在于子结点中。

B+树的遍历查找方式:

• 叶结点顺序遍历
• 根结点出发的类分块查找

第二种查找方式遇到了目标关键字后不会终止，而是需要访问到叶结点才终止查找。

Hash表

Hash函数将关键字映射以某种方式映射到存储地址，记为

$$\text{Hash}(\text{key}) = \text{Addr}$$

Hash 函数通常将