查找算法

阿杰 like coding bug ❥约 10180 字大约 34 分钟

下面代码和示例都默认使用整数类型。

查找的概念

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

查找的结果只能有两种，分别为查找成功和查找失败，前者表示在查找表中寻找到了满足条件的元素，后者表示没有在查找表中寻找到满足条件的元素。

这里出现的查找表就是用于查找的数据集合，其由同一类型的元素组成。

查找表有两种分类分别为：

静态查找表：对查找表只有查找操作，不存在修改元素的操作。
动态查找表：对查找表有动态地插入和删除。

适合静态查找表的查找算法有：折半查找、顺序查找、散列查找等。

适合动态查找表的查找算法有：二叉排序树的查找、散列查找等。

适合静态和动态查找表中都存在散列查找，这是因为其有个的概念，当某刻的装填因子大于规定的阈值时，会对散列表进行扩容操作！

我们查找是根据关键字来进行查找的，那什么是关键字呢？

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

举个例子：以全体中国人做例子，什么数据项可以作为一个中国人的唯一标识呀？肯定就是身份证号撒。没错，身份证号就可以作为查找某个人的关键字！

在查找算法这节中，有个评判查找算法效率的重要指标，这节的重点也是它！它就是。

平均查找长度：在查找过程中，一次查找的长度是指一次查找某个元素需要比较的关键字次数，而平均查找长度则是所有查找过程中进行关键字比较次数的平均次数。

其数学定义式为：

$ASL = \sum_{i=1}^{n} P_iC_i$

查找表的长度为 n，在上面 $ASL$ 的公式中， $P_i$ 表示查找第 i 个数据元素的概率，通常认为每个元素的查找概率相同，即 $P_i = \frac{1}{n}$ ， $C_i$ 是找到第 i 个元素需要进行比较的次数。

顺序查找

该查找算法又被称为“线性查找”，这个名字和之前学习的顺序存储很类似，其实其在逻辑上也是类似的。

和这个算法的名字一样“顺序（线性）”，就是从一侧到另一侧依次的查找呗！如果找到满足条件的元素则返回对应的索引，否则返回查找失败的信息，一般而言返回-1，因为索引是从 0 开始的。

void sequential_search(int *arr, int val, int len){
    for(int i = 0; i < len; i++){
        if(arr[i] == val){
            return i;
        }
    }
    return -1;
}

在王道书上提到了一个哨兵，其实就是牺牲一个单位空间来替代 if 判断，这样就只需要从后往前遍历，直接返回 val 的 index 则可。其实原理都是一样的，无需纠结。

平均查找长度：

查找成功：在查找表长度为 n 的情况下，查找 val 到与第 i 个元素相同时，因为有 n 个元素，故 $P_i = \frac{1}{n}$ ，比较次数 $C_i=i+1$ ，故有：

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

查找失败：因为查找失败只能有一次，就是遍历完所有元素都不满足条件，需要比较 n 次，故有：

$ASL_{查找失败}=n$

补充

王道书上的 $ASL_{查找失败}=n+1$ 的原因是使用了“哨兵”，有 n 个元素再加上一个“哨兵”，故需要比较 n+1 次。

顺序查找的优缺点：

优点：对数据的存储形式没有要求，既可以是顺序存储又可以是链式存储，对查找表中记录的有序性也没有要求，有序无序都可以使用该算法。
缺点：当查找表中的元素个数 n 较大时，其平均查找长度较大，效率较低。

在这里查找每个元素的概率都是相同的，但是实际情况中更多的是概率不同，所以在遇到具体的问题还需要具体的分析！

上面的顺序查找是在查找表中关键字无序情况下进行的，所以查找需要遍历整个查找表。

只要使查找表中的关键字有序，则可以进行优化，提前结束遍历！

int sequential_better_search(int *arr, int val, int len) {
    if (len == 0 || val < arr[0] || val > arr[len - 1]) {
        return -1;  // 快速失败
    }
    for (int i = 0; i < len; i++) {
        if (arr[i] == val) {
            return i;
        }
        if (i < len - 1 && arr[i] < val && arr[i + 1] > val) {
            break;  // 提前终止
        }
    }
    return -1;
}

可以使用一颗判定树来描述有序线性表的查找过程。

判断树：是一种用于描述查找算法执行过程的二叉树，其中每个节点代表一次关键字的比较操作，分支代表比较结果（左分支为“小于”，右分支为“大于”或“等于”），叶子节点代表查找的成功或失败。
对于有序线性表的查找（如顺序查找、折半查找），判定树可以直观展示所有可能的查找路径和比较次数。

