⇧
❮
❯
↻
🍀计算机基础🍀 9111字 46分钟

数据结构强化笔记（8）：查找

作者

本文介绍各种查找算法。

Hyplus目录

1 查找的基本概念

查找：在数据集合中寻找满⾜某种条件的数据元素的过程。

查找表（查找结构）：⽤于查找的数据集合，由同⼀类型的数据元素（或记录）组成

  • 对查找表常⽤的4种操作：
    1. 查询某个特定的数据元素是否在查找表中
    2. 检索满⾜条件的某个特定的数据元素的各种属性
    3. 在查找表中插⼊⼀个数据元素
    4. 从查找表中删除某个数据元素
  • 静态查找表：只涉及上述1、2操作，⽆需动态地修改的查找表。适合⽤顺序查找、折半查找、散列查找等
  • 动态查找表：需要动态地插⼊或删除的查找表。适合⽤⼆叉排序树的查找、散列查找等

关键字：数据元素中唯⼀标识该元素的某个数据项的值

平均查找长度（ASL）：所有查找过程中进⾏关键字的⽐较次数的平均值，定义⻓度为n的查找表的平均查找长度为

\begin{aligned}
\text{ASL} = \sum\limits_{i=1}^n p_ic_i
\end{aligned}
  • p_i为查找第i个数据元素的概率，本章规定每个数据元素的查找概率相等，即p_i=\dfrac{1}{n}
  • c_i为找到第i个数据元素所需进行的比较次数

ASL是衡量查找算法效率的最主要的指标

2 简单查找

若无特殊声明，本章所有折半查找、树型查找的查找表中元素各异。

2.1 顺序查找

顺序查找（Sequence Search）⼜称线性查找，对顺序表与链表都适⽤。本节介绍两种全新的顺序查找技巧。

⼀般线性表的顺序查找：引入哨兵——设定下标0不存储元素，用于存放待查找关键字，其他元素存储于[1, n]

  • 优点：从尾向头查找，⽆需担⼼数组越界问题，减少不必要的判断语句，提⾼程序效率
  • 查找性能分析（同第1章顺序表查找性能分析）：
    • 成功：\text{ASL}_{\text{成功}}=\sum\limits_i p_i(n-i+1)=\dfrac{n+1}2（定位第i个元素时的比较次数c_i=n-i+1）
    • 失败：\text{ASL}_{\text{失败}}=n+1（与表中各关键字+哨兵的比较次数均为n+1）
/* 使⽤"哨兵"的顺序查找（下标0位置存放待查关键字作为哨兵），元素存于A[1...n] */
int sqSearch(ElemType A[], int n, ElemType key) {
    A[0] = key; // 哨兵：寄存待插元素
    for (int i = n; A[i] != key; i--);  // 从后往前找（i遍历只哨兵时必定退出循环）
    return i;   // 查找成功则正确返回下标，返回0时代表查找失败
}

有序表的顺序查找：对递增有序的表查找待查关键字key，若第i个关键字小于key，但第i+1个关键字大于key，则直接查找失败（第i个关键字后的元素均大于key，故不可能查找成功）

  • 优点：减少了查找失败时的⽐较次数；并且适⽤于链式存储结构（注意与折半查找的思想不同）
  • 有序表的顺序查找判定树：如下图所示，其中矩形结点称为失败结点，n个结点对应有n+1个失败结点
  • 查找性能分析：
    • 成功：平均时间与查找⽆序表相同
    • 失败：\text{ASL}_{\text{失败}}=\sum\limits_j q_j(l_j-1)=\dfrac{1+2+\cdots+n+n}{n+1}=\dfrac {n}{2}+\dfrac{n}{n+1}，其中q_j=\dfrac{1}{n+1}为到达第j个失败结点的概率，l_j为第j个失败结点所在判定树中的层数
    • 时间复杂度：T(n)=O(n)

线性表的其他操作性能分析⻅2.2.3线性表的操作性能分析

2.2 二分查找

折半查找（Binary Search，⼆分查找）仅适⽤于有序的顺序表，不适⽤于链表（因为链表⽆法随机存取）。

算法思想：对递增有序的表查找待查关键字，每轮与表的中间元素A[mid]比较，判断待查关键字应当位于中间元素左还是右，然后将对应另⼀侧的界限缩⼩⾄mid之后（mid - 1或mid + 1）。反复缩⼩范围即可获得查找结果。

/* ⾮递归⼆分 */
int biSearch(SqList L, ElemType key) {
    int low = 0, high = L.length - 1;   // 查找边界
    while (low <= high) {
        int mid = (low + high) / 2;
        if (key < L.data[mid]) high = mid - 1;  // 左⼩，缩⼩上界
        else if (key > L.data[mid]) low = mid + 1;  // 右⼤，放⼤下界
        else return mid;    // 查找成功，返回位置
    }
    return ERROR;   // 查找失败，返回ERROR
}

