查找

顺序查找/线性查找

顺序查找

按照顺序查找是否存在目标元素。

当每个元素的查找概率相同时，顺序查找成功的 平均查找次数 ASL 为 $\sum_{i=1}^n P_{i}*(n-i+1) = \frac{n+1}{2}$ ，查找失败的 $ASL$ 为 $n+1$ 时间复杂度为 .

若表中的关键字有序，则不必查找到末尾，只要查找到小于/大于给定关键字的位置即可，则其超找成功的平均查找次数不变，查找失败的平均查找次数为 $\sum_{j=1}^nQ_{j}*j= \frac{1+2+\cdots+n+n}{n+1}= \frac{n}{n+1}$ ，其中 $Q_{j}$ 为在第 $j$ 个位置查找失败的概率，等概率的情况下为 $\frac{1}{n+1}$ .

折半查找/二分查找

tip

顺序查找的平均查找次数太大，如果在存储是将 关键字 按照一定的顺序进行存储，则不需要这么多的查找次数。

假设表的关键字是 从小到大 排序的，则可以直接直接对比中间的关键字，若目标关键字更小，则在左侧以同样的方式查找，代码实现上可以使用左右两个指针表示查找的区间范围

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

折半查找也可以使用二叉树进行存储，其查找次数不会超过树高，因此其时间复杂度为 $O(\log_{2}n)$ .

查找成功的平均查找长度为 $\sum_{i=1}^nP_{i}l_{i}=P_{i}\sum_{j=1}^hj* 2^{j-1}= \frac{n+1}{n}\log_{2}(n+1)-1$ ，这里 $\frac{1}{n}$ 表示等概率， $j*2^{j-1}$ 表示第 $j$ 层中的所有元素被查找成功的概率，因为其所在层有 $2^{j-1}$ 个元素，前面的 $j$ 则表示查找次数， $h$ 表示树高，其值为 $h=[\log_{2}(n+1)]$ .

分块查找/索引顺序查找

tip

吸取了顺序查找和折半查找的优点，即有动态结构，又能快速查找。

基本思想是将查找表分为若干块，块内无序，而块间是整体有序的，查找过程也分为两步，先查找数据在哪个块，再查找数据的在块中的位置；因此需要一个额外的索引表，表示分块中最大的关键字（如果是从小到大的顺序）和分块的起点在整个查找表当中的索引。

若将查找表均匀地分为 $b$ 块，每块中有 $s$ 个记录，等概率情况下，在块内和索引表中使用顺序查找，平均查找长度为

ASL=L_{1}+L_{2}=\frac{{b+1}}{2}+\frac{{s+1}}{2}=\frac{{s^2+2s+n}}{2s}

若 $s=\sqrt{ n }$ ，则取得最小值 $\sqrt{ n }+1$ .

树型查找

二叉排序树/BST

tip

思想类似于上文的二分查找，不过使用树形结构表示，可以动态地插入或者和修改节点；其要求左子树、根和右子树整体有序，而左子树和右子树也是一个二叉排序树。

note

下文所说的所有二叉树的排序顺序都默认从小到大。

插入代码

注意高亮部分是一个引用

int insert(BiTree &T, KeyType k) {
	if (T == NULL) {
		T = init_node(k);
		return 1;
	} else if (k == T -> data) {
		return 0; // 失败
	} else if (k < T -> data) {
		return insert(T->lchild, k);
	} else
		return insert(T->rchild, k);
}

构造代码

void init(BiTree &T, str[], int n) {
	T = NULL;
	int i =0;
	while (i < n) {
		insert(T, str[i]);
		i++;
	}
}

删除代码

删除操作比较复杂，按照三种情况处理：

被删除节点叶节点，则直接删除；
只有一棵子树，则直接让子树成为父节点的子树，代替该节点；
有两棵子树，可以在右子树中寻找一个最小的节点 $t_{0}$ 来代替该节点（因为根据二叉排序树的性质，该位置的键值应该小于所有右子树的）；同时需要调整一下树的形状，从图上来看有一个旋转的操作，实际上是由于 $t_{0}$ 的双亲一定大于它，因此双亲此时应该成为 $t_{0}$ 的 右子树；而 $t_{0}$ 如果有右子树的话，应该成为其双亲的左子树； $t_{0}$ 一定没有左子树。

插入删除的时间复杂度都是 $\log_{2}(n)$ .

二叉排序树的查找效率主要取决于树的高度，在最坏的情况下，构造时的数据是有序的，则会形成一个倾斜的单叉树，相当于顺序查找，其查找成功的平均查找长度与每层的节点个数有关，为

ASL=\frac{1}{n}\sum_{i=1}^hi*num(i)

