DSA

数据结构

一、绪论

A. 计算

B. 计算模型

• 图灵机 （q, c; d, L/R, p）
当前状态，当前字符，改写字符，左右转，转入状态

• RAM

D. 复杂度分析：级数

• 算数级数：末项平方

• 幂方级数：比幂次高一阶

• 几何级数：末项同阶

• 调和级数：

• 对数级数：

• 复杂级数 P49

• 封底估算
赤道周长
1天 1生 三生三世

E. 迭代与递归

• 分治与减治 总和最大区段和算法

• 动态规划——最长公共子序列

二、向量

• 容量递增——分摊后，装填因子100%
容量加倍——分摊后，装填因子>50%

• 二分查找（A） 可能中途取等 平均查找长度

• fibonacci查找
递推式
整理后对\lambda求导可以得到\lambda=(\sqrt{5}-1/2)时，\alpha(\lambda)=1.440420达到最小

• 二分查找（B）只比较一次就深入，无法判等

• 二分查找（C）search()总是返回不大于e的最后一个元素，保持A[lo-1]总是当前已确认的不大于e的最大者，而A[hi]总是大于e的最小者，最终二者重合，A[lo-1]即是不大于e的最大者。

• 插值查找：线性预估mi的位置，只对线性分布的数据有效
平均每次比较宽度缩为，但最坏情况下为（最不线性的时候，例如0,0,0,0,147.92.140.4200000）
从O(logn)到O(loglogn)，优势并不明显

• 实际上可以先插值，再二分，最后顺序

• 冒泡排序（两种改进版？）
最好O(n)最差O(n^2)。稳定。

• 二路归并O(n)总共O(nlogn)
实现恰当时可以保证稳定性（左侧子向量优先）

• 位图
可用于去除重复度极高的元素（一遍插入）（压缩起来的bool数组）
筛法内循环每次迭代O(n/i)步，由素数定理至多次，总耗时O(nlogn)
快速初始化：将位图拆分成一列索引和一列实际存的值

三、列表

• 在后面的数据结构中selectgMax()可改进至O(logn)（堆）

• 每个序列对应一个循环节，循环节之间不相交，每次交换M都会脱离原来的循环节自成一个循环节。M所属的循环节长度恰-1，其余保持不变。无需交换的情况在c个循环节下会出现c次，最大值为n，期望为（n个随机排列时，第n大的在第n位的概率是1/n）

• 逆序对
逆序对记录在后一个元素上，例如{5,3,1,4,2}的逆序对为0+1+2+1+3=7
Bubblesort每次交换逆序元素必减少1对逆序对
Insertionsort的关键码比较次数为O(I)（I为逆序对的数量），总运行时间为O(n+I)

• 游标实现的列表
理解成一条data的链和一条free的链即可

四、栈与队列

• 递归函数的空间复杂度取决于最大递归深度，而非递归实例总数，可以显式地迭代以优化空间

• 尾递归：多一个参数，将中间参数传到下一步，最后一步调用递归。在空间上可以大幅优化。
例如：原本sum(5)=5+4+3+2+sum(1)，最后一次递归的时候存了5个数
但是改成尾递归sum(0, 5)=sum(5, 4)=sum(9, 3)=...=sum(15, 0)return;就节省了很多空间

• 栈的应用：进制转换、括号匹配

• 栈混洗
考虑S再度变空的时刻（也就是1被拿出来的时刻），共n个，1的两边分别有0和k-1到k-1和0个数，于是
不是栈混洗的例子：（3,1,2），以及所有含有（...,k,...,i,...,j,...)的例子（此为充要）
以此可以构造扫描三次的算法，另可由（...,j+1,...,i,...,j,...）（此为充要，考虑j+2在哪）构造算法（扫描两次）。另外可以用栈来模拟，只需要

• 中缀表达式
优先级表

• 逆波兰表达式
适合反复使用。手工转换时先全部加上括号，再用运算符代替右括号并删除左括号。
自动计算的时候只需要在求中缀表达式的过程中，如果是数字就加入表达式，如果是操作符，当前操作符运算的时候（也就是它比后面大的时候），加入表达式。

