查找

在数据集合中寻找满足某种条件的数据元素的过程称为查找。查找成功和查找失败

平均查找长度ASL

顺序查找

$\Large ASL_{成功}=\sum_{i=1}^{n}{P_i(n-i+1)}=\frac{n+1}{2}$ $\Large ASL_{失败}=n+1$

有序线性表查找失败

$\Large ASL_{失败}=\frac{n}{2}+\frac{n}{n+1}$

折半查找

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

int binary_find(SSTable 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;
}

折半查找最多比较次数不会超过树的高度

分块查找

块内元素可以无序，块间元素有序，第一个块中的最大关键字小于第二个块中的所有记录的关键字。

易错

可以称为折半查找判断树的

一定要左子树结点大于等于右子树
或者右子树结点大于等于左子树

可以构成折半查找中关键字比较序列的一定要右子树上的点都大于该点，左子树上的点都小于该点

树形查找

二叉排序树（BST）

插入

删除

若被删除结点z是叶节点，则直接删除
若结点只有一棵左子树或者右子树，则让z的子树称为z父的子树，替代z的位置
若结点z有左、右子树，则令z的直接后继（直接前驱）替代z，然后从二叉排序树中删除这个直接后继（直接前驱）。（可以在右子树上找中序第一个子女填补）

平衡二叉树（AVL）

定义结点左子树和右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡的值只可能是-1，1，0

插入

LL 平衡旋转，由于在结点A的左孩子的左子树插入新节点，导致A不平衡。右旋一次
RR 平衡旋转，在结点A的右孩子的右孩子插入新节点，导致A不平衡，需要一次左旋
LR平衡旋转（先左后右旋转），左孩子的右子树上插入新结点。
RL平衡旋转（先右后左旋转），右孩子的左子树上插入新节点。

删除

用二叉排序树的方法对结点w进行删除操作
若导致了不平衡，则从结点w开始往上回溯，找到第一个不平衡的结点z（即最小不平衡子树），y为结点z的高度最高的孩子结点；x是结点y的高度最高的孩子结点。
然后对以z为根的子树进行平衡调整，其中x、y和z可能的位置有4中情况：
1. y是z的左孩子，x是y的左孩子（LL右旋）
2. y是z的左孩子，x是y的右孩子（LR，先左旋然后右旋）
3. y是z的右孩子，x是y的右孩子（RR，左旋）
4. y是z的右孩子，x是y的左孩子（RL，先右旋然后左旋）

平衡二叉树查找

假设以表示深度为h的平衡二叉树中含有的最少结点树。同时有（1 是根节点）

红黑树

一棵红黑树是满足如下红黑性质的二叉排序树：

每个结点或是红色的，或是黑色的
根节点是黑色的
叶节点（虚构的外部结点，NULL结点）都是黑色的
不存在两个相邻的红结点（即红结点的父节点和孩子结点都是黑色的）
对每个结点，从该结点到任意一个叶子结点的简单路径上，所含黑结点的数量相同。

从某节点出发（不包含该结点）到达一个叶节点的任意一个简单路径上的黑节点总数称为该结点的黑高（记为bh）。

根节点的黑高称为红黑树的黑高

性质

从根到叶节点的最长路径不大于最短路径的2倍
有n个内部结点的红黑树的高度
1. 从根结点到叶节点（不包含叶节点）的任何一条简单路径上至少有一半是黑节点，因此黑高至少为于是

新插入红黑树中的结点始终是红色

红黑树的插入

用二叉查找树插入法插入，并将结点z着为红色，若结点z的父节点是黑色的，无需调整
若z是根节点，则将z染色为黑色
若z不是根节点，且z的父节点z.p是红色的。
1. z的叔结点y是黑色的，且z是一个右孩子
  
  z是爷结点的左孩子的右孩子，先左旋然后右旋
2. z的叔结点y是黑色的，且z是一个左孩子
  
  z是其爷结点的左孩子的右孩子，直接右旋
  
  相似的，当叔结点是左孩子的时候也有RL，RR旋转
z的叔结点时红色的
1. 将z.p 和 y（叔结点）都染成黑色，将z.p.p染成红色，然后把z.p.p作为新的结点z来重复循环，指针z在树种上移两层。

红黑树的删除

B树和B+树

一棵m阶B树或为空树，或为满足如下特性的m叉树

树中每个结点至多m棵子树，即至多m-1个关键词
若根节点不是叶结点，则至少有2棵子树，即至少有一个关键字
除根节点外的所有非叶节点至少有个子树，至少有个关键字
P0指向子树的所有关键字都小于K1（关键字），P1指向子树的关键字都大于K1关键字


n	P0	K1	…	Kn	Pn

性质

结点的孩子个数等于该结点中关键字个数+1
若根节点没有关键字就没有子树，此时B树为空。若根节点有关键字，则其子树个数必然大于等于2
结点中关键字从左到右递增，关键字两侧均指向有子树的指针

B树查找

根据关键字大小查找就好了，找到了叶节点说明没找到（查找失败）

B树高度

B树高度是不包括最后的叶节点的那一层

任意一棵包含n个关键字、高度为h，阶数为m的B树

让每个结点关键字最多，则容纳相同多关键字的B树高度达到最小。

$\Large n<=(m-1)(1+m + m^2 + ... + m^{h-1})=m^h-1 \\$

则有

$\Large h>=log_m(n+1)$

若让每个结点关键字个数达到最少则容纳相同多关键字的B树高度达到最大。

第二层是最少2个结点，除了根节点之外的每个非叶节点至少有棵子树，则第三层至少个结点,…

第h+1层至少有$\Large 2 \lceil \frac{m}{2} \rceil^{h-1} $个结点。则有$ \Large n+1>=2 \lceil \frac{m}{2} \rceil^{h-1}$

B树插入

定位，利用B树查找算法，找到插入该关键字的终端结点。
插入。如果该点插入之后关键字个数小于m，则可以直接插入；否则需要分裂一下、
分裂。去一个新结点，在插入key之后的原结点，从中间位置将其中的关键字分为两个部分，左部分包含的关键字放在原结点中，右部分包含的关键字放在新节点中，中间位置的结点插入原结点的父节点。若导致父节点也超数量了，就继续分裂直到根节点。