数据结构与算法复习（7）查找

发表于 2022-08-15 分类于 Algorithm ， 408

前言

前面几章基本介绍完主要的数据结构，本章着重查找算法，以及一些排序算法用到的数据结构，在前面的基础上延伸。重点是顺序、折半、分块查找，二叉排序、二叉平衡树，红黑树，B树，B+树，散列表。

查找基本概念

查找：在数据集合中寻找某种满足条件的元素的过程；
查找表（查找结构）：用于查找的数据集合，一般有四种操作，1）查询特定元素；2）检索特定元素属性；3）插入数据；4）删除数据；
静态查找表：没有插入删除操作的查找表；
动态查找表：需要动态插入删除操作的查找表；
关键字：数据元素中唯一标识元素的某个数据项的值；
平均查找长度(Average Search Length)：所有查找过程中进行关键字的比较次数的平均值；

顺序和折半查找

顺序查找O(n)

又称线性查找，遍历每个元素进行查找。下面分为对一般无序线性表的查找和对关键字有序的线性表查找。

一般无序

从线性表的一端开始，逐个检查关键字是否满足条件；如果查找到表的另一端还没有找到，那么查找失败。

typedef struct{
    ElemType *elem;//下标0的元素留空
    int TableLen;
}SSTable;

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

需要说明的是，为了防止查找时数组越界，将查找表的0号下标元素留空，用来存放要查找的关键字值，并从后往前遍历查找表，这样当查找到0号元素时循环就会结束，此时i的值为0，表示查找失败。这里的ST.elem[0]被称为“哨兵”，很多时候可以避免不必要的判断语句，提高效率。

笔者个人认为这里做适当处理即可，不一定采取这样的措施，因为查找表的长度已知，可以添加判断条件。不过采用“哨兵”的方法确实能避免添加的判断条件。

所有元素查找成功概率相等，要查找的元素为第i个时，平均查找长度为：

其中p值为1/n。

查找失败时，平均查找长度为：

有序表查找

假设有一个线性表的关键字从小到大排列，查找顺序从前往后，关键字值为key，只要当key的值介于两个元素关键字值之间，就可以判定查找失败。用下图理解查找过程：

圆形内的是查找表的数据元素，矩形内是查找失败结点（n个结点对应n+1个失败结点），如果要匹配的关键字在任何一个矩形范围内，就说明匹配失败。

查找成功时平均查找长度：

查找失败平均查找长度：

q是到第j个失败结点的概率，相等情况下为1/n+1；l是第j个失败结点所在的层数（注意这里的层数从2开始，在某层失败就要查找层数-1次；第7层有两个失败结点，因为最后一层只要不相等都查找失败），注意理解。

折半查找$O(log_2(n))$

又称二分查找，用于查找有序线性表。基本思想是，将关键字key与中间元素关键字比较，相等则查找成功；不相等根据大小关系决定在中间值的左半边还是右半边比较，重复步骤直到查找成功或没有元素可以查找。

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

折半查找过程可以用判定树描述：

可以看出这是一棵平衡二叉树。查找成功的ASL就等于目标结点的层数；查找失败的ASL就等于目标失败结点的层数-1。

查找成功平均查找长度：

其中h是树的高度，n是结点数。1/n表示概率相等。就是结点的层数乘以该层结点数的和，然后乘以概率。

查找失败平均查找长度：
暂时没有公式，其实也是失败结点层数乘以该层失败结点数的和，然后乘以概率。

折半查找需要线性表能够随机存取且关键字有序，因此不适合链式存储。

分块查找

又称索引顺序查找，基本思想是将查找表分为若干块，块内元素无序，块有序，建立一个索引表，每个元素包括块的最大关键字和块第一个元素的地址，然后按照关键字排列这个索引表。

查找时，先通过顺序或折半查找索引表，得到目标块，然后在块内顺序查找。

分块查找的平均查找长度为索引查找和块内查找之和，如果都采用顺序查找O(n)：

长度为n的线性表被分为b块，每块有s个记录。如果索引表采用折半查找$O(log_2(n))$：

树型查找

二叉排序树BST$O(log_2(n))-O(n)$

定义

左子树上所有结点的值均小于根结点；右子树上所有结点的值均大于根结点；左右子树各是一棵二叉排序树。（可以是空树）

