index¶

【考频统计】：

年份	考点	分值
2009	`AVL`定义及其性质、B树	单选2*2=4分
2010	折半查找法、`AVL`插入操作、散列表（大题）	单选2*2+应用题10=\(14\)分
2011	`BST`查找操作、散列表	单选2*2=4分
2012	`AVL`定义及其性质、B树	单选2*2=4分
2013	【顺序查找法、`BST`查找操作】（应用题）、`AVL`插入操作、B树	单选2*3+应用题10=\(16\)分
2014	B树、散列表	单选2*2=4分
2015	折半查找法、`AVL`定义及其性质、`KMP`算法	单选2*3=6分
2016	B树和B+树	单选2分
2017	折半查找法、B+树	单选2*2=4分
2018	`BST`定义及其性质、B树、散列表	单选2*3=6分
2019	`AVL`插入与删除操作、散列表、`KMP`算法	单选2*3=6分
2020	`BST`插入与构造、B树	单选2*2=4分
2021	`AVL`插入操作、B树	单选2*2=4分
2022	B树删除操作、散列表	单选2*2=4分
2023	B树插入、删除、查找操作、折半查找法、散列表（插入再删除）	单选2*3=6分

【考点分析】：AVL考察7次，BST考察4次、B树考察10次、散列表考察6次、折半查找法考察4次；重点掌握各查找算法的ASL的计算！！！

AVL主要考察插入结点操作，删除操作只考察过一次且不是给出具体AVL树删除具体结点的形式，预测有可能出一道这样的选择题：给你一颗具体的AVL树，让你删除某个具体结点，问你调整形态后树的细节，例如根节点的左右孩子是谁这种问题；

B树是超级重要考点，定义性质和基本操作必须全部掌握，此外B+树只考察过两次，要注意它和B树的区别，该考点6年未考，可能与B树一起出个选择题；

散列表的平均查找长度也是常客，主要注意空位置的判断要算作一次比较以及开放定址法删除元素要留标记这两个点。

【未考冷门考点】

2022年新加入的红黑树有可能考，考察点可能为根据红黑树的性质判断谁是或者不是红黑树，记住口诀：“左根右、根叶黑、不红红、黑路同”即可；插入操作考的可能性不大；

分块查找尚未考察过，主要注意\(ASL_{成功}=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s}\), 当\(s=\sqrt{n}\)时，\(ASL_{最小} = \sqrt{n}+1\)（当\(n=10000\)时，\(ASL_{min}=101\)）即可；（注意有个+1）

KMP算法的求next数组或nextval数组；

散列表的拉链法的平均查找长度计算，注意若当前位置为空，查找次数为0，空指针不计入比较次数，注意与线性探测再散列法的空位计入次数对比；

散列表的平方探查法（二次探测再散列），\(d_i=±1^2、±2^2、±3^2\cdots±k^2\)

【查找算法一览表】

