查找的基本概念

查找

在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种：查找成功、查找失败。
查找表(查找结构)

用于查找的数据集合称为查找表，它由同一类型的数据元素（或记录）组成，可以是一个数组或链表等数据类型。

对查找表经常进行的操作一般有 4 种：
1. 查询某个特定的数据元素是否在查找表中：
2. 检索满足条件的某个特定的数据元素的各种属性；
3. 在查找表中插入一个数据元素；
4. 从查找表中删除某个数据元素；
静态查找表

若一个查找表无须动态地修改元素，则此类查找表称为静态查找表。适合静态查找表的查找方法有顺序查找、折半查找、散列查找等；
动态查找表

若一个查找表需要动态地插入或删除元素，则此类查找表称为动态查找表。适合动态查找表的查找方法有二叉排序树的查找、散列查找等。
关键字

数据元素中唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
平均查找长度

在查找过程中，一次查找的长度是指需要比较的关键字的次数称为查找长度，而平均查找长度则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为
$A S L = i = 1 \sum n P_{i} C_{i}$
式中，n 是查找表的长度； $P_{i}$ 是查找第 i 个数据元素的概率，一般认为每个数据元素的查找概率相等，即 $P_{i} = 1/ n$ ； $C_{i}$ 是找到第 i 个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

顺序查找

顺序查找

顺序查找又称线性查找，通常用于线性表，它对顺序表和链表都是适用的。

对于顺序表，可通过数组下标递增来顺序扫描每个元素；
对于链表，可通过指针 next 来依次扫描每个元素；

顺序查找通常分为对一般的无序线性表的顺序查找和对按关键字有序的线性表的顺序查找。

一般线性表的顺序查找

typedef struct {// 查找表的数据结构，顺序表
    int *elem;// 动态数组基址
    int TableLen;// 表的长度
} SSTable;
// 第一种
int Search_Seq1(SSTable ST, int key) {
  int i；
  for (i = 0; i < ST.TableLen && ST.elem[i] != key; i++);
  return i == ST.TableLen ? -1 : i;
}
// 第二种
int Search_Seq2(SSTable ST, int key) {
  ST.elem[0] = key; // 哨兵
  int i；
  for (i = ST.TableLen; ST.elem[i] != key; i--);
  return i;// 若表中不存在关键字为key的元素，将查找到i为0时退出for循环
}

查找成功的平均查找长度 $A S L = \frac{n + 1}{2}$ ；

查找失败的平均查找长度 $A S L = n + 1$ ；

有序表的顺序查找

若在查找之前就已经知道表是关键字有序的，则查找失败时可以不用再比较到表的另一端就能返回查找失败的信息，从而降低顺序查找失败的平均查找长度。

查找成功的平均查找长度 $A S L = \frac{n + 1}{2}$ ；

查找失败的平均查找长度 $A S L = \frac{n}{2} + \frac{n}{n + 1}$ ；

折半查找

折半查找又称二分查找，它仅适用于有序的顺序表。

基本思想：首先将给定值 key 与表中中间位置的元素比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分。然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所需要查找的元素，则查找不成功，返回查找失败的信息。

typedef struct {// 查找表的数据结构，顺序表
    int *elem;// 动态数组基址
    int TableLen;// 表的长度
} SSTable;
 
int Binary_Search(SSTable L, int 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; //从后半部分继续查找
    }
  }
  return -1; //查找失败，返回T
}

判定树：树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点都是方形的，它表示查找不成功的情况。

折半查找判定树是一棵二叉排序树，其中序序列是一个有序序列。

若有序序列有 n 个元素，则对应的判定树有 n 个圆形的非叶结点和 n+1 个方形的叶结点。

折半查找的判定树一定是一棵平衡二叉树。

折半查找的判定树中，只有最下面一层是不满的，因此元素个数为 n 时，树高 $h = ⌈ lo g_{2} (n + 1) ⌉$ 。

折半查找在查找不成功时和给定值进行关键字比较次数最多就是树的高度即 $⌈ lo g_{2} (n + 1) ⌉$ 。

折半查找的的时间复杂度为 $O (lo g_{2} n)$

Tip

若是求查找成功或查找失败的平均查找长度，则需要画出判定树进行求解。

