在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找的结果一般分为两种：一是查找成功，即在数据集合中找到了满足条件的数据元素；二是查找失败。

用于查找的数据集合称为查找表，它由同一类型的数据元素(或记录)组成，可以是一个数组或链表等数据类型。对查找表经常进行的操作一般有$4$种：

• 查询某个特定的数据元素是否在查找表中；

• 检索满足条件的某个特定的数据元素的各种属性；

  若查找表只涉及上述操作，即无须动态地修改查找表，那么称为静态查找表。否则，需要动态地插入或删除的查找表称为动态查找表。

• 在查找表中插入一个数据元素；

• 从查找表中删除某个数据元素。

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

在查找过程中，一次查找的长度是指需要比较的关键字次数，而平均查找长度$ASL$则是所有查找过程中进行关键字的比较次数的平均值，其数学定义为：

$n$是查找表的长度；$P_i$是查找第$i$个数据元素的概率，一般认为每个数据元素的查找概率相等，即$P_i=1/n$，$C_i$是找到第$i$个数据元素所需进行的比较次数。平均查找长度是衡量查找算法效率的最主要的指标。

顺序查找

顺序查找又称线性查找，它对顺序表和链表都是适用的。对于顺序表，可通过数组下标递增来顺序扫描每个元素；对于链表，可通过指针$next$来依次扫描每个元素。顺序查找通常分为：

• 一般线性表的顺序查找：从线性表的一端开始，逐个检查关键字是否满足给定的条件。若查找到某个元素的关键字满足给定条件，则查找成功，返回该元素在线性表中的位置；若已经查找到表的另一端，但还没有查找到符合给定条件的元素，则返回查找失败的信息。

  可以在数组的边界引入哨兵，即插入一个满足搜索条件的数据，使得循环不必判断数组是否会越界。

  typedef struct{        // 查找表的数据结构(顺序表)
      ElemType *elem;        // 动态数组基址
      int TableLen;    // 表的长度
  }SSTable;
  int Search_Seq(SSTable ST,ElemType key){
      ST.elem[0]=key;            // 0号位置存储哨兵
      int i;
      for(i=ST.TableLen;ST.elem[i]!=key;--i);        // 从后往前找
      return i;            // 查找成功返回下标；查找失败返回0
  }
  

  对于有$n$个元素的表，给定值$key$与表中按顺序查找的第$i$个元素相等时，需进行$i$次关键字的比较，查找成功时，顺序查找的平均长度为

  当查找不成功时，与表中各关键字的比较次数显然是$n+1$次，从而顺序查找不成功的平均查找长度为$ASL_{不成功}=n+1$。

  若能预先得知每个记录的查找概率，则应先对记录的查找概率进行排序，使表中记录按查找概率由大至小重新排列。

  缺点：平均查找长度较大，效率低，时间复杂度为$O(n)$；优点：对数据元素的存储没有要求，对表中记录的有序性也没有要求。

  对线性的链表只能进行顺序查找。

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

  查找成功的平均查找长度和一般线性表的顺序查找一样。

  查找不成功的平均查找长度在相等查找概率的情形下为$ASL_{不成功}=\sum\limits_{j=1}^nq_j(l_j-1)=\Large\frac{1+2+...+n+n}{n+1}=\frac{n}{2}+\frac{n}{n+1}$。$q_j$是到达第$j$个失败结点的概率，在相等查找概率的情形下，它为$1/(n+1)$；$l_j$是第$j$个失败结点所在的层数。

折半查找

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

int Binary_Search(SeqList L,ElemType key){    // L升序排列
    int low=0,high=L,TableLen-1,mid;
    while(low<=high){
        mid=(low+high)/2;            // 取中间位置
        if(L.elem[mid]==key)return mid;        // 查找成功，返回所在位置mid
        else if(L.elem[mid]>key)high=mid-1;    // 查找失败，且所在位置元素大于关键字的值，从前半部分继续查找
        else low=mid+1;            // 查找失败，且所在位置元素小于关键字的值，从后半部分继续查找
    }
    return -1;            // 查找失败
}