查找算法名称	顺序查找	折半查找	分块查找	二叉排序树\(BST\)	平衡二叉树\(AVL\)
适用范围或定义	顺序表(数组或链表)	有序数组有序链表不适合	块间有序块内无序	左孩子 < 根 < 右孩子	平衡因子\(≤1\)的\(BST\)
查找的时间复杂度	\(O(n)\)	\(O(logn)\)	\(O(\sqrt{n}+1)\)(\(s=\sqrt{n}\)的前提下)	最好为\(O(logn)\)	\(O(logn)\)
\(ASL_{成功}\)	\(\frac{n+1}{2}\)	\(log_2{(n+1)}-1\)相当于遍历到\(BST\)的内部结点；	\(ASL_{成功}\)（顺序）+\(ASL_{成功}\)（折半）（当(\(s=\sqrt{n}\)时，\(ASL_{min}=\sqrt{n}+1\)）
\(ASL_{失败}\)	\(n\);（等概率下，有序表与无序表的ASL不同，有序表查到失败即停止，无序表会遍历完表）	相当于遍历到BST的外部结点（注意不计算外部结点的比较次数）	\(ASL_{失败}\)(顺序)+\(ASL_{失败}\)（折半）
备注	在数据量小的时候很适合；对线性链表也很适用	关键字比较次数最多为：\(\left \lceil log_2(n+1) \right \rceil\)	能较快地查找又便于线性表动态变化	中序遍历得到有序序列；

6.1 查找的基本概念¶

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

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

关键字 —— 数据元素中唯⼀标识该元素的某个数据项的值，使⽤基于关键字的查找，查找结果应该是唯⼀的。

对查找表的常⻅操作

查找符合条件的数据元素，仅查找的话可以用静态查找表；
插⼊、删除某个数据元素，可以用动态查找表实现；

查找算法的评价指标：

查找⻓度——在查找运算中，需要对⽐关键字的次数称为查找⻓度

平均查找⻓度（ASL, Average Search Length）—— 所有查找过程中进⾏关键字的⽐较次数的平均值

\( ASL=\sum_{i=1}^{n} P_iC_i \)

\(P_i\) 是查找第\(i\) 个元素的概率，通常认为查找任何一个元素的概率都相等，即\(\frac{1}{n}\) , \(C_i\) 是查找第 \(i\) 个元素的比较次数；

使用不同的查找算法，求得的\(ASL\)也会不同， \(ASL\)具体分为查找成功和查找失败两种情况：

\(ASL_{成功}=\frac{总关键字比较次数}{查找元素个数}\) ， \(ASL_{失败} =\frac{总的失败结点比较次数}{不成功位置(失败结点)个数}\)

示例：

6.2 顺序查找与二分查找¶

6.2.1 顺序查找¶

一般线性表的顺序查找

算法思想：从头到尾挨个找；

普通实现：

typedef struct{  //查询表的数据结构(顺序表)
    int *elem;   //动态数组基址；
    int tablelen;   //表长
}SSTable;
//顺序查找
int seq_search(SSTable ST, int target) {
    for(int i = 0; i < ST.tablelen; ++ i) {
        if(ST.elem[i] == target) 
            return i;
    }
    return -1;   //查找失败返回-1；
}

以常规的思路实现顺序查找算法，每次查找都要进行两次判断，既要判断当前元素是否为目标元素，还要判断整张表是否查找完毕。这里给大家提供一种更高效的解决方案：在查找表中的一端添加目标元素，顺序查找算法从查找表的另一端执行。

也就是说将待查找元素放到表尾位置，然后从头开始查找，这样做的好处是，查找过程中不必判断整张表是否查找完毕，因为无论查找能否成功，顺序查找算法都能正常执行结束。数据结构中，将在查找表一端添加的目标元素称为监视哨(哨兵)。

王道中将其放在表头，然后从表尾开始扫描，我更喜欢将其放在表尾。

优化实现：

typedef struct{  //查询表的数据结构(顺序表)
    int *elem;   //动态数组基址；
    int tablelen;   //表长
}SSTable;
//顺序查找
int seq_search(SSTable ST, int target) {
    int i = 0;  //定义循环变量，避免超出for语句作用域；
    // elem需要至少分配tablelen+1个元素，以容纳哨兵；
    ST.elem[ST.tablelen] = target;  //设置“哨兵”
    while(ST.elem[i] != target) ++i;  //从前往后找；
    return i;  //查找成功则返回下标；查找失败则返回表长；
}

这样每次循环都少了一个判断，在数据量很大时，会比较省时间；

【查找效率分析】：\(ASL_{成功} = \frac{1+2+3+\cdots+n}{n} = \frac{n+1}{2}\), \(ASL_{失败} = n+1\)

顺序查找的优化（对有序表）

如果当前有序表是递增排序，从头往后找，如果发现第\(i\)个元素值小于\(target\), 而第\(i+1\) 个元素值大于 \(target\) ,则可以知道已经查找失败了；

int seq_search(SSTable ST, int target) {
    for(int i = 0; i < ST.tablelen; ++ i) {  //遇到大于target的元素时再结束查找；
        if(ST.elem[i] == target) return i;
        if(ST.elem[i] > target) break;  //有序表中已不可能继续找到target；
    }
    return -1;  //循环结束仍未找到时返回失败；
}

如图，用查找判定树来分析

如图，共有\(n+1\)种查找失败的情况，树中的矩形结点是“失败结点”，圆形结点表示有序线性表中存在的元素，即成功结点。

一个成功结点的查找长度 = 自身所在层数； 一个失败结点的查找长度 = 其父节点所在的层数；默认情况下，各种失败情况和成功情况都等概率发生；

优化后的顺序查找的效率分析：\(ASL_{成功} = \frac{1+2+3+\cdots+n}{n} = \frac{n+1}{2}\), \(ASL_{失败} = \frac{1+2+3+\cdots+n+n}{n+1} = \frac{n}{2}+\frac{n}{n+1}\)

如果每个元素被查的概率不相等的话，例如：

【注】：上述线性表的顺序查找可以是顺序存储结构(如数组)，也可以是链式存储结构(链表)，顺序查找的时间复杂度为 \(O(n)\)

6.2.2 折半查找¶

即二分查找，仅适用于有序顺序表；(顺序表可以随机存取，链表不行)

二分有很多模板与细节，这里我们仅研究左闭右闭的版本；更多细节请见：二分查找从入门到入睡

代码为：

int binary_search(vector<int> nums, int target) {
    int l = 0, r = nums.size() - 1, mid;
    while(l <= r) {
        mid = l + (r - l) / 2;  //中间位置；
        if(nums[mid] == target) return mid;  //查找成功返回坐标；
        else if(nums[mid] > target) r = mid - 1; //从前半部分继续查找；
        else l = mid + 1;  //从后半部分继续查找；
    }
    return -1;    //查找失败，返回-1；
}

程序终止时，

由此可见，\(nums[l]\) 是第一个大于\(target\)的元素；

查找效率分析：

\(ASL_{成功} = (1*1+2*2+3*4+4*4)/11=3\) , \(ASL_{失败} = (3*4+4*8)/ 12=\frac{11}{3}\)

【折半查找判定树的构造】：\(mid = \left \lfloor (low+mid)/2 \right \rfloor\) ,如果当前\(low\)和\(high\)之间有奇数个元素，则\(mid\)分割后，左右两部分元素个数相等；如果当前\(low\)和\(high\)之间有偶数个元素，则\(mid\) 分割后，左半部分比右半部分少一个元素；

在折半查找判定树中，如果\(mid = \left \lfloor (low+mid)/2 \right \rfloor\)，对于任何一个结点，必有：右子树结点 — 左子树结点 = 0/1；如果\(mid=\left \lceil (low+high)/2 \right \rceil\) , 对于任何一个结点，必有：左子树结点 – 右子树结点 = 0/1

折半查找判定树一定是平衡二叉树；

折半查找判定树只有最后一层不是满的，因此，元素个数为 \(n\) 时，树高 \(h=\left \lceil log_2(n+1) \right \rceil\)(不包含失败结点) , 查找成功的\(ASL≤h\), 查找失败的\(ASL≤h\)；

折半查找的时间复杂度\(O(log_2n)\)，平均情况下比顺序查找的效率高，特殊情况就不一定了，比如查找元素就在表头位置；

奇数：	偶数：

【优点与局限性】

二分查找在时间和空间方面都有较好的性能：

二分查找的时间效率高。在大数据量下，对数阶的时间复杂度具有显著优势。例如，当数据大小 \(n = 2^{20}\) 时，线性查找需要 \(2^{20} = 1048576\) 轮循环，而二分查找仅需 \(\log_2 2^{20} = 20\) 轮循环。
二分查找无需额外空间。相较于需要借助额外空间的搜索算法（例如哈希查找），二分查找更加节省空间。

然而，二分查找并非适用于所有情况，原因如下：

二分查找仅适用于有序数据。若输入数据无序，为了使用二分查找而专门进行排序，得不偿失。因为排序算法的时间复杂度通常为 \(O(n \log n)\) ，比线性查找和二分查找都更高。对于频繁插入元素的场景，为保持数组有序性，需要将元素插入到特定位置，时间复杂度为 \(O(n)\) ，也是非常昂贵的。
二分查找仅适用于数组。二分查找需要跳跃式（非连续地）访问元素，而在链表中执行跳跃式访问的效率较低，因此不适合应用在链表或基于链表实现的数据结构。
小数据量下，线性查找性能更佳。在线性查找中，每轮只需要 1 次判断操作；而在二分查找中，需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作；因此，当数据量 \(n\) 较小时，线性查找反而比二分查找更快。

6.2.3 分块查找¶

（注意，该考点未考过）

分块查找：又叫索引顺序查找，吸取了顺序查找和二分查找各自的优点，我们可以对数据集进行分块，使其分块有序，然后再对每一块建立一个索引项。分块有序具体是指

块内无序：也即块内的记录不要求有序
块间有序：要求第 \(n + 1\) 块中所有记录的关键字均大于第 \(n\) 块中所有记录的关键字

其中，每一块将对应一个索引表，它保存了每个分块的最大关键字和存储区间

数据结构定义为

typedef struct{
    int maxvalue;   //分块最大值；
    int low,int high;  //分块的存储区间；
}Index[100];  //定义结构体数组

查找时分两步进行

首先在索引表中查找待查找关键字所在的分块。由于索引表是块间有序的，因此可顺序、可二分；
接着在对应的块中查找目标值，由于块中大部分情况下是无序的，所以只能采用顺序查找

特别注意，即便在索引表上直接找到了元素，也仍然要进入块内查找，只有在块内找到才是真的找到。（注意这个，否则计算\(ASL\)容易出错）

【注意】：如果采用折半查找查索引：

如果\(mid\) 指针所指索引块里的最大关键字就是我们要找的，那么直接去\(mid\) 所指索引块内寻找即可；

如果索引表中不包含目标关键字，则根据二分查找的终止条件可知最终停在 \(low > high\) , \(low\) 指针所指的索引块是第一个关键字大于所找关键字的，而分块存储的索引表中保存的是各个分块的最大关键字，因此要去\(low\)指针所指索引块内去寻找；

如果程序终止时\(low\) 超出索引表范围，则查找失败；

【查找效率分析】：

假设，长度为\(n\)的查找表被均匀得分为 \(b\) 块，每块含有 \(s\) 个元素；

设索引查找和块内查找的平均长度分别为 \(L_I,L_S\) ,则分块查找的平均查找长度为：\(ASL = L_I+L_S\)

用顺序查找查索引表，则\(L_I=\frac{1+2+3+\cdots+b}{b}=\frac{b+1}{2}\), \(L_S=\frac{1+2+3+\cdots+s}{s}=\frac{s+1}{2}\)

由于\(n=s\*b\), 所以有 \(ASL_{成功}=\frac{b+1}{2}+\frac{s+1}{2}=\frac{s^2+2s+n}{2s}\), 当\(s=\sqrt{n}\)时，\(ASL_{最小} = \sqrt{n}+1\)（当\(n=10000\)时，\(ASL_{min}=101\)）

用折半查找查索引表，则\(L_I=\left \lceil log_2(b+1) \right \rceil ,L_S=\frac{s+1}{2}\),则\(ASL_{成功}=\left \lceil log_2(b+1) \right \rceil +\frac{s+1}{2}\)

查找失败的\(ASL\)计算过于复杂，一般不会考，如果问你某个关键字的查找失败比较次数，注意细致分析就可以了；

【扩展】：上面介绍的分块查找的查找表是顺序表（数组），对于插入删除元素很不方便，如果要实现“动态查找表”，可以考虑用链表来实现，如下图所示：

6.3 树型查找¶

6.3.1 二叉排序树(`BST`)¶

又叫二叉搜索树、二叉查找树(Binary Search Tree),满足以下条件：

对于根节点，左子树中所有节点的值 < 根节点的值 < 右子树中所有节点的值。
任意节点的左、右子树也是二叉搜索树，即同样满足条件 1. 。

中序遍历BST可以得到一个递增序列。

下面介绍BST的操作

1.【查找结点】¶

700. 二叉搜索树中的搜索

给定目标节点值 num ，可以根据二叉搜索树的性质来查找。我们声明一个节点 cur ，从二叉树的根节点 root 出发，循环比较节点值 cur.val 和 num 之间的大小关系

若 cur.val < num ，说明目标节点在 cur 的右子树中，因此执行 cur = cur.right 。
若 cur.val > num ，说明目标节点在 cur 的左子树中，因此执行 cur = cur.left 。
若 cur.val = num ，说明找到目标节点，跳出循环并返回该节点。

1.【非递归版】

//下面代码都是该结构体；
typedef struct TreeNode{
    int val;
    TreeNode *left,*right;
}TreeNode,*BSTree;

TreeNode *BST_Search(BSTree root, int num) {
    TreeNode* cur = root;
    while(cur != NULL) {    //循环查找，越过叶节点时跳出循环；
        if(cur->val < num) {  
            cur = cur -> right; //目标节点在cur的右子树；
        }else if(cur -> val > num) {
            cur = cur -> left; //目标结点在cur的左子树中；
        }else break;   //cur就是目标节点，跳出循环；
    }
    return cur;   //返回目标节点；
}

时间复杂度：\(O(h)\),\(h\) 为树高，最坏时为\(O(n)\),最好时为\(O(logn)\)

空间复杂度：该算法只用到了常数级别的辅助指针，因此为\(O(1)\)

【递归版】

TreeNode *BST_Search(BSTree root, int num) {
    if(root == NULL) return NULL;  //递归出口；
    if(root -> val > num) return BST_Search(root->left,num);  
    //如果当前结点值大于目标值，则递归查找它的左子树；
    else if(root -> val < num) return BST_Search(root->right,num);  
    //如果当前结点值小于目标值，则递归查找它的右子树；
    else return root;   //查找成功；
}

空间复杂度：主要是递归工作栈的开销，为\(O(h)\)

2.【插入结点】¶

701. 二叉搜索树中的插入操作

给定一个待插入元素 num ，为了保持二叉搜索树“左子树 < 根节点 < 右子树”的性质，插入操作分为两步：

查找插入位置：与查找操作相似，从根节点出发，根据当前节点值和 num 的大小关系循环向下搜索，直到越过叶节点（遍历至 \(NULL\) ）时跳出循环。
在该位置插入节点：初始化节点 num ，将该节点置于 \(NULL\) 的位置。

二叉搜索树不允许存在重复节点，否则将违反其定义。因此，若待插入节点在树中已存在，则不执行插入，直接返回。

【迭代写法】

void insert(BSTree &root, int num) {  //root是根指针的引用；
    if(root == NULL) {  //空树时直接创建根节点；
        root = new TreeNode{num, NULL, NULL};  
        return;
    }
    TreeNode *cur = root, *pre = NULL; 
    //cur用来寻找应该插入的位置，pre用来标记cur的父节点，为后面的插入新节点做准备；
    //寻找插入位置；
    while(cur != NULL) {
        if(cur -> val == num) return;  //如果找到了与待插入值相等的结点，则直接返回；
        pre = cur;
        if(cur -> val > num) {  //插入位置在cur的左子树；
            cur = cur -> left;
        }else{
            cur = cur -> right;  //插入位置在cur的右子树；
        }
    }
    //找到位置后开始执行插入操作；
    TreeNode *node = new TreeNode{num, NULL, NULL};  //创建新节点；
    if(pre -> val < num) pre -> right = node;  //连接新节点而不是整数值；
    else pre -> left = node;  //连接新节点而不是整数值；
}

【注】：为了插入节点，我们需要利用辅助节点 pre 保存上一轮循环的节点，这样在遍历至NULL时，我们可以获取到其父节点，从而完成节点插入操作。

复杂度与查找结点都相同；

【递归写法】

TreeNode* insert(BSTree &root, int num) {  //root是根指针的引用；
    if(root == NULL) {  //如果根节点为空；
        root = new TreeNode{num, NULL, NULL};  //通过引用更新空树或空子树；
        return root;  
    }
    if(root -> val == num) return root;   //如果插入值与当前结点值相等则直接返回；
    else if(root -> val > num) root -> left = insert(root->left,num);
    else root -> right = insert(root -> right, num);  //补充递归参数；
    return root;
}

3.【构造`BST`】¶

//按照str[]中的关键字序列建立二叉排序树；
void Create_BST(BSTree &root, const int str[], int n) {  //数组长度由参数传入；
    root = NULL;  //初始时root为空树；
    //调用插入结点函数依次将关键字插入BST中；
    for(int i = 0; i < n; ++ i) {
        insert(root,str[i]);
    }
}

4. 【删除`BST`的结点】¶

450. 删除二叉搜索树中的节点

与插入节点类似，我们需要在删除操作后维持二叉搜索树的“左子树 < 根节点 < 右子树”的性质。首先，我们需要在二叉树中执行查找操作，获取待删除节点。接下来，根据待删除节点的子节点数量，删除操作需分为三种情况：

当待删除节点的度为 0 时，表示待删除节点是叶节点，可以直接删除。
当待删除节点的度为 1 即只有左子树或右子树时，将待删除节点替换为其子节点即可。
当待删除节点的度为 2 即左右子树都存在时，我们无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树“左 < 根 < 右”的性质，因此这个节点可以是右子树的最小节点（在右子树的最左下位置）或左子树的最大节点(左子树的最右下位置)。

【递归写法】：\(root\)有左右子树，这时可以将 \(root\)的后继节点（比 \(root\) 大的最小节点，即它的右子树中的最小节点，记为\(successor\)）作为新的根节点替代 \(root\)，并将 \(successor\) 从\(root\) 的右子树中删除，使得在保持有序性的情况下合并左右子树。

TreeNode* deleteNode(TreeNode *root, int key) {
    if(root == NULL)  return NULL;
    if(root -> val < key){   
        root -> right = deleteNode(root -> right,key);
        return root;
    }   
    if(root -> val > key) {
        root -> left = deleteNode(root -> left,key);
        return root;
    }
    if(root -> val == key) {
        if(!root -> left && !root -> right) {   //情况1，被删除结点是叶节点，直接删除；
            delete root;  //释放被删除节点；
            return NULL;
        } 
        if(!root -> left) {   //情况2：被删除结点没有左子树，则直接返回其右子树；
            TreeNode *child = root->right;  //保存子树后释放当前节点；
            delete root; 
            return child;  
        } 
        if(!root->right) {    //情况3：被删除结点没有右子树，直接返回其左子树；
            TreeNode *child = root->left;  //保存子树后释放当前节点；
            delete root;  
            return child; 
        }
        TreeNode* successor = root -> right;   //用来寻找root的直接后继结点；
        while(successor -> left) {     //它的直接后继结点是它右子树的最左下结点；
            successor = successor -> left;
        }
        root -> val = successor -> val;  //复制后继值，避免直接移动节点造成指针错误；
        root -> right = deleteNode(root -> right, successor -> val);  //删除右子树中的重复后继节点；
        return root;  
    }
    return root;
}

删除示意图(删除17)：

当然也可以用当前结点的直接前驱来代替它，即它的左子树的最右下的结点；下面为关键部分的修改：

TreeNode *predecessor = root->left;  //当前结点的直接前驱结点；
while (predecessor->right) {    //位于它的左子树最右下位置；
     predecessor= predecessor->right;
}
root->val = predecessor->val;  //复制前驱值，避免删除后继续访问已释放节点；
root->left = deleteNode(root->left, predecessor->val);  //删除左子树中的重复前驱节点；
return root;

这样的话删除结点17的示意图是这样的

还有一种处理方式：若被删除节点有左右子树，将其左子树挂到其右子树的最左下结点的左子树位置，然后让该结点的右子树顶替他的位置，这样也可以删除该结点

图例为：由图可以看出，这样处理的话多次删除几个结点后，树就变成链表了，不推荐使用；

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) 
    {
        if (root == nullptr)    return nullptr;
        if (key > root->val)    root->right = deleteNode(root->right, key);     // 去右子树删除
        else if (key < root->val)    root->left = deleteNode(root->left, key);  // 去左子树删除
        else    // 当前节点就是要删除的节点
        {
            if (! root->left)   return root->right; // 情况1，欲删除节点无左子
            if (! root->right)  return root->left;  // 情况2，欲删除节点无右子
            TreeNode* node = root->right;           // 情况3，欲删除节点左右子都有 
            while (node->left)          // 寻找欲删除节点右子树的最左节点
                node = node->left;
            node->left = root->left;    // 将欲删除节点的左子树成为其右子树的最左节点的左子树
            root = root->right;         // 欲删除节点的右子顶替其位置，节点被删除
        }
        return root;    
    }
};

