《数据结构》第七章 查找

7.1 查找的基本概念

• 查找：在数据集合中寻找满⾜某种条件的数据元素的过程。
• 查找表（查找结构）：⽤于查找的数据集合称为查找表，它由同⼀类型的数据元素（或记录）组成。
• 静态查找表：一个查找表只涉及查找操作，无须动态地修改查找表，则此类表为静态查找表。
• 关键字：数据元素中唯⼀标识该元素的某个数据项的值，使⽤基于关键字的查找，查找结果应该是唯⼀的。
• 查找长度：在查找运算中，需要对⽐关键字的次数。

• 平均查找长度（ASL）：所有查找过程中进⾏关键字的⽐较次数的平均值。

  $$ ASL=\sum_{i=1}^{n}P_i C_i $$

  其中，$P_i$ 是查找第 i 个元素的概率，$C_i$ 是找到第 i 个元素所需的比较次数。

7.2 顺序查找和折半查找

7.2.1 顺序查找

顺序查找也叫线性查找，对顺序表和链表都是适用的。

1. 一般线性表的顺序查找

typedef struct {
    ElemType *elem;
    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;
    }//从后往前找
}

• ST.elem[0]称为哨兵，其作用是使得Search_Seq内的循环不必判断数组是否越界，提高程序的效率。

• 查找效率分析：对于n个元素的表

  • 查找成功的ASL
    $ASL=\sum_{i=1}^{n}P_i(n-i+1)=\frac{n+1}{2}$
  • 查找失败的ASL
    $ASL=n+1$

2. 有序线性表的顺序查找

使用查找判定树分析ASL

$$ ASL_{成功}=\sum_{i=1}^{n}P_i(n-i+1)=\frac{n+1}{2} $$

$$ ASL_{不成功}=\sum_{i=1}^{n}P_i \frac{1+2+...+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1} $$

3. 有序线性表被查概率不相等

举例：

• 从小到大排序

$$ ASL_{成功}=1\times0.15+2\times0.05+3\times0.1+4\times0.4+5\times0.28+6\times0.02=3.67 $$

• 若将被查概率大的放在靠前位置

$$ ASL_{成功}=1\times0.4+2\times0.28+3\times0.15+4\times0.1+5\times0.05+6\times0.02=2.18 $$

由此可见，第二种约定的ASL更加小，查找效率更加高效。

7.2.2 折半查找

折半查找也称二分查找，只适用于有序的顺序表。

• 表为升序表

  ♾️ C 代码:

  int Binary_Search(SSTable L, ElemType key){
    int low =0, high = L.TableLen - 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;
    }
  }

• 表为降序表

  ♾️ C 代码:

  int Binary_Search(SSTable L, ElemType key){
    int low =0, high = L.TableLen - 1, mid;
    while(low <= high){
        mid = (low + high) / 2;
        if(L.elem[mid] == key)
            return mid;
        else if(L.elem[mid] > key) //从前半部分继续查找
            low = mid + 1;
        else //从后半部分继续查找
            high = mid - 1;
    } //降序时，只需将low和high处理方式互换即可
  }

• 使用判定树分析查找效率
  
  显然，判定树是一颗平衡二叉树。
• 当low和high之间有奇数个元素时，则mid分隔后，左右两部分元素个数相等。
• 当low和high之间有偶数个元素时，则mid分隔后，左部分比右部分少一个元素。
  所以，在折半查找的判定树中，若$mid=\left \lfloor (low+high)/2 \right \rfloor$ ,则对于任何一个结点，必有：右子树结点数 - 左子树结点数 = 0或1

7.2.3 分块查找

分块查找也称索引顺序查找，既有动态结构，又适用于快速查找。其特点是：块内无序，块间有序。

typedef struct{
    ElemType maxValue;
    int low, high;
}Index; //索引表

ElemType List[100];//顺序表存储的实际元素

• 查找过程：

  • 第一步：在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表。

    • 其中，折半查找时，查找索引表最终状态是:low > high，因此在low所指的分块查找。
  • 第二部：在块内顺序查找。

• 查找效率分析
  设索引查找和块内查找的平均查找长度为 $L_I$ 和 $L_S$，则 $ASL=L_I + L_S$

  • 将长度为 $n$ 的查找表均匀地分为 $b$ 块，每块有 $s$ 个记录($n=b\times s$)，若采用顺序查找索引表：

    $$ L_I=\frac{1+2+...+b}{b}=\frac{b+1}{2},L_S=\frac{1+2+...+s}{s}=\frac{s+1}{2} $$

    $$ ASL=L_I+L_S=\frac{b+1}{2}+\frac{s+1}{2}=\frac{\frac{n}{s}+s+2}{2}=\frac{s^2+2s+n}{2s} $$

    当 $s=\sqrt{n}$ 时，则平均查找长度取最小值 $\sqrt{n}+1$

  • 将长度为 $n$ 的查找表均匀地分为 $b$ 块，每块有 $s$ 个记录，若采用折半查找索引表：

    $$ L_I=\left \lceil \log_{2}{(b+1)} \right \rceil,L_S=\frac{1+2+...+s}{s}=\frac{s+1}{2} $$

    $$ ASL=\left \lceil \log_{2}{(b+1)} \right \rceil+\frac{s+1}{2} $$