• Steap=Stack+Heap=push=pop+getMax
准备另一个栈P，存储当前位置往后的最大值。每次压入的时候和第一个比较，如果不如它则保持它。（优化：压入相同元素的操作改为，计数+1）
Queap=Queue+Heap=enqueue+dequeue+getMax
准备另一个队列P，存储当前位置往后的最大值。每次加入的时候加在最后一位，并逐次和之前的比较，把比它小的都改成它。（优化：通过计数）最坏情况是O(n)但是均摊分析是O(1)

• 双栈当队
用计数分析、分摊分析、势能分析，均可得到复杂度为O(n)

• 直方图内最大矩形
算法一：算出每个点的左侧最近的一个比它小的点，用栈来记录一个单调不减的序列，直到减了之后，不断pop找到它应该取代的位置（即比它小的位置）。用相反的方式可以得到每个点右侧最近的一个比它小的点，然后得到矩形。
算法二：算法一不能动态输入。可以同样用栈来记录一个单调不减的序列，直到减了之后，算出从当前位置往左所有比当前大的点的maxRect，这些点的右边已经没有任何可能性了，左边由于单调递增，最近的比它小的点就是栈顶。（反证）

五、二叉树

• 记录度数为0,1,2的节点各有个，则：
边数
叶节点数（数学归纳法，对于所有n=k成立）

• 先序、中序、后序，对中心节点的访问从先到后

• 先序遍历：
从左边拉出一条藤，每次访问左孩子时把右孩子入栈。可能把空节点push进S。
左右子树都类似尾递归。

• 中序遍历
从左边拉出一条藤压入S，pop出本次该访问的并访问，转向右子树再拉藤。（转向的右子树可以为空）每个点出栈的时候左子树已经完全遍历，故只需访问它再从其右孩子出发。
S中不可能有空节点
右子树类似尾递归
根据分摊分析，虽然每次迭代不一定是O(1)时间，但是加起来不会超过O(n)。
可以用中序遍历来确定二叉树的顺序。（先后pop）

• 后序遍历
左右子树都不是尾递归
栈顶若是x的父亲，直接pop+visit，若是其右兄，则找到子树中最靠左的节点。
根据分摊分析，虽然每次迭代不一定是时间，但是加起来不会超过。
表达式树：数值作为树叶，用运算符连接。

• 层次遍历
即广度优先，用队列实现。

• 完全二叉树
叶节点仅限于最低两层，底层叶子均居于次底层叶子的左边，除末节点的父亲，内部节点均有双子。
叶节点不少于内部节点（），但至多多出一个。
层次遍历中最大规模n/2上取整（即前n/2上取整-1次均出1入2），最大规模可能出现2次（即有一个最后只有一个子树的情况）

• 重构
先序or后序+中序，数学归纳法，只需要通过先序和后序找到中心节点x在中序遍历中的位置，就可以划分出左右子树并分别重构。
光靠先序+后序是不可以的，因为一旦某个子树为空，则无法区分另一半是左子树还是右子树
但先序+后序+真二叉树（偶度数）就可，由真保证了左右子树要么均空，要么均不空。在先序中找到右子树的开端，在后序中找到左子树的开端，即可递归
增强序列（将nullptr输出为某一字符）先序和后序均可以通过分治重构，中序不行。通过NULL-非NULL=1的性质来找子树。

• PFC编码
用01字典树的叶节点进行编码，互不为前缀，从前向后读取即可
平均情况下，最优编码树叶子只能出现在倒数两层之内，否则可以交换更优

• Huffman
每次取频率最小的两棵树合并
出现频率最低的字符x和y一定在底层且互为兄弟。
以此用数学归纳法可以知道算法正确性。
可以用优先队列优化到O(nlogn)

六、图

• 邻接矩阵
适用于稠密图，空间，具有可扩展性，但是空间利用率很低

• 邻接表
适用于稀疏图，空间O(n+e)，对于平面图来说就是O(n)
可以建立逆邻接表以枚举所有通过定点v的弧

• BFS复杂度（O(n+e)）
无向图中，顶点v到u的最近距离记作
则BFS中，顶点按照进行排列，相邻顶点dist相差不超过1，由树边连接的恰相差1

