week4

408

算法

33.查找算法

②二分查找：仅适用于有序的顺序表，令$mid=\lfloor low+high\rfloor$
时间复杂度：$O(lo{g}_2(n+1))$
判定树的构造：

所以对于$mid=\lfloor low+high\rfloor$，右子树结点数-左子树结点数=0或1
判定树的树高h=$\lfloor lo{g}_2(n+1)\rfloor$
所以ASL成功<=h，ASl失败<=h

③分块查找：又称索引顺序查找，数据分块存储，块内无序，块间有序
算法思想：索引表中记录每个分块的最大关键字、分块的区间；先查索引表(顺序或折半，顺序多)、再对分块内进行顺序查找

ASL=查索引表的ASL+查分块的ASL
设n个记录，均匀分为b块，每块s个记录
若用顺序查找索引表：$ASL=\frac{b+1}{2}+\frac{s+1}{2}$，当$s=\sqrt{n}时，AS{L}_{min}=\sqrt{n}+1$
若用二分查找索引表：$ASL=\lceil lo{g}_2(b+1)\rceil +\frac{s+1}{2}$
块内也可以用链表相连，方便增删

34.二叉排序树

又称二叉查找树，左子树上的所有结点小于根结点的关键字，根结点小于右子树的关键字
左子树和右子树又各是一棵二叉排序树
中序遍历可以得出递增的有序队列
二叉排序树的查找：

插入：

删除：

1. 若被删除的是叶子结点，则直接删除
2. 若结点z只有一棵左子树或者右子树，则让z的子树成为z父结点的子树，替代z的位置
3. 若z又左右两棵子树，则令z的直接后继(或者直接前驱)代替z，然后从二叉排序树直接删除这个直接后继(或者直接前驱)

ASL跟二分查找的相同

35.平衡二叉树

平衡二叉树，简称平衡树(AVL)，树上任意结点的左子树和右子树的高度之差不超过1，也是一棵二叉排序树
结点的平衡因子=左子树高-右子树高

在进行插入操作后，只要调整最小不平衡子树就能恢复平衡

如何调整：

1. LL：在A的左孩子的左子树中插入导致的不平衡
2. RR：在A的右孩子的右子树中插入导致的不平衡
3. LR：在A的左孩子的右子树中插入导致的不平衡
4. RL：在A的右孩子的左子树中插入导致的不平衡

①LL平衡旋转(右旋)：将A的左孩子B向右上旋转代替A成为根结点，将A结点右下旋转成为B的右子树的根结点，而B的原右子树则作为A结点的左子树
②RR平衡旋转(左旋)：将A的右孩子B向左上旋转代替A成为根结点，将A结点左下旋转成为B的左子树的根结点，而B的原左子树则作为A结点的右子树

③LR平衡旋转(先左旋后右旋)：将A的左孩子B的右子树的根结点C向左上旋转代替B成为根结点，再将C结点右上旋转代替A结点
④RL平衡旋转(先右旋后左旋)：将A的右孩子B的左子树的根结点C向右上旋转代替B成为根结点，再将C结点左上旋转代替A结点

平衡二叉树的删除：

1. 删除结点
   1. 若删除的结点是叶子，直接删
   2. 若删除的结点只有一棵子树，用子树顶替删除位置
   3. 若删除的结点有两棵子树，用前驱(或后继)结点顶替，并转换为对前驱(或后继结点)的删除
2. 一路向上找到最小不平衡子树，找不到就break
3. 找到最小不平衡子树中"个头"最高的儿子、孙子
4. 根据孙子的位置，调整平衡(LL/RR/LR/RL)
5. 如果不平衡向上传导，则回到2

"个头"就是其子树的长度

36.红黑树

红黑树也是二叉排序树，跟平衡二叉树相比，红黑特性不容易被破坏，所以适合插入/删除操作
红黑树的定义：

1. 每个结点是红色或者黑色的
2. 根结点是黑色的
3. 叶结点(外部结点、NULL结点、失败结点)是黑色的
4. 不存在两个相邻的红结点
5. 对每个结点，从该节点到任意叶子结点的简单路径上的黑结点的数目相同

查找和二叉排序树是相同的

插入操作：(染色就是染为相反的颜色)