/* 递归⼆分 */
int biSearch(SqList L, ElemType key, int low, int high) {
    if (low > high) return ERROR;   // 递归边界，表示查找失败

    int mid = (low + high) / 2;
    if (key < L.data[mid]) return biSearch(L, key, low, mid - 1);
    else if (key > L.data[mid]) return biSearch(L, key, mid + 1, high);
    else return mid;
}

折半查找判定树：描述折半查找的过程，唯一确定。如图为以有序表{7,10,13,16,19,29,32,33,37,41,43}为例所建的判定树

  1. 从上⾄下第i层结点对应第i次折半时的mid关键字；“空分支”（本章中称为叶结点）表示查找失败的位置
  2. 查找⻓度：
    • 某元素查找成功的查找⻓度为从根结点到该元素路径上的结点数（包含该元素⾃身，故相当于层数）
    • 某元素查找失败（叶结点）的查找⻓度为从根结点到叶结点之前的结点数（正常配置不包含叶结点本身，故相当于层数 - 1）
  3. 每个结点值均⼤于左⼦树、⼩于右⼦树；进⼀步观察可知，折半查找判定树是⼀棵平衡⼆叉树
  4. 若有序序列有n个元素，则对应的判定树有n个圆形的非叶结点和n+1个矩形的叶结点
  5. 折半查找的最⼤⽐较次数即为折半查找判定树的⾼度h=\left \lceil \log_2 (n+1) \right \rceil = \left \lfloor \log_2 n \right \rfloor + 1，即完全⼆叉树的情况

查找性能分析：

  • 成功：\text{ASL}_{\text{成功}}=\dfrac{\sum 层数 \times 该层关键字数}{关键字总数}
  • 失败：\text{ASL}_{\text{失败}}=\dfrac{\sum (层数-1)\times 该层叶结点数}{叶结点总数}（正常配置）
  • 时间复杂度：T(n)=O(\log_2 n)
    • 与BST的区别：BST退化成单⽀树时查找⻓度为O(n)；⼆分查找⻓度始终不变，且⼆分查找判定树唯⼀
  • 计算有序表ASL的步骤：
    1. （选值）画树：不断⼆分算mid建树；然后在空分枝处添上查找失败叶结点即可
    2. 算数：成功算层数，失败算层数 - 1

【例】具有12个关键字的有序表中，对每个关键字的查找效率相同，分别计算折半查找查找成功与失败时的平均查找⻓度

【解】只需两步——

  1. 选值画树：圆形表示查找成功，矩形表示查找失败

  1. 计算ASL：\text{ASL}_{\text{成功}}=\dfrac{1\times 1+2\times 2+3\times 4+4\times 5}{12}=\dfrac {37}{12}，\text{ASL}_{\text{失败}}=\dfrac{3\times 3+4\times 10}{13}=\dfrac{49}{13}

2.2.A 整数与浮点数二分*

折半查找的对象可以为任意问题的解区间。整数二分的一般思路简记如下：

  1. 中点将区间划分出左右两子区间
  2. 判断中间点是否满足某侧区间的性质 check(mid)，查找○边界，目标在○区间，检测○区间性质。易知该种写法条件检测始终为"≥"或"≤"，对应伪代码中记号ge()（greater_equal）、le()（less_equal），对比目标和中点的位置关系即可得出条件检测函数
  3. 返回所检测的○区间的端点○

当查找右边界时中点应为l + r + 1 >> 1，简记：有("右") 加必有("右") 减

/* 查找左边界，即第一个满足条件的元素下标 (lower_bound) */
int biSearchL(int target, int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (ge(mid, target)) {
            r = mid;    // 目标在左，mid元素 ≥ 目标：带mid去左边 [l, mid]
        } else {
            l = mid + 1;    // 否则去右边 [mid + 1, r]
        }
    }
    return l;
}

/* 查找右边界，即最后一个满足条件的元素下标 (upper_bound的前驱) */
int biSearchR(int target, int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;   // 有（“右”）加必有（“右”）减
        if (le(mid, target)) {
            l = mid;    // 目标在右，mid元素 ≤ 目标：带mid去右边 [mid, r]
        } else {
            r = mid - 1;    // 否则去左边 [l, mid - 1]
        }
    }
    return r;
}

浮点数二分：类似整数二分的查找左边界，常写作f(mid) >= target的形式。解唯一，无需处理边界。要注意浮点精度问题

/* 浮点数二分 */
int biSearchF(double target, double l, double r) {
    const double eps = 1e-8;    // 精度，视题目而定
    while (r - l > eps) {
        double mid = (l + r) / 2;
        if (ge(mid, target)) {
            r = mid;    // 目标在左，mid所指>=目标。注意浮点关系运算精度问题
        } else {
            l = mid;    // 边界均无需+1或-1
        }
    }
    return l;
}

2.3 分块查找