复杂度分析

时间复杂度：\(O(n)\)，其中 \(n\)为 \(root\)的节点个数。最差情况下，寻找和删除 \(successor\)各需要遍历一次树。

空间复杂度：\(O(n)\)，其中n为 \(root\)的节点个数。递归的深度最深为 \(O(n)\)。

【注】：如果删除的结点位于叶子节点处，那么将其删除后再插入，树的形态与原来保持不变，因为BST插入结点后该结点成为叶子节点处，这个位置是唯一的；

但是如果被删除的结点不是叶子节点，那么删除再插入其形态就会变化了，因为插入是在某个节点的左右空指针处，插入后它就成了叶子节点，而在原来的树中，它是非叶子节点；

【迭代】：这种写法可以进一步降低空间复杂度

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode *cur = root, *curParent = nullptr;
        while (cur && cur->val != key) {
            curParent = cur;
            if (cur->val > key) {
                cur = cur->left;
            } else {
                cur = cur->right;
            }
        }
        if (!cur) {
            return root;
        }
        if (!cur->left && !cur->right) {
            cur = nullptr;
        } else if (!cur->right) {
            cur = cur->left;
        } else if (!cur->left) {
            cur = cur->right;
        } else {
            TreeNode *successor = cur->right, *successorParent = cur;
            while (successor->left) {
                successorParent = successor;
                successor = successor->left;
            }
            if (successorParent->val == cur->val) {
                successorParent->right = successor->right;
            } else {
                successorParent->left = successor->right;
            }
            successor->right = cur->right;
            successor->left = cur->left;
            cur = successor;
        }
        if (!curParent) {
            return cur;
        } else {
            if (curParent->left && curParent->left->val == key) {
                curParent->left = cur;
            } else {
                curParent->right = cur;
            }
            return root;
        }
    }
};

空间复杂度：\(O(1)\)

【查找效率分析】

查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作的时间复杂度

如图，若树高\(h\)，找到最底层的一个结点需要对比\(h\) 次; 最好情况：\(n\) 个结点的二叉树最小高度为\(\left \lfloor log_2n \right \rfloor +1\), 平均查找长度为\(O(logn)\);

最坏情况：每个结点都只有一个分支，退化成链表，树高\(h\) = 结点数\(n\),平均查找长度为\(O(n)\)

如上左图，\(ASL_{成功} = (1*1+2*2+3*4+4*2)/9=\frac{25}{9}\), \(ASL_{失败} =(3*6+4*4)/10=3.4\)

右图：\(ASL_{成功} = (1+2+3+\cdots+9)/9=\frac{50}{9}\), \(ASL_{失败}=(1+2+3+\cdots+9+9)/10=5.9\)

与二分查找（折半查找判定树）对比：二者查找过程类似，平均时间性能差不多，但是二分查找的判定树唯一，而\(BST\)的查找不唯一，相同的关键字插入顺序不同可能会生成不同的二叉排序树。

就维护表的有序性而言，二叉排序树无需移动节点，只需修改指针即可完成插入和删除操作，平均执行时间为\(O(logn)\)；而二分查找的对象是有序顺序表，插入删除要移动大量元素，因此时间复杂度为\(O(n)\)；

6.3.2 平衡二叉树¶

对于二叉查找树的插入、删除、查找等操作，时间复杂度为 \(O(logn)\) 的前提是 保持树的平衡 ，即保持树的高度为 \(logn\) 。在二叉排序树的的删除结点的操作中，我们总是 删除目标结点右子树中的最小结点 （直接后继），可以预见多次删除操作后将使树呈现 左高右低的倾向 。而一旦树不平衡，插入、删除、查找等操作将无法达到 \(O(logn)\) 的复杂度，于是我们自然会想如何在多次删除操作后，树总能够保持平衡。若一棵 BST在操作后总能保持平衡，我们称其为 平衡 BST 。 AVL树是最早提出的自平衡二叉查找树 。

AVL树以 「旋转 (rotation)」 操作保证 任意结点的左右子树高度差不超过 1，使得树的深度总保持为 \(O(logn)\) 。下图左侧的树是 AVL树，右侧的树则不是 AVL树，在结点 7 处失衡。

「AVL 树」既是二叉搜索树也是平衡二叉树，同时满足这两类二叉树的所有性质，因此也被称为「平衡二叉搜索树」。

【结点高度】：在操作 AVL 树时，我们需要获取节点的高度，因此需要为 AVL树的节点类添加 height 变量。

//平衡二叉树结点
typedef struct AVLNode{
    int val;
    int height;
    struct AVLNode*left,*right;
}AVLNode,*AVLTree;

int height(AVLNode *node) {  
    if(node == NULL) return 0;
    return node->height;  //直接读取已维护的高度，保证更新平衡因子为O(1)；
}

/* 更新节点高度 */
void updateHeight(AVLNode *node) {  //AVL节点应使用AVLNode类型；
    // 节点高度等于最高子树高度 + 1
    node->height = max(height(node->left), height(node->right)) + 1;
}

【结点平衡因子】：节点的「平衡因子 Balance Factor」定义为节点左子树的高度减去右子树的高度，同时规定空节点的平衡因子为 0 。我们同样将获取节点平衡因子的功能封装成函数，方便后续使用。

//获取平衡因子
int balanceFactor(AVLNode *node){
    if(node == NULL) return 0;  //空节点平衡因子为 0
    // 节点平衡因子 = 左子树高度 - 右子树高度
    return height(node->left) - height(node->right);
}

设平衡因子为 \(f\) ，则一棵 AVL 树的任意节点的平衡因子皆满足\(−1≤f≤1\) 。

【`AVL`旋转】¶

AVL 树的特点在于「旋转 Rotation」操作，它能够在不影响二叉树的中序遍历序列的前提下，使失衡节点重新恢复平衡。换句话说，旋转操作既能保持树的「二叉搜索树」属性，也能使树重新变为「平衡二叉树」。

我们将平衡因子绝对值 >1 的节点称为「失衡节点」。根据节点失衡情况的不同，旋转操作分为四种：右旋、左旋、先右旋后左旋、先左旋后右旋。下面我们将详细介绍这些旋转操作。

【LL型，右旋】

如下图所示，节点下方为平衡因子。从底至顶看，二叉树中首个失衡节点是“节点 3”。我们关注以该失衡节点为根节点的子树（最小不平衡子树），将该节点记为 node ，其左子节点记为 child ，执行「右旋」操作。完成右旋后，子树已经恢复平衡，并且仍然保持二叉搜索树的特性。

此外，如果节点 child 本身有右子节点（记为 grandChild ），则需要在「右旋」中添加一步：将 grandChild 作为 node 的左子节点。

“向右旋转”是一种形象化的说法，实际上需要通过修改节点指针来实现，代码如下所示。

//右旋操作，传入最小不平衡子树根结点；
AVLNode *rightRotate(AVLNode *node) {
    AVLNode *child = node -> left;
    AVLNode *grandnode = child -> right;
    // 以 child 为原点，将 node 向右旋转
    child -> right = node;
    node -> left = grandnode;
    //更新结点高度；
    updateHeight(node);
    updateHeight(child);
    //返回旋转后子树的根节点；
    return child;
}

【RR型，左旋】：

相应的，如果考虑上述失衡二叉树的“镜像”，则需要执行「左旋」操作。

同理，若节点 child 本身有左子节点（记为 grandChild ），则需要在「左旋」中添加一步：将 grandChild 作为 node 的右子节点。

可以观察到，右旋和左旋操作在逻辑上是镜像对称的，它们分别解决的两种失衡情况也是对称的。基于对称性，我们可以轻松地从右旋的代码推导出左旋的代码。具体地，只需将「右旋」代码中的把所有的 left 替换为 right ，将所有的 right 替换为 left ，即可得到「左旋」代码。

//左旋操作，传入最小不平衡子树根结点；
AVLNode *leftRotate(AVLNode *node) { 
    AVLNode *child = node -> right;
    AVLNode *grandnode = child -> left;
    // 以 child 为原点，将 node 向左旋转
    child -> left = node;
    node -> right = grandnode;
    //更新结点高度；
    updateHeight(node);
    updateHeight(child);
    //返回旋转后子树的根节点；
    return child;
}

【LR型，先左旋再右旋】

对于下图中的失衡节点 3，仅使用左旋或右旋都无法使子树恢复平衡。此时需要先左旋后右旋，即先对child执行「左旋」，再对node执行「右旋」。

【RL型，先右旋后左旋】

同理，对于上述失衡二叉树的镜像情况，需要先右旋后左旋，即先对child执行「右旋」，然后对node执行「左旋」。

下图展示的四种失衡情况与上述案例逐个对应，分别需要采用右旋、左旋、先右后左、先左后右的旋转操作。

在代码中，我们通过判断失衡节点的平衡因子以及较高一侧子节点的平衡因子的正负号，来确定失衡节点属于上图中的哪种情况。

失衡节点的平衡因子	子节点的平衡因子	应采用的旋转方法
\(>1\) （即左偏树）	\(\geq 0\)	右旋
\(>1\) （即左偏树）	\(<0\)	先左旋后右旋
\(<-1\) （即右偏树）	\(\leq 0\)	左旋
\(<-1\) （即右偏树）	\(>0\)	先右旋后左旋

为了便于使用，我们将旋转操作封装成一个函数。有了这个函数，我们就能对各种失衡情况进行旋转，使失衡节点重新恢复平衡。