查找

从根结点开始，如果小于根结点关键字，在左子树上查找；否则在右子树上查找，直到查找成功或查找了所有结点。

//非递归算法
BSTNode *BST_Search(BiTree T, ElemType key)
{
    while(T != NULL && key != T->data)
    {
        if(key < T->data)
            T = T->lchild;
        else
            T = T->rchild;
    }
    return T;
}
//递归算法
BSTNode *BST_Search(BiTree T, ElemType key)
{
    if(T == NULL)
        return false;
    
    if(key == T->data)
        return T;
    else if (key < T->data)
        return BST_Search(T->lchild, key);
    else
        return BST_Search(T->rchild, key);
}

插入

如果树空，直接插入结点；非空，关键字k小于根结点，插入到左子树；否则插入到右子树。插入的结点一定是叶子结点。

int BST_Insert(BiTree &T, KeyType k)
{
    if(T == NULL)
    {
        T = (BiTree)malloc(sizeof(BSTNode));
        T->data = k;
        T->lchild = T->rchild = NULL;
        return 1;
    }
    else if(T->data == k)
    {
        return 0;//不能有相同值存在
    }
    else if(T ->data > k)
    {
        return BST_Insert(T->lchild, k);
    }
    else
        return BST_Insert(T->rchild, k);
}

构造

给定一个数组，用其中的元素构成一个二叉排序树。

void Create_BST(BiTree &T, KeyType str[], int n)
{
    T = NULL;
    int i = 0;
    while(i < n)
    {
        BST(Insert(T, str[i]));
        i++;
    }
}

删除

如果删除的结点不会破坏排序二叉树性质，则直接删除；如果删除的结点只有一棵左子树或右子树，则让子树根结点代替删除结点；如果有两棵子树，让结点中序遍历（BST的中序遍历是一个升序数组）的直接后继（或前驱）替代结点，然后直接删除这个重复的直接后继（或前驱），这是因为直接后继（或前驱）一定是前面两种情况之一。

或者说用目标右子树中的最小值代替。

（图中是用后继代替的情况)

平均查找长度

取决于树的形状，如果是平衡二叉树（左右子树高度相差最大为1），平均查找长度为O(log(n))，如果是倾斜的单支树，就和一般线性查找表没有区别，平均查找长度为O(n)。这取决于输入的元素序列。

当有序表是静态，选择顺序表进行存储并采用折半查找；当有序表是动态，选择BST作为逻辑结构。

平衡二叉树$O(log_2(n))$

定义

任意结点的左右子树高度相差不超过1，简称平衡树。左右子树的高度差为结点的平衡因子。平衡二叉树可以为空。

平衡二叉树就是左右子树都是平衡二叉树，且左右子树平衡因子的绝对值不超过1。

插入

每次插入结点时，检查是否导致不平衡，如果导致不平衡，找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，调整以A结点为根的子树（最小不平衡子树），在保证二叉排序树的前提下调整子树结点位置关系。

位置调整可以归纳成四种操作：

LL：在左孩子的左子树上插入新结点，断开A与左孩子B的连接，将B的右子树作为A的左子树，A作为B的右子树。右旋转。
RR：在右孩子的右子树上插入新结点，断开A与右孩子B的连接，将B的左子树作为A的右孩子，A作为B的左子树。左旋转。
LR：在左孩子的右子树上插入新结点，先对A的左孩子B进行左旋转；然后再对C进行右旋转；
RL：在右孩子的左子树上插入新结点，先对A的右孩子B进行右旋转；然后再对C进行左旋转；

删除

找到要删除的结点，向上回溯同样找到最小不平衡子树，设根结点为z，y是z两个孩子结点中高度最高的结点，x是结点y两个孩子结点中高度最高的结点。

根据不平衡节点w和最高高度儿子y，最高高度孙子x的关系，可以分为四种类型：

（对x进行操作)
与插入不同的是，插入的调整只需要进行依一次，但是删除后检查原父结点是否失衡，调整后还要进一步回溯到父结点的父结点重新检查调整。

查找

和排序二叉树相同，平均查找长度O(log(n))。

n个结点的平衡二叉树最大深度为O(log(n))。