分块查找⼜称索引顺序查找，吸取了顺序查找和折半查找各⾃的优点，有动态结构，适合快速查找。

算法思想：

  1. 将表分为若⼲⼦块：块内⽆序，但块之间有序（前⼀块的最⼤关键字 \lt 后⼀块的所有关键字）
  2. 建立索引表：键值分量包括各块的第⼀个关键字和各块的标志元素（通常就是第⼀个关键字）在查找表中的位置，索引表按关键字有序排列
struct Index {
    int key;    // 各块的第⼀个关键字
    int idx;    // 标志元素（通常就是第⼀个关键字）在查找表中的位置
} index[MAXSIZE];

查找过程：先在索引表中⼆分查找确定所在的块，再在块中顺序查找确定最终位置

特点：

  • 在表中插⼊和删除数据元素时，只要找到该元素对应的块，就可以在该块内进⾏插⼊和删除运算。由于块内是⽆序的，故插⼊和删除⽐较容易，⽆需进⾏⼤量移动
  • 如果要求⼀个线性表既能较快的查找，⼜能适应动态变化的要求，则可以选择分块查找

查找性能分析：

  • \text{ASL}=\text{ASL}_{\text{索引表}}+\text{ASL}_{\text{块}}
  • 对n个记录的索引表进行查找，最理想的块长为\sqrt{n}

3 树型查找

原版仅含BST、AVL树，新版特别追加红黑树！

3.1 二叉搜索树

⼆叉搜索树（Binary Search Tree，BST）⼜称⼆叉排序树（Sorted Binary Tree），⽤于提⾼查找、插⼊和删除关键字的速度

定义：左⼩右⼤，因此中序遍历序列递增有序

查找关键字：递归版直观且容易书写，但空间复杂度比非递归版高得多，故仍需掌握非递归版写法（下同）

/* ⾮递归BST查找 */
BSTNode *bstSearch(BiTree T, ElemType key) {
    while (T) {
        if (key < T->data) T = T->lchild;   // 左⼩
        else if (key > T->data) T = T->rchild;  // 右⼤
        else return T;  // 关键字相同，查找成功
    }
    return NULL;    // 到达空分枝，查找失败
}

/* 递归BST查找 */
BSTNode *bstSearchR(BiTree T, ElemType key) {
    if (!T) return NULL;    // 到达空分枝，查找失败

    if (key < T->data) return bstSearchR(T->lchild, key);   // 左⼩
    if (key > T->data) return bstSearchR(T->rchild, key);   // 右⼤
    return T;   // 关键字相同，查找成功
}

插⼊关键字：到达空分枝时插入成功

/* 非递归BST插入 */
bool bstInsert(BiTree &T, ElemType key) {
    while (T) {
        if (key < T->data) T = T->lchild;   // 左⼩
        else if (key > T->data) T = T->rchild;  // 右⼤
        else return false;  // 已存在该值结点，插⼊失败
    }
    T = (BiTNode*) malloc(sizeof BiTNode);  // 到达空分枝，则找到插⼊位置，新建结点并赋值
    T->lchild = T->rchild = NULL;
    T->data = key;
    return true;
}

/* 递归BST插入 */
bool bstInsertR(BiTree &T, ElemType key) {
    if (!T) {   // 到达空分枝，则找到插⼊位置，新建结点并赋值
        T = (BiTNode*) malloc(sizeof BiTNode);
        T->lchild = T->rchild = NULL;
        T->data = key;
        return true;
    }

    if (key < T->data) return bstInsertR(T->lchild, key);   // 左⼩
    if (key > T->data) return bstInsertR(T->rchild, key);   // 右⼤
    return false;   // 已存在该值结点，插⼊失败
}

建立二叉排序树：相当于进行n次插入

/* 根据个数为n的关键字数组key[]建⽴BST */
void createBST(BiTree &T, ElemType key[], int n) {
    T = NULL;   // 清空根节点
    for (int i = 0; i < n; i++)
        bstInsert(T, key[i]);
}

删除关键字：

  1. 待删结点为叶结点：直接删除
  2. 待删结点只有⼀个孩⼦：可直接让其⽗亲成为其孩⼦的⽗亲，其孩⼦替代其位置；或同样采⽤下⼀种双分⽀情况的⽅法
  3. 待删结点有左右两个孩⼦：令其后继（右⼦树的最⼩值）或前驱（左⼦树的最⼤值）的值替代它，再删除这个后继/前驱

查找性能分析：

  • 通常情况下\text{ASL}=O(\log_2 n)，当退化成单分支二叉树时达到最差\text{ASL}_{\text{worst}}=O(n)
  • 插入的时间复杂度：T_{\text{avg}}(n)=O(\log_2 n)，T_{\text{worst}}(n)=O(n)（同上）
  • 理想状态下，BST的高度h=\left \lceil \log_2 (n+1) \right \rceil = \left \lfloor \log_2 n \right \rfloor + 1，即完全二叉树的情况