现在将对一个有序表进行查找，其形成的判定树如下：其中圆形结点表示有序表中存在的元素，矩形结点表示失败结点，其描述为不在表中数据值的集合。若找到了矩形结点则说明查找失败！

由此可知，有序序列中的 n 个元素会将整个关键字区间划分为 n+1 个子区间，故矩形结点必有 n+1 个！

平均查找长度：

查找成功：此时查找成功和没有优化的顺序查找一样。故有：

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

查找失败：因为矩形结点是虚拟的，故并不用对其进行比较，所以比较次数等于其上面的一个圆形结点的层数，查找不成功的平均长度在相等查找概率下有：

$ASL_{查找失败}=\sum_{i=i}^{n}P_iC_i=\frac{1}{n+1}(1+2+3+...+n+n)=\frac{n}{2}+\frac{n}{n+1}$

只要牢记 ASL 的定义，就不会出现问题！

折半查找

折半查找又被称为“二分查找”。要使用折半查找的话，对应的查找表必须是的！

核心思想是：比较要查找的元素 val 和查找表的中间元素，若小于则到左侧寻找，若大于则到右侧寻找，往后的查找都使用这种方式进行。在取中间元素时，既可以向下取整又可以向上取整，但在每次查找过程中要相同，这在做题时需要注意。

这样的话，每比较一次就可以缩小一半的查找范围，十分的高效。

int half_search(int *arr, int val, int len){
    //因为是有序的，首先过滤一遍val
    if(val < arr[0] || val > arr[len - 1] || len == 0){
        return -1;
    }
    //区间可以为[low, high]或者[low, high)，这两者实现的代码有些许不同
    int low = 0;
    int high = len - 1;
    while(low <= high){
        //避免溢出
        int mid = low + (high - low) / 2;
        if(arr[mid] < val){
            low = mid + 1;
        }
        if(arr[mid] > val){
            high = mid - 1;
        }
        if(arr[mid] == val){
            return mid;
        }
    }
    return -1;
}

在使用折半查找时，查找表要满足随机存取和有序的特性！故只有顺序存储的有序线性表可以使用，而链式存储的线性表不行。

该算法的判定树如下：

根据判定树进行分析 ASL：

可知判定次数一定不会超过该判定树的高！

在有序表中有 n 个元素和等概率的条件下，有：

$ASL_{查找成功}=\frac{1}{n}(1+2*2+3*2^{h-1}+...+h*2^{h-1})=\frac{n+1}{n}log_2(n+1)-1≈log_2(n+1)-1$

其中，h 为树的高度。有 n 个元素的二叉树高为 $log_2⌈n+1⌉$ ，故折半查找的时间复杂度为： $O(log_2n)$ 。

对于查找失败和查找成功的 ASL 需要根据的情况进行计算：

举个上面判定树中的例子说明：

$ASL_{查找成功}=\frac{1}{6}(1 + 2 * 2 + 3 * 3) = \frac{14}{6}=\frac{7}{3}$

$ASL_{查找失败}=\frac{1}{7}(2 + 3 * 6)=\frac{20}{7}$

所以在计算 ASL 时可以将其判定树画出来，问题就可以轻松解决了！

分块查找

分块查找又被称为“索引顺序查找”。该算法吸收了折半查找和顺序查找各自的优点！既有动态结构又可以快速查找。

核心思想是：将查找表分为若干个子块，块内元素可以无序，但块间元素是有序的，即前一个块中的最大关键字小于后一个块中的最小关键字，建立一个索引表，其中存储着每个块的开始索引和对应块中的最大元素。在查找过程中，首先根据索引表查找到对应的块，然后在块中进行顺序查找或折半查找。

分块查找的平均查找长度为

设：索引查找和块内查找的平均查找长度分别为 $L_I和L_S$ 。

则有：

$ASL_{查找成功}=L_I+L_S$

我们将这个公式再进行展开：

如果将长度为 n 的查找表分为 b 块，每块有 s 个记录，则有：

$ASL_{查找成功}=L_I +L_S = \frac{b+1}{2} + \frac{s + 1}{2}=\frac{s^2+2s+n}{2s}$

根据均值不等式可知：当 $s = \sqrt{n}$ 时，有： $ASL_{平均查找长度min}=\sqrt{n}+1$ 。