红黑树

由于AVL要频繁调整拓扑结构，所以引入红黑树，定义为满足一定红黑性质的二叉排序树：每个结点分为红色和黑色。其中根结点和叶结点是黑色，而且不会存在两个相邻的红色结点（红色结点的双亲和孩子都是黑色）；对每个结点，从该结点到任意叶结点的简单路径上，所含黑色结点的数量相同。

从任意结点出发，到一个叶结点的任一简单路径上黑结点的总数称为该结点的黑高；根结点的黑高就是红黑树的黑高。

从根结点到叶结点的最长路径不大于最短路径的两倍。当根到叶子的路径最短，必然都由黑结点构成；路径最长，路径必然由红黑结点相间构成，红黑结点数量相同。
有n个内部结点的红黑树高度h<=2log(n+1)。因为由上一条结论，从根到叶子结点至少有一半是黑结点，所以树的黑高至少为h/2，考虑结点最少的情况，就是结点全黑，那么高度就是黑高，所以结点数n>=2^(h/2)-1（二叉树定理）。

红黑树放宽了平衡的定义，只要求任意结点的左右子树高度差不超过两倍，从而降低调整频率。

插入

按照排序二叉树的方式插入后，进行调整。

新插入的结点，初始着色为红色，防止破坏黑高相等的性质。

如果新结点的双亲是黑色的，无需调整。
如果新结点是作为根结点插入，将z调整为黑色。
如果新结点的双亲是红色的，分三种情况：1）(LRB)新结点z是右孩子，z的叔结点（双亲的兄弟结点）y是黑色的，对z先左旋，再右旋；2）(LLB)新结点z是左孩子，z的叔结点（双亲的兄弟结点）y是黑色的，对z的双亲结点右旋，交换z原双亲结点和爷结点的颜色；

上面说的都是z的双亲为爷结点左孩子的情况，如果z的双亲是爷结点的右孩子，那么就是对称的情况：先右旋再左旋(RLB)和左单旋(RRB)。

3）z的叔结点是红色。爷结点着色为红色，双亲和叔结点着色为黑色，然后将爷结点作为新的z来重复，也就是上移了两层。(LRR, LLR)

如果双亲结点是右孩子，同样还有两种对称情况。

删除

按照二叉排序树的方法进行删除，设替代删除结点的是x，其兄弟结点为w，下面是在已经删除好的结点上做调整的过程。

如果待删除结点有两个孩子，不管是红色还是黑色，那么需要替换后（颜色也要替换）删除替换结点，该结点要么是叶子结点，要么只有一个孩子；如果待删除结点只有一个孩子，直接删除后用它的孩子替换（颜色变为和删除结点一致）。

如果待删除结点没有孩子，需要分颜色讨论；

如果待删除结点是红色，可以直接删除；

如果待删除结点是黑色，那么设待删除结点为y，x是用来替代它的结点，w是x的兄弟结点。进行删除后，为了保证所有路径上黑色结点数量相同，先将x着色为双重的黑色，问题就转化成将x变成正常结点。下面有四种情况。

w是红色的。由于红黑树的性质，w的双亲和孩子一定是红色的，所以交换w和双亲结点的颜色，并对w做左旋，转换为其他情况；

w是黑色，且w的左孩子是红色，右孩子是黑色。交换w和左孩子的颜色，对w的左孩子做右旋，作为新的w，转换为下一种情况；

w是黑色的，w的右孩子是红色的。交换w和父结点的颜色，w的右孩子变为黑色，对w做左旋，并将x着色为单重黑色。

w是黑色，且w两个孩子都是黑色。将x和w都去掉一层黑色，x由双重黑色变为黑色，w由黑色变为白色，在他们的双亲结点上加上一层黑色，并将这个双亲结点作为新的x循环；而且如果这个双亲结点是红色（情况一转化后变为这种情况），着一层黑色就变为黑色即可，终止循环。

以上仍然是x作为左孩子的情况，作为右孩子时也有对称的四种情况

上面框中的四种情况，只有情况四可能一直重复最多log(n)次（每次上升一层），前面三种情况最多三次旋转后就会停止。因为情况四是唯一能够将任务推给双亲结点的情况，其他三种情况因为w或者w的孩子中有红色，只能在以双亲为根的子树中调整。

