查找

查找长度——在查找运算中，需要对比关键字的次数称为查找长度。
平均查找长度（ASL, Average Search Length ）—— 所有查找过程中进行的关键字的⽐较次数的平均值

顺序查找

思路：从头找到尾

代码实现：

typedef struct {
  ElemType *elem;
  int TableLen;//表长
}SSTable;
int Search_Seq(SSTable ST,ElemType key){
    ST.elem[0]=key;
    for(i=ST.TableLen;ST.elem[i]!=key;--i);
    return i;
}

ST.elem[0]为哨兵：哨兵的作用是遍历时不会越界，即遍历到0时会退出。这要求由后向前遍历

$ALS_{\text{成功}}=\frac{(n+1)}{2}$；$ASL_{\text{不成功}}=n+1$

线性链表只能顺序查找

有序表的顺序查找：不需查找完就可以退出。

$ASL_{成功}=\frac{(n+1)}{2}$；$ASL_{不成功}=\frac{n}{2}+\frac{n}{(n+1)}$

折半查找

二分法，只适用于有序线性表

代码：

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

ASL=$log_2(n+1)-1$

分块查找

块内无序，块间有序

“索引表”中保存每个分块的最大关键字和分块的存储区间。

示意图如下所示：

设索引查找和块内查找的平均查找长度分别为LI、 LS，则分块查找的平均查找长度为

$$ ASL=L_I + L_S $$

假设，⻓度为n的查找表被均匀地分为b块，每块s个元素

⽤顺序查找查索引表：

$$ ASL=\frac{s^2 + 2s + n}{2s} $$

当 $s=\sqrt{n}$ 时，分块查找的平均查找长度达到最优。$ASL_{最小}=\sqrt{n} +1$

⽤折半查找查索引表：

用折半查找查索引表时，平均查找长度为：

$$ ASL = \lceil \log_2(b + 1) \rceil + \frac{s+1}{2} $$

树形查找

二叉排序树

定义

二叉排序树，又称二叉查找树（BST，Binary Search Tree）一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：

• 左子树上所有结点的关键字均小于根结点的关键字；
• 右子树上所有结点的关键字均大于根结点的关键字。
• 左子树和右子树又各是一棵二叉排序树。

所以：左子树结点值< 根结点值< 右子树结点值

所以：进行中序遍历，可以得到一个递增的有序序列

查找过程

若树非空，目标值与根结点的值比较：若相等，则查找成功；若小于根结点，则在左子树上查找，否则在右子树上查找。查找成功，返回结点指针；查找失败返回NULL

相关操作及实现

结点定义：

typedef struct BSTNode{
   int data;
   struct BSTNode *lchild, *rchild;
}BSTNode,*BSTree;

查找：

//非递归
BSTNode *Search(BSTree T, int key){
  while(T!=NULL && key!=T->data){
    if(key < T->data) T = T->lchild;
    else T = T->rchild;
  }
  return T;
}
//递归
BSTNode *Search(BSTree T, int key){
  if(T==NULL || key==T->data) return T;
  if(key < T->data) return Search(T->lchild, key);
  return Search(T->rchild, key);
}

插入：

若原二叉排序树为空，则直接插入结点；否则，若关键字k小于根结点值，则插入到左子树，若关键字k大于根结点值，则插入到右子树

bool Insert(BSTree &T, int key){ 
  if(T==NULL){
    T = (BSTNode *)malloc(sizeof(BSTNode));
    T->data = key;
    T->lchild = T->rchild = NULL;
    return true;
  }
  else if(key == T->data) return false;//树中存在相同关键字的结点，插入失败
  else if(key < T->data) return Insert(T->lchild, key);
  else return Insert(T->rchild, key);
}

不同的关键字序列可能得到同款二叉排序树，也可能得到不同款二叉排序树

删除：

• 先找到被删除的结点z
• 若被删除结点z是叶结点，则直接删除，不会破坏二叉排序树的性质
• 若结点z只有一棵左子树或右子树，则让z的子树成为z父结点的子树，替代z的位置。
• 若结点z有左、右两棵子树，则令z的直接后继（或直接前驱）替代z，然后从二叉排序树中删去这个直接后继（或直接前驱），这样就转换成了第一或第二种情况

直接后继：z的右子树中最左下结点，直接前驱：z的左子树中最右下结点

如下图所示三种情况的删除操作：

复杂度分析

最好情况：n个结点的二叉树最小高度为$(\lfloor log_2n \rfloor+1)$。平均查找长度= $O(log_2n)$

最坏情况：每个结点只有一个分支，树高h=结点数n。平均查找长度=O(n)。

