2025-12-19
2 注：2025 DSA 的期末考试格外困难。但是我仍然认为这份笔记对我还是有所帮助的。总之也就看个乐子吧。
注：只是一个笔记，只看这个无法帮助你在 DSA 中获得正常的成绩，可能还需要一些往年题的 fine-tune.
misc:
- 左旋的定义是把东西往左旋，右旋的定义是把东西往右旋
- 二次探测法：对于哈希表，假如选得的位置是 \(x\)，那么就看 \(x\)，\(x+1\)，\(x+4\)，\(x+9\) 这样下去，对总 size 取模.
- 双散列函数：对于哈希表，假如选的位置是 \(x\)，并且第二个散列函数告诉你是 \(y\)，那么就看 \(x,x+y,x+2y,\dots\) 下去，对总 size 取模.
内排序
Iterative style
插入排序：从前往后，然后看 \(a_i\) 应该插入到 \(a'[1,i-1]\) 的哪里然后插进去，为稳定排序
具体来说就是对于 \(i\)，然后 \(j=i-1\to 1\) 然后每次如果逆序了就 swap，否则 break
冒泡排序：不断（从前往后交换相邻逆序数），直到有序，为稳定排序
选择排序：从前往后，找出后面的最小的放在这里，为不稳定排序
堆排序：建大根堆，然后每次去除堆顶，为不稳定排序
希尔排序：每次选一个 gap 然后将模 gap 同余的项做插入排序. 选 \(2^p3^q\) 为 gap 可以达到 \(O(n\log^2n)\)，其他一些也可以做到 \(O(n^{<2})\). 为不稳定排序.
不需要访问已经排好序的记录：冒泡 & 选择
d&c style
- 归并排序：为稳定排序
- 快速排序：为不稳定排序
indexing
- index array: \(Index_i=\) 第 i 小的值的位置
外排序
如果要排序的东西 RAM 塞不下那么就倒闭了，于是就需要外排序，大体就是说看看先能不能在有限的 RAM 范围内能够将整个序列给分成尽量多的有序段（run，顺串），然后再对这些段做 merge.
分段：
- 假设我们最多能 load \(n\) 个元素
- 那么就每次先 load \(n\) 个元素进堆，然后每次将最小值写入之后再读一个元素，如果元素比最小值大那么就可以塞入堆，否则就把这里面的元素给从小到大写完之后，结束这个 run.
merge：
two-way merge：直接 huffman tree
k-way merge：每次要找 \(k\) 个元素中的最小值.
赢者树：一棵线段树，然后线段树每个节点记录最小值的位置
败者树：一棵线段树，每个节点记录在合并儿子的时候更大的那个元素的位置。好处是替换掉最小值之后，更新的时候从下往上不需要读兄弟节点的信息.
用这个执行 k-way merge 的话一次 merge 的复杂度是点数乘上 \(\log k\).
然后再做类似 huffman 的贪心合并即可
查找 / 索引
散列表：
- open hashing: 使用分离链表，每个哈希值维护一个链表
- close hashing: 撞了之后按一个固定的方式找下一个. 注意这个不能支持直接删除，只能隐式删除.
B 树
考虑要维护动态插入/删除的集合，每个元素是一个 (key, address) 的 pair，然后需要支持给 key 查 address.
结构：
- 每个节点存储 \(k_i\) 个元素 \(a_{i,1}\dots a_{i,k_i}\)，然后有 \(\le k_{i}+1\) 个儿子，其中第 \(i\) 个儿子的子树记录所有 key 在 \((a_{i-1},a_i)\) 间的元素.
- 大概可以用一个 [儿子指针，元素，儿子指针，...，儿子指针] 的一个 list 来表示一个点.
- \(m=\max k_i+1\). \(m=3\) 的时候称为 \(2-3\) 树，因为每个节点只有 \(2\) 或 \(3\) 个儿子.
- 非退化情况下，根至少要有两个儿子. 并且每个点至少有 \(\lceil\frac{m}{2}\rceil-1\) 个元素. 并且每个叶节点深度相同.
插入：
- 先索引到自己适合插入的那个叶子. 如果叶子再多一个 item 还是 \(k_i\le m-1\) 那么就不用管了.
- 否则取出节点的中位元素，然后把这个节点按中位元素 split 成两个. 然后把这个中位元素给插到父亲节点里面.
- 如果插到父亲节点里面之后父亲节点元素数量没爆那么就 ok 了. 如果爆了，那么就需要对这个节点跑第二步，然后不断这样做.
- 最终如果跑到根节点然后根节点爆了，那么就需要建一个新的根就可以了. 新的根的儿子数量为 \(2\).
删除：
- 对于 \(x\)，找到自己的后继 \(x'\)，然后把 \(x'\) 换到自己的位置上即可删除.
- 带来的一个问题是 \(x'\)
所属叶子可能会元素数不够 . 此时我们看它的兄弟.
- 如果兄弟的元素数 \(\ge \lceil\frac{m}{2}\rceil\) 那么就直接把兄弟的最值移到父亲，然后再把父亲的前/后驱给挪过来这样.
- 如果兄弟的元素数小，那么就可以直接带上父亲的那个划分元素给合并到一个节点，这个节点的元素显然满足要求. 但是这可能导致父亲元素数不够，于是就跳到父亲节点然后执行 2.
B+ 树
和 B 树的区别是只有叶节点存元素 （leafy），设儿子数量为 \(d_i\)，则每个节点需要存 \(d_i\) 个数，每个数表示该儿子的 key 的最大值.
插入：
同样，索引到自己应该放的叶节点然后丢进去.
如果没问题的话就一路往上走更新（如果需要更新的话）每个节点存的那个表示最大值的数.
如果爆了那就分成两个节点，这会使得父亲节点需要存储的值多一个. 然后就对父亲回到 2.
同样如果到了根那么可能需要建新根.
删除：
- 这里删就直接删，然后没问题的话还是需要一路往上更新.
- 同样如果个数少了就从兄弟拉一个过来. 如果兄弟没法再拉东西过来了就可以合并.
- 需要注意任意节点发生变动都要去 pushup.
一个变种是使用 B+ 树的 leafy 的思想，但是在非叶节点采用 B 树的方式，这样可以少记录很多冗余值，并且也不需要那么频繁地 pushup.
由于 B+ 树的叶节点实际上是不需要存储的，所以这个 leafy 结构带来的优势就是空间小. 另一方面 B 树的优势是的深度稍微小一些.
高级数据结构
广义表
考虑链表的每个元素，可以是一个原子元素，也可以是一个链表.
这样的链表可以当作邻接表看待.
- 线性表：链.
- 纯表：树.
- 可重入表：图.
- 循环表：有环的图.
AVL
定义：每个点的左子树和右子树高度最多差 1.
balance factor \(bf(x)\) 为右子树 - 左子树高度.
插入：
正常查找然后插入一个叶子
从下往上 check 每个节点符合要求. 三种情况：
当前节点新 \(bf=\pm 1\)，那么继续 check 父亲
当前节点新 \(bf=0\)，那么就不需要管父亲了.
当前节点新 \(bf=\pm 2\)，那么就需要在这里旋转一下. 由于肯定是新加的点来自于那个多的子树，不妨设来源于右子树.
如果来源于右子树 \(r\) 的右儿子 \(r_r\)，那么直接把 \(r\) 旋转上去即可. 如果来源于右子树的左儿子 \(r_l\)，那么就需要把 \(r_l\) 从下往上转两步. 然后就不需要再 check 父亲了.
红黑树
大家都去学 fhq-treap 好不好啊.
结构：
- 每个点被染成红色和黑色
- 不存在相邻红点
- 对于每个点，到子树内所有外部节点所经过的黑点数量一致，称为这个点的 rank
插入：
- 直接做 BST 插入，然后将新的点染成红色.
- 由于直接插入后不存在子节点需要考虑. 只需要考虑和父节点的关系.
- 如果父节点是黑色就什么事都没有.
如果父节点是红色的话需要进入到一个分类讨论：
- 如果父亲的兄弟是红的，那么直接将祖父变成红，父&父兄弟变成黑，然后对祖父继续做 3.
- 如果父亲的兄弟是黑的，由于此时父亲的兄弟&自己的兄弟都是黑，而 (自己，父亲，祖父) 形成一条红红黑的链，于是考虑旋转，把这三者的中位数转成这三者的根，然后根为黑，根的两子为红. 由于剩下的周围节点都是黑所以这样做没有问题.
删除：
- 删除的话首先对于节点 \(x\)，如果度数 <2 直接删，否则和右子树最小的点交换然后删
- 如果删除节点是红色那么 p 事没有，但是如果是黑色那么就需要调整，使得删除之前其唯一子树的 rank 要增大一然后才能放心删.
- 然后我们就关注这个“让rank保持平衡的操作”怎么弄（并且不会让自己变成红色）.
分若干种情况：
- \(x\) 儿子是红色的：那么直接把这个儿子染成黑色.
- \(x\) 无红色儿子，且兄弟是红色的：把兄弟转上去，并且将兄弟染成红，转下来的父亲染成黑. 此时归约到兄弟是黑色的情况.
- \(x\) 无红色儿子，兄弟是黑色的，没有红色侄子：直接把兄弟染成红色. 此时，如果父亲本来就是红色那么染成黑色，如果本来就是黑色那么就要对父亲重复 3.2 / 3.3 / 3.4 了.
- \(x\) 无红色儿子，兄弟是黑色的，有红色侄子. 如果存在父亲-黑色兄弟-红色侄子的一条顺着的链，那直接把黑色兄弟给转上去就行了. 否则就需要把红色侄子转上去. 注意在赋颜色时，父亲位置的颜色要保持不变. 这种情况下也都不需要对父亲重复修复.
建议根据上述规则手搓一下.
AI 产物：
- 插：叔红变色，叔黑旋转
- 删：兄红转黑；兄黑侄黑则父债子偿；兄黑侄红则借位填坑