折半查找的过程可用二叉树来描述，称为判定树。树中每个圆形结点表示一个记录，结点中的值为该记录的关键字值；树中最下面的叶结点(失败结点)都是方形的，它表示查找不成功的情况。查找成功时的查找长度为从根结点到目的结点的路径上的结点数，而查找不成功时的查找长度为从根结点到对应失败结点的父结点的路径上的结点数；每个结点值均大于其左子结点值，且均小于其右子结点值。若有序序列有$n$个元素，则对应的判定树有$n$个圆形的非叶结点和$n+1$个方形的叶结点。判定树是一棵平衡二叉树。

在等概率查找时，查找成功的平均查找长度为：

$h$是树的高度，并且元素个数为$n$时树高$h=\log_2(n+1)$(向上取整)，树高不包括失败结点。所以，折半查找的时间复杂度为$O(\log_2n)$，平均情况下比顺序查找的效率高。

仅适合于顺序存储结构，不适合于链式存储结构，且要求元素按关键字有序排列。

折半查找时，若求得的$mid$值为小数，则选择向上取整或向下取整，一旦确定就不能改变。折半查找的判定树中，若$mid=[(low + high)/2]_{向下取整}$，则对于任何一个结点必有：右子树结点数$-$左子树结点数$=0$或$1$

分块查找

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

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

分块查找的过程分为两步：第一步是在索引表中确定待查记录所在的块，可以顺序查找或折半查找索引表；第二步是在块内顺序查找。

对索引表进行折半查找时，若索引表中不包含目标关键字，则折半查找最终停在$low>high$，要在$low$所指分块中查找。

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

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

若对索引表采用折半查找时，则平均查找长度为

若查找表是“动态查找表”，则采用链式存储更好。

二叉排序树

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

• 若左子树非空，则左子树上所有结点的值均小于根结点的值。

• 若右子树非空，则右子树上所有结点的值均大于根结点的值。

• 左、右子树也分别是一棵二叉排序树。

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

二叉排序树的查找：

BSTNode *BST_Search(BiTree T,ElemType key){
    while(T!=NULL && key!=T->data){        // 若树空或等于根结点值，则结束循环
        if(key < T->data)T=T->lchild;    // 若根节点大于查找值，则在左子树上查找
        else T=T->rchild;                // 若根节点小于查找值，则在右子树上查找
    }
    return T;    // 查找成功，返回结点指针;查找失败返回NULL
}

二叉排序树的插入：(循环执行插入函数，即为构造函数)

int BST_Insert(BiTree &T,keyType k){
    if(T==NULL){    // 树空，插入记录为根结点
        T=(BiTree)malloc(sizeof(BSTNode));
        T->key=k;
        T->lchild=T->rchild=NULL;
        return 1;    // 插入成功
    }else if(k==T->key)return 0;    // 树中存在相同关键字的结点，插入失败
    else if(k < T->key)return BST_Insert(T->lchild,k);    // 在左子树上进行递归插入
    else return BST_Insert(T->rchild,k);    // 在右子树上进行递归插入
}

二叉排序树的删除：

• 若被删除结点$z$是叶结点，则直接删除，不会破坏二叉排序树的性质。

• 若结点$z$只有一棵左子树或右子树，则让$z$的子树成为$z$父结点的子树，替代$z$的位置。

• 若结点$z$有左、右两棵子树，则令$z$的直接后继(或直接前驱)替代$z$，然后从二叉排序树中删去这个直接后继(或直接前驱)，这样就转换成了第一或第二种情况。

  • $z$的前驱：$z$的左子树中最右下结点(该节点一定没有右子树)，即从左子树的根节点开始一直向右遍历，直至右结点为空。
  • $z$的后继：$z$的右子树中最左下结点(该节点一定没有左子树)，即从右子树的根节点开始一直向左遍历，直至左结点为空。

二叉排序树的查找效率，主要取决于树的高度，在查找运算中，需要对比关键字的次数称为查找长度。若二叉排序树的左、右子树的高度之差的绝对值不超过$1$，则这样的二叉排序树称为平衡二叉树，它的平均查找长度为$O(log_2n)$。若二叉排序树是一个只有右(左)孩子的单支树(类似于有序的单链表)，则其平均查找长度为$O(n)$。相同的关键字其插入顺序不同可能生成不同的二叉排序树。不同的关键字序列可能得到同款二叉排序树。

在等概率情况下，查找成功的平均查找长度$ASL$为每个结点查找成功所需要查找的次数和除以总结点数。查找失败的平均查找长度$ASL$为每个结点查找失败所需要查找的次数和除以查找失败的空结点数。