需要借助[[#平衡二叉树]]来解决达到平均查找长度为$O(log_2n)$。

平衡二叉树

定义

平衡二叉树（Balanced Binary Tree），简称平衡树（AVL树）

• 树上任一结点的左子树和右子树的高度之差不超过1。结点的平衡因子=左子树高-右子树高。

相关操作

插入：在插入过程中可能会破坏平衡，因此需要重新平衡。

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

时刻记住：二叉排序树的特性：左子树结点值< 根结点值< 右子树结点值

分为以下四种情况：

1）LL平衡旋转（右单旋转）。由于在结点A的左孩子（L）的左子树（L）上插入了新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将A的左孩子B向右上旋转代替A成为根结点，将A结点向右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树。

2）RR平衡旋转（左单旋转）。由于在结点A的右孩子（R）的右子树（R）上插入了新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将A的右孩子B向左上旋转代替A成为根结点，将A结点向左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树

3）LR平衡旋转（先左后右双旋转）。由于在A的左孩子（L）的右子树（R）上插入新结点，A的平衡因子由1增至2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置，然后再把该C结点向右上旋转提升到A结点的位置

4）RL平衡旋转（先右后左双旋转）。由于在A的右孩子（R）的左子树（L）上插入新结点，A的平衡因子由-1减至-2，导致以A为根的子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置，然后再把该C结点向左上旋转提升到A结点的位置

删除：

平衡二叉树的删除操作具体步骤：

• 删除结点（方法同“二叉排序树”）
• 一路向北找到最小不平衡子树，找不到就完结撒花
• 找最小不平衡子树下，“个头”最高的儿子、孙子
• 根据孙子的位置，调整平衡（LL/RR/LR/RL）
  孙子在LL：儿子右单旋
  孙子在RR：儿子左单旋
  孙子在LR：孙子先左旋，再右旋
  孙子在RL：孙子先右旋，再左旋
• 如果不平衡向上传导，继续一路向北！

删除操作举例：

复杂度分析

平衡二叉树删除操作时间复杂度=$O(log_2n)$

这里其实会有一个红黑树的，但是难度有点高，我就不在这里整理了，等以后有力气学的时候再学

B树

B树中所有结点的孩子结点数的最大值称为B树的阶。一棵m阶树或为空树，或满足如下特征的m叉树：

• 树中每个结点至多有m棵子树，即至多含m-1个关键字
• 若根结点不是终端结点，则至少有两棵子树
• 除根结点外的所有非叶结点至少有$\lceil m/2\rceil$棵子树，即至少$\lceil m/2\rceil -1$个关键字
• 非叶结点关键字递减，且关键字左子树小于该关键字，右子树大于该关键字
• 所有叶结点在同一层，不带信息

B树是所有结点平衡因子都为0的多路查找树。

B树示例：

B树的结点插入示例（3阶B树）：

删除示例：

B+ 树

B与B+树的区别

• 在B+树中，n个关键字的结点含有n棵子树，即每个关键字对应一棵子树。而B树中，具有n个关键字的结点含有n+1棵子树
• 在B+树种，每个结点的关键字个数n的范围是$\lceil m/2\rceil <=n<= m$(根结点1<=n<=n)；在B树中，每个结点的关键字个数n的范围是$\lceil m/2 \rceil -1<=n<=n-1$,(根结点1<=n<=m-1)
• 在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有相应子树的最大关键字和指向该子树的指针，不含该关键字对应记录的存储地址
• 在B+树中，叶结点包含了全部关键字，即在非叶结点种出现的关键字也会出现在叶结点中；而在B树中，叶结点包含的关键字和其他结点包含的关键字是不重复的。

散列表

定义

散列表（哈希表，Hash Table） ：是⼀种数据结构。
特点是：可以根据数据元素的关键字计算出它在散列表中的存储地址
散列函数（哈希函数） ：Addr=H(key) 建⽴了“关键字”→“存储地址”的映射关系

构造方法

• 直接定址法：$H(key) = a \times key + b$，其中 $a, b$ 为常数。最简单且无冲突，适用于关键字分布基本连续的情况。若关键字分布不连续，空位较多，会造成空间浪费。
• 除留余数法：$H(key) = key \bmod p$，其中 $p$ 是一个不大于 $m$（散列表长度）但接近于 $m$ 的质数。
• 数字分析法 —— 选取数码分布较为均匀的若⼲位作为散列地址，设关键字是r进制数（如⼗进制数），而r个数码在各位上出现的频率不⼀定相同，可能在某些位上分布均匀⼀些，每种数码出现的机会均等；⽽在某些位上分布不均匀，只有某⼏种数码经常出现，此时可选取数码分布较为均匀的若⼲位作为散列地址。
• 平⽅取中法——取关键字的平⽅值的中间⼏位作为散列地址。具体取多少位要视实际情况⽽定。 这种⽅法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布⽐较均匀。

处理冲突的方法

线性探测法

$d_i=0,1,2,...,m-1$,发生冲突时，找到一个空闲空间，看看下一个。容易产生堆积现象

平方探测法

$d_i=0^2,1^2,-1^2,2^2,-2^2,...,k^2,-k^2$,k<=m/2.散列表长度m必须是一个可以表示成4k+3的素数。能解决堆积现象，但不能探测到散列表的所有单元

再散列法

$d_i=Hash_2(key)$，再通过另外一个散列函数计算关键字的地址增量。$H_i=(H(key)+i*Hash_2(key))\%m$,i是冲突次数，初始时为0.

拉链法

如果将所有同义词存储在一个线性链表中，那么在查找时只需遍历该链表即可找到所有同义词。假设有关键词序列{19,14,23,01,68,20,84,27,55,11,10,79}，散列函数$H(key)=key\%13$，所建立的表如下图所示：

散列表查找及性能分析

$\alpha=\frac{表中记录数n}{散列表长度m}$，散列表的平均查找长度依赖于散列表的装填因子$\alpha$,而不直接依赖于n或m。$\alpha$越大，冲突的可能性越大。

串的模式匹配算法

也就是KMP算法！由于这一章节相对独立而且相对来说比较复杂，难度并不高，所以在第二轮复习的过程中我没有整理KMP算法，考场上直接暴力解也不是不行，所以等着以后和红黑树一起来整理。

计算next。

前一个next为n时，匹配前面串前n与后n是否相同，相同这个next是n+1,不同的话就-1，再匹配，匹配到相同后+1，以此类推。

计算next，就是看当前字符前的子串前后相同的长度，若由0开始，则next[i]=前后相同长度+1，若由-1开始，next[i]=前后相同长度。nextval第一个是和next值一样，后面的话对比a[next[i]]，如果相同的话，nextval[i]=nextval[next[i]]，就是两个一样，如果不同的话，nextval[i]=next[i]，这个nextval的作用和next一样，只不过是加强版，能更快。都是用来比较用的。