对长度为 n 的有序表，采用折半查找时，查找成功和查找失败的最多比较次数相同，均为 $⌈ lo g_{2} (n + 1) ⌉$

分块查找

分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各自的优点，既有动态结构，又适于快速查找。

分块查找的基本思想：将查找表分为若干子块。块内的元素可以无序，但块间的元素是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。

分块查找的过程分为两步：

在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；
在块内顺序查找。

设索引查找和块内查找的平均查找长度分别为 $L_{I}$ ， $L_{S}$ ，则分块查找的平均查找长度为 $A S L = L_{I} + L_{S}$

用顺序查找查索引表

则 $L_{I} = (1 + 2 + \dots + b) / b = \frac{b + 1}{2}$ ， $L_{S} = (1 + 2 + \dots + s) / s = \frac{s + 1}{2}$ ，则 $A S L = \frac{b + 1}{2} + \frac{s + 1}{2} = \frac{s ^{2} + 2 s + n}{2 s}$ 。当 $s = n$ 时，ASL 最小，为 $n + 1$ 。
用折半查找查索引表

则 $L_{I} = ⌈ lo g_{2} (b + 1) ⌉$ ， $L_{S} = (1 + 2 + \dots + s) / s = \frac{s + 1}{2}$ ，则 $A S L = ⌈ lo g_{2} (b + 1) ⌉ + \frac{s + 1}{2}$

二叉排序树(BST)

Tip

构造一棵二叉排序树的目的并不是为了排序，而是为了提高查找、插入和删除关键字的速度，二叉排序树这种非线性结构也有利于插入和删除的实现。

定义

二叉排序树（也称二叉查找树）(BST，Binary Search Tree)是一棵空树，或者是具有下列特性的二叉树：

左子树结点值<根结点值<右子树结点值
左、右子树分别是一棵二叉排序树。

对二叉排序树进行中序遍历，可以得到一个递增的有序序列。

typedef struct BSTNode {
    int key;
    struct BSTNode *lChild, *rChild;
} BSTNode, *BSTree;

查找

若二叉排序树非空，先将给定值与根结点的关键字比较，若相如果小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。

非递归实现

最坏空间复杂度： $O (1)$

BSTNode *BST_Search(BSTree T, int key) {
  while (T != nullptr && key != T->key) {
    T = key < T->key ? T->lChild : T->rChild;
  }
  return T;
}

递归实现

最坏空间复杂度： $O (h)$ ，h 为递归树的深度

BSTNode *BST_Search(BSTree T, int key) {
  if (T == nullptr)return nullptr;
  if (key == T->key) {
    return T;
  } else if (key < T->key) {
    return BST_Search(T->lChild, key);
  } else {
    return BST_Search(T->rChild, key);
  }
}

插入

若原二叉排序树为空，则直接插入；否则，若关键字 k 小于根结点值，则插入到左子树，若关键字 k 大于根结点值，则插入到右子树。

递归实现

最坏空间复杂度： $O (h)$ ，h 为递归树的深度

int BST_Insert(BSTree &T, int key) {
  if (T == nullptr) {
    T = new BSTNode();
    T->key = key;
    T->lChild = T->rChild = nullptr;
    return 1;
  } else if (key == T->key) {
    return 0;
  } else if (key < T->key) {
    return BST_Insert(T->lChild, key);
  } else {
    return BST_Insert(T->rChild, key);
  }
}

插入的结点一定是一个新添加的叶结点，且是查找失败时的查找路径上访问的最后一个结点的左孩子或右孩子。

构造

不同的关键字序列可能得到同样的二叉排序树，也可能得到不同样的二叉排序树。

void Creat_BST(BSTree &T, int str[], int n) {
  T = nullptr;
  for (int i = 0; i < n; i++) {
    BST_Insert(T, str[i]);
  }
}

删除

在二叉排序树中删除一个结点时，不能把以该结点为根的子树上的结点都删除，必须先把被删除结点从存储二叉排序树的链表上摘下，将因删除结点而断开的二叉链表重新链接起来，同时确保二叉排序树的性质不会丢失。

若被删除结点 z 是叶结点，则直接删除，不会破坏二叉排序树的性质。
若结点 z 只有一棵左子树或右子树，则让 z 的子树成为 z 父结点的子树，替代 z 的位置。
若结点 z 有左、右两棵子树，则令 z 的直接后继（或直接前驱）替代 z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。