当有序表是静态查找表时，宜用顺序表作为其存储结构，而采用二分查找实现其查找操作；若有序表是动态查找表，则应选择二叉排序树作为其逻辑结构。

平衡二叉树

为避免树的高度增长过快，降低二叉排序树的性能，规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过$1$。将这样的二叉树称为平衡二叉树，简称平衡树($AVL$树)。定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是$-1$、$0$或$1$。

typedef struct AVLNode{
    int key;            // 数据域
    int balance;        // 平衡因子
    struct AVLNode *lchild,*rchild;
}AVLNode,*AVLTree;

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

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

平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应的调整。可将调整的规律归纳为下列$4$种情况：

• $LL$平衡旋转(右单旋转)：由于在结点$A$的左孩子($L$)的左子树($L$)上插入了新结点，$A$的平衡因子由$1$增至$2$，导致以$A$为根的子树失去平衡，需要一次向右的旋转操作。将$A$的左孩子$B$向右上旋转代替$A$成为根结点，将$A$结点向右下旋转成为$B$的右子树的根结点，而$B$的原右子树则作为$A$结点的左子树。
• $RR$平衡旋转(左单旋转)：由于在结点$A$的右孩子($R$)的右子树($R$)上插入了新结点，$A$的平衡因子由$-1$减至$-2$，导致以$A$为根的子树失去平衡，需要一次向左的旋转操作。将$A$的右孩子$B$向左上旋转代替$A$成为根结点，将$A$结点向左下旋转成为$B$的左子树的根结点，而$B$的原左子树则作为$A$结点的右子树。
• $LR$平衡旋转(先左后右双旋转)：由于在$A$的左孩子($L$)的右子树($R$)上插入新结点，$A$的平衡因子由$1$增至$2$，导致以$A$为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将$A$结点的左孩子$B$的右子树的根结点$C$向左上旋转提升到$B$结点的位置，然后把该$C$结点向右上旋转提升到$A$结点的位置。
• $RL$平衡旋转(先右后左双旋转)：由于在$A$的右孩子($R$)的左子树($L$)上插入新结点，$A$的平衡因子由$-1$减至$-2$，导致以$A$为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将$A$结点的右孩子$B$的左子树的根结点$C$向右上旋转提升到$B$结点的位置，然后把该$C$结点向左上旋转提升到$A$结点的位置。

假设以$n_h$，表示深度为$h$的平衡树中含有的最少结点数。则有$n_0=0,n_1=1,n_2=2$，并且有$n_h=n_{h-1}+n_{h-2}+1$。平衡二叉树的平均查找长度为$O(log_2n)$。

平衡二叉树的删除过程：时间复杂度为$O(log_2n)$

1. 删除结点(方法同“二叉排序树”)
2. 一路向上找到最小不平衡子树，若无不平衡子树，删除过程结束，若有不平衡子树，则继续
3. 找最小不平衡子树$A$下，“个头”最高的儿子、孙子。设$A$的左右子树的根分别为$B,C$，$h_B,h_C$分别为以$B,C$为根的子树的树高，若$h_B>h_C$则儿子为$B$，否则为$C$。同理，孙子为儿子的儿子。
4. 根据孙子的位置，调整平衡($LL/RR/LR/RL$)，调整方法与插入方法一致。
5. 如果不平衡向上传导，继续2

删除一个结点后，再将其重新插入平衡树，所得的平衡树和原来的平衡树可能相同也可能不同，不论删去的结点是否是叶子结点。

红黑树

平衡二叉树$AVL$：插入/删除很容易破坏“平衡”特性，需要频繁调整树的形态。如：插入操作导致不平衡，则需要先计算平衡因子，找到最小不平衡子树(时间开销大)，再进行$LL/RR/LR/RL$调整。适用于以查为主、很少插入/删除的场景。

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

红黑树是二叉排序树：左子树结点值≤ 根结点值≤ 右子树结点值。与普通$BST$相比，差别：

• 每个结点或是红色，或是黑色的

• 根节点是黑色的

• 叶结点(外部结点、$NULL$结点、失败结点)均是黑色的

• 不存在两个相邻的红结点(即红结点的父节点和孩子结点均是黑色)

  可能存在两个相邻的黑结点。

• 对每个结点，从该节点到任一叶结点的简单路径上，所含黑结点的数目相同

