有错请指教。
没啥时间了，应该会专攻Tree、Search & Sort、Graph这三章，其他加减看了。
之前太混，想认真就是认真不起来。
Def:
- Tree
- m-way search Tree
degree 0 ~ m，if node degree m, number of keys in node m-1
- Balanced m-way search Tree(B tree of order m)
root degree 2 ~ m，others degree [m]/2 ~ m
external nodes are the same level
- B+ tree of order m
分Index level(不放Data), Data blocks level(存Data，以Link list串连)
- 2-3 tree(B tree of order 3)
- 2-3-4 tree(B tree of order 4)
- Binomial Tree with order h
root之level为0，高度h(只有root一个点为高度0)
- Binomial Heap
- Fibonacci Heap
- Forest
- Binary Tree(BT)
- skewed BT
- Complete BT
- Full BT
- Binary Heap(Heap)
- min-max Heap
- Doubled-ended Heap(Deap)
- symmetric min-max Heap(SMMH)
- strict BT
- Binary Search Tree(BST)
- Balanced BST
- AVL Tree
Balance factor = 1 or -1 or 0
- Red-Black Tree(RB Tree)
same black height
- optimal BST(OBST)
- Splay Tree
- Thread BT
- Extended BT
Weighted External path length(WEPL)
- Leftist Heap(min Leftist Tree)
shortest(x) = 0 (外部node) or
1 + min{shortest(x->lchild),shortest(x->rchild)} (内部node)
- BT Traversal(追踪)
- Preorder(DLR)
- Inorder(LDR)
- Postorder(LRD)
- level-order
Def(Representation):
- Tree表示方式
- Link list
- 化成Binary Tree(leftmost-child-next-right-sibling 左儿子,右兄弟)
- 给定 Tree，求 BT
给定 BT，求 Tree
- child-sibling(左儿子,右兄弟)
- 括号法
- Forest表示方式
- 化成Binary Tree
- BT表示方式
- Array
Complete BT
容易存左右子点父点、不易增删Node
- Link list
skewed BT
Thread BT
每个node多出LeftThread, RightThread，True为引线、False为子点
多一Head node不存Data(空树为左T右F，非空树左右F指向Root)
Extend BT
node存weight(非Data)
容易增删Node、不易存父点、浪费links space
- Disjoint sets表示方式
- Link list
Data以及Parent(pointer指向父点，root指向Null)
- Array
root指向0(表示Null)或(-1)*(node数)
Thm:
- Tree之基本定理
- if Tree's Degree = k
node数 = leaf数 + Degree-1之node数 + ... + Degree-k之node数
= Branch数 + 1
= (1*Degree-1之node数 + ... + k*Degree-k之node数) + 1
- BT之基本定理
- 给定 高度k，求 最多node数
- 第i个level上，最多node数
- 给定 node数，求 最小高度
- leaf数 = Degree-2之node数 + 1
- 给定 node数，求 可能的BT个数
n个node可能的BT数 = sum(i个node可能的BT数 * n-1-i个node可能的BT数)
= 1/(n+1) * C(2n取n)
where i=0~n-1
- Complete BT之基本定理
- if n个node编号:1~n
给定 编号为i的node，求 左子点、右子点、父点编号
- BT Traversal(追踪)
- 给定 BT，求 Traversal
- 给定 Traversal，求 BT
- 给定 Pre+Inorder或Post+Inorder或level+Inorder，求 BT
对node总数或顺序长度作induction
- 给定 Pre或Post或level或Inorder，求 Complete BT
- 给定 Pre或Post或level，求 BST
- Extended BT之定理
- External path length = Internal path length + 2n
External node数 = Internal node数 + 1
对Internal node数作induction(拆成左右子树)
- 给定 External node数及其加权值，求 min.WEPL
use Huffman Algo，在可能的Extend BT找出min.WEPL
- AVL Tree之定理
- 给定 高度h，求 所需最少node数、最多node数(Full)
对高度作induction
- 给定 node数，求 最小高度(Full)、最大高度
- m-way search Tree之定理
- 给定 高度h，求 最多node数、最多key(Data)数
- B Tree之定理
- 给定 高度h，求 最多、最少node数、最多、最少key(Data)数
- RB Tree之定理
- 给定 node数，求 最大高度
先证明以某一node x为root的子树，至少包含2^(bh(x))-1 node
where bh(x)为以x为root的子树到leaf会有的黑色node数
对bh(x)作induction
n >= 2^(bh(x))-1 >= 2^(h/2)-1 (因为红黑树的特性)
2*log(n+1) >= h
- 给定 2-3-4 tree，求 RB Tree
原本2-3-4 tree存在的link视为黑色，否则视为红色
- OBST之定理
- 给定 内外部node数及其加权值，求 最小搜寻总成本之BST(OBST)及其cost
use DP
O(n^3)
- Cij = Wi,j + min{ Ci,r-1 + Cr,j }
where i+1 <= r <= j
- Leftist Heap之定理
- n >= 2^(shortest(x))-1 where x为root
对shortest(x)作induction
- Binomial Tree之定理
- 给定 高度h，求 第i个level上node数、总node数
对高度h作induction 或 加总各个level上node数(C(h取0)+...C(h取h))
- Binomial Heap之定理
- 给定 node数，求 最多Binomial Tree数
O(log n)，node数写成二进制
DS with Algo(要知道时间复杂度、怎么写，会写就会操作):
- ☆BT recursive algo
- BT Traversal
- Preorder(T:BT), Postorder(T:BT), Inorder(T:BT)
用Stack，O(n)
- level-order
用Queue，O(n)
- Count(T:BT), CountDegree1(T:BT), CountDegree2(T:BT), Leaf(T:BT)
- Height(T:BT)
- Swap(T:BT)
- Eval(T:expression BT)
node结构多出Res栏(存运算结果或变量值)
- 给定 expression，求 BT
- Copy(orig:BT)
- Equal(S,T:BT)
- ☆BST recursive algo
Tree's sorting: Inorder可得小至大排序，RDL追踪或stack可得大至小排序
- Search(T:BST,x:Data)
给定 BST及其Data range，求 平均比较次数 = 总比较次数/Data range
- ☆☆Search ith smallest item
- Find-max, Find-min
- Insert
- rotation (AVL, RB Tree)
O(1)
- Bottom up (RB Tree先插node再检查)
- Top Down (RB Tree先检查再插node)
- Delete
上述皆是O(h) = O(n) ~ avg O(log n)
高度最小化最佳(Full, Complete, AVL, RB Tree)
splay tree会再作rotation
- Heap algo
可制作Priority Queue
- Search
O(n)
- Find-max or min
Θ(1)
- Insert
O(h) = O(log n)
- ☆☆Build
- Top-Down(边Insert边排序)
O(n*log n)，(log1 + ... + log n) = log(n!) ≒ n*log n
- Bottom-up(全Insert再排序)
O(n)
最大成本 = sum(level i最多node数 * 以level i为root之子树高)
= sum( 2^(i-1) * (h-i) )
= n-h+1
where i = 1 ~ h = 1 ~ log n
- Adjust(tree,i,n)
O(log n)
- CreateHeap(tree,n)
- Delete-max or min
O(h) = O(log n)
- Adjust
- Merge
O(n)
- Decrease key of a node
O(log n)
- Delete(先Decrease key变min，再Delete-min)
O(log n)
- Disjoint sets
Kurskal's algo中判断边(u,v)加入spanning Tree中是否形成cycle
Find Equiv Sets根据等位配对资讯，求出等位集合
Find connected components of undirected graph 找出无向图之连通子图
- Make-Set(x)
- Union(x,y)
O(1)
- Arbitrary Union
- Union by Height
Binomial Tree
- Union by Weighting rule(多node为爸)
- Union by rank
- Find(x) 找root
O(h) = O(log n)
- with Collapsing rule(path Compression) 经过之node改指向root
O(α(m,n))