• DFS
dTime fTime
dTime(v) < dTime(u) ? FORWARD : CROSS;
Parenthesis Lemma（括号引理）
定义活跃期active[u] = (dTime[u], fTime[u])
活跃期的包含关系代表继承，无交集则无关。
后向边数等于回路数？每个回路确实对应一条后向边，但是可能出现共用

• 拓扑排序
零入度算法
针对有向无环图（DAG），每个DAG是一个偏序集，而拓扑排序对应与一个全序集。每次取出零入度的点即可。
零出度算法
基于DFS，将VISITED节点压入栈，一旦发现向后边即报告NOT_A_DAG
DFS后，如果没有报告，顺序弹出VISITED，各节点按照fTime逆序排列。

七、图应用

• 优先级搜索
先对当前节点的邻居更新优先级，再选出优先级最高的，直到所有节点都加入。
时间复杂度为，若采用优先级队列，则两层循环分别是和，合计复杂度为。（对于稠密图来说这是倒退）

• 最小支撑树
Cayley公式：连接n个互异顶点的树共有棵
Prim算法：寻找极短跨边。证明见习题解析，6-28，数学归纳

• Dijkstra算法
各边权重均为正

• 双连通分量
关节点：删除后连通分量增多
无关节点的图称为双连通图，极大双连通子图称作双连通分量
如何确定关节点？
• 通过DFS留下的标记来甄别
• 需满足：
根r至少有2棵子树（否则r就是要找的）
有某个孩子u，其子树不能经由BACKWORD边连接到v的任何真祖先a
此时v是两个BCC的关节点
hca(v) = subtree(v)表示经后向边能抵达的最高祖先。
DFS过程中，一旦发现后向边(v,u)，即取hca(v) = min(hca(v), dTime(u))

• Kruskal
每次选择最廉价的边加入

• 并查集

八、二叉搜索树

• search的时候想象一个和e相同数值的哨兵节点
删除时分单双分支，单分支直接用子树取代，双分支找到直接后继并交换。其直接后继必然不是双分支。双分支时succ()耗时

• 随机生成排列则平均树高为
随机组成拓扑关系则平均树高为
随机情况并不常见。例如删除算法固定使用succ()会使得左倾

• BBST——适度平衡，高度渐进不超过

• 经过不超过O(n)次旋转，等价的BST之间均可相互转化

• avl
balFac(v) = height(lc(v)) - height(rc(v))绝对值小于1
高度为h的AVL至少包含个节点
反过来由n个节点构成的AVL，高度不至于超过
插入时失衡的至少是祖父，删除时可能是父亲。
删除操作最多需要旋转次（Knuth：平均0.21次）

九、二叉搜索树应用

• Range Query
可以通过在每个坐标点记录左下方的点的个数来判断，耗费空间过多且无法处理小数

• KDTree
• 1D
构造成BST然后二分查找，并找到Lowest Common Ancestor(LCA)，从LCA拉出左右两藤并找出藤上节点即为所求
查找O(n)，预处理O(nlogn)，储存空间O(n)
• 2D
每次对横竖两个方向分别找到中间值进行划分
分割线包括上右但不包括下左
每次查找如果包含在内就报告，如果有交集就深入。
预处理
查询与报告加起来，这是由于每次查询在四个孩子中不会超过两个

• Multi-Level Search Tree
用BBST按照x的顺序存储所有数据，对于每个x的节点，存储一个按照y排序的树。
线段树套线段树

十、高级搜索树

• splay
双层伸展。在单层的时候每一周期累积，分摊下来则是。而双层伸展后分摊仅需
插入时先splay，在根处插入
删除时先splay，再对右侧子树再次splay根节点，从而转化成没有左子树的形式
分摊复杂度为，效率甚至可以达到，任何连续m次查找都可在时间内完成
势能定义为
只需要证明每次操作