B树

多路平衡查找树，定义为满足如下特性的m叉树：

每个结点至多有m棵子树，至多有m-1个关键字；
如果根结点不是终端结点，至少有两棵子树；
除根结点外的所有非叶子结点，至少有m/2取上界的子树，至少有m/2取上界-1的关键字；
非叶子结点的结构如下：

其中k是结点的关键字，按升序排列；p为指向子树根结点的指针，p[i-1]指向子树的关键字均小于k[i]；n是结点中关键字的个数。
所有叶子结点在同一层次上，而且不带信息；

B树是所有结点平衡因子都是0的多路平衡查找树。

上面的五阶B树有以下性质：

结点孩子数等于关键字数+1；
根结点没有关键字，树空；有关键字，子树必定大于等于两棵；
除根结点外的非终端结点，至少有5(m)/2向上取整=3棵子树，至多有五棵子树；
所有叶子结点都在第四层，代表查找失败结点。（虚构不存在）

B树高度

B树高度不包括叶子结点一层。设一棵B树包含n个关键字，高度为h，阶数为m：

每个结点最多有m棵子树，m-1个关键字，所以关键字个数n应该满足上界：
让每个结点的关键字数最少，可以找到关键字个数n的下界，第一层至少一个结点，第二次至少两个结点，除根结点外的每个非终端结点至少有m/2取上界棵子树，所以第三层至少2*(m/2)取上界个结点，第h+1层（叶子结点层）至少有结点数：

又因为查找不成功结点（叶子结点数）等于n+1，所以有：

得到h的上界。

查找

与二叉查找树类似，只是子树有多路分支。B树存储在硬盘中，先找到目标结点读取到内存，然后在结点内使用顺序查找或者折半查找内存中的有序表，如果没找到，则去对应指针信息指向的子树中查找，直到找到失败结点。

插入

1）定位，用前面查找的办法，会找到待插入结点对应的叶子结点（失败结点）和其对应的上一层，最底层非叶子结点；
2）插入，检查待插入结点的关键字个数，如果插入后关键字个数大于m-1，需要进行分裂；否则可以直接插入；
3）分裂，取一个新的结点，在插入关键字的后的原结点，从中间m/2取上界位置，分为两部分，左边部分放在原结点中，右边包含新关键字的部分放到新结点中，m/2取上界位置的结点插入原结点的父亲结点上，多出来的指针指向新结点作为原结点的兄弟存在；如果插入父亲结点又使得父亲结点关键字个数超过上限，则对父亲结点进行相同的分裂操作；

删除

与插入操作类似，不过要使得删除后的结点关键字个数大于下界，要采用合并操作。

如果被删除关键字k不在终端结点（最底层非叶子结点），用k的前驱k’替代k，然后删除k’，因为k’一定在某个终端结点中，所以就转化成了删除k在终端结点中的情况；

如果被删除关键字k在终端结点中，分三种情况：

如果k所在结点关键字个数删除后仍然满足，可以直接删除；
如果k所在结点关键字个数删除后不满足，但兄弟结点的的关键字个数足够，那么将父亲结点中相邻大小的关键字和兄弟结点相邻大小的关键字进行替换，父亲结点替换下来的关键字送给删除后不足够的结点；
如果k所在结点关键字个数删除后不满足，而且兄弟结点也能借走，就将关键字删除后与相邻兄弟结点以及双亲结点的关键字进行合并，让双亲结点的关键字移动到下层，和删除后剩下的关键字，以及兄弟结点的关键字，组成满足定义的新的结点。如果双亲结点是根结点，关键字个数合并后减1，变成0，直接删除，让合并后的新结点替代根结点的位置；如果双亲结点不是根结点，关键字个数又减少到不满足定义，就重复上面的合并操作，直到满足定义；

B+树

B+树的要求比较低，掌握原理即可。B+树是一种B树的变形，满足以下条件：

由于B+树一个指针头指向关键字有序序列，可以用顺序查找（链表不方便用折半查找）；另一个指针头指向根结点，可以使用多路查找（类似B树）。B+树的插入删除也类似B树，但是在非叶子结点中找到记录时，还要继续下降到叶子结点中，所以每次查找都是一条从树根到叶子的路径。