/* 执行旋转操作，使该子树重新恢复平衡 */
AVLNode *rotate(AVLNode *node) {
    // 获取节点 node 的平衡因子
    int _balanceFactor = balanceFactor(node);
    // 左偏树
    if (_balanceFactor > 1) {
        if (balanceFactor(node->left) >= 0) {
            // 右旋
            return rightRotate(node);
        } else {
            // 先左旋后右旋
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
    }
    // 右偏树
    if (_balanceFactor < -1) {
        if (balanceFactor(node->right) <= 0) {
            // 左旋
            return leftRotate(node);
        } else {
            // 先右旋后左旋
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
    }
    // 平衡树，无需旋转，直接返回
    return node;
}

【插入结点】¶

「AVL 树」的节点插入操作与「二叉搜索树」在主体上类似。唯一的区别在于，在 AVL树中插入节点后，从该节点到根节点的路径上可能会出现失衡节点。因此，我们需要从这个节点开始，自底向上执行旋转操作，使失衡节点恢复平衡。

在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡；

_d62a86747e480dcad0c3e793f301f5e0_1098011062_Screenshot_2023-08-19-14-18-53-385_com.jideos.jnotes.png

_c096a501cb18220414cdff19da4a6c3c_913365033_Screenshot_2023-08-19-14-18-39-418_com.jideos.jnotes.png

9e221cef1897c18c31bf65d76d415510-1155592285_Screenshot_2023-08-19-14-33-17-064_com.jideos.jnotes.png

【偷懒方法】： _e29a41a93572b55749ab7a2ce5f7772b_508299575_Screenshot_2023-08-19-14-40-09-968_com.jideos.jnotes.png

AVLTree root = nullptr;  
AVLNode *insertHelper(AVLNode *node, int val);  //先声明辅助函数；

/* 插入节点 */
void insert(int val) {
    root = insertHelper(root, val);
}

/* 递归插入节点（辅助方法） */
AVLNode *insertHelper(AVLNode *node, int val) {
    if (node == nullptr)
        return new AVLNode{val, 1, nullptr, nullptr};  //创建AVLNode并初始化高度；
    /* 1. 查找插入位置，并插入节点 */
    if (val < node->val)
        node->left = insertHelper(node->left, val);
    else if (val > node->val)
        node->right = insertHelper(node->right, val);
    else
        return node;    // 重复节点不插入，直接返回
    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}

【删除结点】¶

类似地，在二叉搜索树的删除节点方法的基础上，需要从底至顶地执行旋转操作，使所有失衡节点恢复平衡。

AVL的删除操作：

删除结点后，要保持二叉排序树的特性不变；
若删除结点导致不平衡，则需要自底向顶调整平衡；

📌这个十分重要，我觉得考题很有可能是这样的形式，给你一棵AVL，让你删除某个结点，问你调整后的AVL的情况，比如根节点是谁，根节点的左右孩子结点是谁；

这样可以考到BST的删除操作、AVL的旋转调整平衡操作、AVL的删除操作，我觉得是一个很好的出题形式；

AVL的删除结点具体操作：

用\(BST\)的删除结点方法删除结点:

当待删除节点的度为 0 时，表示待删除节点是叶节点，可以直接删除。
当待删除节点的度为 1 即只有左子树或右子树时，将待删除节点替换为其子节点即可。
当待删除节点的度为 2 即左右子树都存在时，我们无法直接删除它，而需要使用一个节点替换该节点。由于要保持二叉搜索树“左 < 根 < 右”的性质，因此这个节点可以是右子树的最小节点（在右子树的最左下位置）或左子树的最大节点(左子树的最右下位置)。

从删除结点一直往上回溯，寻找第一个失衡结点，找不到说明此时AVL还是平衡的，到这里就结束了；否则标记它为\(node\),其高度最高的儿子结点为\(child\),高度最高的孙子结点为\(grandchild\); （只有调整长得高的那部分子树才能重新恢复平衡）

对以node的最小不平衡子树进行调整，先观察node、child、grandchild的关系，判断是执行(LL/RR/LR/RL)中的哪一种；然后执行相应的旋转操作，将以node为根的子树调整平衡；

如果调整后由于子树高度-1导致不平衡向上传导，则从第步继续执行调整操作，直至该树平衡；

例子1：

例子2：

例子3：

例子4：该例有多种情况，可以拿前驱或后继代替他，多种情况，得到的最终AVL形态也不同，考试不会考这种有多种情况的类型，了解即可。

AVLNode *removeHelper(AVLNode *node, int val);  //先声明辅助函数；

/* 删除节点 */
void remove(int val) {
    root = removeHelper(root, val);
}

/* 递归删除节点（辅助方法） */
AVLNode *removeHelper(AVLNode *node, int val) {
    if (node == nullptr)
        return nullptr;
    /* 1. 查找节点，并删除之 */
    if (val < node->val)
        node->left = removeHelper(node->left, val);
    else if (val > node->val)
        node->right = removeHelper(node->right, val);
    else {
        if (node->left == nullptr || node->right == nullptr) {
            AVLNode *child = node->left != nullptr ? node->left : node->right;  
            // 子节点数量 = 0 ，直接删除 node 并返回
            if (child == nullptr) {
                delete node;
                return nullptr;
            }
            // 子节点数量 = 1 ，直接删除 node
            else {
                delete node;
                node = child;
            }
        } else {
            // 子节点数量 = 2 ，则将中序遍历的下个节点删除，并用该节点替换当前节点
            AVLNode *temp = node->right;  
            while (temp->left != nullptr) {
                temp = temp->left;
            }
            int tempVal = temp->val;
            node->right = removeHelper(node->right, temp->val);
            node->val = tempVal;
        }
    }
    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}

【查找效率分析】：¶

若树高为 \(h\), 则最坏情况下，查找一个关键字最多需要对比 \(h\) 次，及查找操作的时间复杂度为 \(O(h)\)

重要结论：假设以\(n_h\) 表示深度为 \(h\) 的平衡二叉树含有的最少结点数，则有 \(n_0=0,n_1=1,n_2=2,并且有n_h=n_{h-1}+n_{h-2}+1\)(递推求解)

\(n_{h-1}\)即左子树高度，\(n_{h-2}\)即右子树高度，因为二者高度差为1，根节点为1.

该结论常用于给定平衡二叉树的高度求最少结点数，或给定结点数的平衡二叉树所需要的最多比较次数(即树的最大高度)；

含有\(n\) 个结点的AVL最大深度为\(O(logn)\),因此AVL的平均查找长度为\(O(logn)\)；

AVL树典型应用:

组织和存储大型数据，适用于高频查找、低频增删的场景。

用于构建数据库中的索引系统。

为什么红黑树比AVL树更受欢迎？

红黑树的平衡条件相对宽松，因此在红黑树中插入与删除节点所需的旋转操作相对较少，在节点增删操作上的平均效率高于AVL树。

6.3.3 红黑树¶

【主要掌握定义及性质，插入操作也可以了解一下】

平衡二叉树 AVL：插入/删除很容易破坏“平衡”特性，需要频繁调整树的形态。如：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树（时间开销大），再进行 LL/RR/LR/RL 调整

而红黑树 RBT：插入/删除很多时候不会破坏“红黑”特性，无需频繁调整树的形态。即便需要调整，一般都可以在常数级时间内完成

所以：

平衡二叉树：适用于以查为主、很少插入/删除的场景
红黑树：适用于频繁插入、删除的场景，实用性更强

6.3.3.1 红黑树的定义¶

首先红黑树是二叉排序树，与普通的BST相比，它有以下要求：

每个结点或是红色，或是黑色的；
根节点是黑的；
叶节点（即外部结点/NULL结点/失败结点）均是黑色的；
不存在两个相邻的红结点（即红结点的父节点和孩子结点均是黑色的）
对于每个结点，从该结点到任一叶节点的简单路径上，所含黑节点的数目相同。

用咸鱼口诀记忆：左根右，根叶黑，不红红，黑路同；

数据结构定义为：

struct RBNode{
    int val;
    RBNode *parent;  //父节点指针；
    RBNode *left;    //左孩子指针；
    RBNode *right;   //右孩子指针；
    int color;      //结点颜色，用0/1表示黑/红，也可以用其他数据类型；
}

实例图：

【结论1】：在红黑树中从根到叶节点的最长路径不大于最短路径的两倍

由黑路同可知这两条路径上的黑节点数目相等，又因为有不红红的限制，极端情况下，最长路径上的结点数最多时是这样的情况：黑、红、黑、红 ……；最短路径上的结点数最少时路径上全是黑节点，这种情况下才是2倍，其他情况下都小于2；

【结论2】：有\(n\)个内部节点的红黑树的高度\(h≤2log_2(n+1)\),所以其查找操作的时间复杂度为\(O(logn)\)

结点的黑高(bh,black height)：从某节点出发（不含该结点）到达任一叶结点的简单路径上黑结点总数；

根节点黑高为 \(h\) 时，内部结点数（不包含空的叶节点）最少时，即总共有 \(h\) 层的全黑结点，因此其内部节点数至少有 \(2^h-1\) 个

所以若红黑树总高度为 \(h\), 那么根结点的黑高 \(≥\left \lfloor \frac{h}{2} \right \rfloor\), 因此内部节点数 \(n ≥2^{\frac{h}{2}}－１\),由此推出 \(h ≤2log_2(n+1)\)

6.3.3.2 红黑树的相关操作¶

【查找操作】：与 BST、AVL 相同，从根出发，左小右大，若查找到一个空叶节点，则查找失败

【插入操作】：

先查找，确定插入位置（原理同二叉排序树），插入新结点
新结点是根——染为黑色\ 新结点非根——染为红色
若插入新结点后依然满足红黑树定义，则插入结束
若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义, 调整需要新结点叔叔的脸色；
- 黑叔：旋转+染色（交换位置的两结点染色）\ • LL型：右单旋，父换爷+染色\ • RR型：左单旋，父换爷+染色\ • LR型：左、右双旋，儿换爷+染色\ • RL型：右、左双旋，儿换爷+染色
- 红叔：染色+变新\ • 叔父爷染色，爷变为新结点（把爷结点当作新节点按步骤2处理）

示例：从一棵空的红黑树开始，插入：\(20, 10, 5, 30, 40, 57, 3, 2, 4, 35, 25, 18, 22, 23, 24, 19, 18\)

后面略；可以到这里模拟实战；

【删除操作】：过于复杂，不会考察

红黑树删除操作的时间复杂度 = \(O(log_2n)\)
在红黑树中删除结点的处理方式和“二叉排序树的删除”一样
删除结点后，可能破坏“红黑树特性”，此时需要调整结点颜色、位置，使其再次满足“红黑树特性”。

6.4 B树()¶

💢该考点不仅考察频率极高，15次408考试考察了11次，同时也是408最难的数据结构之一，必须掌握！！！

转载自408数据结构考点：B树

6.4.1 B树的定义¶

B树是一种平衡的多路查找树。这句话看起来非常简单，实际上信息量非常大，理解了这句话，才能对B树的性质有深度理解。

【平衡】

我们已经学过了很多平衡树，当然这里的平衡是广义的平衡，比如AVL树和红黑树，我们回忆一下它们的平衡分别是如何定义的：

在一棵AVL树中，每个结点的左右子树的高度之差的绝对值（平衡因子）最多为 1 。
在一棵红黑树中，从某结点到其后代叶结点的所有简单路径中，最长的一条路径长度至多为最短的一条路径长度的 2 倍。该性质是红黑树的性质 4 和性质 5 的推论。

那么B树中的平衡又是怎么样的呢？在一棵B树中，每个结点的任意两个子树的高度之差的绝对值（平衡因子）为 0 。结果就是在一棵B树中，所有的叶结点都在同一层。这条性质将在B树的性质 5 中有所体现。

【多路】

路数指的是树中结点的分叉数，比如二叉树就是二路树，B树是一棵多叉树，在B树中路数也称阶数，假设给定的一棵 \(k\) 阶B树，则一定有 \(k≥2\)，当 \(k=2\) 时，B树的效果就类似于二叉树。

【查找】

查找也可以翻译成搜索，即B树中的关键字时有序的，回忆一下二叉搜索树，也称二叉查找树，设\(x\) 是二叉搜索树中的一个结点。如果\(y\) 是 \(x\) 左子树中的一个结点，那么 \(y.key≤x.key\)，如果 \(y\) 是 \(x\) 右子树中的一个结点，那么 \(y.key≥x.key\)。通俗地说，从左往右遍历一棵二叉查找树，得到的序列是单调递增序列。严格地说，对二叉搜索树进行二叉树的中序遍历输出所有关键字的序列是单调递增序列。

那么拓展到B树中又是什么样呢？类似二叉搜索树，设 \(x\) 是B树中的一个关键字。如果 \(y\) 是\(x\) 的前驱关键字，那么 \(y\<x\)，如果 \(y\)是 \(x\) 后继关键字，那么 \(y>x\)。通俗地说，从左往右遍历一棵B树，得到的序列是单调递增序列。严格地说，对B树进行“中序遍历”输出所有关键字的序列是单调递增序列。

为了方便，我们采用环线法对B树进行“中序遍历”，得到一个单调递增序列。

得到的单调递增序列为\(⟨30,50,60,70,80,85,90,100,110,260,280,300,350,400,500⟩\)。

【深入理解】

B树实际上是树和顺序表的结合体，总体结构一棵树，每个结点是一个顺序表，其“中序遍历”序列也是一个顺序表，B树兼具了树和顺序表的优点。

B树的性质：

一棵 \(m\) 阶B树，或为空树，或为满足下列特性的 \(m\) 叉树：

树中每个结点至多有 \(m\) 棵子树。
若根结点不是叶结点（空结点），则至少有两棵子树。
除根结点外的所有非叶结点至少有\(⌈m/2⌉\) 棵子树。
所有非叶结点包含下列信息数据 \((n,A_0,K_1,A_1,K_2,A_2,\cdots,K_n,A_n)\)。首先，\(K_i\) 为关键字，其中\(i=1,2,\cdots,n\), 满足\(K_i\<K_{i+1}\)；然后，\(A_i\) 为指向子树根结点的指针，其中\(i=0,1,2,\cdots,n\),满足 \(A_{i-1}\) 所指向子树中所有结点的关键字均小于 \(K_i\)且 \(A_i\) 所指向子树中所有结点的关键字均大于\(K_i\),其中\(i=1,2,\cdots,n\); 最后，\(n\) 为该结点中的关键字个数，除根结点外的非叶节点满足 \(⌈m/2⌉−1≤n≤m−1\)，根结点满足\(1≤n≤m−1\) 。
所有叶结点（空结点）都出现在同一层上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空）

【注意】：B树的叶结点不是一般意义上树的叶结点，B树的叶结点是空结点。空结点在B树中可以被视为额外的叶结点，即外部结点，那些包含关键字的正常结点为内部结点。这点和红黑树一致。

实际上，B树中我们一般称最下面一层包含关键字的结点为叶结点，其它包含关键字的结点为非叶结点，空结点就是空结点，详见2023年真题第 7 题，所以一定要根据上下文随机应变，根据这个设定，我们重写B树的五条性质如下：

树中每个结点至多有\(m\)棵子树。
若根结点不是叶结点，则至少有两棵子树。
除根结点外的所有非叶结点至少有\(⌈m/2⌉\)棵子树，即至少含有\(⌈m/2⌉ -1\)个关键字
所有非叶结点包含下列信息数据 \((n,A_0,K_1,A_1,K_2,A_2,\cdots,K_n,A_n)\)。首先，\(K_i\) 为关键字，其中\(i=1,2,\cdots,n\), 满足\(K_i\<K_{i+1}\)；然后，\(A_i\) 为指向子树根结点的指针，其中\(i=0,1,2,\cdots,n\),满足 \(A_{i-1}\) 所指向子树中所有结点的关键字均小于 \(K_i\)且 \(A_i\) 所指向子树中所有结点的关键字均大于\(K_i\),其中\(i=1,2,\cdots,n\); 最后，\(n\) 为该结点中的关键字个数，除根结点外的非空节点满足\(⌈m/2⌉−1≤n≤m−1\)，根结点满足\(1≤n≤m−1\)。
所有叶结点都出现在同一层上。

考察最多的也是最重要的是性质 4，注意性质 2 中的根结点特殊，已经融合写入性质 4。

假设一棵B树的高度为 \(ℎ\) ， \(ℎ\) 等于叶结点所在层数，一棵空的B树高度 \(ℎ=0\)。

根据性质 2、4 和 5，我们可以得到下面一条推论：

一棵高度为\(ℎ\)的\(m\)阶B树关键字数最少为\(2⌈m/2⌉^{ℎ−1}−1\)。

另一个思路：含\(n\)个关键字的\(m\)阶B树，最⼤⾼度是多少？

最⼤⾼度——让各层的分叉尽可能的少，即根节点只有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\)个关键字将数域切分为\(n+1\)个区间），则 \(n+1≥2( ⌈m/2⌉ )^{h-1}\), 即\(h≤log_{⌈m/2⌉}\frac{n+1}{2}+1\)

根据性质 4 和 5，我们可以得到下面一条推论：

一棵高度为 ℎ 的\(m\)阶B树关键字数最多为\(m^ℎ−1\)。

另一个思路：含\(n\)个关键字的\(m\)阶B树，最小⾼度是多少？

最⼩⾼度——让每个结点尽可能的满，有\(m-1\)个关键字，\(m\)个分叉，则有

\(n≤(m-1)(1+m+m^2+m^3+\cdots+m^{h-1})=m^h-1\) ,因此，\(h≥log_m(n+1)\)

根据性质 6 和 7，我们可以得到下面一条推论：

已知一棵B树的关键字数量为\(N\)，设该B树高度为\(h\)，则 ℎ 满足\(log_m⁡(N+1)≤ℎ≤log_{⌈m/2⌉⁡}\frac{N+1}{2}+1\)

【相关例题】：

已知一棵5阶B树有53个关键字，则它的高度最高为？（不包含空结点层）答案：4

在一棵具有20个关键字的3阶B树中，含关键字的结点个数最多是( )，最少是( )\ \(A. 10\) \(B.11\) \(C.18\) \(D.20\) \(E.15\)\ 下图是结点个数最多的情况 \ 对于结点个数最少问题的选择，很多人会认为是下图中的形态（结点内数字表示序号而非元素值）；3阶B树每个结点最多含有2个元素，有的考生就会误以为最少需要\(20/2=10\)个结点；但是这样违背了B树的重要性质：B树的叶节点必须在同一层！ \ 正确答案其实是这种形态：

【B树判定】

判定一棵树是否为一棵B树：

第一步：检查是否平衡，B树要求所有叶结点都出现在同一层上。

第二步：检查是否是一棵查找树，采用环线法对该树进行“中序遍历”，得到一个单调递增序列。

第三步：检查除根结点外的每个结点关键字个数，要求对于其中任意一个结点，关键字个数 \(n\) 满足 \(⌈m/2⌉−1≤n≤m−1\) ，严谨一点也需要检查根结点，根结点关键字个数 \(n\) 满足 \(1≤n≤m−1\) 。

【2022】年考题：

在下图所示的 5 阶B树 \(T\) 中，删除关键字 260 之后需要进行必要的调整，得到新的B树 \(T_1\) 。下列选项中，不可能是 \(T_1\) 根结点中的关键字序列的是（）。

A. \(60,90,280\)

B. \(60,90,350\)

C. \(60,85,110,350\)

D.\(60,90,110,350\)

解答：

这道题考察了B树的删除操作，但是从删除操作入手这道题难度较大，可以从B树的性质入手，根据选项构造出删除关键字 260 之后的B树，然后进行B树判定。

先用搜索树性质构造出一棵B树，然后检查该树是否为一棵 5 阶B树。

\(m\)阶B树每个结点（除根结点外）关键字数量 \(n\) 为 \(⌈m/2⌉−1≤n≤m−1\) 。本题为 5 阶B树，有 \(2≤n≤4\)

很明显 D 中关键字 100 所在的结点只有一个关键字，违反 \(2≤n≤4。\)

本题选D。

根据算法的定义，算法具有确定性，也就是删除关键字 260 之后的得到的B树是唯一的，不可能有多个结果符合要求。但是 260 位于非叶结点，从非叶结点中删除关键字为超纲考点，命题组这道题本意是考察B的性质。虽然这道题确实存在争议，但假设从算法设计的角度看，即设计的从B树中删除一个关键字的算法不能违反数据结构的性质，确实是一道好题。

6.4.2 B树的查找操作¶

【注意】：B树中的每个结点里的关键字都是序列中真实存在的关键字，如果在内部节点中就找到了目标关键字，则不用继续往下找了；如果到NULL结点都没有找到，则查找失败。

B树查找操作为必须要掌握的考点，要求能够对B树的查找操作进行模拟。B树查找操作也是B树插入操作和B树删除操作的基础。

【查找操作步骤】

B树是一棵查找树，默认关键字的值为从左到右单调递增分布的。设查找关键字为 \(x\) ，从B树的根结点开始搜索，需要分情况讨论。

基本情况：

搜索结点为空，即到达最下层空结点，查找失败，查找结束。
搜索结点非空且包含查找关键字\(x\)，查找成功，查找结束。

迭代情况：

搜索结点非空且不包含查找关键字，该非空结点包含下列信息数据\((n,A_0,K_1,A_1,K_2,A_2,\cdots,K_n,A_n)\)。

若 \(x\<K_1\) ，则进入该结点的孩子结点\(A_0\) 继续搜索关键字 \(x\)。
若 \(K_i\<x\<K_{i+1}\) ，其中 \(i=1,2,...,n−1\) ，则进入该结点的孩子结点 \(A_i\) 继续搜索关键字 \(x\) 。
若 \(x>K_n\)，则进入该结点的孩子结点 \(A_n\) 继续搜索关键字 \(x\) 。

直到到达基本情况终止。

【查找操作分析】

假设查找的B树阶数为 \(m\)，在每个结点内部，由于关键字单调有序，可以用线性查找，时间复杂度为 \(O(n)\)，也可以用二分查找，时间复杂度为 \(O(log⁡n)\) 。

给定下面一棵B树，观察在该B树中分别查找关键字 66、 70 和 90 的过程：

若查找关键字存在，则查找成功，查找关键字位于某一内部结点。

若查找关键字不存在，则查找失败，搜索到达某一外部结点（空结点）。

所以搜索最多到达外部结点（空结点），此时搜索路径长度等于内部结点层数 \(ℎ\) ，设为树高等于 ℎ ，B树中关键字总数为 \(n\) ，根据上一节B树的定义中的推论 6 和 7，有 \(2⌈m/2⌉^{ℎ−1}−1≤n≤m^{ℎ−1}\)，有 \(ℎ=O(log_mn)\) 。

又因为 \(m\) 为常数，假设结点内部采用二分查找，则B树查找操作的时间复杂度为 \(O(log⁡m)O(log_mn)=O(log⁡n)\)。

6.4.3 B树的插入操作¶

【要领】：通过查找操作确定插入位置，注意一定是从终端结点处插入，如果插入后超过上限，将当前结点的中间元素即第\(⌈m/2⌉\)个关键字放到父节点，然后当前结点分裂出两部分；该操作导致父节点关键字数增加，若其也超上限了，则再向上分裂；

【插入操作步骤】

第一步：查找B树并确定待插入关键字插入位置并插入该关键字

需要分情况讨论。

情况一：若插入前B树为空，则创建新的结点作为根结点，并放入需要插入的关键字。
情况二：若插入前B树不为空，则从根结点开始，单程向下查找需要插入的关键字插入位置，一定查找到叶结点为止，插入后插入的关键字左边的关键字（若存在）的值小于插入的关键字的值，右边的关键字（若存在）的值大于插入的关键字的值。

以往一棵4阶B树中插入一个关键字 66 为例： images

第二步：调整B树以维护B树性质

调整B树是为了使得插入关键字后的B树始终满足B树的性质。

需要分情况讨论。

不分裂（仅插入）：被插入关键字所在结点关键字个数小于B树的阶数\(m\) ，无需调整，操作完成。其中包含待插入结点为空的情况，若插入前待插入结点为空，则创建新的结点作为根结点，并放入需要插入的关键字。此时B树的高度相比插入前加一。

如第一步中情况二的例子，关键字 66 所在结点中有 3 个关键字，因为 3 < 4，所以被插入关键字所在结点关键字个数小于B树的阶数 \(m\) ，无需调整。

分裂（插入后分裂，需要迭代）：被插入关键字所在结点关键字个数等于B树的阶数 \(m\) ，需要分裂该结点，将第 \(⌈m/2⌉\)个关键字插入到该结点的父结点，该结点分裂成两个结点，第 1 到 \(⌈m/2⌉−1\) 个关键字和第 0 到 \(⌈m/2⌉−1\) 个孩子指针属于第 \(⌈m/2⌉\) 个关键字的左孩子结点，第 \(⌈m/2⌉+1\) 到 \(m\) 个关键字和第 \(⌈m/2⌉\) 到 \(m\) 个孩子指针属于第 \(⌈m/2⌉\) 个关键字的右孩子结点。此时令被插入关键字为第 \(⌈m/2⌉\) 个关键字，被插入结点为该结点的父结点，然后迭代执行，到达不分裂情况终止。

注意：上移插入父结点的关键字为关键字数组的下中位数点的关键字，即若B树的阶数为4，则将第2个关键字上移插入，若B树的阶数为5，则将第3个关键字上移插入。另外，一般分裂后的左孩子结点在原来结点的基础上修改，分裂后的右孩子结点需要新创建结点。

观察下面的一个4阶B树插入关键字 66 后例子：

观察下面的另一个插入关键字 66 后例子：

数据可视化网站：B-Tree Visualization，可以模拟B树的插入过程。注意不要勾选 Preemtive Split / Merge (Even max degree only)，即前置拆分或合并（仅适用于偶数阶B树），如果勾选，那么就变成了《算法导论》版的算法。

6.4.4 B树的删除操作¶

B树的删除操作为必须要掌握的考点，要求能够对B树的删除操作进行模拟。毫无疑问，B树的删除操作是B树的所有基本操作中最难的

【删除操作步骤】

《数据结构（C语言版）》中B树的删除操作是后处理，即先删除后调整，很明显分成两步，第一步删除，第二步调整。

第一步：查找B树并确定待删除关键字位置并删除该关键字

需要分情况讨论。

若该关键字位于终端结点，直接删除即可。
若该关键字位于非终端结点，则用它的直接后继或直接前驱来替代被删除的关键字；（将对非终端节点的删除操作转化为对终端结点的删除操作）
直接前驱：当前关键字左侧指针所指子树中“最右下”的元素；
直接后继：当前关键字右侧指针所指子树中“最左下”的元素；

具体例子如下，从如下3阶B树中删除关键字 45。

第二步：调整B树以维护B树性质
情况 1：直接删除\ 被删除结点关键字数目删除后满足 \(n≥⌈m/2⌉−1\) ，则在该结点内部调整即可，调整方法同顺序表的删除操作，将该被删关键字后面的关键字都往前移动一个位置。
情况 2：需要从其它结点“借”关键字\ 被删除结点关键字数目删除后满足 \( n<⌈m/2⌉−1 \) ，仅内部调整已无法满足B树性质，只能去其它结点“借”，就是从其父结点和左右兄弟结点“借”。这里又分为两种情况。
情况 2.1：“兄弟够借”（旋转操作）\ 如果被删除结点关键字 \(P\) 有右兄弟结点 \(Y\)，且 \(Y\) 中关键字个数满足 \(≥⌈m/2⌉\) ，即 Y 被“借”走一个关键字后仍满足B树性质，就是“兄弟够借”。“兄弟够借”的处理方案为旋转。也就是说用当前结点的后继、后继的后继来填补空缺；如果右兄弟不够借，左兄弟够，那就用当前结点的前驱、前驱的前驱来填补空缺；具体例子如下，左图为借右兄弟，右图为借左兄弟：

\ _673594d109c72cace51062d1dac2ad14_2014721477_Screenshot_2023-08-21-12-59-03-000_com.jideos.jnotes.png

情况 2.2：“兄弟不够借”（合并操作）

如果被删除结点关键字 \(P\) 有右兄弟结点 \(Y\)，且 \(Y\) 中关键字个数满足 \(=⌈m/2⌉−1\) ，即 \(Y\) 被“借”走一个关键字后不满足B树性质，就是“兄弟不够借”。\ “兄弟不够借”的处理方案为将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进⾏合并。\ 在合并过程中，双亲结点中的关键字个数会减_1_。若其双亲结点是根结点且关键字个数减少⾄\(0\)（根结点关键字个数为_1_时，有_2_棵⼦树），则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到 \(=⌈m/2⌉−2\)，则⼜要与它⾃⼰的兄弟结点进⾏调整或合并操作，并重复上述步骤，直⾄符合_B_\ 树的要求为⽌。具体步骤见下例：\

【2022】年考题：

在下图所示的 5 阶B树 \(T\) 中，删除关键字 260 之后需要进行必要的调整，得到新的B树 \(T_1\) 。下列选项中，不可能是 \(T_1\) 根结点中的关键字序列的是（）。

A. \(60,90,280\)

B. \(60,90,350\)

C. \(60,85,110,350\)

D. \(60,90,110,350\)

分情况讨论：

用后继代替

然后与右兄弟合并

与左兄弟合并

2. 用前驱代替 - 左兄弟够借，找左兄弟借

右兄弟不够借，与右兄弟合并

6.5 B+树¶

产生原因：源于操作系统的文件索引和数据库索引；

可类比分块查找记忆：

⼀棵\(m\)阶的\(B+\)树需满⾜下列条件：

1）每个分⽀结点最多有\(m\)棵⼦树（孩⼦结点）。

2）⾮叶根结点⾄少有两棵⼦树，其他每个分⽀结点⾄少有 \(⌈m/2⌉\)棵⼦树。

3）结点的子树个数与关键字个数相等。

4）所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来（支持顺序查找）。

5）所有分⽀结点中仅包含它的各个⼦结点中关键字的最⼤值及指向其⼦结点的指针。

【查找】：在B+树中有两个头指针，一个指向头节点，一个指向关键字最小的叶节点，因此B+树支持：一种是从最小关键字开始的顺序查找；另一种是从根节点开始的多路查找；（与B树查找成功可能停留在任意一层不同，在B+树中，无论查找成功与否，最终一定要走到最下面一层结点，因为B+树中只有叶节点包含信息）

B树与B+树的对比

	\(m\) 阶B树	\(m\) 阶B+树
类比	二叉查找树的进化 ——> \(m\) 叉查找树	分块查找的进化 —–> 多级分块查找
关键字与分叉	\(n\) 个关键字对应 \(n+1\) 个个分叉（子树）	\(n\) 个关键字对应 \(n\) 个个分叉（子树）
根节点为非叶子结点时关键字个数最少/最多	最少\(1\)个/最多\(m-1\)个	最少\(2\)个（根节点若为叶子节点时可以只有一个关键字）最多\(m\)个
结点包含的信息	所有结点中都包含记录的信息（包括该记录的存储地址）	只有最下层叶子节点才包含记录的信息，而非叶结点仅起索引作用，只含有对应子树的最大关键字和指针，这样可以使一个磁盘块包含更多关键字，从而使B+树的阶更大，树高更矮，读磁盘次数减少，查找更快；
查找方式	不支持顺序查找；查找成功时，可能停在任意一层结点，查找速度不稳定	支持顺序查找和多路查找。查找成功或失败都会到达最后一层结点，查找速度稳定；
关键字出现次数	B树中，各结点中包含的关键字是不重复的	在B+树中，叶节点中包含全部关键字，非叶结点中出现的关键字也会出现在叶节点中
相同点	除根节点外，最少 \(⌈m/2⌉\)个分叉（确保结点不要太“空”）	任何一个结点的子树都要一样高，确保绝对平衡；

6.6 散列表¶

6.6.1 散列表的基本概念¶

散列表（哈希表，Hash Table）：是⼀种数据结构。特点是：可以根据数据元素的关键字计算出它在散列表中的存储地址

一种以空间换时间的算法。

散列函数（哈希函数）：\(Addr=H(key)\) 建⽴了“关键字”→“存储地址”的映射关系

冲突（碰撞）：在散列表中插⼊⼀个数据元素时，需要根据关键字的值确定其存储地址，若该地址已经存储了其他元素，则称这种情况为“冲突（碰撞）”

同义词：若不同的关键字通过散列函数映射到同⼀个存储地址，则称它们为“同义词”

装填因子: 一般将其标记为 \(\alpha\),定义为一个表的装满程度，即\(\alpha=\frac{表中记录数n}{散列表长度m}\)

散列表的平均查找长度依赖于散列表的装填因子\(\alpha\),而不直接依赖于\(n\)或\(m\),直观地看，\(\alpha\)越大，表示装填的记录越“满”，发生冲突的可能性更大。

如何减少冲突？构造更合适的散列函数，让各个关键字尽可能地映射到不同的存储位置，从而减少冲突；

引出问题：如何构造散列函数；

若冲突无法避免，如何处理冲突？ 引出处理冲突的办法——开放定址法、拉链法

6.6.2 散列函数的构造方法¶

设计散列函数应该注意什么？

假设现在有一个长度为13的散列表，关键字可能是任一整数。

定义域必须涵盖所有可能出现的关键字。 反例：\(H(key)=\sqrt{key}\) % \(13\)，该散列函数不支持负值；
值域不能超出散列表的地址范围。 反例：\(H(key)=key\) % \(15\), 关键字可能被映射到非法地址13、14
尽可能减少冲突。散列函数计算出来的地址应尽可能均匀分布在整个地址空间。 反例：\(H(key)=(key\*13)\) % \(13\)，任何关键字都会被映射到地址0；
散列函数应尽量简单，能够快速计算出任意⼀个关键字对应的散列地址。 反例：\(H(key)=(key!)\) % \(13\),若关键字数值较大，计算阶乘耗时高；

【法一】：除留余数法——\(H(key)=key\)%\(p\)

散列表表长为\(m\)，取⼀个不⼤于\(m\)但最接近或等于 \(m\) 的质数 \(p\)

适用场景：较为通用，只要关键字是整数即可。

注意，计算平均失败查找长度时，分母取决于散列表长度和\(p\)中的较小者，即初次探测可能会落在的区间。

计算平均成功查找长度，分母为关键字个数。

为什么要对质数取余？

原因：对质数取余，可以分布更均匀，从而减少冲突；（取余运算会被公因子影响）

【法二】：直接定址法———\(H(key)=key\)或\(H(key) = a\*key+b\)

其中，\(a\) 和 \(b\) 是常数。这种⽅法计算最简单，且不会产⽣冲突。若关键字分布不连续，空位较多，则会造成存储空间的浪费。

适用场景：关键字分布基本连续。

【法三】：数字分析法———–选取数码分布较为均匀的若⼲位作为散列地址

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

例：要求将⼿机⽤户的信息存⼊⻓度为 10000 的散列表。以“⼿机号码”作为关键字设计散列函数

【法四】：平方取中法——取关键字的平方值的中间几位作为散列地址。

具体取多少位要视实际情况⽽定。这种⽅法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布⽐较均匀。

适⽤场景：关键字的每位取值都不够均匀。

例：某汽⻋品牌，以（底盘号、发动机号、外观号）作为⼀款汽⻋型号的标识。该品牌有100种⻋型，欲将这这些⻋型信息存⼊⻓度为100的散列表，如何设计散列函数？

6.6.3 处理冲突的办法¶

6.6.3.1 拉链法¶

拉链法（⼜称链接法、链地址法）：把所有“同义词”存储在⼀个链表中

如何在散列表（拉链法解决冲突）中插入一个新元素？

Step 1：结合散列函数计算新元素的散列地址
Step 2：将新元素插入散列地址对应的链表（可⽤头插法，也可⽤尾插法）

例：若散列表长度为13，散列函数 \(H(key)=key\) % \(13\)，⽤拉链法解决冲突。依次插⼊关键字 {\({19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}\)}

【注】：在拉链法中，如果该位置为空，则查找长度为0，查找长度即对比关键字的次数，空指针的对比不计入查找长度。如21%13=8,查找失败，查找长度为0；27%13=1,查找成功，查找长度为2；66%13=1,查找失败，查找长度为4；

拉链法的删除操作：根据散列函数计算目标元素的散列地址；顺序查找散列地址对应的链表，若查找成功，将目标元素从链表中删除，与链表的删除操作类似。

如果在新元素插入链表时，保持链表的有序性，则可以提高查找的效率。

当链表很长时，查询效率 \(O(n)\) 很差，此时可以将链表转换为“AVL 树”或“红黑树”，从而将查询操作的时间复杂度优化至 \(O(log⁡n)\) 。

6.6.3.2 开放定址法¶

主要注意点：

计算查找长度时，遇到空位置就可以确定查找失败，但是要注意如果这个空位置有标记（该位置元素被删除），则不能退出，还要继续往后查找；

删除元素要在该位置留下标记；

空位置的比较也要计入查找长度。

主要思想：如果发生冲突，就给新元素另外找一个空闲位置；

为什么叫“开放定址”？—— ⼀个散列地址，既对同义词开放，也对非同义词开放

思路：需确定⼀个“探测的顺序”，从初始散列地址出发，去寻找下⼀个空闲位置。\(H_i=(H(key)+d_i)\) % \(m\)

\(d_i\)是增量序列，表示第\(i\) 次发生冲突时，下一个探测地址与初始散列地址的相对偏移量；\(m\)是散列表表长；

根据增量序列的不同取值，有以下四种方法：

线性探测法（）

【插入操作】：先计算散列地址，若发生冲突，顺序查看表中的下一个单元（探测到表尾地址后，下一个探测位置是表头），直到找到一个空闲单元或查遍全表。

【查找操作】：根据探测序列依次对比各存储单元内的关键字，若探测到目标关键字，则查找成功；若探测到空单元，则查找失败；注意，空单元的判断也要算作一次比较，要算入查找长度！！！！

线性探测法很容易造成同义词、非同义词的聚集“堆积”现象，严重影响查找效率；（只有同义词比如链地址法的链，不叫聚集）

产生原因：冲突后再探测，一定是放在某个连续的位置。数组内连续被占用位置越长，这些连续位置发生哈希冲突的可能性越大，进一步促使这一位置的聚堆生长，形成恶性循环，最终导致增删查改操作效率劣化。

平方探测法

【插入操作】：见该例：⻓度为13的散列表状态如下图所示，散列函数 \(H(key)=key\%13\)，采⽤平⽅探测法解决冲突。分析：插⼊元素1、查找元素1 的过程

该方法可以避免出现“堆积”现象，但是不能探测到散列表的所有单元，但至少能探测到一半单元。另外列表长度 \(m\) 如果是一个可以表示为 \(4k+3\) 的质数，则可以探测到所有位置。

双散列法(有可能考，还未考过)

该方法不易产生聚集现象！注意，只能是缓解聚集现象，而不能避免！

需要使用两个散列函数，如果第一个散列函数得出的地址冲突，则使用第二个散列函数\(hash_2(key)\)计算其地址增量\(d_i=i \*hash_2(key)\),\(H_i=(H(key)+d_i)\) % \(m\)

示例：长度为13的散列表状态如下图所示，散列函数 \(H(key)=key\)%13，采⽤双散列法解决冲突，假设\(hash2(key)=13-(key\)%\(13)\)。分析：插⼊元素1、查找元素1 的过程

伪随机序列法

即\(d_i=\) 伪随机序列。示例：长度为13的散列表状态如下图所示，散列函数 \(H(key)=key\%13\)，采⽤伪随机序列法解决冲突，假设伪随机序列\(d_i=0, 5, 3, 11, …，\)其中\(d_i\)表示第\(i\)次发⽣冲突时的增量。分析：插⼊元素1、查找元素1 的过程

开放定址法如何删除一个元素？

Step 1：先根据散列函数算出散列地址，并对⽐关键字是否匹配。若匹配，则“查找成功”
Step 2：若关键字不匹配，则根据“探测序列”对⽐下⼀个地址的关键字，直到“查找成功”或“查找失败”
Step 3：若“查找成功”，则删除找到的元素

【特别注意】：采用开放定址法时，删除元素不能简单地将被删元素的空间置为空，否则将截断在它之后的探测路径，可以做一个“已删除”标记，进行逻辑删除（删除元素会在数组内产生一个空位，当查找该空位之后的元素时，该空位可能导致程序误判元素不存在。为此，通常需要借助一个标志位来标记已删除元素）。

开放寻址法都有不能直接删除元素的缺陷，需要通过标记删除。被标记为已删除的空间是可以再次被使用的。当将新元素插入哈希表，并且通过哈希函数找到了被标记为已删除的位置时，该位置可以被新的元素使用。这样做既能保持哈希表的探测序列不变，又能保证哈希表的空间使用率。

示例：长度为13的散列表状态如下图所示，散列函数 \(H(key)=key\%13\)，采⽤线性探测法解决冲突。

关于探测覆盖率的问题：

采⽤线性探测法，⼀定可以探测到散列表的每个位置；只要散列表中有空闲位置，就⼀定可以插⼊成功

理想情况下，若散列表表⻓\(=m\)，则最多发⽣\(m-1\) 次冲突即可“探测”完整个散列表。

采⽤平方探测法，⾄少可以探测到散列表中⼀半的位置；这意味着，即便散列表中有空闲位置，也未必能插⼊成功

若散列表⻓度 \(m\) 是⼀个可以表示成\(4j + 3\)的素数(如 7、11、19)，平⽅探测法就能探测到所有位置

双散列法未必能探测到散列表的所有位置。双散列法的探测覆盖率取决于第⼆个散列函数 \(hash_2(key)\) 设计的是否合理。\ 若\(hash_2(key)\) 计算得到的值与散列表表⻓ \(m\)互质，就能保证双散列发可以探测所有单元

双散列法常用套路：令表⻓\(m\)本身就是质数，\(hash_2(key)=m-(key\)% \(m)\),这样⽆论 \(key\) 值是多少，\(hash_2(key)\) 和 \(m\) ⼀定互质

采⽤伪随机序列法，是否能探测到散列表中全部位置，取决于伪随机序列的设计是否合理

【例题】：

1.【东北大学2002 二、2 (5分)】设有一组关键字\((9, 1,23, 14, 55, 20, 84,27)\)，采用哈希函数: H(key)=key mod 7，表长为10，用开放地址法的二次探测再散列方法 \(H_i=(H(k e y)+d i) \bmod 10\quad\left(d_i=1^{2}, 2^{2}, 3^{2}, \ldots\right)\)解决冲突。要求:对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

key	9	1	23	14	55	20	84	27
H(key)=key mod 7	2	1	2	0	6	6	0	6
第一次冲突 +1			3			7	1	7
第二次冲突 +4							4	0
第三次冲突 +9								5
实际位置	2	1	3	0	6	7	4	5
查找成功需要次数	1	1	2	1	1	2	3	4

0	1	2	3	4	5	6	7	8	9
14	1	9	23	84	27	55	20

查找成功所需的\(ASL=\frac{1+1+2+1+1+2+3+4}{8}=\frac{15}{8}\)

2.设散列表的表长\(m=15\),散列函数H(key)=key mod 13,关键字集合为（53, 17,12, 61, 89, 70, 87, 25, 64, 46),采用线性探测法处理冲突,试构造散列表,并计算查找成功和查找失败的平均查找长度。