• B树
关键码和节点各组织成一个vector
每d代合并为一个超级节点，为路数，有m-1个关键码（可以空缺）
设关键码个数为n，则分支数为n+1，于是有
分支数也不能太少，上取整，称作(m/2上取整,m)-树（例如(3,5)-树）（根节点有两个分支）
设总共关键码数量为N，则外部节点数量为N+1（归纳证明）
(2,3)-树是最简单的B树
• 查找
对关键码进行查找，如果找到就返回，否则转向找到位置的节点。
根节点常驻RAM，忽略内存查找的时间，于是运行时间主要取决于I/O次数，O(logn)
• 最大树高和最小树高
第k层节点数为n_k则有
考虑外部节点那层，，带入即得到：
• 插入
发生上溢的时候，取中点分裂。上溢有可能进行树高次，当根节点上溢时树高增加。上溢裂开而不旋转，可以避免I/O
• 删除
找到后继，进行交换并删除。出现下溢时如果左右兄弟能够支援，就通过父节点旋转一下。
左右兄弟不存在或者自身难保的时候，左右必然至少有一个兄弟关键码恰m/2下取整-1（极限）
于是相邻两个一个有m/2下取整-1个关键码，一个有m/2下取整-2个，取它们夹着的那个父节点合并。但是可能导致下溢传播，但不会超过O(h)次处理

• 红黑树
并发性 insert/remove局部需要改动的区域都不超过O(1)
持久性 支持对历史版本的访问，相邻版本差异不超过O(1)，可以共享节点
（1）树根为黑，（2）外部节点为黑（真二叉树），（3）其余节点若为红则只能有黑孩子
（4）外部节点到根途中的黑节点数目（黑深度）相等
将红节点提升与黑父亲等高，则每棵红黑树对应于一棵(2,4)B-树
设红高度R黑高度H，总高度h，则有
带入B树的公式则有：
zig/zag不改变旋转节点子树的黑深度，该是爹的还是爹。
• 插入
首先找到待插入的末端节点的插入位置x，若非根，将其染成红色。1,2,4仍满足，但3并不一定
双红修正（x和p均红）
祖父g一定为黑，叔父u若为黑，此时xpg的四个孩子均黑且黑高度相同。直接34重构，中间那个染黑，左右染红。
从B-树角度理解，失衡的原因是在三叉节点插入红关键码使得黑不再居中。故只需调整颜色。拓扑结构不变。
叔父u若为红，此时该超级节点三红一黑（g），将g转红上溢，p,u转黑，其余分裂。局部黑高度保持。g可能再次构成双红，将g当做新插入的节点如法炮制，直到条件满足或抵达树根，抵达树根就将g强行转黑，此时黑高度加一。（与上溢类似）
每次插入至多O(logn)次染色和1次34重构
• 删除
将待删除节点数值与其直接后继交换，设实际删除的节点为x。x由孩子r接替，则另一孩子k必为Null，但可以假想一个与r等高的子树随x一并删除。
完成removeAt()之后，条件1,2满足，但3,4不一定。
考察x与r，若x为红，则删除后仍满足；若r为红，则另其与x交换颜色。
只有x和r均黑的情况不满足。黑深度不再统一。
双黑修正
考虑原来x的父亲现在r的父亲p和兄弟s。
若s为黑，设其红孩子为t(可能Null)
t存在时，对tsp使用34重构，并染成黑，p原色，黑。B树中就是旋转。（O(1))
t不存在，若p为红，将其转黑并把s转红。相当于B树下溢。由于p为红，超级节点失去p后仍能支撑。p的黑高度不变。（O(1))
若p为黑，s转红p保持黑，此时对应B树中p下溢与s合并。失去p之后上层必然继续下溢，从p开始继续双黑修正。p的黑高度下降。（O(logn))
s为红的情况，zig(or zag)一下，并且红s转黑，黑p转红，此时x换了一个黑兄弟，且父亲p为红。继续考虑黑兄弟的红孩子，但p为红保证了至多一轮就能正常。（O(1))

十一、词典

• 只需支持比对判等，不必支持大小比较

• 完美散列（数据集已知且固定时可以实现）
• 两级散列，O(n)空间，关键码互不冲突，最坏情况下不超过O(1)时间

• 23人聚会存在生日冲突概率为50.7%

• 理想随机时除余法可以使用任意表长，但是大多数情况下并不理想随机，所以需要选用质数
0总是到0，且相邻关键码一定到相邻散列地址

• 其它散列函数：抽取数字，平方取中，折叠取和（分割为等宽），位异或法（二进制后分割等宽取异或），伪随机数法（可移植性差），多项式法（每次把首五位移到最后）