7.3 树形查找

7.3.1 二叉排序树（BST）

1. 定义

又叫二叉查找树、二叉搜索树，具有下列特性：

• 若左子树非空，则左子树上所有结点的值均小于根结点的值。
• 若右子树非空，则右子树上所有结点的值均大于根节点的值。
• 左、右子树分别是一棵二叉排序树。

2. 查找

• 非递归查找算法

  ♾️ C 代码:

  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;
  }

• 递归查找算法

  ♾️ C 代码:

  BSTNode *BST_Search (BiTree T, ElemType key) {
    if(T == NULL)
        return NULL;
    if(key < T->data)
        BST_Search(T->lchild, key);
    else
        BST_Search(T->rchild, key);
    return T;
  }

3. 插入

• 示例：
  依次插入该序列：54，20，66，40，28，79，58
  动画：
  

• 递归算法

  ♾️ C 代码:

  int BST_Insert(BiTree &T, keyType k){
    if(T == NULL){
        T = (BiTree)malloc(sizeof(BSTNode));
        T->data = k;
        T->lchild = T->rchild = NULL;
    }
    else if(k == T->data)
        return 0;
    else if(k < T->data)
        return BST_Insert(T->lchild, k);
    else
        return BST_Insert(T->rchild, k);
  }

• 非递归算法

  ♾️ C 代码:

  int BST_Insert(BiTree &T, keyType k) {
    BiTree *p = T; // 使用指针的指针来跟踪插入位置
    while (p != NULL) {
        if (k == p->data) {
            return 0; // 节点已存在，插入失败
        } else if (k < p->data) {
            p = p->lchild); // 转向左子树
        } else {
            p = p->rchild); // 转向右子树
        }
    }
    // 找到插入位置，创建新节点
    p = (BiTree)malloc(sizeof(BSTNode));
    p->data = k;
    p->lchild = p->rchild = NULL;
    return 1; // 插入成功
  }

4. 构造

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

5. 删除

• 删除操作的实现过程有三种情况：

  • 若被删除结点 $z$ 是叶结点，则直接删除。
  • 若结点 $z$ 只有一棵左子树或右子树，则让 $z$ 的子树成为 $z$ 父结点的子树，替代 $z$ 的位置。
  • 若结点 $z$ 有左子树和右子树，则令 $z$ 的直接后继（或直接前驱）替代 $z$ ，然后从树中删除这个直接后继（或直接前驱），这样就转换成第一或第二种情况。

• 示例：

  • 第二种情况（只有左子树）：删除45
    
  • 第二种情况（只有右子树）：删除78
    
  • 第三种情况：删除78
    

6. 查找效率分析

• 当树高最小时，平均执行时间为 $O(log_{2}{n})$
• 当树高最大时，平均执行时间为 $O(n)$

7.3.2 平衡二叉树

1. 定义

• 平衡二叉树：为了避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除结点时，保证任意结点的左、右子树高度差的绝对值不超过 1，这样的树叫做平衡二叉树（AVL）。
• 平衡因子：该结点的左、右子树高度差。且平衡因子只可能是 -1、0、1。

2. 插入

若插入后导致不平衡，有以下调整操作：

• LL 平衡旋转（右单旋转）：在结点 A 的左孩子（L）的左子树（L）上插入。
  插入17
  
• RR平衡旋转（左单旋转）：在结点 A 的右孩子（R）的右子树（R）上插入。
  插入90
  
• LR平衡旋转（先左后右双旋转）：在结点 A 的左孩子（L）的右子树（R）上插入。
  插入57
  
• RL平衡旋转（先右后左双旋转）：在结点 A 的右孩子（R）的左子树（L）上插入。
  插入63
  

3. 删除

删除操作和插入操作类似，以删除 $w$ 结点为例：

• 用二叉排序树的方法对结点 $w$ 执行删除操作
• 若导致不平衡，则从结点 $w$ 开始向上回溯，找到第一个不平衡的结点 $z$ ； $y$ 是结点 $z$ 的高度最高的孩子； $x$ 是结点 $y$ 的高度最高的孩子。