key	53	17	12	61	89	70	87	25	64	46
H(key)	1	4	12	9	11	5	9	12	12	7
第一次冲突 +1							10	13	13
第二次冲突 +2									14
实际的散列位置	1	4	12	9	11	5	10	13	14	7
查找成功比较次数	1	1	1	1	1	1	2	2	3	1

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14
	53			17	70		46		61	87	89	12	25	64

查找成功的\(ASL=\frac{1+1+1+1+1+1+2+2+3+1}{10}=\frac{7}{5}\)

查找模为0的关键字，失败时的比较次数是1
查找模为1的关键字，失败时的比较次数是2
查找模为2的关键字，失败时的比较次数是1
查找模为3的关键字，失败时的比较次数是1
查找模为4的关键字，失败时的比较次数是3
查找模为5的关键字，失败时的比较次数是2
查找模为6的关键字，失败时的比较次数是1
查找模为7的关键字，失败时的比较次数是2\ 查找模为8的关键字，失败时的比较次数是1
查找模为9的关键字，失败时的比较次数是7
查找模为10的关键字，失败时的比较次数是6
查找模为11的关键字，失败时的比较次数是5
查找模为12的关键字，失败时的比较次数是4

查找失败的 \(ASL=\frac{1+2+1+1+3+2+1+2+1+7+6+5+4}{13}=\frac{36}{13}\)