虽然索引表会使用额外的存储空间，但是为其带来了效率上的提升，这是典型的空间换时间！

树形查找

树形查找：是一种基于树形数据结构实现的查找算法，它利用树的分层特性将数据组织成具有层次关系的结构，从而大幅提升查找效率（尤其是动态数据的查找、插入和删除操作）。

二叉排序树（BST）

BST 存在的意义是什么？不可能平白无故地构造一个 BST 吧！我们思考一下，在之前的顺序查找过程中是属于线性的，可以归结为“一条路走到黑”，而在折半查找过程中因为每次从中间元素比较，可以构造为一颗二叉判定树，其时间复杂度被优化为 $O(log_2n)$ ，但是折半查找要的是查找表关键字有序，那我们可以不可以思考一下怎样可以让一个无序的查找表时间复杂度也可以被优化成 $O(log_2n)$ 呢？

没错，救赎之道就在这里——BST！

构造一颗 BST，就可以提高查找、删除、插入关键字的效率，而且不管这个查找表中的关键字是有序还是无序，只要构造为了一颗 BST，一切就好起来了。

BST 的定义：

又被称为二叉查找树，其可以是一颗空树或者具有一下特征的二叉树：

若左子树非空，则左子树上所有结点的值都小于根结点的值。
若右子树非空，则右子树上所有结点的值都大于根结点的值。
左、右子树也分别是一颗 BST。

因为左子树的结点值<根结点值<右子树结点值，故若使用中序遍历一颗 BST 可以得到一个递增的有序序列！

BST 的查找：
因为可以视为二叉树的查找且有目标性（直到从左子树还是从右子树进行查找），可以利用递归！也可以使用迭代，在这里使用递归，因为代码简单。

//定义结构体
typedef struct bst_tree_node {
    int data;
    struct bst_tree_node *left_child, *right_child;
}BST_TREE_NODE;

BST_TREE_NODE *bst_search(BST_TREE_NODE *root, int val) {
    if (root == NULL) {
        return NULL;
    }
    if (val < root->data) {
        return bst_search(root->left_child, val);
    }
    if (val > root->data) {
        return bst_search(root->right_child, val);
    }
    if (val == root->data) {
        return root;
    }
}

在 BST 中进行查找，显然比较次数不会超过树高，和折半查找类似，但是这个树高是不能确定的！若查找表中的元素非常合适，构造的 BST 为一颗近似于完全二叉树的形式，则其时间复杂度显然为： $O(log_2n)$ ，但是在某些时候，给定的查找表元素会让 BST 退化为一条链表形式，此时时间复杂度为： $O(n)$ 。前者的平均查找成功长度和 $O(log_2n)$ 成比例，后者的平均查找成功长度和顺序查找的一样为 $\frac{n+1}{2}$ 。

在具体的计算中可以构建好 BST 树然后根据定义进行计算则可。

BST 的插入：

BST 是一颗“动态”的二叉树，其特点是树形结构不是一次性形成的，而是在寻找的过程中，若树中不存在满足条件的关键字时，将该关键字插入到合适的位置。

插入的过程是：如果根为空，则直接插入；否则，给定关键字小于根结点值则插入到左子树，给定关键字大于根结点值则插入右子树，新插入的结点一定是叶子结点。

以下是递归和迭代实现方式。

void insert_bst(BST_TREE_NODE **root, BST_TREE_NODE *node) {
    if (node == NULL)
		return;
    if (*root == NULL) {
        *root = node;
        return;
    }
    BST_TREE_NODE *current = *root;
    while (1) {
        if (node->data < current->data) {
            if (current->left_child == NULL) {
                current->left_child = node;
                break;
            }
            current = current->left_child;
        } else if (node->data > current->data) {
            if (current->right_child == NULL) {
                current->right_child = node;
                break;
            }
            current = current->right_child;
        } else {
			//已存在时，释放要插入的元素
            free(node);
            break;
        }
    }
}
void insert_bst(BST_TREE_NODE **root, BST_TREE_NODE *node){
	if(node == NULL){
		return ;
	}
	if(*root == NULL){
		*root = node;
		return ;
	}
	if(val < (*root)->data){
		insert_bst(&((*root)->left_child), node);
	}else if(val > (*root)->data){
		insert_bst(&((*root)->right_child), node);
	}else{
		free(node);
	}
}

BST 的构造：

将一个查找表中的元素构造为一颗 BST 不外乎就是一直向 BST 根结点中插入元素。

