有錯請指教。
沒啥時間了，應該會專攻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))