Chapter 12 高级数据结构
12.1 多维数组¶
12.2 特殊矩阵¶
对称矩阵: 只需要存上三角元素, 所需空间 \(n(n+1)/2\)
三角矩阵: 一半是常数, 比起对称矩阵多一个常数的空间
稀疏矩阵: 只存非零元素
稀疏矩阵的顺序存储: 三元组表
稀疏矩阵的链式存储: 十字链表
CSR: 压缩稀疏矩阵表示
把数据压成一维, 行数组(第一个总是为 0), \([a[i],a[i+1]-1]\) 代表第 \(i\) 行的数据
12.3 广义表¶
线性表是由 \(n\) 个元素组成的有限有序序列
广义表是特殊的线性表, 表内可能包括子表
广义表的类型
- 纯表 (pure list)
- 从根节点到任何叶节点只有一条路径
- 任何元素 (原子, 子表) 只能出现一次
- 可重入表(再入表) (reentrant list)
- 任何元素可以出现多次
- 对应一个DAG
- 循环表(递归表) (circular list)
- 包含回路, 深度无穷大
增加头指针简化删除插入
12.4 扩展 BST¶
12.4.1 最佳 BST¶
根据输入习惯确定的
12.4.2 AVL¶
平衡因子: \(bf(x)=\) \(x\) 的右子树高度 - \(x\) 的左子树高度 \(\in\{0,1,-1\}\)
AVL 的插入¶
删除与 BST 类似, 注意调整的时候如果高度改变要继续往上传
12.4.3 Splay¶
每次访问结点都把 \(x\) 移到根节点
- 如果 \(x\) 是根节点的子结点, 执行单旋转即可
- 否则需要递归进行双旋转
一字型:
注意这里是先把父结点提升到根节点再把子结点提示到根节点, 而不是提升 x 两次
之字形:
如果插入一个node引起了树的不平衡，AVL和RB-Tree都是最多只需要2次旋转操作，即两者都是O(1)；但是在删除node引起树的不平衡时，最坏情况下，AVL需要维护从被删node到root这条路径上所有node的平衡性，因此需要旋转的量级O(logN)，而RB-Tree最多只需3次旋转(但是遍历还是要log)，只需要O(1)的复杂度。
其次，AVL的结构相较RB-Tree来说更为平衡，在插入和删除node更容易引起Tree的unbalance，因此在大量数据需要插入或者删除时，AVL需要rebalance的频率会更高。因此，RB-Tree在需要大量插入和删除node的场景下，效率更高。自然，由于AVL高度平衡，因此AVL的search效率更高。
基于伸展树的区间操作¶
- 区间提取 : 给定数列 \(\{n_i\}_m\), 提取区间 \([n_a,n_b]\) 的子序列
- 将 \(n_{a-1}\) 旋转到根节点
- 将 \(n_{b+1}\) 旋转到根节点的右子节点
- 提取树根右子树的左子树即为所求子序列
- 区间删除 : 删除区间 \([n_a,n_b]\) 的子序列
- 同区间提取
- 删除树根右子树的左子树
- 区间插入 : 插入区间 \([n_a,n_b]\) 的子序列
- 将 \(n_a\) 旋转到根节点
- 将 \(n_{a+1}\) 旋转到根节点的右子节点
- 将待插入子序列构建成伸展树, 插入成为树根右子树的左子树
- 区间翻转 : 翻转区间 \([n_a,n_b]\) 的子序列
- 同区间提取
- 对树根右子树的左子树进行翻转 (交换每个节点的左右儿子)
半伸展树¶
zig-zig 只旋转一次, 然后把待处理结点设为父结点