对比B树，B+树的优点是：

层级更少，查询快速；
非叶子节点仅做索引，关键字全部在叶子节点中，使得查询速度稳定；
叶子节点顺序保存了所有关键字，方便查询，数据紧密性高；
遍历全部数据只需要遍历叶子节点，有利于数据库全盘扫描。

散列表

基本概念

散列函数，把查找表中的关键字映射成该关键字对应的地址的函数，记为Hash(key)=Addr；
当散列函数把不同关键字映射到同一个地址，就是发生了冲突。

散列表，根据关键字直接进行访问的数据结构，建立关键字和存储地址之间的一种直接映射关系；理想情况下散列表查找任何元素都是随机存取，即常数级时间复杂度。

散列函数的构造

散列函数的构造遵循几个规则：

散列函数的定义域要包括全部关键字，值域取决于散列表大小；
散列函数计算的地址应该尽可能均匀分布在空间中，减少冲突；
散列函数应该尽量设计地简单计算；

直接定址法

直接取关键字的某个线性函数值为地址，散列函数形式为：

适合关键字分布基本连续的情况，如果不连续会造成空间浪费。适合查找表较小且连续的情况。

除留余数法

散列表表长m，取一个不大于m但接近m的质数p，防止因为关键字可能得到相同的地址从而造成冲突。通过取模运算得到地址：

数字分析法

设关键字是r进制，r个数码在各位上出现的频率不一定相同，选择其中的r个数字作为地址，关键字改变，要重新构造。适合处理知道关键字分布，且关键字位数比较大的情况。

平方取中法

取关键字平方的中间某几位作为散列地址，视情况而定。适合于不知道关键字的分布，而位数又不是很大的情况。

冲突处理

发生冲突时，应该考虑为冲突的关键字寻找到一个空的地址，用Hi表示处理冲突中第i次探测得到的散列地址，每次冲突就让i+1，寻找下一个不冲突的地址。

开放寻址法

增量序列有四种取法：
1）线性探测法，d从0开始依次+1，冲突发生的时候顺序查看表中下一个地址单元，当探测到表尾地址m-1，下一个地址单元是0，直到找到一个空闲的地址。这样可能使得关键字聚集在某个地方，降低查找效率。

2）平方探测法，d取值如下：

其中k<=m/2，有定理表明，散列表长度m能表示成4k+3的素数时，可以探测到所有单元。这样可以避免堆积的问题，但是如果不满足定理条件，则不能探测到所有散列表上的单元。

3）双散列法，使用两个散列函数，第一个函数得到的地址冲突，再利用第二个函数计算地址增量。最多经过m-1次就会遍历整个表。

4）伪随机序列法，d取值伪随机序列。

拉链法

把所有冲突的关键字存储到一个线性链表中，链表由散列地址唯一标识。

适用于经常插入和删除表的情况。

散列查找

查找方式就是根据关键字和函数映射，计算出散列地址Addr。
访问Addr，检查是否有记录，没有记录则查找失败；有记录则比较关键字是否相等，相等时查找成功，不相等可能是发生冲突被移动了，转到下一步。

用给定的冲突处理方法找到下一个散列地址，转入上一步。

平均查找长度

比较次数就是平均查找长度，不同的冲突处理方法得到的散列表不同，平均查找长度也不同。
以下面12个元素，线性探测和模13构造的散列表为例：

查找84的过程为先计算散列地址84%13=6，查找地址6存储的元素19不等于84，找下一个线性探测的位置，m=16，(6+1)%16=7，7存储的元素20不等于84，找到下一个位置(6+2)%16=8，相等，查找成功，总共进行了3次比较。

采用上面这样的方式得到下面各个关键字的比较次数：

总共12个关键字，设查找每个关键字概率相等，统计所有比较此时并乘以访问概率：

散列表总结

1）虽然存储位置和关键字能之间映射，但是仍然要通过比较的方式解决冲突问题，所以要以ASL为准；
2）散列表的查找效率取决于散列函数、处理冲突方法和装填因子。其中装填因子α=元素数n/散列表长度m。而散列表的ASL依赖于α，不直接依赖于n或m，α越大，越容易发生冲突，反之越不容易冲突。