【例题】判断给定序列是否可能为BST某遍历序列？

  1. 判断序列1, 2, 5, 4, 3是否可能为BST后序遍历序列：根据后序定义结点3为根，往前观察可明显发现存在两段左⼩右⼤⼦序列；进⼀步递归亦可发现存在同样结论，因此该序列可能为BST后序遍历序列
  2. 判断序列3, 5, 1, 4, 2是否可能为BST后序遍历序列：同上，但显然不存在两段满⾜要求的⼦序列，故必不可能！

3.2 平衡二叉树

平衡⼆叉树（Balanced Binary Tree，AVL Tree）是一种经过改进的二叉搜索树，规定左、右⼦树⾼度差的绝对值不超过1（平衡因⼦|BF|≤1）

获取属性：

  • 计算子树根高度，规定为与叶结点之间的最长路径：h(根)=\max(h(左子树),h(右子树)) + 1
  • 计算平衡因子，规定为左减右：BF=h(左子树)-h(右子树)

基本旋转调整操作：

  • L() 左旋⼦树根：对根的右孩⼦操作，右孩⼦的左⼦树成为根的右孩⼦，根成为右孩⼦的左⼦树，根位改变

  • R() 右旋⼦树根：对根的左孩⼦操作，左孩⼦的右⼦树成为根的左孩⼦，根成为左孩⼦的右⼦树，根位改变

“往X旋，就对Y孩⼦下⼿，切其X⼦树，再顺次接Y断枝”

插⼊：类似于BST，到达子树根u后进行如下判断操作

  1. 子树根u为空分枝，则找到插入位置，进行插入
  2. 权值小于u，则去根u的左子树插入，若导致不平衡（BF(u)=2）则按类型进行调整：
    • LL型（在左子树根的左子树u_{\text{LL}}插入，BF(u_{\text{LL}})=1）：对根右单旋——R(u)
    • LR型（在左子树根的右子树u_{\text{LR}}插入，BF(u_{\text{LR}})=-1）：先左旋左子树再右旋根——L(u->lchild), R(u)
  3. 权值大于u，则去根u的右子树插入，若导致不平衡（BF(u)=-2）则按类型进行调整：
    • RR型（在右子树根的右子树u_{\text{RR}}插入，BF(u_{\text{RR}})=-1）：对根左单旋——L(u)
    • RL型（在右子树根的左子树u_{\text{RL}}插入，BF(u_{\text{RL}})=1）：先右旋右子树再左旋根——R(u->rchild), L(u)
  4. 事后统一操作：更新⼦树根u的⾼度

调整核⼼思路：寻找最⼩不平衡⼦树——离叶结点最近的、最不"茂盛"的不平衡结点（|BF|>1）为根的子树

删除（不建议进行删除操作）：删除后回溯⾄最⼩不平衡⼦树根结点，根据路径中离该结点最近的两个结点的位置，转化成上述4种类型进⾏调整

查找：与BST相同

查找性能分析及性质：

  • \text{ASL}=O(\log_2 n)
  • 设n_h为深度为h的AVL树含有的最少结点数，则有n_0=0,n_1=1,n_2=2,n_h=n_{h-1}+n_{h-2}+1
    • 实为“斐波那契数列+1”，可使用递归求取：n_3=4,n_4=7,n_5=12,n_6=20,n_7=33,\cdots

【拓展】AVL树各操作的代码实现：

int l[N], r[N], v[N], h[N], idx;
// v[]：结点权值
// h[]：结点高度

/* 更新子树根高度 */
void update(int u) {
    h[u] = max(h[l[u]], h[r[u]]) + 1;
}

/* 计算子树根的平衡因子 */
int getBF(int u) {
    return h[l[u]] - h[r[u]];
}

/* 左旋子树根 */
void L(int &u) {
    int p = r[u];
    r[u] = l[p], l[p] = u;
    update(u), update(p);
    u = p;
}

/* 右旋子树根 */
void R(int &u) {
    int p = l[u];
    l[u] = r[p], r[p] = u;
    update(u), update(p);
    u = p;
}

/* 在子树根u处插入权值w的结点 */
void insert(int &u, int w) {
    if (!u) {   // 插入
        u = ++idx;
        v[u] = w;
    } else if (w < v[u]) {
        insert(l[u], w);
        if (getBF(u) == 2) {    // L
            if (getBF(l[u]) == 1) { // LL型，右单旋
                R(u);
            } else {    // LR型，先左旋再右旋
                L(l[u]);
                R(u);
            }
        }
    } else { /* 此处保证输入流中无重复权值 */
        insert(r[u], w);
        if (getBF(u) == -2) {   // R
            if (getBF(r[u]) == -1) {    // RR型，左单旋
                L(u);
            } else {    // RL型，先右旋再左旋
                R(r[u]);
                L(u);
            }
        }
    }
    update(u);
}