struct RBnode{        // 红黑树的结点定义
    int key;        // 关键字的值
    RBnode* parent;    // 父结点指针
    RBnode* lChild;    // 左孩子指针
    RBnode* rChild;    // 右孩子指针
    int color;        // 结点颜色
}

结点的黑高$bh$——从某结点出发(不含该结点)到达任一空叶结点的路径上黑结点总数。

性质：

• 从根节点到叶结点的最长路径不大于最短路径的$2$倍
• 有$n$个内部节点的红黑树高度$h ≤ 2???_2(? + 1)$
• 若根结点黑高为$h$，内部结点数(关键字)最少有$2^h-1$个(总共$h$层黑结点的满树形态)

红黑树的查找：与$BST$、$AVL$相同，从根出发，左小右大，若查找到一个空叶节点，则查找失败。红黑树查找操作时间复杂度$= O(???_2?)$

红黑树的插入：

• 先查找，确定插入位置(原理同二叉排序树)，插入新结点

• 新结点是根——染为黑色

• 新结点非根——染为红色

  • 若插入新结点后依然满足红黑树定义，则插入结束

  • 若插入新结点后不满足红黑树定义，需要调整，使其重新满足红黑树定义。看叔结点的颜色，叔结点即父结点的兄弟结点。

    • 黑叔：旋转+染色

      • $LL$型：右单旋，父换爷+染色(父&爷结点变色)
      • $RR$型：左单旋，父换爷+染色(父&爷结点变色)
      • $LR$型：左、右双旋，儿换爷+染色(儿&爷结点变色)
      • $RL$型：右、左双旋，儿换爷+染色(儿&爷结点变色)

    • 红叔：染色+变新

      • 叔父爷染色，爷变为新结点(即将原来的爷结点看作是新插入的结点，从头开始判断)

红黑树的删除：删除过程也是先执行二叉查找树的删除方法。若待删结点有两个孩子，不能直接删除，而是找到该结点的中序后继(或前驱)填补，即右子树中最小的结点，然后转换为删除该后继结点。由于后继结点至多只有一个孩子，这样就转换为待删结点是叶结点或仅有一个孩子的情况。最终，删除一个结点有以下两种情况:

• 待删结点没有孩子。

• 待删结点只有右子树或左子树。

  • 如果待删结点只有右子树或左子树，则只有两种情况，均用子树代替待删结点，并变色。

  • 如果待删结点没有孩子。若该结点是红色的，直接删除，无需做任何调整。

  • 如果待删结点没有孩子，并且该结点是黑色的。假设待删结点为$y$，$x$是用来替换$y$的结点(注意，当$y$是终端结点时，$x$是黑色的$NULL$结点)。删除$y$后将导致先前包含$y$的任何路径上的黑结点数目减$1$，因此$y$的任何祖先都不再满足性质⑤，简单的修正办法就是将替换$y$的结点$x$视为还有额外的一重黑色，定义为双黑结点。即，如果将任何包含结点$x$的路径上黑结点数目加$1$，在此假设下，性质⑤满足，但破坏了性质1。那么，删除操作的任务就转化为将双黑结点恢复为普通结点。

    分为下面四种情况，区别在于$x$的兄弟结点$w$及$w$的孩子的颜色不同。

    • $x$的兄弟结点$w$是红色的。

      $w$必须有黑色左右孩子和父结点。交换$w$和$x$的父结点$x.p$的颜色，然后对$x. p$做一次左旋，而不会破坏红黑树的任何规则。现在，$x$的新兄弟结点是旋转之前$w$的某个孩子结点，其颜色为黑色，这样，就将情况$1$转换为情况$2$、$3$或$4$处理。

    • $x$的兄弟结点$w$是黑色的，$w$的左孩子是红色的，$w$的右孩子是黑色的。

      ($RL$，先右旋，再左旋)即红结点是其爷结点的右孩子的左孩子。交换$w$和其左孩子的颜色，然后对$w$做一次右旋，而不破坏红黑树的任何性质。现在，$x$的新兄弟结点$w$的右孩子是红色的，这样就将情况$2$转换为了情况$3$。

    • $x$的兄弟结点$w$是黑色的，且$w$的右孩子是红色的。

      ($RR$，左单旋)即红结点是其爷结点的右孩子的右孩子。交换$w$和其父结点$x.p$的颜色，把$w$的右孩子着为黑色，并对$x$的父结点$x.p$做一次左旋，将$x$变为单重黑色，此时不再破坏红黑树的任何性质，结束。

    • $x$的兄弟结点$w$是黑色的，且$w$的两个孩子结点都是黑色的。

      因为$w$也是黑色的，所以从$x$和$w$上去掉一重黑色，使得$x$只有一重黑色而$w$为红色。为了补偿从$x$和$w$中去掉的一重黑色，把$x$的父结点$x.p$额外着一层黑色，以保持局部的黑高不变。通过将$x.p$作为新结点$x$来循环，$x$上升一层。如果是通过情况$1$进入到情况$4$，因为原来的$x.p$是红色的，此时终止循环，并将新结点$x$变为黑色，结束。