查我效率分析

二叉排序树的查找效率，主要取决于树的高度。

平衡二叉树(AVL)

定义

为了避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除结点时，要保证任意结点的左、右子树高度差的绝对值不超过 1，将这样的二叉树称为平衡二叉树(Balanced Binary Tree)，或称 AVL 树。

结点左子树减去右子树的高度的值为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是-1、0 或 1。

插入

每当在二叉排序树中插入（或删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点 A 再对以 A 为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。

插入位置可查看二叉排序树的插入

每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点作为根的子树。

Tip

在插入操作中，只需将最小不平衡二叉树调整平衡，则其它祖先节点都会恢复平衡。因为插入操作会导致“最小不平衡子树”高度+1，经过调整后高度恢复。

LL 平衡旋转(右单旋转)

由于在结点 A 的左孩子(L)的左子树(L)上插入了新结点，A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要一次向右的旋转操作。

将 A 的左孩子B 向右上旋转代替 A 成为根结点，将 A 结点向右下旋转成为 B 的右子树的根结点，而 B 的原右子树则作为 A 结点的左子树。

RR 平衡旋转（左单旋转）

由于在结点 A 的右孩子(R)的右子树(R)上插入了新结点，S 的平衡因子由-1 减至-2，导致以 A 为根的子树失去平衡，需要一次向左的旋转操作。

将 A 的右孩子B 向左上旋转代替 A 成为根结点，将 A 结点向左下旋转成为 B 的左子树的根结点，而 B 的原左子树则作为 A 结点的右子树。

LR 平衡旋转（先左后右双旋转）

由于在 A 的左孩子(L)的右子树(R)上插入新结点， A 的平衡因子由 1 增至 2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。

先将 A 结点的左孩子 B 的右子树的根结点 C 向左上旋转提升到 B 结点的位置，然后把该 C 结点向右上旋转提升到 A 结点的位置。
- 若插入结点在 C 的右子树上
- 若插入结点在 C 的左子树上，处理方式与右子树一样
RL 平衡旋转（先右后左双旋转）

由于在 A 的右孩子(R)的左子树(L)上插入新结点， A 的平衡因子由-1 减至-2，导致以 A 为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。

先将 A 结点的右孩子 B 的左子树的根结点 C 向右上旋转提升到 B 结点的位置，然后把该 C 结点向左上旋转提升到 A 结点的位置

查找

在平衡二叉树上进行查找的过程与二叉排序树的相同。因此，在查找过程中，与给定值进行比较的关键字个数不超过树的深度。

平衡二叉树的平均查找长度为 $O (lo g_{2} n)$

删除

与平衡二叉树的插入操作类似，以删除结点 w 为例来说明平衡二叉树删除操作的步骤：

用二叉排序树的方法对结点 W 执行删除操作。
若导致了不平衡，则从结点 w 开始向上回溯，找到第一个不平衡的结点 z （即最小不平衡子树）；y 为结点 z 的高度最高的孩子结点；x 是结点 y 的高度最高的孩子结点。
然后对以 z 为根的子树进行平衡调整，其中 x、y 和 z 可能的位置有 4 种情况：
- y 是 z 的左孩子，x 是 y 的左孩子（LL，右单旋转）
- y 是 z 的左孩子，x 是 y 的右孩子（LR，先左后右双旋转）
- y 是 z 的右孩子，x 是 y 的右孩子（RR，左单旋转）
- y 是 z 的右孩子，x 是 y 的左孩子（RL，先右后左双旋转）
这四种情况与插入操作的调整方式一样。不同之处在于，插入操作仅需要对以 z 为根的子树进行平衡调整；而删除操作就不一样，先对以 z 为根的子树进行平衡调整，如果调整后子树的高度减 1，则可能需要对 z 的祖先结点进行平衡调整，甚至回溯到根结点（导致树高减 1）。

红黑树(RBT)

平衡二叉树 AVL，插入和删除操作很容易破坏平衡特性，需要频繁地调整树的形态。为此在 AVL 树的平衡标准上进一步放宽条件，引入了红黑树的结构。