• 排解冲突
多槽位 O(1)但是空间浪费且可能不够
独立链 空间未必连续，难以利用缓存
公共溢出区
封闭散列
• 线性试探：新增非同义词之间的冲突，数据堆积严重但局部性良好，通过装填因子解决冲突和堆积。插入可以顺次找，删除需要故居法，查找时为非空，插入时可以加入。
• 平方试探：对大散列表I/O增加，空桶不一定能找到（二次剩余类！）需要M是素数且装填因子小于等于0.5，此时平方模M的取值恰有M/2上取整种，一定能够找到！
• 双向平方试探：由于单向时小于M/2上取整的任意两个不冲突，可以把另一半也利用起来，正反向各有M/2上取整个互异的桶，可以证明当M取4k+3的素数时两个序列不冲突。（引理：任一素数p可表示为一对整数的平方和，当且仅当4k+1）
再散列 线性叠加第二散列函数确定地址
重散列 用更大的散列表，注意考虑懒惰标记

• 桶排序
0到m中的n个整数，空间O(m+n)时间O(n)，如果允许重复各自组织成一个列表
MaxGap
先找到最左最右点，均匀划分成n-1段（n个桶），通过散列归入对应桶，在各桶中维护最左最右点。MaxGap只能出现在相邻非空桶之间而不能在桶内。

• 基数排序
归纳：前i趟排序后，所有词条关于低i位有序。第i位不同则转为有序，相同则保持稳定。
每趟时间为（为域的取值范围），总和当时，且t为常数时，时间为O(n)
常对数密度整数集排序
d>1为常数，考察0到的n个整数，对数密度为
将整数转化为n进制，每个元素有d个域，直接用基数排序，排序时间

• 计数排序
已按点数排序，下对花色排序。（）扫描一遍统计各花色的数量，以此累加找到花色最后一位的位置（秩区间的最后一位），自后向前扫描并记录到对应的秩的位置。时间O(n)，空间O(m)

• 跳转表
底层为普通列表，纵向成塔，每层生长概率减半，塔高符合几何分布，期望塔高为2。总空间O(n)
k增加S(k)为空的概率急剧增加，跳转表高度O(logn)概率极大，纵向跳转累积不过O(logn)
横向跳转节点必然近邻，且每次抵达都是塔顶，于是沿同一层跳转的次数Y=k符合几何分布（往下的概率是p），E(Y)=1，在同一层跳转时间成本不过2，于是每次查找都是O(logn)
插入过程先查找，如果找到了（此时在塔顶），强制转移到塔底。在其后生成一座塔。（每次随机是否生长，若生长则找到其最近前驱，如果是header要考虑是否上溢）
删除过程先查找，如果找到了（此时在塔顶），逐层删除。最后考虑是否降低塔高。

十二、优先级队列

• 完全二叉堆（利用Vector实现，逻辑上等同于完全二叉树）
插入后逐层上滤，最多O(logn)，但是从数学期望来考虑，每次有1/2概率停止，总期望为2
删除之后用末尾取代并下滤
批量建堆：依次上滤十分缓慢（nlogn），主要是每个都考虑深度和，而叶节点很深根节点很浅。于是转换思路为高度和，依次下滤，最多O(n) 。

• 堆排序
把选择排序的左边无序部分组织成堆，就很容易找到最大值。每次把首元素（根，最大）和末元素交换，再下滤，即完成一次选择。总时间O(nlogn)

• 锦标赛树
父节点为比赛胜者，空间为O(结点数)=O(叶节点数)=O(n)，建树时间O(n)（n-1次比较），每次更新只需更新祖先，O(logn)

• 败者树
重赛过程中（取出冠军后）避免交替访问沿途节点及其兄弟，内部节点记录对应比赛的败者，并增设根的父节点以记录冠军。由于每个点只会失败一次，所以在树中只出现一次。而取出冠军之后，冠军的所有祖先就是它打败的那些，从冠军的父节点开始一路向上比较，如果小于就继续往上，如果大于就取代并将较小的继续向上比较（相当于一路重赛）