其中 $h$ 表示树高， $num(i)$ 表示第 $i$ 层的节点个数。

平衡二叉树

tip

为了解决上文中的特殊场景下形成单叉树的情况，需要对树的高度之差进行限制，需要保证 左右子树高度之差不超过 1；

定义左子树和右子树的高度之差为 平衡因子，取值有 $-1, 0, 1$ .

插入

插入完成之后如果高度之差大于 $1$ ，则需要对树的结构进行调整，分析方式与上文二叉排序树一致，一般分为几种类型：

LL 平衡旋转（右单旋转）：插入节点插入到不平衡节点（平衡因子非法） $t_{0}$ 的左子树的左子树中，此时对 $t_{0}$ 的左子树的左子树太高（实际上可能仍是合法的，太高是相对于不平衡节点的右子树而言的，后同），需要进行右旋，让 $t_{0}$ 的左子树 $t_{1}$ 代替 $t_{0}$ 的位置，而 $t_{0}>t_{1}$ ，因此 $t_{0}$ 成为 $t_{1}$ 的右子树，而原本 $t_{1}$ 的右子树 $t_{2}$ 大于 $t_{1}$ 小于 $t_{0}$ ，成为 $t_{0}$ 的左子树；
RR 平衡旋转（左单旋转）：类似的操作；
LR 平衡旋转（先左后右旋转）：插入节点插入到不平衡节点（平衡因子非法） $t_{0}$ 的左子树的右子树中，对比第一种方式，其将 $t_{1}$ 的右子树作为旋转后 $t_{0}$ 的左子树，由于本身右子树并没有超高，因此无所谓，而对于现在这种情况，是 $t_{0}$ 的左子树的右子树太高，因此首先要对以 $t_{1}$ 为根的平衡二叉树的右子树进行一次左旋，再以 $t_{0}$ 进行右旋；
RL 平衡旋转（先右后左旋转）：类似的操作。

总结一下

旋转调整操作与树高的对应关系如下：

旋转操作	情形
LL	左子树的左子树太高
RR	右子树的右子树太高
LR	左子树的右子树太高
RL	右子树的左子树太高

可以将旋转操作想象为 提拉，例如 $L L$ 平衡旋转，是因为左子树的左子树太高了，因此可以将往右侧调整一下，而 $LR$ 平衡旋转是因为左子树的右子树太高了，同样进行右旋时需要将被提拉节点的右子树置为其原双亲的左子树，这样转换到右边依旧超高，只是平衡因子换了正负号，因此要先对左子树向左侧调整，再整体向右调整。

删除

删除操作与二叉搜索树一致，但是要沿着搜索路径回溯并检查平衡因子，并进行相应地调整；由于平衡因子定义为 左子树树高减去右子树树高，很容易得到结论：若节点的平衡因子大于 $1$ ，则说明左子树太高了，因此需要调整其左子树，同理若平衡因子小于 $-1$ ，则说明右子树太高了，依照此类方式再根据上文中的旋转操作进行调整即可。

note

通过插入和删除的操作可以看出来，二叉平衡树不适合于增删频繁的使用场景，这实际上是用插入时间来换查找时间。

插入相关代码如下：

// 右旋操作
TreeNode* rightRotate(TreeNode* node) {
    TreeNode* newRoot = node->left; // 新建变量保存左子树
    node->left = newRoot->right; // 使用左子树的右子树替换左子树。  
    newRoot->right = node; // 左子树的右指针连接 node 

    updateHeight(node);
    updateHeight(newRoot);
    return newRoot;
}

// 左旋操作
TreeNode* leftRotate(TreeNode* node) {
    TreeNode* newRoot = node->right;
    node->right = newRoot->left;
    newRoot->left = node;

    updateHeight(node);
    updateHeight(newRoot);
    return newRoot;
}