例3：设散列表长度为13，采用拉链法解决冲突，从空表开始，依次插入关键字 \({19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}\)，散列函数H(key)=key%13

注：如果采用拉链法处理冲突，则散列表的长度应该和散列函数的映射范围相同，散列函数的映射范围是 0~12。

考虑查找成功的所有情况。元素 14、68、19、29、23、11 的查找长度为1；元素1、55、84、10 的查找长度为2；元素27的查找长度为3；元素79的查找长度为4，因此：

\(ASL_{成功}=\frac{1*6+2*4+3+4}{12}=1.75\)

考虑查找失败的所有情况。若目标元素的散列值为0，则无需对比任何关键字即可确定查找失败，查找长度为0；若目标元素的散列值为1，则需要依次对比关键字14、1、27、79才能确定查找失败，查找长度为4；其他散列值同理。

\(ASL_{失败}=\frac{0+4+0+2+0+0+2+1+0+0+2+1+0}{13}=0.92\)

采用链地址法解决冲突的哈希表中，查找成功的平均查找长度( )。【北京交通大学2005 —. 6 (2分) 2007】\ A.直接与关键字个数有关\ B.直接与装填因子有关\ C.直接与表的容量有关\ D.直接与哈希函数有关

选D，好的散列函数得到的是左图这样的，不好的可以是右图这样的。为啥不是选项A呢？如果散列函数足够好，关键字有多少个平均查找长度都是1。