红黑树 RBT，插入和删除操作很多时候不会破坏红黑树的特性，无需频繁地调整树的形态、即使需要调整，一般可以在常数级时间内完成。

总结

平衡二叉树：适用于以查为主，很少插入和删除的场景；

红黑树：适用于频繁插入和删除的场景，实用性更强；

定义和性质

红黑树是二叉排序树。

红黑树满足如下红黑性质：

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

struct RBNode {
    int key;
    RBNode *parent;
    RBNode *lChild;
    RBNode *rChild;
    int color; // 结点颜色，可用0/1 表示黑红
};

结点的黑高bh：从某结点出发（不含该结点）到达一个叶结点的任意一个简单路径上的黑结点总数。

黑高的概念是由性质 5 确定的。根结点的黑高称为红黑树的黑高。

Tip

结论 1：从根到叶结点的最长路径不大于最短路径的 2 倍。

当从根到任意一个叶结点的简单路径最短时，这条路径必然全由黑结点构成。当某条路径最长时，这条路径必然是由黑结点和红结点相间构成的，此时红结点和黑结点的数量相同。

结论 2 ：若根节点黑高为 h，内部结点数（关键字）最少有 $2^{h} - 1$ 个。

查找

查找的过程与二叉排序树和平衡二叉树相同。

Tip

结论 3 ：有 n 个内部结点的红黑树的高度 $h \leq 2 lo g_{2} (n + 1)$ 。

从根到叶结点（不含叶结点）的任何一条简单路径上都至少有一半是黑结点，因此，根的黑高至少为 $h /2$ ，于是有 $n ⩾ 2^{h /2} - 1$ 。

可得红黑树查找操作的时间复杂度= $O (lo g_{2} n)$

插入

红黑树的插入过程和二叉查找树的插入过程基本类似，不同之处在于，在红黑树中插入新结点后需要进行调整（主要通过重新着色或旋转操作进行），以满足红黑树的性质。

Tip

结论：新插入红黑树中的结点初始着为红色

假设新插入的结点初始着为黑色，那么这个结点所在的路径比其他路径多出一个黑结点，调整起来也比较麻烦。如果插入的结点是红色的，此时所有路径上的黑结点数量不变，仅在出现连续两个红结点时才需要调整，而且这种调整也比较简单。

案列：

删除

红黑树的插入操作容易导致连续的两个红结点，破坏性质 4。而删除操作容易造成子树黑高的变化（删除黑结点会导致根结点到叶结点间的黑结点数量减少），破坏性质 5。

红黑树删除操作的时间复杂度为 $O (lo g_{2} n)$ 。
红黑树中删除结点的处理方式与二叉排序树的删除一样。但红黑树中删除结点后可能破坏“红黑树特性”，此时需要调整结点颜色、位置。

B 树

7.4_1_B 树

定义

B 树，又称多路平衡查找树，B 树中所有结点的孩子个数的最大值称为 B 树的阶，通常用 m 表示。所谓 m 阶 B 树是所有结点的平衡因子均等于 0 的 m 路平衡查找树。

一棵 m 阶 B 树可能是空树，也可能是满足如下特性的 m 叉树：

树中每个结点至多有 m 棵子树，即至多含有 m-1 个关键字。
若根结点不是终端结点，则至少有两棵子树。
除根结点外的所有非叶结点至少有 $⌈ m /2 ⌉$ 棵子树，即至少含有 $⌈ m /2 ⌉ - 1$ 个关键字。
所有的叶结点都出现在同一层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）。
所有非叶结点的结构如下：
- $K_{i} (i = 1, 2, \dots, n)$ 为结点的关键字，且满足 $K_{1} < K_{2} < \dots < K_{n}$ ；
- $P_{i} (i = 0, 1, \dots, n)$ 为指向子树根节点的指针，且指针** $P_{i} - 1$ 所指子树中所有结点的关键字均小于 $K_{i}$ ， $P_{i}$ 所指子树中所有结点的关键字均大于 $K_{i}$ **；
- n （ $⌈ m /2 ⌉ ⩽ n ⩽ m - 1$ ）为结点中关键字的个数；

Tip

当整棵树只有 1 个元素时，根节点只有两个分叉，所以根结点不用保证至少有 $⌈ m /2 ⌉$ 棵子树。

高度