void build_bst(BST_TREE_NODE **root, BST_TREE_NODE **nodes, int len) {
    *root = NULL;
    for (int i = 0; i < len; i++) {
        insert_bst(root, nodes[i]);
    }
}

相信理解了 BST 的插入和寻找，这个是非常容易理解的！

BST 的删除：

在删除了某个结点后不是笼统的将其和子树结点一起删除，而是只删除该结点并使 BST 保持原本的性质。

在这里就会出现 3 种情况了：

删除叶子结点：直接删除则可，并不会影响任何东西，这是最爽的😛。
删除的结点只有一颗子树（不管是左还是右，反正只有一颗）：那么在删除了该结点后要将子树的根结点补上。
删除的结构有两颗子树：在删除该结点后使用该结点中序遍历序列的直接前驱或者直接后继补上，这样就可以转换为前两种情况了！

注意

因为一个根结点的直接前驱会跑到左子树的最右侧的节点，必为上面的两种情况之一，同理，直接后继也是这样的情况。

前两种情况较为简单，则只举第三种情况的例子。

平衡二叉树（AVL）

BST 在某些时候会退化为链表，故引入平衡二叉树，避免出现这种情况。

AVL：可以是一颗空树或者满足以下性质的二叉树：

平衡二叉树的左右子树也是一颗平衡二叉树
左右子树的高度只差不超过 1，也就是 $-1\le 平衡因子 \le1$
AVL 中结点值关系和 BST 一致（左小、根中、右大）

每个结点中的数值就为该结点的平衡因子（左右子树高度之差）。

AVL 的插入：

AVL 的性质比 BST 的严格多了，所以在插入结点后被破坏了性质而进行的操作也比 BST 的操作复杂许多！

会涉及到 RR、LL、RL、LR 这四种操作。下面一一来说明什么情况下使用什么操作。

AVL 插入的过程：先和 BST 一样，找到合适的位置插入，但是这个插入可能会导致平衡因子的绝对值大于 1，此时引入下面 4 种操作！注意每次操作都是在最小不平衡子树上进行的。

最小不平衡子树：在插入路径上离插入结点最近的平衡因子绝对值大于 1 的结点作为根的子树。

下面的操作的最小不平衡子树的根结点为 A。

RR（左单旋操作）：新结点在 A 的右孩子的右子树上插入，A 的右孩子为 B，则需要将 B 代替 A 作为根结点，A 作为 B 的左孩子，B 原本的左子树作为 A 的右子树。
LL（右单旋操作）：新结点在 A 的左孩子的左子树上插入，A 的左孩子为 B，则需要将 B 代替 A 作为根节点，A 作为 B 的右孩子，B 原本的右子树作为 A 的左子树。
RL（右左双旋操作）：新结点在 A 的右孩子的左子树上插入，A 的右孩子为 B，B 的左子树的根结点为 C，则需要先将 C 进行右旋操作，让 C 代替 B 的位置，然后再对 C 进行左旋操作，代替 A 的位置。
LR（左右双旋操作）：新结点在 A 的左孩子的右子树上插入，A 的左孩子为 B，B 的右子树的根结点为 C，则需要先将 C 进行左旋操作，让 C 代替 B 的位置，然后再对 C 进行右旋操作，代替 A 的位置。

具体的例子：单次操作和多次操作的各举一个例子，比较简单，理解一下则可。

AVL 的构造：

构造就是不断地插入结点，若插入的节点导致不满足 AVL 的性质时，使用上面的 4 中操作进行调整，直到要插入的结点全部插入。

AVL 的删除：

AVL 删除和 BST 的删除一样，不管多了一个判断平衡因子的步骤！

假设：删除 w 结点，判断该 AVL 是否平衡，若不平衡则从 w 开始向上回溯，找到的第一个不平衡的结点 z（最小不平衡子树的根）；y 是结点 z 高度最高的孩子结点，x 为结点 y 高度最高的孩子结点。

若 y 是 z 的左孩子，x 是 y 的左孩子，使用右单旋操作。
若 y 是 z 的右孩子，x 是 y 的右孩子，使用左单旋操作。
若 y 是 z 的左孩子，x 是 y 的右孩子，使用左右双旋操作。
若 y 是 z 的右孩子，x 是 y 的左孩子，使用右左双旋操作。

这些操作都和 AVL 的插入如出一辙，就不再赘述了。

AVL 的查找：