假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测? ( ) 【中国科技大学1998二、3 (2分)】【中科院计算所1998二、3(2分)】\ A.k-1次\ B.k次\ C.k+1次\ D.k (k+1) /2次

解析：\ 第一个元素，先探测一下，可以存入。所以探测次数为1。\ 第二个元素，第一次探测遇到了第一个元素，第二次探测，可以存入，探测次数为2。\ ...\ 第k个元素，探测词素为k。\ 等差数列求和，一共进行了k (k+1) /2次

6.7 串的模式匹配¶

知乎问题：如何更好地理解和掌握 KMP 算法?

https://www.zhihu.com/people/0x3F/answers

28. 找出字符串中第一个匹配项的下标

第四章串-第二节：串的模式匹配算法（朴素和KMP）

角色：

甲：\(abbaabbaaba\)\ 乙：\(abbaaba\)

乙对甲说：「帮忙找一下我在你的哪个位置。」

甲从头开始与乙一一比较，发现第 7 个字符不匹配。

要是在往常，甲会回退到自己的第 2 个字符，乙则回退到自己的开头，然后两人开始重新比较。这样的事情在字符串王国中每天都在上演：不匹配，回退，不匹配，回退，……

但总有一些妖艳字符串要花自己不少的时间。

上了年纪的甲想做出一些改变。于是乎定了个小目标：发生不匹配，自身不回退。