• 然后对以 $z$ 为根的子树进行平衡调整，有以下四种情况：

  • $y$ 是 $z$ 的左孩子，$x$ 是 $y$ 的左孩子（LL，右单旋转）
  • $y$ 是 $z$ 的右孩子，$x$ 是 $y$ 的右孩子（RR，左单旋转）
  • $y$ 是 $z$ 的左孩子，$x$ 是 $y$ 的右孩子（LR，先左后右双旋转）
  • $y$ 是 $z$ 的右孩子，$x$ 是 $y$ 的左孩子（RL，先右后左双旋转）
  

  4. 查找

  假设 $n_h$ 表示深度为 $h$ 的AVL树中含有的最少结点数。

• $n_0 = 0,n_1=1,n_2=2$
• 并且有 $n_h=n_{h-1}+n_{h-2}+1$
• 由此推出，含有 n 个结点的AVL树的最大深度为 $O(log_{2}{n})$
• 因此平均查找效率为 $O(log_{2}{n})$

7.3.3 红黑树

1. 定义

在AVL树的平衡标准下进一步放宽条件，引入了红黑树（RBT）的结构。（左根右）

• ① 每个结点或是红色，或是黑色。
• ② 根结点是黑色。（根叶黑）
• ③ 叶结点（虚构的外部结点,NULL结点）都是黑色的。
• ④ 不存在两个相邻的红结点（红结点的父结点和孩子结点均是黑色）。（不红红）
• ⑤ 对每个结点，从该结点到任意一个叶结点的简单路径上，所含黑结点的数量相同。（黑路同）

黑高（记为 bh）：从该结点到任意一个叶结点的简单路径上，所含黑结点的数量。

由以上性质得出结论：

• 结论一：从根到叶结点的最长路径不大于最短路径的2倍。（性质4、5推出）

• 结论二：有 $n$ 个内部结点的红黑树的高度 $h\le2log_{2}{(n+1)}$ 。

  • 由此推出：黑高为 $h$ 的红黑树的内部结点 $n$ 数最少是 $2^h-1$ ，最多是 $2^{2h}-1$ 。
• 结论三：新插入红黑树的结点初始为红色。（保证性质5）

2. 插入

• 新结点是根——染为黑色。

• 新结点非根——染为红色。

  • 若插入新结点后依然满足红黑树定义，则插入结束。

  • 若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义。

    • 黑叔：旋转+染色

      • LL型：右单旋，父换爷+染色
      • RR型：左单旋，父换爷+染色
      • LR型：左、右双旋，儿换爷+染色
      • RL型：右、左双旋，儿换爷+染色

    • 红叔：染色+变新

      • 叔父爷染色，爷变为新结点

7.4 B树和B+树

7.4.1 B树及其基本操作

1. 定义

$m$ 阶 B树是所有结点平衡因子均为0的 $m$ 路平衡查找树。对于任何一个结点，每个子树的高度都相同。

$m$ 阶B树满足以下特性：

• 树中每个结点⾄多有 $m$ 棵⼦树，即⾄多含有 $m-1$ 个关键字。
• 若根结点不是终端结点，则⾄少有两棵⼦树。
• 除根结点外的所有⾮叶结点⾄少有 $\left \lceil \frac{m}{2} \right \rceil$ 棵⼦树，即⾄少含有 $\left \lceil \frac{m}{2} \right \rceil-1$ 个关键字。
• 所有的叶结点都出现在同⼀层次上，并且不带信息。
• 所有非叶结点的结构：

$K_i$ 是 结点的关键字；
$P_i$ 是 指向子树根结点的指针，$P_i$ 指向的子树的所有结点的关键字都大于 $K_i$；
$n$ 是结点中关键字的个数。（$\left \lceil \frac{m}{2} \right \rceil \le n \le m-1$）

2. B树的高度

• 若让每个结点的关键字个数达到最多，则有最小高度
  对于高度为 $h$ 的 $m$ 阶 B树的关键字个数 $n \le (m-1)(1+m+m^2+...+m^{h-1})=m^h-1$
  则最小高度 $h \ge log_m{(n+1)}$
• 若让每个结点的关键字个数达到最少，则有最大高度
  对于高度为 $h$ 的 $m$ 阶 B树，第 $i$ 层$(i \ge 3)$至少有 $2(\left \lceil \frac{m}{2} \right \rceil)^{i-2}$ 个结点；
  而第 $h+1$ 层是不包含任何信息的失败结点，所以 $n+1 \ge 2(\left \lceil \frac{m}{2} \right \rceil)^{h-1}$ ,
  得出最大高度 $h \le log_{\left \lceil \frac{m}{2} \right \rceil}{(\frac{n+1}{2})+1}$

3. B树的插入

例如：插入序列为 22 5 11 36 45 1 3 6 8 9 13 15 30 35 40 42 47 48 50 56

4. B树的删除