红黑树的删除操作的时间复杂度$= O(???_2?)$

$B$树

$B$树又称多路平衡查找树，$B$树中所有结点的孩子个数的最大值称为$B$树的阶，通常用$m$表示。一棵$m$阶$B$树或为空树，或为满足如下特性的$m$叉树：

• 树中每个结点至多有$m$棵子树，即至多含有$m-1$个关键字。
• 若根结点不是终端结点，则至少有两棵子树。
• 除根结点外的所有非叶结点至少有$[m/2]_{向上取整}$棵子树，即至少含有$[m/2]_{向上取整}-1$个关键字。
• 结点中关键字从左到右递增有序，关键字两侧均有指向子树的指针，左边指针所指子树的所有关键字均小于该关键字，右边指针所指子树的所有关键字均大于该关键字。
• 所有的叶结点都出现在同一层次上(任一结点的所有子树高度都相同)，并且不带信息，可以视为外部结点或类似于折半查找判定树的查找失败结点，实际上这些结点不存在，指向这些结点的指针为空。
• 所有结点的平衡因子均等于$0$。$n$个关键字的$B$树必有$n+1$个叶子结点。

$B$树的高度不包括最后的不带任何信息的叶结点所处的那一层，若$n\geq1$，则对任意一棵包含$n$个关键字、高度为$h$、阶数为$m$的$B$树：

• 因为$B$树中每个结点最多有$m$棵子树，$m-1$个关键字，所以关键字的个数应满足$n\leq(m-1)(1+m+m^2+...+m^{h-1})=m^h-1$，因此有$h\geq log_m(n+1)$。
• 若让每个结点中的关键字个数达到最少，则容纳同样多关键字的$B$树的高度达到最大。由$B$树的定义：第一层至少有$1$个结点；第二层至少有$2$个结点；除根结点外的每个非终端结点至少有$[m/2]_{向上取整}$棵子树，则第三层至少有$2[m/2]_{向上取整}$个结点，第$h+1$层至少有$2[m/2]_{向上取整}^{h-1}$个结点，第$h+1$层是不包含任何信息的叶结点。对于关键字个数为$n$的$B$树，叶结点即查找不成功的结点为$n+1$，由此有$n+1\geq2[m/2]_{向上取整}^{h-1}$，即$h\leq\log_{[m/2]_{向上取整}}(\frac{n+1}{2})+1$。

$B$树的查找包含两个基本操作：在$B$树中找结点；在结点内找关键字。由于$B$树常存储在磁盘上，因此前一个查找操作是在磁盘上进行的，而后一个查找操作是在内存中进行的，即在找到目标结点后，先将结点信息读入内存，然后在结点内采用顺序查找法或折半查找法。

在$B$树上查找到某个结点后，先在有序表中进行查找，若找到则查找成功，否则按照对应的指针信息到所指的子树中去查找。查找到叶结点时(对应指针为空指针)，则说明树中没有对应的关键字，查找失败。

$B$树的插入删除

核心要求：

• 对$m$阶$B$树，除根节点外，结点的关键字个数$[m/2]_{向上取整}-1\leq n\leq m-1]$。
• 子树$0<$关键字$1<$子树$1<$关键字$2<$子树$2<...$

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

1. 定位：利用前述的$B$树查找算法，找出插入该关键字的最低层中的某个非叶结点，在$B$树中查找$key$时，会找到表示查找失败的叶结点，这样就确定了最底层非叶结点的插入位置。插入位置一定是最低层中的某个非叶结点(终端结点)。

