
#import "../template.typ": *
#import "@preview/pinit:0.1.4": *
#import "@preview/fletcher:0.5.0" as fletcher: diagram, node, edge

#import "/book.typ": book-page

#show: book-page.with(title: "查找 | DSA")

= 查找
<查找>

#definition[
  *平均查找长度（#underline[A]verage #underline[S]earch #underline[L]ength, ASL）*：在查找成功时，查找到目标的平均查找长度。$
  "ASL" = sum_(i=1)^(n) p_i times c_i
  $
]

== 静态查找表

先把需要比较的值复制为*监视哨*，放在数组的第一个位置。

若有序，使用折半查找。

```C
int Search_Bin(SSTable ST, KeyType key) {
    //在有序表ST中折半查找其关键字等于key的数据元素。
    //若找到，则函数值为该元素在表中的位置，否则为0。
    low = 1;
    high = ST.length;// 置区间初值
    while (low <= high) {
        mid = (low + high) / 2;
        if （EQ (key , ST.elem[mid].key) )
        return  mid;        // 找到待查元素
        else if (LT(key, ST.elem[mid].key))
            high = mid - 1;// 继续在前半区间进行查找
        else
            low = mid + 1;// 继续在后半区间进行查找
    }
    return 0;// 顺序表中不存在待查元素
}            // Search_Bin
```

一般情况下，表长为 $n$ 的折半查找的判定树的深度和含有 $n$ 个结点的完全二叉树的深度相同。所以，折半查找的时间复杂度为 $O(log n)$，ASL 约为 $log_2(n+1) - 1$。

- 优点：查找速度快，ASL 小。
- 缺点：关键字必须有序，只适用于顺序表。（链表不支持随机读取）

#image("../assets/2024-06-25-21-07-56.png")

== 动态查找表

#definition[
  *动态查找表*：一种查找表，其查找表的长度是动态变化的。
]

在调用插入函数的时候，如果表中不存在该元素，则插入到表中。删除函数，如果表中存在该元素，则删除。

=== 二叉排序树

#definition[
  *二叉排序树*：或者为空树，或者满足以下性质的二叉树：

  1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值。
  2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
  3. 左、右子树也分别为二叉排序树。
]

==== 查找算法

+ 若树为空，查找失败。
+ 若树非空，若 $"key" = T->"data"$，查找成功。
+ 若 $"key" < T->"data"$，在左子树中查找。
+ 若 $"key" > T->"data"$，在右子树中查找。

==== 插入算法

根据动态查找表的定义，“插入”操作在查找不成功时才进行。若树为空，插入为根结点。否则，新插入的结点总是叶子结点，其插入位置由查找的结果决定。

==== 删除算法

根据动态查找表的定义，“插入”操作在查找不成功时才进行。

删除结点的操作分为三种情况：

1. 被删除的结点是叶子结点。
  - 直接删除，将其父结点指向它的指针置为空。
2. 被删除的结点只有一个孩子。
  - 将其父结点指向它的指针指向它的孩子。
3. 被删除的结点有两个孩子。
  - 以其中序遍历前驱（或后继）结点替代它，然后删除前驱（或后继）结点。就是左树中最大的结点或右树中最小的结点。

在多次插入和删除操作后，二叉搜索树可能退化为链表。在这种情况下，所有操作的时间复杂度将从 $O(log n)$ 劣化为 $O(n)$。

=== 平衡二叉树

#definition[
  *平衡二叉树*：或者为空树，或者满足以下性质的二叉树：它的左右子树的深度之差的绝对值不超过 $1$，并且左右子树也分别为平衡二叉树。又称 AVL 树。
]

#definition[
  *平衡因子*：平衡二叉树中，左子树的深度减去右子树的深度。
]

平衡二叉树的 ASL 相当于 $O(log n)$。

平衡二叉树的插入和删除操作会导致树的失衡，需要进行调整。

==== 平衡二叉树的调整

首先找到失衡的结点，然后根据失衡的情况进行调整。根据新结点的插入位置，可以分为四种失衡情况：

1. LL 型失衡：在结点的左子树的左子树上插入。
2. LR 型失衡：在结点的左子树的右子树上插入。
3. RR 型失衡：在结点的右子树的右子树上插入。
4. RL 型失衡：在结点的右子树的左子树上插入。

#image("../assets/2024-06-25-21-30-28.png")

+ LL 型：右旋

  #image("../assets/2024-06-25-21-25-34.png")

  把失衡的结点的左子树的根结点作为新的根结点，失衡的结点作为新的根结点的右子树。形象地来说，把左子树的根结点拎起来。

  #image("../assets/2024-06-25-21-26-19.png")

  如果左子树的右子树不为空，把左子树的右子树作为失衡结点的左子树。反正无论如何失衡结点都在左子树的右子树的根节点上。PPT 里就是这样的例子，所以 B 的右子树到 A 的左子树上了。

  #image("../assets/2024-06-25-21-33-48.png")