三种情况

• 直接删除关键字
  删除15
  
• 兄弟够借、
  删除42
  
• 兄弟不够借
  删除03
  

7.4.2 B+树的基本概念

B+树是应数据库所需而出现的一种B树的变形树。类似分块查找。
一棵 m阶 B+树应满足下列条件：

• 每个分支结点最多有 m 棵子树（孩子结点）。
• 非叶根结点至少有两棵子树，其他每个分支结点至少有 $\left \lceil \frac{m}{2} \right \rceil$ 棵子树。
• 结点的子树个数与关键字个数相等。（与B树不同）
• 在B+树中，叶结点包含信息，所有⾮叶结点仅起索引作⽤，⾮叶结点中的每个索引项只含有对应⼦树的最⼤关键字和指向该⼦树的指针，不含有该关键字对应记录的存储地址。
• 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针

7.4.3 B树与B+树的差异

相同点：除根结点外，最少 $\left \lceil \frac{m}{2} \right \rceil$ 个分叉（确保结点不要太“空”），任何一个结点的子树都要一样高（保证“绝对平衡”）。

7.5 散列（Hash）表

7.5.1 散列表的基本概念

• 散列表（哈希表）：是⼀种数据结构。特点是：可以根据数据元素的关键字计算出它在散列表中的存储地址。
• 散列函数（哈希函数）：Addr=H(key) 建⽴了“关键字”→“存储地址”的映射关系。
• 冲突：散列函数可能会把两个及以上的不同关键字映射到同一地址，这种情况为冲突。
• 同义词：这些发生冲突的不同关键字称为同义词。

7.5.2 散列函数的构造方法

要领：

• 定义域必须涵盖所有可能出现的关键字。
  反例：$H(key)=\sqrt{key}\%13$ ，不支持关键字为负值。
• 值域不能超出散列表的地址范围。
  反例：$H(key)=key\%15$，可能被映射到非法地址13、14。
• 尽可能减少冲突。散列函数计算出来的地址应尽可能均匀分布在整个地址空间。
  反例：$H(key)=(key \times 13)\%13$，任何关键字都会被映射到地址 0。
• 散列函数应尽量简单，能够快速计算出任意⼀个关键字对应的散列地址。
  反例：$H(key)=(key!)\%13$，若关键字较大，计算阶乘耗时高。

1. 直接地址法

$H(key) = key 或 H(key) = a \times key + b$
适用场景：关键字分布基本连续

2. 除留余数法（常用）

$H(key) = key \% p$
设散列表表⻓为 m，取⼀个不⼤于 m 但最接近或等于 m 的质数p
适用场景：较为通⽤，只要关键字是整数即可

3. 数字分析法

选取数码分布较为均匀的若⼲位作为散列地址
适⽤场景：关键字集合已知，且关键字的某⼏个数码位分布均匀

4. 平方取中法

取关键字的平⽅值的中间⼏位作为散列地址
适⽤场景：关键字的每位取值都不够均匀

7.5.3 处理冲突的方法

1. 开放定址法

如果发⽣“冲突”，就给新元素找另⼀个空闲位置。
递推公式：第 i 次发生冲突：$H_i=(H(key)+d_i) \% m$
其中，$m$ 表示散列表表长；$d_i$ 为增量序列（偏移量）。

$d_i$ 增量序列（偏移量）有以下取法（$0\le i \le m-1$）：

• 线性探测法
  $d_i= 1, 2, 3, ..., m-1$
  可能导致聚集（堆积）：大量元素在相邻的散列地址上，大大降低了查找效率
• 平方探测法
  $d_i=1^2,-1^2,2^2,-2^2,...,k^2,-k^2$，其中$k \le \frac{m}{2}$
  可以避免出现“堆积”的问题，缺点是不能探测到散列表上的所有单元，至少能探测到一般单元
• 双散列法
  $d_i=i \times Hash_2(key)$，使用两个散列函数，利用第二个函数计算关键字的地址增量：
  $H_i=(H(key)+i \times Hash_2(key)) \% m$
• 伪随机序列法

2. 拉链法

把所有“同义词”存储在⼀个链表中

• Step 1：结合散列函数计算新元素的散列地址
• Step 2：将新元素插⼊散列地址对应的链表（可⽤头插法，也可⽤尾插法）
  
  优化：新元素插⼊链表时，若能保持链表有序，可以略微提⾼“查找”效率。

7.5.4 散列查找及性能分析的应用

散列表的查找效率取决于三个因素：

• 散列函数
• 处理冲突的方法
• 装填因子

装填因子 $\alpha = \frac{表中记录数 n}{散列表长度 m}$
散列表的平均查找长度依赖于散列表的装填因子 $\alpha$，而不直接依赖于 $n$ 或 $m$。