3.3 红黑树*

红黑树（Red Black Tree）是一种自平衡二叉搜索树，因每个结点中都有用于表示颜色的存储位而得名。

红黑树的5条特性：

  1. 结点包含颜色信息，红色或黑色其一
  2. 根结点为黑色
  3. 所有叶结点都是黑色，且不保存数据信息，只保存颜色信息，标记为NIL结点
  4. 每个红色结点必须有两个黑色的子结点（从每个叶结点到根的所有路径上不能有两个连续的红色结点）
  5. 从任一结点到其每个叶结点的所有简单路径都包含相同数目的黑色结点
    • 由性质4、5可得：从根到叶结点的最长可能路径数不多于最短可能路径的2倍

性能分析：查找、插入、删除的时间复杂度均为O(\log n)，旋转调整次数必不超过3次，综合性能超过AVL树。

4 多路平衡搜索树

外部存储常用的数据结构：B树、B+树

暂不收录B*树

4.1 B树

B树（B-树，B_树，B-Tree）：⼦树⾼度相同的一种m路平衡搜索树，其中m为阶数（⼈为规定）。可以为空树。

特性：

  1. ⼦树数与关键字数：关键字数 = ⼦树数 - 1
    • 每个结点至多有m棵子树——至多有m-1个关键字
    • 非叶根结点至少有\text{2}棵子树——至少有\text{1}个关键字
    • 非根非叶结点至少有\left \lceil \dfrac{m}{2} \right \rceil棵子树——至少有\left \lceil \dfrac{m}{2} \right \rceil -1个关键字
  2. 各结点BF=0，即⼦树⾼度相同
  3. 结点的结构：形如n | P[0] | K[1] | P[1] | K[2] | P[2] | ... | K[n] | P[n]
    • 关键字个数n：K[1] ~ K[n]
    • 关键字K[i]：升序排列，即K[1] < K[2] < ... < K[i - 1] < K[i] < ... < K[n]
    • 指针P[i]：{ P[i - 1]所指子树所有结点的关键字 } < K[i] < { P[i]所指子树所有结点的关键字 }
  4. 失败结点：最后⼀层“空分支”，常称为叶⼦结点。为便于区分，将此时叶结点上⼀层的结点称为终端结点
    • 特点：实际为外部结点（存储结构中并不存在）；不带信息，代表查找失败的位置
  5. B树的高度：设有一棵含有n个关键字的m阶B树，则其高度h满足（注：B树的高度不包括叶结点，即失败结点）
    • 最低：h_{\min}=\log_m(n + 1)

      【推导】等比数列求和可得n ≤ (m-1)(1+m+m^2+\cdots+m^{h-1})=m^h-1，移项可得

    • 最高：h_{\max}=\log_{\left \lceil \dfrac{m}{2} \right \rceil}\dfrac{n+1}{2}+1

      【推导】想要层数最⾼需让各层分叉尽可能少，即根只有\text{2}分叉，其他结点只有\left \lceil \dfrac{m}{2} \right \rceil分叉，记k=\left \lceil \dfrac{m}{2} \right \rceil；归纳可知第h层有2k^{h-2}个结点，则第h+1层（叶结点层）有2k^{h-1}个结点；因为n个关键字的B树必有n+1个叶结点（参考BST失败结点），则n+1≥2k^{h-1}，移项可得

【总结与归纳】B树的计算题

  • 若要B树的关键字最少，则其形如⼆叉树，可参考6.2.1“⼆叉树的重要性质”相关公式进行计算

多路查找：从根结点开始，从左至右扫描结点关键字K[i]与待查找关键字key对比（BST的扩展版）——

  1. key == K[i]：查找成功
  2. key < K[1]：去*P[0]结点查找
  3. K[i] < key < K[i + 1]：去*P[i]结点查找
  4. key > K[n]：去*P[n]结点查找
  5. 遇到叶结点（“空指针”，失败结点）：查找失败

插⼊关键字：先多路查找找到关键字key的插入点（叶结点），若插入后关键字数量超过上限m-1，则进行结点【拆分】操作——

  1. 对于有m个关键字的待拆分结点，取出其第\left \lceil \dfrac{m}{2} \right \rceil个关键字，并将其第1~\left \lceil \dfrac{m}{2} \right \rceil-1个关键字和第\left \lceil \dfrac{m}{2} \right \rceil+1~m个关键字做成两个结点连接在第\left \lceil \dfrac{m}{2} \right \rceil个关键字的左右指针上，并将第\left \lceil \dfrac{m}{2} \right \rceil个关键字插入其父结点中的相应位置
  2. 若导致⽗结点超上限，则继续执⾏⽗结点的【拆分】（把中间结点提⾄更上⼀级⽗结点，不存在（即试图拆分根）则新建，其余同前述步骤），插入操作只会导致B树逐渐变高而不会改变叶子结点在同一层的特性