一般情况下，B 树的高度不包括最后的叶结点（失败节点）。

若 $n ⩾ 1$ ，则对任意一棵包含 $n$ 个关键字、高度为 $h$ 、阶数为 $m$ 的 B 树：

最小高度： $h ⩾ lo g_{m} (n + 1)$

让每个结点尽可能的满，则 $n ⩽ (m - 1) (1 + m + m^{2} + m^{3} + \dots + m^{h - 1}) = m^{h} - 1$ ，因此 $h ⩾ lo g_{m} (n + 1)$ 。
最大高度： $h ⩽ (lo g_{⌈ m /2 ⌉} \frac{n + 1}{2}) + 1$

让各层的分叉尽可能少，即根节点只有 2 个分叉，其它结点只有 $⌈ m /2 ⌉$ 个分叉。因此第一层 1 个结点；第二层至少有 2 个结点；第三层至少有 $2 ⌈ m /2 ⌉$ 个结点；第 $h$ 层至少有 $2 (⌈ m /2 ⌉)^{h - 2}$ 个结点。第 $h + 1$ 层至少有 $2 (⌈ m /2 ⌉)^{h - 1}$ 个叶子结点（失败结点）。

因为n 个关键字的 B 树必有 n+1 个叶子结点，则 $n + 1 ⩾ 2 (⌈ m /2 ⌉)^{h - 1}$ ，得 $h ⩽ (lo g_{⌈ m /2 ⌉} \frac{n + 1}{2}) + 1$ 。

n 个关键字的 B 树必有 n+1 个叶子结点

原理跟前面折半查找的“n 个圆形的非叶结点有 n+1 个方形的叶结点”一样，都是用关键字切割 $(- \infty, + \infty)$ 然后得到各个区间，这个区间就是失败结点。

插入

将关键字 key 插入 B 树的过程如下：

定位：找出插入该关键字的最底层中的某个非叶结点（在 B 树中查找 key 时，会找到表示查找失败的叶结点，这样就确定了最底层非叶结点的插入位置）。
插入：在 B 树中，每个非失败结点的关键字个数都在区间内。插入后的结点关键字个数小于 m，可以直接插入；插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于 m-1 时，必须对结点进行分裂。
分裂：取一个新结点，在插入 key 后的原结点，从中间位置（ $⌈ m /2 ⌉$ ）将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（ $⌈ m /2 ⌉$ ）的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致 B 树高度增 1。

Tip

插入位置一定是“终端结点”

以 5 阶 B 树为例，该树的结点关键字个数 $2 ⩽ n ⩽ 4$ 。

插入 80
插入 90
插入 99
插入 88
插入 83，87
插入 70
插入 92，93，94
插入 73，74，75

删除

删除操作一定会导致叶节点的变化。

若被删关键字不在终端结点中时，可以用直接前驱或直接后继来替代被删除的关键字。

直接前驱：当前关键字左侧指针所指子树中“最右下”的关键字。

例如下图中 80 的直接前驱就是 77，因此删除 80 只需用 77 顶替 80 即可，顶替后要记得删去终端结点的 77。

直接后继：当前关键字右侧指针所指子树中“最左下”的关键字。

例如下图中 77 的直接后继就是 82。

对非终端结点关键字的删除，必然可以转化成对终端结点的删除操作。
若被删除关键字在终端结点：
1. 直接删除该关键字
  
  若被删关键字所在结点的关键字个数 $⩾ ⌈ m /2 ⌉$ ，则可以直接删去该关键字。
2. 兄弟够借
  
  若被删关键字所在结点删除前的关键字个数 $= ⌈ m /2 ⌉ - 1$ ，且与该结点相邻的右兄弟结点或左兄弟结点的关键字个数 $⩾ ⌈ m /2 ⌉$ ，则需要调整该结点的兄弟结点或左兄弟结点及其双亲结点（父子换位法），以达到新的平衡。
  
  换句话说，当右兄弟很宽裕时，用当前结点的后继、后继的后继来填补空缺；当左兄弟很宽裕时，用当前结点的前驱、前驱的前驱来填补空缺；