+ RR 型：左旋

  #image("../assets/2024-06-25-21-27-35.png")
  #image("../assets/2024-06-25-21-28-02.png")
  #image("../assets/2024-06-25-21-36-17.png")

+ LR 型：先左旋再右旋

  #image("../assets/2024-06-25-21-29-51.png")

  先对失衡结点的左子树进行左旋，再对失衡结点进行右旋。

  #image("../assets/2024-06-25-21-36-28.png")

+ RL 型：先右旋再左旋

  #image("../assets/2024-06-25-21-30-17.png")

  先对失衡结点的右子树进行右旋，再对失衡结点进行左旋。

  #image("../assets/2024-06-25-21-36-40.png")

==== 平衡二叉树的判断

使用后序遍历可以判断一个二叉树是否为平衡二叉树。#note_block[
  *后序遍历*：递归遍历左子树，递归遍历右子树，访问根结点。

  访问根节点相当于判断左右子树的深度差是否小于等于 1。
]

```c
int IsBalanced(BiTree T, int *depth) {
    int ldepth, rdepth;
    if (T == NULL) {
        *depth = 0;
        return 1;
    }
    if (IsBalanced(T->lchild, &ldepth) && IsBalanced(T->rchild, &rdepth)) {
        if (abs(ldepth - rdepth) <= 1) {
            *depth = 1 + (ldepth > rdepth ? ldepth : rdepth);
            return 1;
        }
    }
    return 0;
}
```

=== B - 树

#definition[
  *B - 树*：一种平衡多路查找树。对于一棵 $m$ 阶的 B - 树，或者为空树，或者满足以下性质：
  // floor() 的反义词是 ceil()
  1. 所有非叶结点至少含有 $ceil(m/2)$ 棵子树，至多含有 $m$ 棵子树；关键字个数不少于 $ceil(m/2) - 1$ 个，至多 $m - 1$ 个。
  2. 根结点或为叶子结点，或至少有两棵子树。
  其余略。
]

==== 查找过程

查找过程和二叉排序树类似，不同的是，B - 树的结点不止一个关键字，所以查找的过程需要对结点的关键字进行顺序或二分查找。

==== 查找性能

在含有 $n$ 个关键字的 B - 树中，查找需要访问的结点个数不超过 $log_(ceil(m/2)) ((n+1)/2) +1$。

=== $B^+$ 树

#image("../assets/2024-06-25-21-53-14.png")

== 哈希表

对于频繁使用的查找表，希望 $"ASL" = 0$。要求：记录在表中的位置和其关键字之间存在一种确定的关系。

#definition[
  *哈希表*：根据关键字的值直接进行访问的数据结构。通过哈希函数将关键字映射到表中的位置。
]

#definition[
  *哈希函数*：将关键字映射到表中的位置的函数，是一个压缩映象。
]

#definition[
  *哈希冲突*：不同关键字映射到同一个位置的现象。具有相同哈希地址的记录称为*同义词*。
]

=== 哈希表查找的分析

决定哈希表查找性能，或者说决定 ASL 的因素有：

+ 选用的哈希函数，但一般情况下认为哈希函数是均匀的，所以不考虑它的影响。
+ 处理冲突的方法
+ 哈希表的装填因子 $alpha = n/m$，$n$ 是表中记录的个数，$m$ 是表长。

因此，哈希表的ASL是处理冲突方法和装填因子的函数。


=== 哈希函数的构造方法

#definition[*除留余数法*：$
H("key") = "key" mod p
$，其中 $p$ 是一个不大于表长的素数或不含小于 $20$ 的质因子，避免映射到同一个位置。]

=== 处理冲突的方法

==== 开放定址法

#definition[
  *开放定址法*：为产生冲突的地址 $H("key")$ 求得一个地址序列 $H_i = (H("key") + d_i) mod m$，直到找到一个空的存储位置。
]

$d_i$ 有三种计算方法：

1. 线性探测再散列：$d_i = i$。
2. 二次探测再散列：$d_i = 1^2, -1^2, 2^2, -2^2, 3^2, -3^2, dots$。
3. 伪随机探测再散列：$d_i = R_i$，$R_i$ 是一个伪随机数列，或者 $d_i = i times P_i$，$P_i$ 是关键字的另一个哈希函数（又称双散列函数探测）。

#definition[
  *二次聚集*：在处理冲突过程中发生的两个第一个哈希地址不同的记录争夺同一个后继哈希地址的现象。
]

#note_block[
  计算 ASL 的例子：
  #grid(
    columns: 2,

  )[#image("../assets/2024-06-25-22-04-57.png")
  ][#image("../assets/2024-06-25-22-05-03.png")]
]
==== 链地址法

#definition[
  *链地址法*：将所有关键字为 $H("key")$ 的记录存储在一个链表中。
]