【例】已知关键字集{37, 70, 12, 45, 90, 3, 24, 61, 53}，要求从空树开始逐⼀插⼊关键字，创建⼀棵3阶B树

【解】如下所示，其中插⼊53后的分裂情况：53插⾄⽗结点（70的左边），45、61分别挂于其左右两指针所指新结点

删除关键字：较为复杂，了解即可

  • 删除⾮终端结点的关键字：转化成删除终端结点的操作——寻找其"直接前驱"或"直接后继"代替之（参考BST）
  • 删除终端结点的关键字：分为如下几种情况
    1. 结点内关键字数大于下限\left \lceil \dfrac{m}{2} \right \rceil-1：直接删除
    2. 结点内关键字数等于下限\left \lceil \dfrac{m}{2} \right \rceil-1，且其左、右兄弟结点中存在关键字数大于下限的结点：从关键字数大于下限的兄弟中借关键字（如下图所示）
    3. 结点内关键字数等于下限\left \lceil \dfrac{m}{2} \right \rceil-1，且其左、右兄弟结点中不存在关键字数大于下限的结点：进行结点【合并】操作（如下图所示）。这可能引发连锁反应，导致父结点关键字数量低于下限，此时需要对父结点继续进行【合并】操作

4.2 B+树

B+树（B+Tree）：应数据库所需⽽出现的⼀种B树的变形树，终端结点称为"叶结点"，非根非叶结点称为"分枝结点"。

原理极为复杂，只要求简单理解与B树的区别：

B+树 B树
结构 子树数 = 关键字数
（不再设置P[0]指针，指针/⼦树数与关键字数形成了统⼀）		 子树数 = 关键字数 + 1
叶结点 叶结点⽤于存储关键字及指向相应记录的指针，记录⾥存有最终的信息
所有叶结点按关键字值的⼤⼩顺序排列，⽤指针串联成⼀根单链表，可顺着这条单链表进⾏顺序查找		 叶结点仅作为失败结点
分枝结点 各分枝结点，包含各个⼦结点的关键字最⼤值及指向对应⼦结点的指针，仅起索引作⽤，不直接存储关键字 所有结点都起存储作⽤；关键字互不相同，相当于引出对应记录的存储地址

查找操作与应⽤：

  • 查找⽅式：
    1. 多路查找：类似B树，区别在于必须⼀路查找⾄叶结点层才算真正完成本次查找。
    2. 顺序查找：遍历叶结点层单链表，参考单链表查找操作。
  • 应⽤：⽤于外存数据库（MySQL）的存储结构。【例】存储学⽣信息

5 散列表

散列函数（Hash Function，哈希函数）：把查找表中的关键字映射成对应的地址的函数H(key)=Addr

  • 冲突：将两个或以上不同关键字映射到同⼀地址的情况
  • 同义词：发⽣冲突的不同关键字

散列表（Hash Table，哈希表）：根据关键字⽽直接进⾏访问的数据结构，建⽴了关键字与存储地址之间的直接映射关系

装填因子：\alpha=\dfrac{表中记录数n}{散列表长度m}

具体实现时，最简单的哈希表容器为一维数组，在C++中还可直接使用STL建立哈希表，常用容器有以下两种：

  • unordered_set：容器内存放无序且唯一的元素
  • unordered_map：容器内存放无序的映射（一一映射）

利用unordered_set在大量数据中快速找出一对符合条件的数据：可在读入数据时立刻进行判定——若哈希表中存在与当前读入数据“配对”的元素，则说明找到了一对解，并将当前读入元素放入哈希表；否则只将当前读入元素放入哈希表不进行其他操作。

5.1 散列方法与冲突

散列函数的构造⽅法：

  1. 直接定址法：直接线性取址，散列函数为H(key)=a \cdot key+b，其中a,b为常数，最常用的此类散列函数为H(key)=key
    • 优点：适合关键字的分布基本连续的情况，简单，且不会产⽣冲突
    • 缺点：分布不连续时空位较多，易造成存储空间的浪费
  2. 除留余数法：取不⼤于但最接近表⻓的素数p，散列函数为H(key)=key \bmod p
    • 通常情况下，除留余数法是最简单、最常⽤的⽅法。
  3. 数字分析法：适合于已知关键字的集合。选取数字尽可能随机的若⼲数位，使得哈希地址尽量减少
  4. 平⽅取中法：适⽤于位数较少的关键字。取关键字平⽅后的中间⼏位作为地址