3. 兄弟不够借
  
  若被删关键字所在结点删除前的关键字个数 $= ⌈ m /2 ⌉ - 1$ ，且此时与该结点相邻的左、右兄弟结点的关键字个数均 $= ⌈ m /2 ⌉ - 1$ ，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并。
  
  在合并过程中，双亲结点中的关键字个数会减 1。若其双亲结点是根结点且关键字个数减少至 0，则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到 $⌈ m /2 ⌉ - 2$ ，则又要与它自己的兄弟结点进行调整或合并操作。
  
  假设要删除 49
  
  右兄弟不够借，只能合并。
  
  由于 73 所处的结点不满足 B 树的性质，继续合并。
  
  根节点变空了，直接删除根节点。

B+树

B+ 树是应文件系统所需而产生的 B 树的变形，B+ 树更加适用于实际应用中操作系统的文件索引和数据库索引，因为 B+ 树的磁盘读写代价更低，查询效率更稳定。

一棵 m 阶的 B+树需满足下列条件：

每个分支结点最多有 m 棵子树（孩子结点）；
非叶根结点至少有两棵子树，其他每个分支结点至少有 $⌈ m /2 ⌉$ 棵子树；
结点的子树个数与关键字个数相等；
所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来（因此支持顺序查找）；
所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针；

m 阶的 B+树与 m 阶的 B 树的区别：

- 在 B+树中，具有 n 个关键字的结点只含有 n 棵子树；
- 在 B 树中，具有 n 个关键字的结点含有 n+1 棵子树；
- 在 B+树中，根结点关键字个数 $1 ⩽ n ⩽ m$ ，其它结点的关键字个数 $⌈ m /2 ⌉ ⩽ n ⩽ m$ ；
- 在 B 树中，根结点关键字个数 $1 ⩽ n ⩽ m - 1$ ，其它结点的关键字个数 $⌈ m /2 ⌉ - 1 ⩽ n ⩽ m - 1$ ；
- 在 B+树中，叶结点包含全部关键字，非叶结点中出现的关键字也会出现在叶结点中；
- 在 B 树中，各结点包含的关键字是不重复的；
- 在 B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
- 在 B 树中，结点都包含了关键字对应记录地址的存储地址；

Tip

B+树是应数据库所需而出现的一种 B 树的变形树。

在 B+树中，非叶结点不含有该关键字对应记录的存储地址，可以使一个磁盘块能够包含更多个关键字，使 B+树的阶更大，树更矮，读磁盘次数更少，查找更快。

散列查找（哈希查找）

散列表的基本概念

散列表（Hash Table）：又称哈希表，是一种数据结构。特点是关键字与其存储地址直接相关。
散列函数：把查找表中的关键字映射成该关键字对应的地址的函数，记为 Hash(key)=Addr。

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。如下图所示，

冲突总是不可避免的。

理想情况下，对散列表进行查找的时间复杂度为 $O (1)$ ，即与表中元素的个数无关。

散列函数的构造方法

散列函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于散列表的大小或地址范围。
散列函数计算出来的地址应该能等概率、均匀地分布在整个地址空间中，从而减少冲突的发生。
散列函数应尽量简单，能够在较短的时间内计算出任意一个关键字对应的散列地址。

散列函数设计目标：尽量降低不同关键字产生冲突的可能性。

直接定址法

直接取关键字的某个线性函数值为散列地址，散列函数为 $H (k ey) = k ey$ 或 $H (k ey) = a \times k ey + b$ 。式中，a 和 b 是常数。

这种方法不会产生冲突，它适合关键字的分布基本连续的情况。若关键字分布不连续，空位较多，则会造成存储空间的浪费。
除留余数法

假定散列表表长为 m，取一个不大于 m 但最接近或等于 m 的质数 p，利用以下公式把关键字转换成散列地址。散列函数为 $H (k ey) = k ey % p$

除留余数法的关键是选好 p，使得每个关键字通过该函数转换后等概率地映射到散列空间上的任意一个地址，从而尽可能减少冲突的可能性。

质数

质数又称素数，一个大于 1 的自然数，除了 1 和它自身外，不能被其他自然数整除的数；
数字分析法

设关键字是 r 进制数（如十进制数），r 个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。

这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。
平方取中法

取关键字的平方值的中间几位作为散列地址。

具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀， 适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

查找

散列表的查找过程与构造散列表的过程基本一致。