这个和 BST 的查找一样，故其比较关键字的次数还是不超过 AVL 树的深度。

我们使用 $n_h$ 来表示深度为 $h$ 的 AVL 中含有最少的结点数，则有：

$n_0=0$ ；

$n_1=1$ ；

$n_2=2$ ;

因为有左右子树相差不能超过 1 的条件，我们可以知道， $n_h = n_{h-1}+n_{h-2}+1$ ，因此含有 $n$ 个结点的 AVL 最大深度为 $O(log_2n)$ 故平均查找效率为： $O(log_2n)$

说了最少结点数的情况，不得不说一下最多结点数的情况，显然是 AVL 为满二叉树时，结点数最多咯！

红黑树（RBT）

在 AVL 中插入或者删除一个结点后，会频繁地调整全树整体的拓扑结构，这样的代价是很大的，究其原因还是条件太过严格，故为了减小消耗，引入条件更加宽松的红黑树。

RBT：可以是一颗空树或者满足以下条件的二叉树：

每颗结点要么是红色的，要么是黑色的
根节点是黑色的
叶结点（虚构的外部结点，NULL 结点）
不存在两个相邻的红结点
满足 BST 结点值的关系
每个结点到任意叶子结点的简单路径上，所含有的黑色结点数相同

怎样描述 RBT 的特性的呢？使用黑高（bh），概念如下：

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

根据 RBT 的定义，我们可以知道几个关于 RBT的结论：

从根结点到叶子结点的最长路径不大于最短路径的 2 倍。原因：在最短时，路径上的所有结点都为黑色，而最长时，是红黑相间的，故最长的路径不会超过最短的路径 2 倍。
有 n 个内部结点的 RBT 的高度 $h\le2log_2(n+1)$ 。原因：因为在 $bh = h_b$ 时，RBT 的最少内部结点数 $n_{min}=2^{h_b}-1$ 个，又因为 RBT 的 $h\le2h_b$ ，故在 RBT 的内部结点树高为 h 时有： $n \ge 2^{\frac{h}{2}} - 1$ ，化简后就为上面的结论。
新插入 RBT 的结点初始时为红色。原因：若插入结点为黑色则需要考虑每个结点到叶子结点的 bh 是否相等，调整起来很麻烦，而插入的新结点为红色的话，则只需要考虑相邻的结点是不是一样的红色，较为简单，而且只会在出现连续的两个红色结点才进行调整。

因为 RBT 是“适度平衡”，从 AVL 中每颗结点的子树高度相差不能超过 1 扩展到 RBT 每颗结点的子树相差不超过两倍，所以降低了调整的频率，维护的代价比收益小，故 RBT 在实际运用的很广！Java 中的 TreeMap和 TreeSet就是使用 RBT 实现的。

其查找的时间复杂度还是为： $O(log_2n)$ 。

红黑树的插入：

因为最基础的还是 BST，不过在这基础上进行优化了，所以插入的方式和 BST 的一样，但是若出现了违背 RBT 性质的结点出现则需要调整，调整的手段就是旋转+调色！

对于为什么会这样，有兴趣可以去搜索看看具体的证明，设计到了数学上面的证明，而我们是应试考试和使用者，明白这样使用就已经可以了，所以不用纠结为什么会这样，说白了，这样调整就是为了保持 RBT 的性质。

ok，下面来具体介绍怎样调整！

设插入的结点为 z，那么具体的插入过程如下：

若 z 的父结点是黑色的，则直接插入则可（不破坏红结点不相邻的性质）

若 z 插入的位置是 RBT 的根结点，则把 z 染成黑色并将高度加 1

若 z 的父结点是红色的，且 z 不是根结点，则分为两种情况：

先说明一下什么是叔结点和爷结点：

叔结点：父结点的兄弟节点

爷结点：父结点的父结点

叔结点为黑色：则进行旋转+染色：以爷结点为根，判断插入的新结点为什么类型（LL、LR、RR、RL），是什么类型就进行对应的旋转操作。染色操作：若为 LL、RR，因为是将父结点和爷结点交换，故将原本的父结点和爷结点进行染色（染成相反的颜色）；若为 LR、RL，因为是将插入的新结点和爷结点交换，故将原本的新结点和爷结点进行染色（染成相反的颜色）。
叔结点为红色：则进行染色+变新：将父结点、叔结点、爷结点进行染色（染成相反的颜色），然后视爷结点为新结点进行再次判断。

RBT 的删除：