冲突处理办法：

  1. 开放定址法（再散列法）：对产⽣冲突的哈希值取哈希函数（即为再散列），通式为H_i=(H(key)+d_i) \bmod m,\ i=0,1,2,\cdots,k\ (k\lt m)，其中m为散列表的表长，i为冲突次数，d_i为增量序列，有以下4种常见取法——
    1. 线性探测法【默认取法】：d_i=1,2,\cdots,m-1，探测到表尾时则探测完全表，容易造成⼤量元素堆积，⼤⼤降低查找效率
    2. 平方探测法（二次探测法）：d_i=1^2,-1^2,2^2,-2^2,\cdots,k^2,-k^2\ (k≤\dfrac{m}{2})，可以避免堆积问题，但⽆法探测到表上所有单元（但⾄少能探测⼀半）
      • 偶尔为了⽅便亦可只取正值：d_i=1^2, 2^2,\cdots,k^2
    3. 双散列法：d_i=i\cdot H'(key)，需要两个散列函数，当⽤第⼀个函数得到的地址发⽣冲突时就启⽤第⼆个函数，即最终哈希值H_i=(H(key)+i\cdot H'(key)) \bmod m，经过m-1次探测就会遍历表中所有位置回到H_0
    4. 伪随机序列法：d_i为伪随机数序列
  2. 拉链法（Chaining，链接法）：把所有的同义词存储在⼀个链表中，此时哈希表内存放的是链表的指针。特点如下——
    • 具有链表的各种逻辑、存储结构特点，如适合经常进⾏插⼊与删除的情况
    • 允许装填因⼦\alpha≥1，因此特别适合处理结点规模较⼤的情况，规模⾜够⼤时可忽略指针域的空间消耗，此时反⽽⽐开放定址法省空间

5.1.A 冲突解决算法实现*

开放寻址法：（数组长度应开到最大数据量的2~3倍）

const int INF = 0x3f3f3f3f;     // 表示该哈希值的元素不在哈希表内

int h[N];

/* 哈希表初始化 */
void init() {
    memset(h, 0x3f, sizeof h);      // 初始化为无穷
}

/* 若x在哈希表中，返回x的下标；否则返回x应该插入的位置*/
int find(int x) {
    int t = (x % N + N) % N;
    while (h[t] != INF && h[t] != x) {  // 若已存在该哈希值的元素且该元素不等于x
        t++;
        if (t == N) t = 0;
    }
    return t;
}

拉链法：

int h[N], e[N], ne[N], idx;

/* 链表初始化 */
void init() {
    memset(h, -1, sizeof h);
}

/* 向哈希表中插入一个数 */
void insert(int x) {
    int t = (x % N + N) % N;    // C++的负数取余运算：(-n) mod k = -(n mod k)
    e[idx] = x;
    ne[idx] = h[t];
    h[t] = idx++;   // 将x头插在链表h[t]
}

/* 在哈希表中查询某个数是否存在 */
bool find(int x) {
    int t = (x % N + N) % N;
    for (int i = h[t]; ~i; i = ne[i]) {     // 遍历整条链表h[t]
        if (e[i] == x) {
            return true;
        }
    }
    return false;
}

5.1.B 字符串前缀哈希法*

字符串前缀哈希法：快速判断两段字符串是否相等（不考虑冲突）

  • 核心思想：将字符串看成P进制数，P的经验值为131或13331，取这两个值的冲突概率极低
  • C++小技巧：取模的数用2^{64}，这样直接用unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL;

const int P = 131;

char str[N];    // 待哈希字符串str[1 ... n]
int n;          // 字符串的长度
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值（前缀和），p[k]存储 P^k mod 2^64

/* 预处理前缀哈希 */
void init() {
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * P + str[i];   // 求前缀和
        p[i] = p[i - 1] * P;    // unsigned long long溢出相当于对2^64取模
    }
}