1. 先确定位置，原理同二叉排序树
2. 若新结点是根，则染为黑色
3. 若新结点非根，则染为红色
   1. 若新结点插入后依然满足红黑树定义，则插入结束
   2. 若插入新结点后不满足，则需要调整
      1. 若新结点的叔叔结点是黑的，则旋转+染色：
         1. LL：右旋，父换爷+染色
         2. RR：左旋，父换爷+染色
         3. LR：左旋再右旋，儿换爷+染色
         4. RL：右旋再左旋，儿换爷+染色
      2. 红的，则叔父爷染色，爷变为新结点

LL：

叔红：

RR：

红黑树的删除操作的时间复杂度：O(log2 n)
删除结点的处理方式跟二叉排序树的删除一样
删除后很可能会破坏红黑特性，需要调整结点颜色、位置

37.B树

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

1. 树中每个结点至多有m棵子树，即至多含有m-1个关键字
2. 若根结点不是终端结点，则至多有两棵子树
3. 除根结点外的所有非叶结点至少有$\lceil m/2\rceil$棵子树，即至少含有$\lceil m/2-1\rceil$个关键字
4. 所有的叶结点都出现在同一层次上，并且不带信息(值为null)

m阶B树的核心特性：

1. 根结点的子树数量∈[2, m]，关键字数∈[1, m-1]，其它结点的子树数∈[$\lceil m/2\rceil$, m]，关键字数∈[$\lceil m/2\rceil -1$, m-1]
2. 对任一结点，其所有子树的高度相同
3. 关键字的值：子树0<关键字1<子树1<关键字2<子树2

含n个关键字的B树的高度(不包含叶子结点)为$lo{g}_m(n+1)<=h<=lo{g}_{\lceil m/2\rceil }(\frac{n+1}{2}+1)$

插入操作：

1. 先通过查找找到插入位置(一定是在终端结点)
2. 若插入后结点的关键字个数未超过上限，则无需其它处理
3. 若插入后关键字个数超过上限，则需要将当前结点的中间元素放到父节点中，当前结点按中间元素分裂成两个结点
4. 若3导致父节点的关键字个数超过上限，则再执行3的操作
5. 根结点的分裂会让B树的高度++

删除操作：

1. 若不是终端结点的关键字
   1. 用直接前驱或直接后继替代其位置，转化为对终端结点的删除
   2. 直接前驱：当前关键字左子树中位置最右下的元素
   3. 直接后继：当前关键字右子树中位置最左下的元素
2. 是终端结点的关键字
   1. 删除后结点关键字未低于下限，则break
   2. 若低于下限
      1. 若右兄弟够借，则用当前结点的后继、后继的后继依次顶替空缺
      2. 若左兄弟够借，则用当前结点的前驱、前驱的前驱依次顶替空缺
      3. 若都不够，则需要与父结点内的关键字、左右兄弟进行合并；合并后可能导致父节点关键字数量不够，需要继续和合并

38.B+树

B+树的特性：

1. 每个分支结点最多有m棵子树(孩子结点)
2. 非叶根结点至少有两棵子树，其它每个分支结点至少有$\lceil m/2\rceil$
3. 结点的子树个数与关键字个数相同
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小排序，并且相邻叶结点按大小顺序相互连接起来

根结点的关键字数n∈[1, m]
其它结点的关键字数n∈[$\lceil m/2\rceil$, m]
在B+树中，叶结点包含信息，所有非叶结点仅起索引作用，非叶结点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针，不含有该关键字对应记录的存储地址

39.散列表

散列表，又称哈希表，可以根据数据元素的关键字计算出它在散列表中的存储地址
散列函数，或哈希函数，建立了 “关键字”-> "存储地址"的映射关系
同义词：若不同的关键字通过散列函数映射到同一个存储地址，则称它们为同义词
冲突(碰撞)：在散列表中插入一个元素时，若插入的位置已经存储了其它元素，则称这种情况为冲突

构造散列函数的方法：

1. 除留余数法：H(key)=key % p，p通常为不大于散列表的最大质数，较为通用
2. 直接定址法：H(key)=a*key+b，适用于关键字分布基本连续
3. 数字分析法：选取数码分布较为均匀的若干位作为散列地址，适用于关键字集合已知
4. 平方取中法：计算关键字的平方，取中间几位作为散列地址，适用于关键字的每位取指都不够均匀

解决冲突的方法：

1. 拉链法(链接法、链地址法)：把所有同义词存储在一个链表中
2. 开放定址法：当初始散列地址发生冲突时，根据探测序列di探测下一个地址
   1. 线性探测法：di=0,1,2,…,m-1，也就是将元素放到原本位置的后面
   2. 平方探测法：di=0^2,12,-(1^2),22,-(2^2),…,k2,-(k^2)
   3. 双散列法：di=i*hash2(key)，其中hash2(key是另一个散列函数)
   4. 伪随机序列法：di是一个伪随机序列，如di=0,5,3,11…