我们现在只需要知道 RBT 的删除操作时间复杂度为： $O(log_2n)$ ，并且 RBT 的删除操作和 BST 的删除操作一样，不过删除后将 RBT 的性质破坏了需要进行调整操作。

删除操作比插入操作更复杂，后期会在这里补上（需要的话）。

B 树和 B+树

对于 B 树和 B+，需要将重点放在 B 树上，B+树在考研中只会出概念题。

B 树

为什么会引出 B 树呢？为了解决传统树形结构在磁盘存储系统中效率低下的问题而被提出来的！

传统的树形结构在数据量大时树高很高，会增加磁盘 IO 操作，B 树会增加一个结点的分支使得树更矮、更宽，这样是便于磁盘 IO 操作的，还有其他的优点，这里就不赘述了。

需要说明的是：m 阶 B 树表示所有结点子树高度相同的 m 路平衡查找树（说 B 树就是默认 m 阶 B 树，只是后者显示表示其最多有 m 颗子树）。

平衡查找树 是一种 自平衡的、有序的树形数据结构，用于高效存储和检索数据。它在动态插入、删除操作后能自动调整结构，确保最坏情况下的时间复杂度保持为 O(log n)

常见的平衡查找树有：AVL、RBT、B 树。对于不同的平衡查找树会有不同的约束条件！

简单解释一下：

对于 AVL ，约束条件是任意一颗结点的左右子树高度差不能相差 1。

对于这里的 B 树，约束条件是每个结点的子树高度相同，结点关键字个数和子树个数限制。

B 树的定义：为空树或者满足以下性质的 m 叉树：

树中每个结点最多有 m 个子树，最多有 m - 1 个关键字
若树中不是只有一个根结点，则根结点至少有 2 颗子树，至少有 1 个关键字
除了根结点外，其余的内部结点至少有 $⌈\frac{m}{2}⌉$ 颗子树，至少有 $⌈\frac{m}{2}-1⌉$ 个关键字
所有叶子结点都在同一层上，并且不存在信息（视其为折半查找判定树中的失败结点，其并不存在，是虚构的，也就是外部结点）

因为每个结点中有最多关键字和最少关键字，故可以推导：

设：一颗关键字个数为$n(n\ge1) $，高度为$ h $，阶数为$ m$的 B 树