/* 计算子串str[l ... r]的哈希值 */
ULL get(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

5.2 散列性能分析

散列查找的时间复杂度：T(n)=O(1)，即与表中元素的个数⽆关

查找性能分析：

  • 因为冲突的产⽣，查找时仍需要与关键字进⾏⽐较，故同样需使⽤上述⼏种冲突处理⽅法
  • 查找效率的3个取决因素：散列函数、冲突处理⽅法、装填因⼦\alpha
  • 平均探测次数（即平均查找⻓度）依赖于装填因⼦，\alpha越大表越满，不依赖于记录数或表⻓

【总结与归纳】冲突/堆积的影响

  • 产⽣堆积现象，即产⽣了冲突，它对存储效率、散列函数和装填因⼦均不会有影响，⽽平均查找⻓度会因为堆积现象⽽增⼤
  • 在开放定址的情形下，不能随便删除散列表中的某个元素，否则会导致搜索路径被中断（正确做法：在删除的地⽅做删除标记，即只进行逻辑删除）

计算平均查找⻓度/平均探测次数：

  1. 计算每个关键字的散列函数值，构造散列函数值表
  2. 填表：采⽤规定的冲突处理⽅法解决冲突，构造哈希表
  3. 求ASL：使⽤通⽤⽅法\text{ASL}=\dfrac{\sum 查找次数}{关键字数}
    • 查找成功时，查找次数：无冲突时为1，有冲突时为冲突次数 + 1
    • 查找失败时，需计算表中每个可被哈希到的地址的被检索次数：对着哈希表操作，从当前地址开始往后计数直⾄遇⻅空位，即得检索次数（次数包含空位）
      • 对于链地址法则是顺着链表⾛，直⾄遇⻅表尾空指针（次数同样包含空指针），故相当于链表长度 + 1
      • 注意超出模数p的地址⽆需计算（因为不可能被哈希到），此时ASL的除数也应当为模数p范围内地址的个数

【例】设⼀组关键字为{33, 10, 45, 20, 53, 43, 31, 15, 65, 40}，假定哈希函数为H(key)=key \bmod 11，采⽤开放定址法的再散列法解决冲突，试⽤数组A[14]对该关键字序列构造哈希表，并在等概率情况下计算查找成功和查找不成功时的平均查找⻓度

【解】只需以下三步——

  1. 构造哈希函数值表：计算每个关键字的哈希函数值
key 33 10 45 20 53 43 31 15 65 40
H(key) 0 10 1 9 9 10 9 4 10 7
  1. 构造哈希表：填表，使⽤再散列法解决冲突，该哈希表⻓m=14（记录"冲突次数"是为之后计算ASL时使⽤，单纯考察建表则⽆需写出）
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13
key 33 45 65 15 40 20 10 53 43 31
冲突次数 0 0 6 0 0 0 0 2 2 4
  1. 计算ASL：由上表可得，\text{ASL}_{成功}=\dfrac{1\times 6+3\times 2+5\times 1+7\times 1}{10}-2.4
下标 0 1 2 3 4 5 6 7 8 9 10 11 12 13
检索次数 4 3 2 1 2 1 1 2 1 9 8 - - -

\therefore\ \text{ASL}_{失败}=\dfrac{4+3+2+1+2+1+1+2+1+9+8+7+6+5}{11}=\dfrac{34}{11}

A 查找算法编程练习

A.1 简单查找

【例1】线性表中各结点的检索概率不等时，可用如下策略提高顺序检索的效率：若找到指定的结点，则将该结点和其前驱结点（若存在）交换，使得经常被检索的结点尽量位于表的前端。试设计在顺序存储和链式存储（带头结点）的线性表上实现上述策略的顺序检索算法

/* 顺序结构 */
void search(SqList &L, ElemType key) {
    if (L.data[0] == key) return;   // 第一个元素无前驱结点，则直接结束
    for (int i = 1; i < L.length; i++)
        if (L.data[i] == key) { // 若找到则让它与前驱交换
            ElemType temp = L.data[i];
            L.data[i] = L.data[i - 1];
            L.data[i - 1] = temp;
            return;
        }
}

/* 链式结构 */
void search(LinkList &L, ElemType key) {
    if (L->next->data == key) return;   // 第一个元素无前驱结点，则直接结束
    LNode *p = L;   // 遍历指针
    while (p->next->next) { // 往后看两步
        if (p->next->next->data == key) {   // 若找到则将两者交换
            LNode *q = p->next, *r = q->next;   // 辅助指针
            q->next = r->next;
            p->next = r;
            r->next = q;
            return;
        }
        p = p->next;
    }
}

A.2 二叉排序树

【例1】求给定二叉排序树中的最大和最小关键字（假设数据类型为int型）

/* 求最小值 */
int getMin(BSTree T) {
    while (T->lchild) T = T->lchild;
    return T->data;
}

/* 求最大值 */
int getMax(BSTree T) {
    while (T->rchild) T = T->rchild;
    return T->data;
}

【例2】求指定结点在二叉排序树中的层次

int getLevel(BSTree T, BSTNode *p) {
    int level = 1;  // 记录T所指结点的层次
    while (T != p) {
        if (p->data < T->data) T = T->lchild;   // 左小
        else T = T->rchild; // 右大
        level++;    // 无论T去哪个子树，层数均需+1
    }
    return level;
}

【例3】设计算法从大到小输出二叉排序树中所有值不小于k的关键字

void printGt(BSTree T, int k) {
    if (T) {
        printGt(T->rchild, k);  // 先右大
        if (T->data >= k) printf("%d ", T->data);   // 符合要求则打印
        printGt(T->lchild, k);  // 再左小
    }
}

【例4】编写算法判断给定的二叉树是否是二叉排序树

bool inOrder(BiTree T, int &pre) {
    if (!T) return true;
    bool lflag = inOrder(T->lchild, pre);   // 递归判断左子树是否为BST
    if (!lflag || T->data <= pre) return false; // 若左子树非BST或根结点不满足“左小”则不是
    pre = T->data;
    bool rflag = inOrder(T->rchild, pre);   // 递归判断右子树是否为BST
    return rflag;   // 返回右子树判断结果
}

bool isBST(BiTree T) {
    int pre = -INT_MAX; // 记录中序遍历的上一结点的值
    return inOrder(T, pre);
}

发表评论