• 多叉堆
pfs经过PQ组织后，总体运行时间变为，对于稀疏图效率很高，但是稠密图倒不如常规版本。（分为delMax和更新的消耗，忽略建堆O(n)）
多叉堆上滤成本降至，但是下滤成本却增至，如此pfs时间为
取d\approx e/n+2时，总体性能达到最优的，对于稀疏图（）保持了，但是对于稠密图（）却改进为
利用斐波那契堆还可以进一步优化，更新变成了O(1)

• 左式堆
merge的消耗时间正比于右侧藤长，向左倾斜以控制藤长。
引入所有外部节点以转化为真二叉树。记录npl(x)=x到外部节点最近的距离=以x为根的最大满子树高度
对任何内部节点x都有，可推知
这不意味着左子树规模和高度大于右子树！
右侧链长为d的左式堆，至少包含个内部节点和个节点
于是在包含n个节点的左式堆中，右侧链长度
递归实现合并，确保a不小，将a的右子堆和b合并，如有必要，交换左右子堆以保证左子堆npl不小，更新a的npl
插入：merge单个节点
删除：merge左右子堆

十三、串

• KMP
next表记录前后缀相等最大位置，自匹配+绝不回退
令可以指导每一次迭代k单调递增，故事迭代步数的上界。结束时，于是最坏情况也不过O(n)，建立next表O(m)
再改进
对于000100001和00001的情况很不友好，只会利用过去成就而不知道当前位置的教训。
目的：保证了P[N[j]]和P[j]不相等，减少不必要的比对

• BM算法
从右向左，找到极大匹配后缀
bc[] 画家算法不断覆盖，初始为-1，之后遍历一遍字符串找到最靠前的位置。
查找到不对应的地方，找到这个不对应的字母在bc表中的位置，也就是在字符串中最靠前的位置，右移过去。

• Karp-Rabin算法：串即是数
，长度有限的字符串都可以表示成d进制数，长度无限的字符串都可以表示成d进制[0,1)小数
每个字符串对应与一个d进制自然数（不是单射），P在T中出现仅当T中某一子串与P相等，可以通过hash筛选

• Trie树（retrieval）
PATRICIA Tree 压缩不必要指针
Ternary Trie 三叉搜索树 左边是比自己小的 中间是自己的 右边是比自己大的

十四、排序

• 快排，根据pivot进行分治
LUG版 随机选取轴点（随机使0位置和某位置交换），记录下来并且不断拓展G和L
最好情况最差，平均情况下
准居中：pivot位于中间，每递归一层就有的概率准居中，每一递归路径上至多出现个准居中的pivots，当之后，至少有的概率使得递归深度不超过
记期望的比较次数为，，于是可以求得
DUP版 大量元素重复时，轴点总是接近lo，极度失衡，对于雷同元素选择交换，懒于拓展，勤于交换
LGU版 从两边向中间改为从左到右遍历，如果是G就直接拓展，如果是L就和mi交换

• 众数
无序向量中占有率一半以上的称为众数。众数必为中位数。
在向量A的前缀P（有偶数个元素）中，元素x恰出现半数，则A有众数当且仅当后缀A-P有众数m。

• 中位数
两个有序向量找中位数？（设长度都为n）
找到两个的中间元素（一个除以二下取整，一个上取整减1），若相等则其为共同中位数，若则中位数在的右边和的左边，如此减治。

• QuickSelect
直接排序O(nlogn)，小顶堆，大顶堆维护最小的k个数，大小顶堆不断交换堆顶元素
任取一个pivot（大胆猜测），两边逼近找到它的位置（小心求证），确定是在左半区还是在右半区
期望的比较次数为T(n)，则

• LinearSelect

• 希尔排序
组织成宽度为h的矩阵，上下排序，h满足的序列
，但最坏情况下为，因为每次调整后逆序对仍然很多
邮票问题中最小不能表示的正整数，当g和h为素数时，该正整数为
A g-ordered sequence REMAINS g-ordered after being h-sorted！
利用这个结论可以解决：矩阵元素纵向排列后再横向排列，会保持纵向有序
某序列末尾几位对应大于等于另一序列开头，则两个分别排序后该序仍存在
g-ordered+h-ordered可以保证(mg+nh)-ordered
PS序列两两互素
• O(logn) outer interactions time
Pratt序列
Sedgewick序列
最差平均