若要使该 B 树的高最大，则每个结点中的关键字数要最少，子树个数也要最少。每个结点的关键字最少为 $⌈\frac{m}{2} - 1⌉$ ，子树最少为 $⌈\frac{m}{2}⌉$ ，故有 $n+1\ge 2*⌈\frac{m}{2}^{}⌉^{h-1}$ ，所以可以得到： $h\le log_{⌈\frac{m}{2}⌉}((\frac{n+1}{2})+1）$
若要使该 B 树的高最小，则每个结点中的关键字数要最多，子树个数也要最多。每个结点的关键字最多为 $m-1$ ，子树个数最多为 $m$ ，故有 $n\le m^h-1$ ，所以可以得到： $h\ge log_m(n+1)$

最终得到 h 的取值范围： $log_m(n+1)\le h\le log_{⌈\frac{m}{2}⌉}((\frac{n+1}{2})+1)$ ！

B 树的查找：

和 BST 的查找类似，只不过内部结点会有多个关键字。

因为 B 树常存储在磁盘上，所以在查找关键字时，需要先在磁盘上找到目标结点，然后将结点中的数据放到内存中采用顺序查找或者折半查找，故目标结点在 B 树上的层数决定了 B 树的查找效率（因为磁盘上查找比内存中查找慢得多）。

查找的过程：

先查找根结点，若找到了则返回查找成功，否则到满足条件的子树中去找（和 BST 一样，只不过多了几个范围罢了），一直到找到目标关键字或者找到叶子结点为止。

B 树的插入：（分裂）

B 树的插入比 BST 的插入更复杂，因为将关键字插入到终端结点后可能导致不在满足 B 树的性质，因为除根结点外每个结点关键字个数最多有 $m-1$ 个，所以如果插入结点后违背了这条性质就需要进行调整！

设插入的结点为 w。

首先需要找到关键字插入的终端结点，如果在对应的终端结点中插入新结点后其关键字数仍小于等于 $m-1$ ，则结束；

否则先将关键字插入再将该终端结点从 $⌈\frac{m}{2}⌉$ （结点第 1 个关键字在 1 处，以此类推）处分裂，左侧关键字保留在该终端结点中，右侧关键字放到一个新的结点中，终端结点中 $⌈\frac{m}{2}⌉$ 处的关键字提高到父结点中，若父结点被提入一个关键字后有破坏了最多关键字的性质，则重复此过程知道满足性质为止（最多提升到根结点，使得树高增加 1）。

B树的删除：（合并）

因为除根节点外每个结点的关键字个数最少要有： $⌈\frac{m}{2}-1⌉$ 个，所以如果删除结点后违背了这条性质就需要进行调整！

当删除的关键字 k 不在终端结点时，在将 k 删除后会使用 k 的前驱结点或者后继结点进行补充，故最终可以将删除关键字的后果转移到终端结点上，我们就只用讨论在终端结点上删除的可能了。

若删除终端结点上的关键字后，被删的终端结点中关键字数仍然大于等于 $⌈\frac{m}{2}-1⌉$ ，则直接结束。
若删除终端结点上的关键字后，被删的终端结点中关键字数小于 $⌈\frac{m}{2}-1⌉$ ，但是兄弟结点（左右都行）的关键字数大于 $⌈\frac{m}{2}-1⌉$ ，也就是说有兄弟“够借”，就会先从父结点中拿一个关键字到删除关键字的终端结点中，然后再从兄弟那拿一个关键字到父结点中（注意兄弟结点和父结点拿的关键字）。
若删除终端结点上的关键字后，被删的终端结点中关键字数小于 $⌈\frac{m}{2}-1⌉$ ，但是兄弟结点（左右都行）的关键字数小于等于 $⌈\frac{m}{2}-1⌉$ ，也就是说所有兄弟都“不够借”，则将该终端结点的关键字删除后，让这个终端结点合并一个兄弟结点+父结点中的一个关键字进行合并（注意父结点选择的关键字）。

同样的，在取了父结点中的一个关键字后可能会造成父结点不满足性质，还是使用合并的方法进行处理，直到满足性质（最多将 B 树根结点删除，使得树高减少 1）。

设有一个 3 阶 B 树，我们对其进行插入和删除操作，看看会调整为什么样！

对 3 阶 B 树插入 14，则调整为：

对 3 阶 B 树删除 46，则调整为（合并右兄弟）：

B+树

大名鼎鼎的 MySql 中的 InnoDB 引擎底层就是使用的 B+树！

B+树：是应数据库所需而诞生的一种 B 树的变形树。

一颗 m 阶的 B+树应满足下列条件：

每个分支结点最多有 m 颗子树
非叶根结点至少有 2 颗子树，其余分支结点至少有 $⌈\frac{m}{2}⌉$ 颗子树
结点的子树棵数和关键字个数相等
所有叶子结点中包含全部关键字以及只想相应记录（一般指数据存储的磁盘地址）的指针，叶子结点中将关键字有序排列，并且相邻叶子结点按大小顺序相互连接起来（支持顺序查找）
所有分支结点中仅包含它各个子结点中关键字最大值以及指向子结点的指针

B+树中的所有分支结点仅其索引作用，只存在对应子树的最大关键字和指向该子树的指针，不存在记录的地址，故一个磁盘块可以存储更多的关键字，使得磁盘 IO 操作次数更少，查找速度更快！

查找有两种方式：其一为从根结点开始的多路查找，其二为从关键字最小的节点开始在链表上顺序查找。

散列表

在之前学习的查找都是基于关键字的比较的，那我们能不能像访问数组一样直接的访问想要查询的关键字呢？

答案是肯定，这一节要学习的散列表就实现了这种功能。使用一种散列函数将要查找的关键字映射为存储的地址，就可以通过存储地址直接访问到。

定义

散列函数（哈希函数）：将查找表中的关键字映射为该关键字对应的地址的函数。

散列表：根据关键字而直接进行访问的数据结构，也就是建立了关键字和存储地址之间的一种直接映射关系。

因为可以直接访问关键字的存储地址，故使用散列表进行查找的时间复杂度为： $O(1)$ 。

构造哈希函数

但是散列表也不全是优点，在数据量大并且哈希函数取得不好的情况下，会发生“冲突”（多个关键字映射到同一个地址）！

那怎样解决这个问题呢？在这里会介绍拉链法和开放地址法。但在介绍这些“冲突解决方案”前，让我们先来了解一下怎样“构造哈希函数”吧！

构造哈希函数是非常重要的，一个优秀的哈希函数会让“冲突”次数大大减少，相反地，一个差的哈希函数会让冲突充满整个映射过程！一般来说有以下 4 种构造方法：

直接定址法：取关键字的某个线性函数值为散列地址： $Hash(key)=a*key+b$ 。这种设计方法不会发生冲突，但如果 key 之间相差太多会造成空间的浪费。
除留余数法：取一个小于且最接近查找表长度 m 的质数 p，并使用后面的公式进行映射： $Hash(key)=key \% p$ 。使用这种方案可以尽可能地减少发生冲突的概率。
数字分析法：数字分析法适用于关键字本身由多位数字或字符组成的情况。其核心思想是分析关键字的各位分布规律，选取分布较为均匀的若干位作为散列地址。举个例子：假设关键字是 8 位十进制数字（如学号），统计发现前 3 位是学校编号（所有关键字相同），中间 2 位波动较小，后 3 位随机分布。则可直接取后 3 位作为散列地址
平方取中法：平方取中法通过将关键字平方后取中间几位作为散列地址。目的是利用平方运算扩大关键字的差异，使散列地址分布更均匀。举个例子：关键字为 123，散列地址需要 2 位，123 平方后的值为：15129，我们就可以取 51 作为该关键字的散列地址。

ok，在解决了怎样构造哈希函数后，我们来说说怎样处理“冲突”吧！

拉链法

因为可能有多个关键字会被映射到同一个存储地址，故可以将这些“同义词”用一个链表连起来！

这样散列表中存储的就为指向存入元素的指针了。

举个例子：关键字序列为{12，24，1，2，3}，散列函数为： $Hash(key)=key\%12$ 。

因为是链表故非常适合插入、删除操作多的情况。

开放地址法

开放地址法：如果一个关键字映射的地址已经存在另一个关键字了，则可以以一种方式取另一个地址用于存放该关键字。

数学递推公式为：

$H_i = (H(key) +d_i)\%m$

$m$ 为散列表的长度， $d_i$ 为增量。

开放地址法中又可以分为 4 种具体的实现方式。

线性探测法： $d_i$ 以线性增长 $（d_i=1,2,3...,m-1）$ 的方式探测对应的地址是否存在关键字，只要表没有被填满就一定可以找到一个没有存储关键字的地址。其缺点也很大，可能会让本该在第 i 个散列地址的元素存到第 i+1 个散列地址，本该在 i+1 地址的元素又存到了 i+2 个散列地址，以此类推，造成大量的元素在相邻的散列地址上“聚集”起来，使得查找效率大大降低！
平方探测法： $d_i$ 以平方增长 $（d_i=1^2,-1^2,2^2,-2^2...,k^2,-k^2）$ 的方式探测，需要散列表长度 m 必须为可以表示为 $4*k+1$ 的素数。这种方式可以解决上面方法存在的“堆积”问题，缺点是不能探测所有的元素，但至少可以探测一半的元素。
双散列法：需要使用两个散列函数，当通过第一个散列函数发生“冲突”时，则利用第二个散列函数计算 $d_i$ ,其散列函数为： $H_i=(Hash_1(key)+i*Hash_2(key))\%m$ ，其中 i 为发生冲突的次数，初始值为 0。
伪随机序列法： $d_i$ 为伪随机序列。

在使用开放地址法时，不能随意地物理删除表中的已有元素，因为在查找时是遇到满足条件的元素或者为空时结束，如果物理删除了某个元素则可能导致查找中断！解决方式是：使用一个删除标记进行逻辑删除，这样做的副作用是空间利用率会下降；在多次的逻辑删除后，虽然散列表看起来比较满，但是有许多空间并没有被真正地利用。

散列表查找与性能分析

查找过程：和构造类似，也是通过散列函数，传入要查找的关键字计算出散列地址。

检查地址上是否存储有记录，若没有记录则查找失败；若有记录且关键字相同则返回查找成功；若有记录但是关键字不相同，则需要根据给定的处理冲突方法进行探测。

影响散列表查找效率的因素：散列函数、处理冲突的方法、装填因子。

装填因子：一般定义为α，用于形容一个散列表的装满程度。

$α=\frac{表中的记录数}{散列表长度}$

散列表的平均查找长度（ASL）依赖是α 而不是“表中的记录数”或“散列表长度”，使两者的共同作用！

当然α 越大表示散列表越“满”，此时就更容易发生冲突，故需要制定在α 大于多少时对散列表进行扩容！