数据结构与算法分析,Java语言描述,第2版 Mark Allen Weiss
目录 |
伸展树(splay tree)
- 从空树开始任意连续M次操作最多花费O(M log N),均摊代价O(log N)
- 基本想法:当一个节点被访问后,通过一系列AVL旋转推到根上(LRU Cache?)
- 一个简单的想法:。。。不够好,其他节点深度加深,Ω(M N)
- splaying:将访问路径上的节点深度大致减少一半?
- zig-zag:\ * / AVL双旋
- zig-zig:/ * / “拉起”?
- 少数真正麻烦的访问却留给我们一棵几乎平衡的树
优先队列(堆)
d-堆
- 简单推广:每个节点都有d个儿子
- 找到d个儿子的最小(大):d-1次比较
- insert:O(log_d N)
- deleteMin:O(d log_d N)
- merge困难
左式堆
- 所有支持高效merge的都需要使用链式数据结构
- 零路径长:到叶子节点的最短路径
- zpl(X) = min{ zpl(child of X) } + 1
- 性质:zpl(X's left child) >= zpl(X's right child)
- 偏向于向左增加深度
- merge:H_1 H_2
- 递归地,将具有大根值的堆与具有小根值的堆的右子堆合并(why?)
- 上面最后的结果是一个左式堆(?),将它作为具有小根值的堆的新的右子堆
- 此时,左子树的zpl=1,而右子树的zpl=2,对根进行调整:
- 交换根的左右子女,并更新zpl,就完成了merge(???)
- 这里‘零路径长’的约束条件到底起到一个什么样的作用呢
- deleteMin :=> remove root + merge 2 heaps
斜堆(skew heap)
- 斜堆是左式堆的自调节形式,斜堆 ~ 左式堆 <=> 伸展树 ~ AVL树
- 不保存zpl信息,右路径可以任意长,均摊为O(log N)
- 对于斜堆,最后左右子女的交换是无条件的(Why?)
- *递归与非递归的差别:右路径用完???
二项队列
- 二项树(binomial tree)的森林:B_0 B_1 B_2 ...
- 高度为k的B_k由一个B_(k-1)附接到另一个B_(k-1)上构成
- findMin:O(log N)
- merge:O(log N)
- insert:特殊的merge
DFS应用
(无向图的)双连通性
- 割点(最大流最小割?)
- DFS遍历,先序编号为Num(v)
- Low(v):
- Num(v)
- 所有Back edge(v,w)中的最低Num(w)
- 树的所有边(v,w)中的最低Low(w)
- assignLow?
查找强分支
- 两次DFS
- 通过后序遍历将顶点编号,然后再把边反向,从编号最高的顶点开始新的DFS
回溯算法(Backtracking)
- 极大极小
- α-β裁剪
第10章习题
- 1D circle packing
- Voronoi图
- Convex Hull
- 调整段落问题(靠,文本布局?):最少的丑点设置(看来只有justify时才需要均匀分配?均匀分配实际还会遇到精度问题)
- 最长递增子序列:O(N^2) ——?
- LCS:O(MN)
- 8皇后问题(回溯方法)
- 国际象棋马的环游问题
均摊分析
二项队列
斜堆
Fibonacci堆
- 以O(1)均摊时间支持所有基本堆操作,但deleteMin/delete需O(log N)
- 通过添加2个新观念推广了二项队列:
- 左式堆的decreaseKey
- 懒惰合并(函数式数据结构???)
伸展树
高级数据结构
自顶向下伸展树
红黑树
确定性跳跃表
AA树
- 由于大量可能的旋转,红黑树编程十分复杂,特别是删除操作
- BB树是带有附加条件的红黑树:一个节点最多有一个红儿子,进一步为使编程容易:
- 只有右儿子可以是红色;
- 递归
- level:=1,树叶;=parent's,if red;=parent's -1,if black
- 如此得到的结果是一棵AA树
- *水平链接 ?
- AA树:skew/split
treap树
- 指定一个随机的优先级,并要求优先级满足堆序
k-d树
- 在不同层上按不同关键字索引???还不如直接多重索引呢