void insert() {
	...
    int balanceFactor = getBalanceFactor(root);

    // LL 左子树太高，且插入值小于左子树，也就是插入了左子树的左子树，进行右旋
    if (balanceFactor > 1 && value < root->left->value) { 
        return rightRotate(root);
    }

    // RR 右子树太高，且插入值大于右子树，也就是插入了右子树的右子树，进行左旋
    if (balanceFactor < -1 && value > root->right->value) {
        // 右右情况，进行左旋操作
        return leftRotate(root);
    }
	// LR 左子树太高，但插入值大于左子树，也就是插入了左子树的右子树
    if (balanceFactor > 1 && value > root->left->value) {
        // 左右情况，先对左子节点进行左旋，然后对根节点进行右旋
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

	// RL 右子树太高，但插入值小于右子树，也就是插入了右子树的左子树
    if (balanceFactor < -1 && value < root->right->value) {
        // 右左情况，先对右子节点进行右旋，然后对根节点进行左旋
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }
	...
}

红黑树

tip

二叉排序树为了保持平衡性，在插入和删除操作之后，需要非常频繁地调整树的结构，在经常插入的使用场景下开销很大，因此可以在二叉排序树的标准上进一步放宽条件，即红黑树。

红黑树可以看作是一种 2-3-4 树，只是将其中的多值节点拆成单节点，多叉树拆为二叉树。

2-3 树

tip

2-3 树是一种多路搜索树，是 $B$ - 树一个特例，一个满足二叉搜索树的性质，每个节点可以存放一个/两个键，每个节点有两个/三个孩子的树；2-3 树有两种不同的节点，2 - 节点和 3 - 节点，表示所存放的键个数和孩子的个数；对于 3 - 节点来说，设其所存储键为 $v_{1},v_{2}$ ，三个孩子的键是 $a_{1},a_{2},a_{3}$ ，则一定满足

a_{1}<v_{1}\leq a_{2}\leq v_{2}\leq a_{3}

此外， $B$ - 树还应该满足所有叶子节点都在同一层（底部）的性质。

插入

2-3 树的插入并不是直接插入新的节点，而是将插入值直接放入对应位置的节点，此时 2 - 节点会变成 3 - 节点；若对应位置是 3 - 节点，插入之后已经满了，则需要进行分裂。

分裂

对于已满的 3 - 节点，有以下处理：

该节点保留最小的值；
新建立一个节点，存储最大的值；
中间的值传递回父节点。

由于父节点可能是 2 - 节点或 3 - 节点，因此需要分情况讨论

若是 2 - 节点：插入中间值后变为三节点，并将新的节点作为其孩子；
若是 3 - 节点：3 - 节点的情况可能需要将递归进行，直到遇到根节点，方式与上面相同，但此时该节点就有“四个”孩子了，这是不合法的，因此需要继续分裂该节点；
父节点不存在：情况 2 遍历到根节点的情况，只需要新建一个节点存储即可。

删除

若要删除的节点是叶节点，则分为以下几种情况：

若为 3 - 节点，删除对应值，变为 2 - 节点；
若为 2 - 节点，且其兄弟节点为 3 - 节点，则需要向兄弟节点解一个值（因为 2 - 节点只有一个值，3 - 节点可以有两个或者三个值），并且要和其父节点的值交换，因为兄弟节点的值一定超过了父节点的值所规定的界限，因此要与对应的值进行交换；
若为 2 - 节点，且其兄弟为 2 - 节点，父节点为 3 - 节点，此时只能找父节点借一个值，添加在兄弟节点中，使其成为 2 - 节点；
若为 2 - 节点，且其兄弟、父节点都是 2 - 节点，则从父节点借一个值给其右孩子，此时父节点为空，执行删除操作即可（这应该是一个递归吧？）；

若删除节点不是叶节点，分为以下情况：

待续

2-3-4 树

待续

B - 树

使用场景

B - 树是一种 多路平衡查找树，不同于二叉平衡树和红黑树的数据全部存在主存中，当数据规模不断增大时，数据只能存在外存中，只能以块的形式读取，因此要尽可能的减少 I/O 次数；主要方式是通过多路的方式来限制树的高度。

特点

对于一个 $m$ 阶的 B - 树，其有以下特点：

每个节点内部最多有 $m$ 个子节点；
除了根，每个节点至少有 $m/2$ （向上取整，为了避免其退化为二叉树）个子节点；
若根是内部节点（内部节点没有明确定义，可以认为包含键就是内部节点），则至少包含两个子节点；
具有 $k$ 个子节点的节点有 $k-1$ 个键；
所有外部节点的层级相同，且不携带任何信息。

上文中所说的 2-3 树就是 3 阶 B - 树。

caution

原论文中认为叶子节点是包含键的最底层节点，外部节点指的是最底层节点的孩子，可以为空指针，也可以指向一些无关的东西，在 B + 树中外部节点存储了键的关联信息，是有用的。另一说外部节点就是叶子节点。

节点的键是升序存储的，因此在节点内部比较键值时，使用二分查找的方式。节点与其孩子的键值与其交替排序，具体可视为上文 2-3 树的推广。

插入

找到需要插入的节点，若其插入后键值过多（上溢），则需要进行分裂：找出插入后的中间值，传递给父节点，并以其为界限，分裂为两个节点，并作为父节点的两个孩子；此时如果父节点键值过多，执行相同的操作，向上递归到无此类情况为止。

删除

找到需要删除的节点，若是叶子节点直接删除，若不是则找到其直接前驱（左侧子节点的最右侧），二者交换，删除需要删除的节点；

此时如果发生下溢现象（节点中的键值过少），则需要看其左右兄弟有无富裕的节点，若有，执行旋转操作（在逻辑顺序上旋转，和平衡二叉树的旋转规则相当，可以以逻辑顺序看作一串珠子，哪边少就往哪边拉）；若左右兄弟都没有富裕节点，则需要执行合并操作：

从父节点借一个键过来，并和兄弟节点进行合并（合并节点是借过来这个节点的左右两个孩子），此时，父节点可能会因为借走一个节点而导致下溢的问题；
对父节点执行相同的操作：1. 左右兄弟有富裕则旋转；2. 左右兄弟无富裕则借其父节点进行合并；直至遍历到不发生下溢的情况。

info

解决下溢的时候可能发生父节点为空，删除即可。注意这里的旋转和合并都是处理下溢的操作，代码实现时写在一个接口中。

B+ 树

tip

进一步改进，由于读取磁盘的块大小有限，而 B - 树中每个节点都存储着数据块，占用较大的空间，因此 B + 树的非叶子节点只存储键而不存储数据，因此其会更加矮胖一点；且 B - 树不适合遍历，因此 B+ 树中叶子节点也会形成一个双向链表，比较适合范围查找。

由于 B + 树非叶子节点不存储数据，其查询时间固定为 $\log_{2}n$ ，而 B - 树是情况而定。

散列表

tip

上文提到的查找基本上都建立在比较的基础上，因而查找效率取决于查找次数，而散列表在理想状态下查找的时间复杂度是 $O(1)$ ，其底层是一个数组，通过 散列函数 将关键字映射到其对应的地址；然而当散列函数设计的不够好或者数据量过大时，会发生 碰撞、冲突 ，这是不可避免的，因此除了设计好的散列函数外，还需要一定的处理冲突的方式。

散列函数

设计散列函数时，需要注意以下几点：

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

一般常用散列方法有

直接定址法，取关键的某个线性函数 $H(key)=a key+b$ ，适用于关键字分布 基本连续 的情况，否则可能会造成空间浪费；
除留余数法，最简单常用的方式，假定散列表长为 $m$ ，取一个不大于 $m$ 但最接近 $m$ 的质数 $p$ ，使用公式 $H(key)=key\%p$ ；本方法的关键是就选好 $p$ ，从而使得映射地址均匀分布；
数字分析法，若关键字是 $r$ 进制数，而 $r$ 个数码在各位上出现的频率是不同的，因此需要构造相应的散列函数；
平方取中法，将关键字的平方的中间几位数作为散列地址，取多少位视情况而定，适用于关键字眉尾取值都不够均匀或均小于散列地址所需的位数。

处理冲突

再次强调

任何散列函数都不能避免冲突，当冲突发生时必须以某种方式寻找下一个空的地址直到找到空地址为之。

一般使用 开放定址法，数学递推公式为

H_{i}=(H(key)+d_{i})\%m

其中 $d_{i}$ 为增量序列，通常有以下四种取法：

线性探测法：即 $d_{i}=0,1,2,\cdots,m-1$ ，冲突发生是直接查看下一个地址是否空闲，直到找出一个空闲地址或遍历完整表，但是可能造成堆积可能；
平方探测法： $d_{i}=0,1,-1,2,-2,\cdots,k^2,-k^2$ ，其中 $k\leq \frac{m}{2}$ ，散列表长度 $m$ 须是一个可以表示称 $4k+3$ 的素数，又称为 二次探测法；可以避免堆积，但是不能探测到散列表的所有单元（至少能探测到一半）；
双散列法： $d_{i}=Hash_{2}(key)$ ，再使用一个散列函数计算该关键字的 地址增量，则总散列函数为 $H_{i}=(H(key)+i\times Hash_{2}(key))\%m$ ，初始探测位置 $H_{0}=H(key)\%m$ ；双散列法中，最多经过 $m$ 次探测会回到 $H_{0}$ 位置；
伪随机序列法： $d_{i}$ 为伪随机数序列。

另一种方式是使用 拉链法，类似与图的邻接表法，使用一个指针数组存储，冲突时向后添加关键字即可。

平均查找长度

所有关键字的平均查找次数，记作 $ASL$ ，主要取决于三个因素：散列函数、冲突处理方式和装填因子。

装填因子

即散列表中所存储的记录数量占总表长百分比。

顺序查找/线性查找​

折半查找/二分查找​

分块查找/索引顺序查找​

树型查找​

二叉排序树/BST​

平衡二叉树​

红黑树​

2-3 树​

2-3-4 树​

B - 树​

B+ 树​

散列表​

散列函数​

处理冲突​

平均查找长度​

装填因子​