2. 插入：在$B$树中，每个非失败结点的关键字个数都在区间$[[m/2]_{向上取整}-1,m-1]$内。插入后的结点关键字个数小于$m$，可以直接插入；插入后检查被插入结点内关键字的个数，当插入后的结点关键字个数大于$m-1$时，必须对结点进行分裂：

   • 取一个新结点，在插入$key$后的原结点，从中间位置$[m/2]_{向上取整}$将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置$[m/2]_{向上取整}$的结点插入原结点的父结点。
   • 若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致$B$树高度增$1$。

$B$树中的删除操作要使得删除后的结点中的关键字个数$\geq[m/2]_{向上取整}-1$，因此将涉及结点的“合并”问题。

• 当被删关键字$k$不在终端结点(最低层非叶结点)中时，可以用$k$的直接前驱(或直接后继)$k^`$来替代$k$，然后在相应的结点中删除$k^`$，关键字$k^`$必定落在某个终端结点中，则转换成了被删关键字在终端结点中的情形。

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

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

• 当被删关键字在终端结点(最低层非叶结点)中时，有下列三种情况：

  • 直接删除关键字。若被删除关键字所在结点的关键字个数$\geq[m/2]_{向上取整}$，表明删除该关键字后仍满足$B$树的定义，则直接删去该关键字。

  • 兄弟够借。若被删除关键字所在结点删除前的关键字个数$=[m/2]_{向上取整}-1$，且与此结点相邻的右(或左)兄弟结点的关键字个数$\geq[m/2]_{向上取整}$，则需要调整该结点、右(或左)兄弟结点及其双亲结点(父子换位法)，以达到新的平衡。

  • 兄弟不够借。若被删除关键字所在结点删除前的关键字个数$=[m/2]_{向上取整}-1$，且与该结点相邻的左右兄弟结点的关键字个数均$=[m/2]_{向上取整}-1$，则将关键字删除后与左(或右)兄弟结点及双亲结点中的关键字进行合并。

    在合并过程中，双亲结点中的关键字个数会减$1$。若其双亲结点是根结点且关键字个数减少至$0$(根结点关键字个数为$1$时，有$2$棵子树)，则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到$[m/2]_{向上取整}-2$，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合$B$树的要求为止。

$B+$树

$B+$树是应数据库所需而出现的一种$B$树的变形树。一棵$m$阶的$B+$树需满足下列条件：

• 每个分支结点最多有$m$棵子树(孩子结点)。
• 非叶根结点至少有两棵子树，其他每个分支结点至少有$[m/2]_{向上取整}$棵子树。
• 结点的子树个数与关键字个数相等。
• 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来。(支持顺序查找)
• 所有分支结点(可视为索引的索引)中仅包含它的各个子结点(即下一级的索引块)中关键字的最大值及指向其子结点的指针。

$m$阶的$B+$树与$m$阶的$B$树的主要差异如下：

• 在$B+$树中，具有$n$个关键字的结点只含有$n$棵子树，即每个关键字对应一棵子树；而在$B$树中，具有$n$个关键字的结点含有$n+1$棵子树。
• 在$B+$树中，每个结点(非根内部结点)的关键字个数$n$的范围是$[m/2]_{向上取整}\leq n\leq m$(根结点：$1\leq n\leq m$)；在$B$树中，每个结点(非根内部结点)的关键字个数$n$的范围是$[m/2]_{向上取整}-1\leq n\leq m-1$(根结点：$1\leq n\leq m-1$)。
• 在$B+$树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址。可以使一个磁盘块可以包含更多个关键字，使得$B+$树的阶更大，树高更矮，读磁盘次数更少，查找更快。
• 在$B+$树中，叶结点包含了全部关键字，即在非叶结点中出现的关键字也会出现在叶结点中；而在$B$树中，叶结点(最外层内部结点)包含的关键字和其他结点包含的关键字是不重复的。

分支结点的某个关键字是其子树中最大关键字的副本。通常在$B+$树中有两个头指针：一个指向根结点，另一个指向关键字最小的叶结点。因此，可以对$B+$ 树进行两种查找运算：一种是从最小关键字开始的顺序查找，另一种是从根结点开始的多路查找。

$B+$树的查找、插入和删除操作和$B$树的基本类似。只是在查找过程中，非叶结点上的关键字值等于给定值时并不终止，而是继续向下查找，直到叶结点上的该关键字为止。所以，在$B+$树中查找时，无论查找成功与否，每次查找都是一条从根结点到叶结点的路径。

散列查找

散列函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为$Hash(key)=Addr$(这里的地址可以是数组下标、索引或内存地址等)

散列函数可能会把两个或两个以上的不同关键字映射到同一地址，称这种情况为冲突，这些发生碰撞的不同关键字称为同义词。一方面，设计得好的散列函数应尽量减少这样的冲突；另一方面，由于这样的冲突总是不可避免的，所以还要设计好处理冲突的方法。

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

理想情况下，对散列表进行查找的时间复杂度为$O(1)$，即与表中元素的个数无关。查找长度定义为：在查找运算中，需要对比关键字的次数。

在构造散列函数时，必须注意以下几点：

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

常用的散列函数：

• 直接定址法：直接取关键字的某个线性函数值为散列地址， 散列函数为：

  计算最简单，且不会产生冲突。适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

• 除留余数法：假定散列表表长为$m$，取一个不大于$m$但最接近或等于$m$的质数$p$，利用以下公式把关键字转换成散列地址。散列函数为

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

• 数字分析法：设关键字是$r$进制数(如十进制数)，而$r$个数码在各位上出现的频率不一定相同，可能在某些位上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时应选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

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

任何设计出来的散列函数都不可能绝对地避免冲突，处理冲突的方法：

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

  取定某一增量序列后，对应的处理方法就是确定的。通常有以下$4$种取法：

  • 线性探测法：当$d=0,1,...,m-1$时，称为线性探测法。这种方法的特点是：冲突发生时，顺序查看表中下一个单元(探测到表尾地址$m-1$时，下一个探测地址是表首地址$0$)，直到找出一个空闲单元(当表未填满时一定能找到一个空闲单元)或查遍全表。 可能会使大量元素在相邻的散列地址上聚集(或堆积)起来，大大降低了查找效率。

  • 平方探测法：当$d=0^2,1^2,-1^2,...,k^2,-k^2$时，称为平方探测法，其中$k\leq m/2$，散列表长度$m$必须是一个可以表示成$4k+3$的素数，又称二次探测法。可以避免出现“堆积”问题，它的缺点是不能探测到散列表上的所有单元，但至少能探测到一半单元。

  • 再散列法：当$d=Hash_2(key)$时，称为再散列法，又称双散列法。需要使用两个散列函数，当通过第一个散列函数$H(key)$得到的地址发生冲突时，则利用第二个散列函数$Hash_2(key)$计算该关键字的地址增量。它的具体散列函数形式如下：

    初始探测位置$H_0=H(key)\%m$。$i$冲突的次数，初始为$0$。在再散列法中，最多经过$m-1$次探测就会遍历表中所有位置，回到$H_0$位置。

  • 伪随机序列法：当$d=$伪随机数序列 时，称为伪随机序列法。

  不能随便物理删除表中的已有元素，因为若删除元素，则会截断其他具有相同散列地址的元素的查找地址。因此，要删除一个元素时，可给它做一个删除标记，进行逻辑删除。但这样做的副作用是：执行多次删除后，表面上看起来散列表很满，实际上有许多位置未利用，因此需要定期维护散列表，要把删除标记的元素物理删除。在数组中，空位置的对比要算作关键字的比较次数。

• 拉链法(链接法)：把所有的同义词存储在一个线性链表中，这个线性链表由其散列地址唯一标识。拉链法适用于经常进行插入和删除的情况。对链表中空指针的对比不算做关键字的比较。

散列表的查找过程：

1. 初始化：$Addr=Hash(key)$；
2. 检测查找表中地址为$Addr$的位置上是否有记录，若无记录，返回查找失败；若有则比较它与$key$的值，若相等，则返回查找成功标志，否则执行下一步。
3. 用给定的处理冲突方法计算“下一个散列地址“，并把$Addr$置为此地址，转入步骤$2$。

散列表的查找效率取决于三个因素：散列函数、处理冲突的方法和装填因子。散列表的装填因子一般记为$\alpha$，定义为一个表的装满程度，即表中记录数除以散列表长度。散列表的平均查找长度依赖于散列表的装填因子$\alpha$，而不直接依赖于 表中记录数 或 散列表长度。$\alpha$越大，发生冲突的可能性越大。