甲发现，若要成功与乙匹配，必须要匹配 7 个长度的字符。所以就算自己回退到第 2 个字符，在后续的匹配流程中，肯定还会重新匹配到自己的第 7 个字符上。

当在甲的某个字符 c 上发生不匹配时，甲即使回退，最终还是会重新匹配到字符 c 上。

那干脆不回退，岂不美哉！

甲不回退，乙必须回退地尽可能少，并且乙回退位置的前面那段已经和甲匹配，这样甲才能不用回退。

如何找到乙回退的位置？

「不匹配发生时，前面匹配的那一小段 \(abbaab\) 于我俩是相同的」，甲想，「这样的话，用 \(abbaab\) 的头部去匹配 \(abbaab\) 的尾部，最长的那段就是答案。」

abbaab 的头部有 a, ab, abb, abba, abbaa（不包含最后一个字符。下文称之为「真前缀」）
abbaab 的尾部有 b, ab, aab, baab, bbaab（不包含第一个字符。下文称之为「真后缀」）
这样最长匹配是 ab。也就是说甲不回退时，乙需要回退到第三个字符去和甲继续匹配。

「要计算的内容只和乙有关」，甲想，「那就假设乙在其所有位置上都发生了不匹配，乙在和我匹配前把其所有位置的最长匹配都算出来（算个长度就行），生成一张表，之后我俩发生不匹配时直接查这张表就行。」

据此，甲总结出了一条规则并告诉了乙：

所有要与甲匹配的字符串（称之为模式串），必须先自身匹配：对每个子字符串[0...i]，算出其「相匹配的真前缀与真后缀中，最长的字符串的长度」。

「小 case，我对自己还不了解吗」，乙眨了一下眼睛，「那我回退到第三个字符和你继续匹配吧~」

新的规则很快传遍了字符串王国。现在来看看如何高效地计算这条规则。这里有个很好的例子：\(abababzabababa\)。

列个表手算一下：（最大匹配数为子字符串 \([0...i]\) 的最长匹配的长度）

子字符串　 a b a b a b z a b a b a b a
最大匹配数 0 0 1 2 3 4 0 1 2 3 4 5 6 ?

一直算到 6 都很容易。在往下算之前，先回顾下我们所做的工作：

对子字符串 \(abababzababab\) 来说，

真前缀有 \(a, ab, aba, abab, ababa, ababab, abababz, ...\)

真后缀有 \(b, ab, bab, abab, babab, ababab, zababab, ...\)

所以子字符串 \(abababzababab\) 的真前缀和真后缀最大匹配了 6 个（\(ababab\)），那次大匹配了多少呢？

容易看出次大匹配了 4 个（\(abab\)），更仔细地观察可以发现，次大匹配必定在最大匹配\(ababab\)中，所以次大匹配数就是\(ababab\)的最大匹配数！

直接去查算出的表，可以得出该值为 4。

第三大的匹配数同理，它既然比 4 要小，那真前缀和真后缀也只能在 \(abab\) 中找，即 \(abab\) 的最大匹配数，查表可得该值为 2。

再往下就没有更短的匹配了。

回顾完毕，来计算 ? 的值：既然末尾字母不是 \(z\)，那么就不能直接 6+1=7 了，我们回退到次大匹配 \(abab\)，刚好 \(abab\) 之后的 \(a\) 与末尾的 \(a\) 匹配，所以 ? 处的最大匹配数为 5。

上面所述的最大匹配数数组被称为部分匹配表(PMT,Partial Match Table)

以下图中的例子来说，在 i 处失配，那么主字符串和模式字符串的前边6位就是相同的。又因为模式字符串的前6位，它的前4位前缀和后4位后缀是相同的，所以我们推知主字符串i之前的4位和模式字符串开头的4位是相同的。就是图中的灰色部分。那这部分就不用再比较了。

有了该思路，我们就可以使用PMT加速字符串的查找了。我们看到如果是在 j位失配，那么影响j指针回溯的位置的其实是第 j−1 位的 PMT 值，所以为了编程的方便，我们不直接使用PMT数组，而是将PMT数组向后偏移一位。我们把新得到的这个数组称为 next数组。下面给出根据next数组进行字符串匹配加速的字符串匹配程序。其中要注意的一个技巧是，在把PMT进行向右偏移时，第0位的值，我们将其设成了-1，这只是为了编程的方便，并没有其他的意义。在下面的例子中，next数组如下表所示。

具体的程序如下所示：

int KMP(const string& a, const string& b, const int next[]) {   
    //给出字符串a,b和next数组，返回b在a中的下标
    int i = 0, j = 0;
    while(i < a.length() && j < b.length()) {
        if(j == -1 || a[i] == b[j]) {  
            i++;
            j++;
        }else{
            j = next[j];
        }
    }
    if(j == b.length())  return i - j;   //j指针跳出循环，说明已经找到，返回在a中的下标；
    else return -1;  //找遍a数组都没有找到，查找失败；
}

好了，讲到这里，其实KMP算法的主体就已经讲解完了。现在，我们再看一下如何编程快速求得next数组。其实，求next数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。

具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行匹配运算。在任一位置，能匹配的最长长度就是当前位置的next值。如下图所示。

求next数组值的程序如下所示：

void getnext(const string& s,int next[]) {  
    if(s.empty()) return;  //空模式串没有next[0]可写；
    next[0] = -1;
    int i = 0, j = -1;
    while(i + 1 < static_cast<int>(s.length())) {  //使用s并避免空串时length()-1下溢；
        if(j == -1 || s[i] == s[j]) {
            i++;
            j++;
            next[i] = j;
        }else{
            j = next[j];   //即上面所说的回退到次大匹配值；
        }
    }
}

代码具体解释见参考资料。

KMP的进一步优化之\(nextval\) 数组

nextval数组可由next数组求得，具体求法看以下代码：

// 由 next 数组求得 nextval 数组
void getnextval(const string& s, const int next[], int nextval[]) {  
   if (s.empty()) return;  //空模式串不访问下标0；
   nextval[0] = -1;  //next[0]为-1，不能访问s[-1]；
   for (int i = 1; i < static_cast<int>(s.length()); i++)  //从下标1开始计算；
   {
      if (next[i] == -1 || s[i] != s[next[i]])  //避免next[i]为-1时访问越界；
         nextval[i] = next[i];
      else
         nextval[i] = nextval[next[i]];
   }
}

递归求解。

示例：求字符串 s" \(ababaaababaa\)” 的nextval数组

char	a	b	a	b	a	a	a	b	a	b	a	a
index	0	1	2	3	4	5	6	7	8	9	10	11
PMT	0	0	1	2	3	1	1	2	3	4	5	6
next	-1	0	0	1	2	3	1	1	2	3	4	5
nextval	-1	0	-1	0	-1	3	1	0	-1	0	-1	3

解释：

s[next[1]] != s[1] 所以nextval[1] = next[1];

s[next[2]]==s[2] 所以 nextval[2] == nextval[next[2]]=-1;

s[next[4]] == s[4] 所以nextval[4] = nextval[next[4]]=-1;

求解next数组时，先计算最大匹配数数组（部分匹配表），即从开头到该位置的字串中真前缀和真后缀的最大匹配长度，然后将其后移一位，第0位为-1即可，如上例，计算index等于4的最大匹配数，由于子串ababa的真前缀aba与真后缀aba相等，因此最大匹配数为3.

求字符串“\(ababaabab\)”的nextval

char	a	b	a	b	a	a	b	a	b
index	0	1	2	3	4	5	6	7	8
PMT	0	0	1	2	3	1	2	3	4
next	-1	0	0	1	2	3	1	2	3
nextval	-1	0	-1	0	-1	3	0	-1	0

求字符串“\(pqppqpqp\)”的nextval

char	p	q	p	p	q	p	q	p
index	0	1	2	3	4	5	6	7
PMT	0	0	1	1	2	3	2	3
next	-1	0	0	1	1	2	3	2
nextval	-1	0	-1	1	0	-1	3	-1

求字符串“\(abaabcac\)”的nextval

char	a	b	a	a	b	c	a	c
index	0	1	2	3	4	5	6	7
PMT	0	0	1	1	2	0	1	0
next	-1	0	0	1	1	2	0	1
nextval	-1	0	-1	1	0	2	-1	1

在多数教材的选项中，给出的next数组和nextval数组按位数计算，只要将上面的答案依次加1即可

index¶

6.1 查找的基本概念¶

6.2 顺序查找与二分查找¶

6.2.1 顺序查找¶

6.2.2 折半查找¶

6.2.3 分块查找¶

6.3 树型查找¶

6.3.1 二叉排序树(BST)¶

1.【查找结点】¶

2.【插入结点】¶

3.【构造BST】¶

4. 【删除BST的结点】¶

6.3.2 平衡二叉树¶

【AVL旋转】¶

【插入结点】¶

【删除结点】¶

【查找效率分析】：¶

6.3.3 红黑树¶

6.3.3.1 红黑树的定义¶

6.3.3.2 红黑树的相关操作¶

6.4 B树()¶

6.4.1 B树的定义¶

6.4.2 B树的查找操作¶

6.4.3 B树的插入操作¶

6.4.4 B树的删除操作¶

6.5 B+树¶

6.6 散列表¶

6.6.1 散列表的基本概念¶

6.6.2 散列函数的构造方法¶

6.6.3 处理冲突的办法¶

6.6.3.1 拉链法¶

6.6.3.2 开放定址法¶

6.7 串的模式匹配¶

6.3.1 二叉排序树(`BST`)¶

3.【构造`BST`】¶

4. 【删除`BST`的结点】¶

【`AVL`旋转】¶