对于一个给定的关键字 key，根据散列函数计算出其散列地址。检测查找表中相应地址位置上是否有记录，若无记录，返回查找失败；若有记录，与 key 值进行比较，相等则返回查找成功标志，不相等则返回查找失败。

对同一组关键字，即使使用相同的散列函数，则不同的处理冲突的方法得到的散列表不同，它们的平均查找长度也不同。

散列表的查找效率的度量仍以平均查找长度作为衡量。因为散列表在关键字与记录的存储位置之间建立了直接映像，但由于”冲突”的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。

散列表的查找效率取决于三个因素：散列函数、处理冲突的方法、装填因子。

装填因子

散列表的装填因子一般记为 $α$ ，定义为一个表的装满程度， $α =$ 表中记录数 $n$ / 散列表长度 $m$

散列表的平均查找长度依赖于散列表的装填因子 $α$ ，而不直接依赖于 $n$ 或 $m$ 。

$α$ 越大，表示装填的记录越“满”，发生冲突的可能性越大，反之发生冲突的可能性越小。

处理冲突的方法

开放定址法

开放定址法，是指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放。其数学递推公式为

H_{i} = (H (k ey) + d_{i}) % m

$i$ 为第 $i$ 次发生冲突， $i = 0, 1, 2, \dots, k (k ⩽ m - 1)$ ； $m$ 表示散列表表长； $d_{i}$ 为增量序列；

Tip

如果遇到空位置还没有查找到元素，就可以确定查找失败了。

Tip

删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填入散列表的同义词结点的查找路径。我们可以将被删结点添加一个标记，在逻辑上进行删除。

计算查找失败的平均查找长度时，遇到删除节点应该继续往后查找。

如何确定增量序列：

线性探测法

$d_{i} = 0, 1, 2, 3, \dots, m - 1$ 。冲突发生时，顺序查看表中下一个单元，直到找出一个空闲单元（当表未填满时一定能找到一个空闲单元）或查遍全表。
由于 $H (k ey)$ 的取值为 0~13，所有查找失败时可能对应的地址有 13 个。
- 对于地址为 0 的关键字，需要比较 1 次即可确定该关键字不在哈希表中，因为该地址没有元素（若该地址有元素则需要比较到地址 13，即比较 14 次才能确定）。
- 对于地址为 1 的关键字，需要从地址 1 比较到地址 13，即需要比较 13 次才能确定该关键字不在哈希表中（若地址 13，14 有元素，则需要比较到地址 15 才能确定不在哈希表中，即比较 15 次）。
- 其他元素同理。
线性探测法容易造成大量元素在相邻的散列地址上“聚集”（或堆积）起来，大大降低了查找效率。
平方探测法

$d_{i} = 0^{2}, 1^{2}, - 1^{2}, 2^{2}, - 2^{2}, \dots, k^{2}, - k^{2}$ 时，称为平方探测法，又称二次探测法，其中 $k ⩽ m /2$ ，散列表长度 m 必须是一个可以表示成 $4 k + 3$ 的素数。

平方探测法比线性探测法更不易出现”堆积”问题，但它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。
伪随机序列法

当 $d_{i}$ 伪随机数序列时，称为伪随机序列法。

再散列法

又称再哈希法

当第一个散列函数 $H (k ey)$ 得到的地址发生冲突时，则利用下一个散列函数计算该关键字的新地址，直到不冲突为止。此时，

H_{i} = R H_{i} (k ey)

这种方法不易产生“聚集”，但增加了计算的时间。

拉链法

又称链接法、链地址法。

对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。

由上图可知，冲突越多，查找效率越低。

😶‍🌫️ Notes

探索

最近

TS 笔记

常用工具函数

Promise和Async

Express实现用户认证

事件循环(Event Loop)

在 Express 中使用 Mongose

查找

查找的基本概念

顺序查找

折半查找

分块查找

二叉排序树(BST)

定义

查找

插入

构造

删除

查我效率分析

平衡二叉树(AVL)

定义

插入

查找

删除

红黑树(RBT)

定义和性质

查找

插入

删除

B 树

定义

高度

插入

删除

B+树

散列查找（哈希查找）

散列表的基本概念

散列函数的构造方法

查找

处理冲突的方法

开放定址法

再散列法

拉链法

关系图谱

目录