好好学习，天天向上
本文已收录至我的Github仓库DayDayUP：github.com/RobodLee/DayDayUP，欢迎Star
⭐⭐⭐⭐⭐
转载请注明出处：https://blog.csdn.net/weixin_43461520/article/details/124377079
查找：在数据集合中寻找满足某种条件的数据元素的过程称为查找。
查找表（查找结构）：用于查找的数据集合称为查找表，它由同⼀类型的数据元素（或记录）组成。对于只需要进行查找符合条件的数据元素操作的查找表称为静态查找表；对于也需要进行插入、删除某个数据元素操作的称为动态查找表。
关键字：数据元素中唯⼀标识该元素的某个数据项的值，使⽤基于关键字的查找，查找结果应该是唯⼀的。
查找长度：在查找运算中，需要对比关键字的次数称为查找长度。所有查找过程中进⾏关键字的⽐较次数的平均值称为平均查找长度。
顺序查找又称线性查找，它对顺序表和链表都是适用的。从头到尾查找或者从尾到头查找。时间复杂度为O(n)。
typedef struct { ElemType *elem; int TableLen; } SSTable; //顺序查找 int Search_Seq(SSTable ST, ElemType key) { int i; //遍历找到指定元素 for (i = 0; i < ST.TableLen && ST.elem[i] != key; i++); //找到返回数组下标，未找到返回-1 return i != ST.TableLen ? i : -1; } 对于一个有序的线性表而言，使用查找判定树分析，其查找效率为👇：
从上图👆中可以看出⼀个成功结点的查找长度 = 自身所在层数，⼀个失败结点的查找长度 = 其父节点所在层数。
折半查找，⼜称“⼆分查找”，仅适用于有序的顺序表。其算法思想为首先将给定值key与表中中间位置的元素进行比较，若相等，则查找成功，返回该元素的存储位置；若不等，则所需查找的元素只能在中间元素以外的前半部分或后半部分，然后在缩小的范围内继续进行同样的查找，如此重复，直到找到为止，或确定表中没有所需要查找的元素。折半查找的时间复杂度为O(log₂n)。
#include <iostream> #define ElemType int using namespace std; typedef struct { ElemType *elem; int TableLen; } SSTable; //顺序查找 int Binary_Search(SSTable L, ElemType key) { int low = 0; int high = L.TableLen - 1; int mid; while (low <= high) { mid = (low + high) / 2; //取中间位置 if (L.elem[mid] == key) { return mid; //查找成功则返回所在位置 } else if (L.elem[mid] < key) { low = mid + 1; //从后半部分继续查找 } else { high = mid - 1; //从前半部分继续查找 } } return -1; } 折半查找判定树
如果当前low和high之间有奇数个元素，则 mid 分隔后，左右两部分元素个数相等。
如果当前low和high之间有偶数个元素，则 mid 分隔后，左半部分⽐右半部分少⼀个元素。
若 mid = ⌊(low + high)/2⌋，则对于任何⼀个结点，必有右⼦树结点数-左⼦树结点数=0或1。
折半查找的判定树⼀定是平衡⼆叉树，折半查找的判定树中，只有最下面一层是不满的，元素个数为n时树⾼h = ⌈log₂(n + 1)⌉。
查找效率
上图为折半查找排序树，图中绿色圆点是成功结点，紫色方块是失败结点。失败结点：n+1个（等于成功结点的空链域数量）。
ASL成功 = ( 1*1+ 2*2 + 3*4 + 4*4 ) / 11 = 3。
ASL失败 = ( 3*4 + 4*8 ) / 12 = 11/3。
分块查找又称索引顺序查找。其基本思想为将查找表分为若干子块。块内的元素可以无序，但块之间是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，第二个块中的最大关键字小于第三个块中的所有记录的关键字，以此类推。再建立一个索引表，索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址，索引表按关键字有序排列。
分块查找的过程分为两步：
第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表。
第二步是在块内顺序查找。
查找效率分析
在上图中，假设采用顺序查找方式查找19，首先在索引表中需要查找两次才能确定处于第二个分块，然后在第二个分块中再查找两次确定最终位置，所以元素19的查找长度为4。每个元素被查的概率都是1/14，将所有元素的查找长度相加除以14就是上图采用顺序查找的ASL。
动态查找表——链表
如果查找表是动态查找表，采用数组实现，添加或删除数据时，需要修改查找表与索引表，而且可能需要移动大量元素，效率不高。可以采用链表实现。
具有如下性质的二叉树称为二叉排序树，又称二叉查找树。
左子树上所有结点的关键字均小于根结点的关键字
右子树上所有结点的关键字均大于根结点的关键字
左子树和右子树又各是一棵二叉排序树
进行中序遍历，可以得到一个递增的有序序列
typedef struct BSTNode { int key; //结点上的关键字 BSTNode *lChild, *rChild; //左右子树指针 } BSTNode, *BSTree; 根据二叉排序树的特点，可以知道查找是沿某个分支逐层向下比较的过程。从根结点开始比较，若小于根结点的关键字，则在根结点的左子树上查找，否则在根结点的右子树上查找。
//在二叉排序树中查找值为key的结点，非递归实现，最坏空间复杂度为O(1) BSTNode *BST_SearchNotRecursion(BSTree t, int key) { while (t != nullptr && key != t->key) { //若树空或等于根结点值，结束循环 if (key < t->key) { //小于根结点值，在左子树上查找 t = t->lChild; } else { //大于根结点值，在右子树上查找 t = t->rChild; } } return t; } //在二叉排序树中查找值为key的结点，递归实现，最坏空间复杂度为O(h)，即等于树的高度 BSTNode *BST_SearchRecursion(BSTree t, int key) { if (t == nullptr) { //查找失败，返回null return nullptr; } else if (key == t->key) { //等于根结点值，返回结点 return t; } else if (key < t->key) { //小于根结点值，在左子树中查找 return BST_SearchRecursion(t->lChild, key); } else { //大于根结点值，在右子树中查找 return BST_SearchRecursion(t->rChild, key); } } 插入与查找操作类似，如果二叉树为空，则直接插入结点，反之寻找插入的位置。若关键字小于根结点值，则插入到左子树，反之插入到右子树。
//在二叉排序树插入关键字为k的新节点，递归实现，最坏空间复杂度为O(n) bool BST_Insert_Recursion(BSTree &t, int k) { if (t == nullptr) { t = new BSTNode; t->key = k; t->lChild = nullptr; t->rChild = nullptr; return true; //插入成功 } else if (k == t->key) { return false; //存在相同的值，插入失败 } else if (k < t->key) { BST_Insert_Recursion(t->lChild, k); //值比根结点小，插入到左子树 } else { BST_Insert_Recursion(t->rChild, k); //值比根结点小，插入到右子树 } return false; } //在二叉排序树插入关键字为k的新节点，非递归实现 bool BST_Insert_NotRecursion(BSTree &t, int k) { BSTNode *p = t; BSTNode *pp; //p的父节点 bool tag; //true新节点插入到p左子树，反之插入到右子树 while (p) { pp = p; if (k == p->key) { return false; //存在相同的值，插入失败 } else if (k < p->key) { p = p->lChild; //值比结点p小，插入到左子树 tag = true; } else { p = p->rChild; //值比结点p小，插入到右子树 tag = false; } } p = new BSTNode; p->key = k; p->lChild = nullptr; p->rChild = nullptr; if (t == nullptr) { //根结点t为null t = p; } else if (tag) { pp->lChild = p; } else { pp->rChild = p; } return true; //插入成功 } 二叉排序树的构造就是给定一个序列，然后不断插入新结点的过程。不同的关键字序列可能得到同款二叉排序树，也可能得到不同款二叉排序树。
void Create_BST(BSTree &t, int values[], int len) { t = nullptr; for (int i = 0; i < len; i++) { // BST_Insert_NotRecursion(t, values[i]); BST_Insert_Recursion(t, values[i]); } } 二叉排序树的删除需要先找到待删除的结点，然后根据三种不同的情况采用不同的方式进行删除。
①被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质。
例如删除图中的8、21、65，由于这三个结点都是叶子结点，所以可以直接删除。
②若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
比如左图中结点13只有一棵左子树，结点60只有一棵右子树，删除时，直接让其子树成为其父节点的子树即可。
③若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况。
👆对z进行中序遍历，可以得到一个递增的有序序列，从而找到z的直接后继。也可以根据中序遍历的特点得出，z的后继是z的右子树中最左下结点，也就是图中的p结点60。将结点p的值赋给结点z，然后根据情况②删除结点p。
👆或者对z进行中序遍历，可以得到一个递增的有序序列，从而找到z的直接后继。也可以根据中序遍历的特点得出，z的直接前驱是z左子树最右下结点(该结点一定没有右子树)，也就是图中的p结点30。将结点p的值赋给结点z，然后根据情况①删除结点p。
/** * 找到待删除的结点 * @param t 二叉排序树 * @param key 待删除的结点值 * @param z 待删除的结点 * @param zParent 待删除结点z的父节点 */ void BST_SearchToDelete(BSTree t, int key, BSTNode *&z, BSTNode *&zParent, bool &flag) { if (t != nullptr && key == t->key) { //待删除的结点是根结点 z = t; return; } while (t != nullptr && key != t->key) { zParent = t; if (key < t->key) { //小于根结点值，在左子树上查找 flag = true; t = t->lChild; } else { //大于根结点值，在右子树上查找 flag = false; t = t->rChild; } z = t; } } //删除指定结点z void BST_Delete_Node_Z(BSTNode *&z, BSTNode *&zParent, bool flag) { if (z->lChild == nullptr && z->rChild == nullptr) { //第一种情况，z是叶子结点，直接删除 if (flag) { zParent->lChild = nullptr; } else { zParent->rChild = nullptr; } } else if (z->lChild != nullptr && z->rChild == nullptr) { //情况2，只有一棵左子树 if (flag) { zParent->lChild = z->lChild; } else { zParent->rChild = z->lChild; } } else if (z->rChild != nullptr && z->lChild == nullptr) { //情况2，只有一棵右子树 if (flag) { zParent->lChild = z->rChild; } else { zParent->rChild = z->rChild; } } } //删除二叉排序树中关键字为k的节点 void BST_Delete(BSTNode *&t, int k) { BSTNode *z = nullptr; //待删除结点 BSTNode *zParent = nullptr; //待删除结点的父节点 bool flag; //true表示 z 是左孩子，false表示是右孩子 BST_SearchToDelete(t, k, z, zParent, flag); if (z != nullptr) { if (z->lChild != nullptr && z->rChild != nullptr) { //情况3，z有左右两棵子树 //找到直接后继，替换 BSTNode *zNext = z->rChild; BSTNode *zNextParent = z; //z的右孩子是叶子结点，说明z的后继就是 rChild，那么删除时 flag应该是false，表示删除的是右孩子 flag = !(zNext->lChild == nullptr && zNext->rChild == nullptr); while (zNext != nullptr && zNext->lChild != nullptr) { zNextParent = zNext; zNext = zNext->lChild; } z->key = zNext->key; BST_Delete_Node_Z(zNext, zNextParent, flag); } else { //待删除结点是根结点，并且是情况1或2 if (zParent == nullptr) { if (z->lChild != nullptr) { t = z->lChild; } else { t = z->rChild; } } else { //情况1,2时删除结点z BST_Delete_Node_Z(z, zParent, flag); } } } } 查找长度：在查找运算中，需要对比关键字的次数称为查找长度，反映了查找操作时间复杂度。
若树高h，找到最下层的一个结点需要对比h次。
最好情况：n个结点的二叉树最小高度为⌊log₂n⌋ + 1。平均查找长度= O(log₂n)。
最坏情况：每个结点只有一个分支，树高h=结点数n。平均查找长度=O(n)。
以上左图为例，蓝色圆圈为成功结点，⼀个成功结点的查找长度 = 自身所在层数。第一层对比1次，1个结点；第二层对比2次，2个结点；第三层对比3次，4个结点，第四次对比4次，1个结点；所以查找成功的ASL=( 1*1 + 2*2 + 3*4 + 4*1 ) / 8 = 2.625。
紫色方块为失败结点，⼀个失败结点的查找长度 = 其父节点所在层数。所以第四层的7个失败结点每个查找长度为3，第五层的2个失败结点每个查找长度为4；所以查找失败的ASL= ( 3*7 + 4*2 ) / 9 = 3.22。
为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差不超过1，这样的二叉树就称为平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树）。结点的平衡因子=左子树高 - 右子树高，平衡因子的值只可能是-1、0或1。
在二叉排序树中插入新结点后，可能导致其不平衡。从插入点往回找到第一个不平衡结点，调整以该结点为根的子树（最小不平衡子树）。
在插入操作中，只要将最小不平衡子树调整平衡，则其他祖先结点都会恢复平衡。在平衡二叉树A中插入新结点导致A成为最小不平衡子树的情况一共分为四种：
LL：在A的左孩子的左子树中插入导致不平衡。
LL平衡旋转（右单旋转）。由于在结点A的左孩子（B）的左子树（BL）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树BR则作为A结点的左子树。
RR：在A的右孩子的右子树中插入导致不平衡
RR平衡旋转（左单旋转）。由于在结点A的右孩子（B）的右子树（BR）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树BL则作为A结点的右子树。
LR：在A的左孩子的右子树中插入导致不平衡
LR平衡旋转（先左后右双旋转）。由于在A的左孩子（B）的右子树（BR）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置。
RL：在A的右孩子的左子树中插入导致不平衡
RL平衡旋转（先右后左双旋转）。由于在A的右孩子（B）的左子树（BL）上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置。
平衡二叉树在删除结点后，要保持二叉排序树的特性不变（左<根<右），若删除结点后导致不平衡，则需要调整平衡。平衡二叉树的删除操作时间复杂度为O(log₂n)。
删除操作的具体步骤如下👇
删除结点（方法同二叉排序树）
若删除的结点是叶子，直接删。
若删除的结点只有一个子树，用子树顶替删除位置
若删除的结点有两棵子树，用前驱（或后继）结点顶替，并转换为对前驱（或后继）结点的删除。
一路向上找到最小不平衡子树，找不到就结束。
找最小不平衡子树下，个头(树高)最高的儿子、孙子。
根据孙子的位置，调整平衡（LL / RR / LR / RL）。
孙子在LL：儿子右单旋。
孙子在RR：儿子左单旋。
孙子在LR：孙子先左旋，再右旋。
孙子在RL：孙子先右旋，再左旋。
如果不平衡向上传导，继续第2步。
由于对最小不平衡子树的旋转可能导致树变矮，从而导致上层祖先不平衡。
例1：
删除叶子结点32。
👇由于结点32是叶子结点，所以直接删除，删除后，一路向上，发现以44为根结点的子树不平衡，所以进行调整。
👇以44为根结点的树中，其个头最高的儿子结点为结点78，个头最高的孙子结点为50，由于孙子结点50的位置是RL，所以先右旋再左旋，即可将其调整平衡。继续向上看，以33为根结点的树此时不平衡了，继续进行调整。
👇结点33的个头最高的儿子结点是结点10，个头最高的孙子结点是结点20，由于孙子结点20的位置是LR，所以结点20先左旋再右旋。此时树已经平衡了，不用继续调整了。
例2：
删除非叶子结点75。
👇由于77是非叶结点，且有两棵子树，所以先用前驱或者后继结点顶替，这里采用后继结点(右子树最左下结点)77顶替，在删除结点77。由于结点77是叶子结点，直接删除即可，删除后结点80失去平衡，对结点80进行调整。
👇对于结点80而言，其个头最高的儿子是结点90，结点85和结点95都是个头最高的孙子，任选一个即可，这里选结点95。由于孙子结点95的位置是RR，所以儿子结点90进行左旋，左旋后结点80平衡，而且其上级结点77和50都是平衡的，调整结束。
若树高为h，则最坏情况下，查找一个关键字最多需要对比 h 次，即查找操作的时间复杂度不可能超过O(h)。分析查找效率，就是要分析一棵平衡二叉树高度有多高。
平衡二叉树在插入删除的的时候很容易破坏其平衡的特性，需要频繁地调整树的形态。而红黑树(Red-Black Tree)很多时候不会破坏其红黑的特性，无需频繁调整树的形态。红黑树也是一棵二叉排序树，相较于普通的二叉排序树，有如下的特点：
每个结点或是红色的，或是黑色的
左根右：左子树上的关键字均小于根结点，右子树上的关键字均大于根结点。
根叶黑：根结点是黑色的，叶结点（外部结点、NULL结点、失败结点）均是黑色的。
不红红：不存在两个相邻的红结点（即红结点的父结点和孩子结点均是黑色）。
黑路同：对每个结点，从该结点到任一叶结点的简单路径上，所含黑结点的数目相同。
struct RBNode { //红黑树结点定义 int key; //关键字的值 RBNode *parent; //父结点指针 RBNode *lChild; //左孩子指针 RBNode *rChild; //右孩子指针 int color; //结点颜色，0表示红，1表示黑 };
👆上图就是一棵红黑树，其中的bh是黑高，指的是从某结点出发（不含该结点）到达任一空叶结点的路径上黑结点（含叶结点）总数。
若一棵红黑树是一棵全是黑结点的满树，则内部结点(关键字)最少，若根结点黑高为h，内部结点最少有2^h - 1个，此时根结点的黑高等于树高。
红黑树具有如下性质：
从根结点到叶结点的最长路径不大于最大路径的2倍。最长路径为红结点穿插在每两个相邻的黑结点之间。
有n个内部结点的红黑树高度h≤2log₂(n+1)。若红黑树总高度为h，则根结点黑高≥h/2(由不红红的特性得出)，因此内部结点数n≥2^(h/2) - 1，得出h≤2log₂(n+1)。
红黑树的查找与BST和AVL相同，都是从根结点出发，根据左小右大的原则进行查找，若查找到一个空叶结点，则查找失败。
比如查找15，从根结点出发，15>13，查找右子树，15<17，再查找左子树，然后找到15。
红黑树查找操作的时间复杂度为O(log₂n)。
新结点的插入规则如下：
以下是从一棵空树开始，依次插入{20, 10, 5, 30, 40, 57, 3, 2, 4, 35, 25, 18, 22, 23, 24, 19, 18}的过程。
插入20：由于是根结点，所以染成黑色。
插入10：新结点非根，染成红色，满足红黑树定义。
插入5：将新结点染成红色后不满足红黑树定义。由于其叔结点是黑色的，并且是LL型插入，所以右单旋，再将原来的父结点10和爷结点20染色。
插入30：将新结点30染成红色后不满足红黑树定义。由于其叔结点5是红色的，所以将其叔结点5、父结点20、爷结点10染色，然后将爷结点10视作新插入的结点，由于是根结点，所以直接染成黑色即可。
插入40：由于新结点40的叔结点是黑色的，而且是RR型。所以左单旋，并将其原来的爷结点20，父结点30染色。
插入57：新结点57的叔结点20是红色的。其叔结点20、父结点40、爷结点30染色，并将其爷结点30视作新结点，并未违背红黑树的特性，不用继续调整。
插入3：插入后并未违反红黑树特性，不用调整。
插入2：其叔结点是黑色，并且是LL型。右单旋，结点2原来的父结点3和爷结点5染色。
插入4：新结点4的叔结点是红色的，所以将其叔结点2，父结点5，爷结点3染色，并将爷结点3视为新结点，并未违反红黑树特性，不用继续调整。
插入35、25、18：插入后均符合红黑树特性，不用调整。
插入22：新结点22的叔结点是红色的，所以将其叔结点18、父结点25、爷结点20染色，并将爷结点20视为新结点继续调整。由于结点20的叔结点是红色的，将其叔结点3、父结点30、爷结点10染色，并将爷结点10视为新结点继续调整。由于结点10是根结点，直接染成黑色即可。
插入23：新结点的叔结点是黑色的，而且是LR型。所以左单旋后再右单旋，并将原来作为儿结点的新结点23与其爷结点25染色。
插入24：新结点24的叔结点是红色的。所以将其叔结点22、父结点25、爷结点23染色，并将爷结点23视为新结点继续调整。新结点23的叔结点40是黑色的，并且是LR型，所以先左单旋后再右单旋，并将原来的儿结点23与爷结点30染色。
插入19：插入新结点后符合红黑树特性，不用调整。
插入18：新结点的叔结点是黑色的，并且是RL型。所以先右单旋再左单旋，并将原来的儿结点18和爷结点18染色。
B树，又称多路平衡查找树，B树中所有结点的孩子个数的最大值称为B树的阶。m 叉查找树规定：除了根节点外，任何结点⾄少有⌈m/2⌉个分叉，即⾄少含有⌈m/2⌉ − 1 个关键字，并且对于任何一个结点，其所有子树的高度都要相同。
一棵m阶B树或为空树，或为满足如下特性的m叉树：
树中每个结点⾄多有m棵子树，即⾄多含有m-1个关键字。
若根结点不是终端结点，则⾄少有两棵⼦树。
除根结点外的所有⾮叶结点⾄少有 ⌈m/2⌉ 棵⼦树，即⾄少含有 ⌈m/2⌉-1个关键字。
所有非叶结点的结构如下：
其中，Ki（i = 1, 2,…, n）为结点的关键字，且满⾜K1 < K2 <…< Kn；Pi（i = 0, 1,…, n）为指向子树根结点
的指针，且指针Pi-1所指子树中所有结点的关键字均小于Ki，Pi所指子树中所有结点的关键字均大于Ki，n（
⌈m/2⌉- 1 ≤ n ≤ m-1）为结点中关键字的个数。
所有的叶结点都出现在同⼀层次上，并且不带信息（可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为null）。
m阶B树的核心特性：
根节点的子树数∈[2, m]，关键字数∈[1, m-1]。其他结点的子树数∈[ ⌈m/2⌉ , m]；关键字数∈[ ⌈m/2⌉-1 , m-1]
对任⼀结点，其所有子树高度都相同。保证所有结点都绝对平衡。
关键字的值：子树0 < 关键字1 < 子树1 < 关键字2 < 子树2 <…. (类⽐⼆叉查找树 左<中<右)。
算B树高度时不包括叶子结点(失败结点)。
含n个关键字的m阶B树的最小高度
含n个关键字的m阶B树的最大高度
新元素⼀定是插⼊到最底层“终端节点”，⽤“查找”来确定插⼊位置。
在插⼊key后，若导致原结点关键字个数超过上限，则从中间位置（⌈m/2⌉）将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置（⌈m/2⌉）的结点插⼊原结点的⽗结点(若原结点为根结点，则中间位置结点成为新的根结点)。若此时导致其⽗结点的关键字个数也超过了上限，则继续进⾏这种分裂操作，直⾄这个过程传到根结点为⽌，进⽽导致B树⾼度增1。
👆上面这个动画中，由于插入80导致关键字超过上限，此时中间位置为49，将49变为根结点，49右侧的60和80放到新结点中。
👆上面这个动画中，首先正常的插入了83和87，然后插入70时导致关键字个数超过上限，所以中间位置关键字80插入到父结点中，80右侧的83和87放到新结点中。
👆删除的60在终端结点，且删除后关键字个数没有低于下限，所以直接删除即可。
👆删除的80在非终端结点，则⽤直接前驱或直接后继来替代被删除的关键字，这里用直接前驱77替代。找直接前驱的方法与二叉排序树一样类似，当前关键字左侧指针所指⼦树中“最右下”的元素。
👆删除的77在非终端结点，这里使用直接后继进行替换，也可以采用直接前驱替换。当前关键字右侧指针所指⼦树中“最左下”的元素就是直接后继，也就是用82替代77，然后82后面的几个关键字往前移即可。
👆删除关键字38后，该结点的关键字个数低于下限，但是它的右兄弟结点比较富余，向右兄弟结点借一个。采用父子换位法调整该结点、右兄弟及其双亲结点。将父结点中的49（38的后继）移动到原来38所在的位置，再将右兄弟中的70（49的后继也是38后继的后继）移动到父结点中原来49所在的位置。
👆删除关键字90后，该结点的关键字个数低于下限，但是它的左兄弟结点比较富余，向左兄弟借一个。采用父子换位法调整该结点、左兄弟及其双亲结点。将父结点中的88（90的前驱）移动到原来90的位置，再将左兄弟中的87（88的前驱也是90前驱的前驱）移动到父结点中原来88的位置。
👆删除关键字49后，它的兄弟结点不够借，将关键字删除后与兄弟结点及双亲结点中的关键字进行合并。将49的后继节点也就是父结点中的70移动到原来49的位置，再与它的兄弟结点进行合并。但是此时它的父结点中只剩一个关键字了，低于下限了，所以再按同样的方法进行合并，将73的后继也就是82与73合并，再将其与右兄弟结点合并，此时73的父结点已经空了，所以73所在的结点成为新的根结点。
B+树是应数据库所需而出现的一种B树的变形树，有点类似于分块查找。⼀棵m阶的B+树需满⾜下列条件：
每个分支结点最多有m棵子树（孩子结点）。
非叶根结点至少有两棵树，其它每个分支结点至少有 ⌈m/2⌉ 棵子树。目的是追求“绝对平衡”，即所有⼦树⾼度要相同，同时使树尽量矮胖，提高查找效率。
结点的子树个数与关键字个数相等。
所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。
所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。
方法一：从根结点出发，按照类似分块查找的方式进行查找
方法二：沿着p指针的方向进行查找。
B+树中，⽆论查找成功与否，最终⼀定都要⾛到最下面一层结点。
m阶B+树：结点中的n个关键字对应n棵⼦树。
m阶B树：结点中的n个关键字对应n+1棵⼦树。
m阶B+树：根结点的关键字树 n∈[1, m]，其它结点的关键字树 n∈[ ⌈m/2⌉, m ]。
m阶B树：根结点的关键字个数 n∈[1, m-1]，其它结点的关键字个数 n∈[ ⌈m/2⌉-1, m-1 ]。
m阶B+树：在B+树中，叶结点包含全部关键字，⾮叶结点中出现过的关键字也会出现在叶结点中。
m阶B树：在B树中，各结点中包含的关键字是不重复的。
m阶B+树：在B+树中，叶结点包含信息，所有非叶结点仅起索引作⽤，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。
m阶B树：B树的结点中都包含了关键字对应的记录的存储地址。
对于B+树，每个结点都保存在磁盘的一个磁盘块中，查找某个元素时，每次查找一个结点，都会有一次读盘的操作，所以为了提高B+树的性能，可以使一个磁盘块可以包含更多个关键字，使得B+树的阶更大，树高更矮，读盘次数更少，查找更快。
散列表（Hash Table），⼜称哈希表。是⼀种数据结构，特点是：数据元素的关键字与其存储地址直接相关。通过散列函数（哈希函数）进行计算可以得到数据元素的存储地址。若不同的关键字通过散列函数映射到同⼀个值，则称它们为同义词，通过散列函数确定的位置已经存放了其他元素，则称这种情况为冲突。
散列函数的设计目标是让不同关键字的冲突尽可能减少。
散列表表长为m，取一个不大于m但最接近或等于m的质数p。用质数取模，可以使分布更均匀，冲突更少，但是可能会导致一部分空间利用不上。
其中，a和b是常数。这种⽅法计算最简单，且不会产⽣冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。
设关键字是r进制数（如⼗进制数），而r个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；⽽在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。
具体取多少位要视实际情况⽽定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。
拉链法（又称链接法、链地址法），哈希表采用数组+链表的方式实现，把所有“同义词”存储在⼀个链表中。
从图中可以看出，68与55通过哈希函数计算后得到同样的值，所以挂在同一个链表上。
如果要查找元素79，通过哈希函数计算后得出地址为1，就从地址为1的链表上挨个对比，通过对比4次关键字后就可以找到元素79了，那么79的查找长度就是4，也就是对比关键字的次数。
如果查找元素21，H(21)=21%13=8，地址为8的位置只有一个空指针，所以查找失败，由于没有对比任何元素，所以查找长度就是0。
指可存放新表项的空闲地址既向它的同义词表项开放，⼜向它的非同义词表项开放。其数学递推公式为：Hi = (H(key) + di) % m
i = 0, 1, 2,…, k（k ≤ m-1），m表示散列表表长；di为增量序列；i 可理解为“第i次发生冲突”
开放地址法的作用就是当发生冲突时，通过改变di的值推算出元素应该存储在哈希表的什么位置。开放定址法包括线性探测法、平方探测法以及伪随机序列法。
线性探测法
di = 0, 1, 2, 3, …, m-1；即发生冲突时，每次往后探测相邻的下⼀个单元是否为空。
这里需要注意的是，该哈希函数计算出的值域为[0, 12]，但是冲突处理函数的值域为[0, 15]。
查找元素也是同样的道理👇
从8一直对比到13，13是个空位置，可以判断出数组里没有21这个元素，一共对比了6次。这里和拉链法不用的是，空位置的判断也要算作一次比较，因为数组中存放的是和查找目标同类型的元素，而拉链法的数组中存放的是一个指针。
采⽤“开放定址法”时，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填⼊散列表的同义词结点的查找路径，可以做⼀个删除标记，进行逻辑删除。👇
查找效率分析👇
可以看出，查找失败时需要对比的次数还是很多的，因为线性探测法很容易造成同义词、非同义词的“聚集（堆积）”现象，严重影响查找效率。
平方探测法
当di = 0², 1², -1², 2², -2², …, k², -k²时，称为平方探测法，⼜称二次探测法，其中k ≤ m/2
比起线性探测法更不易产生“聚集（堆积）”问题。散列表长度m必须是⼀个可以表示成4j + 3的素数，才能探测到所有位置。
伪随机序列法
di 是⼀个伪随机序列，如 di= 0, 5, 24, 11, …
除了原始的散列函数 H(key) 之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算⼀个新地址，直到不冲突为止：Hi = RHi(Key) 。i=1,2,3….,k。
⭐⭐⭐⭐⭐
转载请注明出处：https://blog.csdn.net/weixin_43461520/article/details/124377079本文已收录至我的Github仓库DayDayUP：github.com/RobodLee/DayDayUP，欢迎Star
如果您觉得文章还不错，请给我来个
点赞，收藏，关注学习更多编程知识，WeChat扫描下方二维码关注公众号『 R o b o d 』：