注意：采用开放定址法时，删除操作不能简单地将元素删除，这样会截断探测路径，可以做一个已删除标记，做逻辑上的删除

计算散列表的ASL：

1. $AS{L}_{成功}=\frac{1}{n}\ast {\sum }_{i=1}^n{C}_i$，其中，n为散列表中已存在的元素个数，Ci为成功查找第i个元素所需的比较次数
2. $AS{L}_{失败}=\frac{1}{r}\ast {\sum }_{i=1}^r{C}_i$，其中，r为散列函数取值的个数，Ci为散列函数取值为i时查找失败的比较次数

注意：散列函数取值的个数跟散列表的长度可能不同
装填因子：$\alpha =\frac{表中记录数n}{散列表长度m}$，反映了一个散列表 "满"的程度
装填因子越大，越容易发生冲突；从而导致插入、查找效率降低，ASL增大
聚集现象：在处理冲突的过程中，几个初始散列地址不同的元素争夺同一个后继散列地址
聚集现象会影响查找效率，导致ASL提升
采用线性探测法容易导致聚集现象

40.排序

排序算法的稳定性：对于两个相等的元素R1和R2，R1在R2前面，排序后R1还在R2前面，这个算法就是稳定的，否则就是不稳定的
内部排序：数据都在内存中，外部排序：数据太多，无法全部放入内存

①插入排序：将每一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成

空间复杂度：O(1)；时间复杂度：O(n^2)；稳定性：稳定

②希尔排序(shell sort)将待排序列表分割成若干形如L[i, i+d, i+2d,…, i+kd]的特殊子表，对各个子表进行直接插入排序。缩小增量d，重复上述过程直到d=1

空间复杂度：O(1)；时间复杂度：未知，但优于直接插入排序；稳定性：不稳定

③冒泡排序：两两对比，按需交换位置，直到比较完。若某一趟排序过程中未发生交换，则算法可提前结束

空间复杂度：O(1)；时间复杂度：O(n^2)；稳定性：稳定

④快速排序：在待排序列表L[1…n]中任取一个元素pivot作为枢轴，通过一躺排序将待排序列分为两个独立的部分L[1…k-1]和L[k+1…n]，使得左边的子序列的元素都小于pivot，右侧的都大于等于，则pivot放在了其最终位置L(k)上，这个过程称为依次划分。然后分别递归地对两个子序列进行划分，直到每部分只有一个元素或者为空为止

空间复杂度：O(n)；时间复杂度：O(nlogn)；稳定性：不稳定

⑤简单选择排序：每一趟在待排序元素中选取关键字最小的元素加入有序子序列

空间复杂度：O(1)；时间复杂度：O(n^2)；稳定性：不稳定

⑥堆排序：
堆：顺序存储的完全二叉树，结点i的左孩子是2i，右孩子是2i+1，父节点是i/2
大根堆：根结点大于左右孩子；小根堆：根结点小于左右孩子
算法思想(以大根堆为例)：

1. 建堆
   1. 编号<=n/2的所有结点依次下坠调整(自底向上处理各个结点)
   2. 调整规则：小元素逐层下坠(与关键字更大的孩子交换)
2. 排序
   1. 将堆顶元素加入有序子序列(将其与待排序列的最后一个元素互换)
   2. 堆底元素换到堆顶后，需要进行下坠调整，恢复大根堆的特性
   3. 每次调整后根结点就是待排序列中最大的元素，就可以将其加入有序序列(类似选择排序)
   4. 上述过程重复n-1趟

空间复杂度：O(1)；时间复杂度：O(nlogn)；稳定性：不稳定

⑦归并排序：
归并：将多个有序的序列合并为一个
算法思想：

1. 若low>high，则将序列分从中间mid=(low+high)/2分开
2. 对左半部分[low, mid]递归地进行归并排序
3. 对右半部分[mid+1, high]递归地进行归并排序
4. 将左右两个有序子序列合并为一个

空间复杂度：O(n)；时间复杂度：O(nlogn)；稳定性：稳定

41.堆的插入与删除

插入：新元素放到表尾，根据大/小根堆的要求，新元素不断上升，直到无法继续上升为止
删除：被删除元素用表尾元素替代，根据大/小根堆的要求，新元素不断下坠，直到无法继续上升为止