# 資結（下）- 課輔
[TOC]
## 說明
### 時間
- 每個星期一的 20:00~22:00
### 內容
- 以老師上課的範圍為主，再幫同學複習一次全部的內容
- 總共有 4 個章節，預計每 2 次課輔講完一章。
- 每次課輔 2 小時，預計 1.5 小時講上課內容，剩餘時間讓同學提問。
- 程式碼會以 java 為主
### 老師 moddle 的課程大綱
- 
## Tree
### 定義
- tree 是由 1~n 個 node 組成的集合
- 有 1 個特定 node 作為 root，且此 node 沒有 parent
- 其餘的 node 組成 x 個互斥集合（subtree）
- node
- parent node
- child node
- leaf/terminal node
- 沒有 child node
- sibling
- node 間有相同 parent
- tree degree
- tree 的分支度
- 一個 tree 的 node 中有的最大分支度就是此 tree 的分支度
- tree height/depth
- 一般 root 會從 1 開始計算，少數從 0 開始
- forest
- 由 0~N 個互斥的 tree 組成
- tree 的表示方式
1. linked list
- 每個 node 除了自身的 data 外，還有 k 個 link（k = degree），用於連到其他 node
- node structure
| data | Link 1 | Link 2 | Link k |
| -------- | -------- | -------- | -------- |
- 缺點
- 浪費空間存無用的 link
- 共需 n*k link 的空間存 link，但實際上有存 node 的 link 只有 n-1 個
- 故使用率只有 (n-1) / n*k ≒ 1 / k
- 會剩下很多空 link，浪費空間，且當 k 越大，浪費的空間越多
3. 轉為 binary tree
- binary tree 的 degree 最大為 2
- 所以可以確保使用率可達到接近 1/2
5. 括號法
- 用括號和巢狀關係表示 parent and child node
- node structure
- 父(子)
- ex.
- 
- A(B(EF)C(G)D)
### binary tree
- 定義
- 由 root, left subtree, right subtree 組成
- left, right subtree 亦是 binary tree
- 可以為空樹（root 為空）
- degree 最大只能為 2
- node 有左右之分
- 3 大定理
1. 第 i level 的 node 數量最多共為 2^(i - 1)
2. 高度為 k 的 binary tree, 總 node 數最多為 2^k - 1
3. 一非空的 binary tree, 若 n0 = leaf node 數量， n2 = degree 為 2 的 node 數量，則 n0 = n2 + 1
- 練習
1. binary tree 有用的 link 數量為 99，則共有多少 node
2. binary tree 有 n 個 node, 則最高和最低的 level 為多少
3. binary tree 有 12 個 node, 且 degree = 1 的 node 有 5 個，則 leaf node 數量有幾個
- 特殊 binary tree
1. skewed binary tree
- 分為左斜曲和右斜曲
- 
2. full binary tree
- 當 tree 高度為 k, 總 node 為 2^k - 1
- 
3. complete binary tree
- 將高度為 k 且總 node 為 n 的 tree 的 node 依照 level 依序編號後，會與高度一樣為 k 的 full binary tree 的前 n 個 node 的編號對應
- 
- 定理
- 有一編號為 i 的 node
1. 其 left child 編號為 2i, 若 2i <= n
2. 其 right child 編號為 2i+1, 若 2i+1 <= n
3. 其 parent 編號為 [i/2], 若 [i/2] > 1
4. degree = 1 的 node 數量為 1 or 0
- 
- 練習
- complete binary tree 有 1000 nodes
1. 最後一個 parent node 的編號
2. 編號 250, 251 的 node 是否為 sibling
3. 編號 250 的祖父 node（parent 的 parent）
4. 編號 371 的 left, right, parent node
5. 編號 512 的 left node
6. 此樹的 depth
7. degree = 1 的 node 數量
4. strict binary tree
- 所有 non-leaf node 的 degree 皆為 2
- 
- 練習
1. full binary tree 一定是 strict binary tree ?
2. complete binary tree 一定是 strict binary tree ?
3. strict binary tree 一定是 full binary tree ?
4. strict binary tree 一定是 complete binary tree ?
- binary tree 表示法
1. linked list
- node structure
| LChild | data | RChild |
| -------- | -------- | -------- |
- ex.
- 
- 優點
- insert, delete node 方便
- 缺點
- 不易知道 parent
- 浪費約一半的 link 存空值
2. array
- 若 tree 的高度為 k, 則準備一個 1-D array, Arr[1 ~ 2^k-1]
- 
- 優點
- 可容易用 index 知道 parent
- 不須 link space
- 缺點
- insert, delete 不便
- 不適用於 skewed tree (浪費太多空間)
- binary tree traversal
- 走訪 binary tree 的所有 node 一次，且 L 要在 R 之前走訪
- 
- 前序
- DLR
- code
```java=
class Node {
int data; // data of node
Node LChild; // left child
Node RChild; // right child
}
void preorder(Node n) {
if (n != null) {
System.out.println(n.data);
preorder(n.LChild);
preorder(n.RChild);
}
}
```
- 中序
- LDR
- code
```java=
void inorder(Node n) {
if (n != null) {
preorder(n.LChild);
System.out.println(n.data);
preorder(n.RChild);
}
}
```
- 後序
- LRD
- code
```java=
void inorder(Node n) {
if (n != null) {
preorder(n.LChild);
preorder(n.RChild);
System.out.println(n.data);
}
}
```
- 練習
- 求以下 binary tree 的 前中後序
1. 
:::spoiler ANS
前 : ABDCEGLF
中 : BDAGELCF
後 : DBGLEFCA
:::
3. 
:::spoiler ANS
前 : LMNOQPRS
中 : MQONPSRL
後 : QOSRPNML
:::
- 給定 前序+中序 or 後序+中序，找出唯一的 binary tree
1. 前 : ABDCEGLF；中 : BDAGELCF
:::spoiler ANS
:::
3. 後 : QOSRPNML；中 : MQONPSRL
:::spoiler ANS
:::
- 舉例給定 前序+後序，無法找出唯一的 binary tree
:::spoiler ANS
前 : ABC；後 : CBA
:::
- binary tree 的應用
1. expression tree
- 利用 binary tree 表達運算式
- 規範
- non-leaf 代表 operator
- leaf 代表 operand
- prioity 越高的 operand 會在 tree 的越下層（代表先被執行）
- ex.
1. A + B * C - D / E
:::spoiler ANS
:::
2. 給一 expression tree, 回推 expression
:::spoiler ANS
A + B * C - D / E
:::
### binary search tree
- 為一 binary tree, 可為空樹
- 若不為空，則滿足：
- root > left child 的值
- root < right child 的值
- left and right subtree 亦是 binary search tree
- 用中序走訪可得到由小到大排序的 data
- ex.
- 
- 練習
1. 依序將下列 data 建立 binary search tree, 並用中序走訪建完的樹 : 26, 5, 77, 8, 19, 31, 17, 45
:::spoiler ANS
:::
2. binary search tree 的後序 : ACBFKPLD。求此樹的前序
:::spoiler ANS
前序 : DBACLKFP
:::
- search
- 搜尋一值是否存在於一 binary search tree 平均只需 O(logn)
- 若欲找值小於 root, 則往 left subtree 繼續找，反之往 right subtree 找
- code
```java=
boolean search(Node n, int data) {
if (n == null) {
// 欲找的 data 不存在於 tree
return false;
}
else {
if (n.data == data) {
return true;
}
else if (n.data > data) {
return search(n.LChild, data);
}
else {
return search(n.RChild, data);
}
}
}
```
- delete
- 欲在一 binary search tree 中刪除一 node 有兩種狀況
1. 該 node 為 leaf node : 直接刪除
2. 該 node 為 non-leaf node
- 有 1 個 child : child 直接取代
- 有 2 個 child : 有兩種方式，都可以用
- 拿 left subtree 的最大值取代
- 拿 right subtree 的最小值取代
- 練習
- 
1. delete 30
:::spoiler ANS
直接刪除 30
:::
3. delete 80
:::spoiler ANS
70 取代 80
:::
5. delete 50
:::spoiler ANS
20 取代 50
60 取代 50
:::
### Thread binary tree
- 若 node 的 LChild/RChild 為空，則視為 左/右引線。引線會指向中序中 node 的 前/後一個 node
- 優點
- 充分利用 n+1 條空 link
- 簡化中序追蹤，無須遞迴和 stack
- 容易找到中序前後繼者
- node structure
| LeftThread | LChild | data | RChild | RightThread |
| -------- | -------- | -------- | -------- | --------|
- LeftThread : true, 左 link 為 thread；反之為 false
- RightThread : true, 右 link 為 thread；反之為 false
- 在 thread binary tree 需額外引入一個串列首，又分為兩種狀況
1. 空樹
- 
2. 非空樹
- 
- ex. 以下 binary tree 用 thread binary tree 表示
- 
- 
- 找 node 的中序 前/後繼者
- 後繼者：分為 2 種狀況
1. node 的 RightThread = true
- 則 node 的 RChild 為後繼者
2. otherwise
- 設 node 的 RChild 為 X
- 找到 X 的最後一個非空的 LChild node Y
- 則 Y 的 LChild 為後繼者
- code
```java=
Node InSuc(Node n) {
Node temp = n.RChild;
if (temp.RightThread == false) { // 不是引線
while (temp.LChild != null) {
// 找到最左兒子
temp = temp.LChild;
}
}
return temp;
}
```
- 前繼者
- 和找後繼者的方式一樣，差在方向相反
- code
```java=
Node PreSuc(Node n) {
Node temp = n.LChild;
if (temp.LeftThread == false) { // 不是引線
while (temp.RChild != null) {
// 找到最右兒子
temp = temp.RChild;
}
}
return temp;
}
```
## Heap
## Advanced Tree
### AVL
- 概念
- 動態平衡，維持高度為 logn，避免成為 skewed tree
- search, insert, delete 皆為 O(logn)
- 定義
- binary search tree
- 左右子樹亦是 AVL tree
- node 的 balance factor 會是 -1, 0, 1
- 動態平衡調整方法
1. LL
2. LR
3. RL
4. RR
- 定理
- 高度為 h 的 avl tree, 最少 node 數為 Fh+2 - 1
- 費氏數列
- f0 = 0, f1 = 1
- fh = fh-1 + fh-2
- 練習
1. 欲形成高度為 5 的 AVL tree
- 最少 node 數 : 12
- 最多 node 數 : 31
2. 有一 AVL tree, node 數 = 15, 求最大高度
- 5
### m-way search tree
- 通常 tree degree > 2
- 以空間換時間
### B-tree
- 定義
- balanced m-way search tree
- root 至少要有 2 個 child
- 除了 root 和 leaf 以外，其餘 node degree m/2~m 之間
- 所有 leaf, failure node 都在同一層
- 2-3 tree
- m=3
- degree : 2~3, if not root or leaf
- 2-3-4 tree
- m=4
- degree : 2~4, if not root or leaf
- insert
- 找到插入位置
- check overflow (key 數 > m-1)
- 若有 overflow, 則 split
- split : 將第 m/2 個 key 作為 parent, 其餘 key 分裂為 2 個 node
- delete
- 要刪除 X key, 有兩種狀況
1. leaf
- 直接把 X 刪除
- check underflow (key 數 < m/2 - 1), 做調整
1. 看是否可以做 rotation (借 sibling node 的一個 node)
2. 若無法，做 combination (合併 parent and sibling node)
2. non-leaf
- 找左子樹的 max or 右子樹的 min 取代
- 取代完後 check underflow
1. 看是否可以做 rotation (借 sibling node 的一個 node)
2. 若無法，做 combination (合併 parent and sibling node)
## Graph
### 定義
- G = <V,E>
- 圖形（Graph）由頂點（Vertex）集合、邊（Edge）集合所組成
- ex.
- 
- V = {1,2,3}, E = {(1,2), (2,3), (1,3)}
### 種類
1. Undirected Graph
- 定義
- G = <V,E>, 若 vi, vj 屬於 E，則 (vi, vj) = (vj, vi)
- ex.
- 
2. Directed Graph (digraph)
- 定義
- G = <V,E>, 若 vi, vj 屬於 E，則 (vi, vj) != (vj, vi)
- ex.
- 
### 常用術語
1. complete graph
- undirected graph
- 定義
- V = n, 有 n(n-1) / 2 個邊
- 圖形中的任一頂點，可直接用一條邊到其他頂點
- ex.
- 
- directed graph
- 定義
- V = n, 有 n(n-1) 個邊
- 圖形中的任一頂點，可直接用一條邊到其他頂點
- ex.
- 
3. subgraph
- ex.
- 
5. path
- 定義
- 由邊集合組成
- ex.
- 
7. path length
- 定義
- path 中的邊的數量
- ex.
- 
9. simple path
- 定義
- 除起點和終點可相同外，其餘路徑中不可經過相同頂點
- ex.
- 
11. cycle
- 定義
- 為 simple path, 且起點、終點需相同
- ex.
- 
13. connected
- 定義
- 一 undirected graph 中，所有頂點都有 path 可以到達其他頂點
- ex.
- connected
- 
- unconnected
- 
15. connected components
- ex.
- 
17. strongly connected
- 定義
- 一 directed graph 中，所有頂點都有 path 可以到達其他頂點
- ex.
- not strongly connected
- 
- strongly connected
- 
19. degree
- digraph
- 有分為 in-degree and out-degree
- ex.
- 
- in-degree = out-degree = E
- undirected graph
- ex.
- 
- degree 的總和 / 2 = E
- 練習
1. Tree is connected undirected graph
- T
3. A graph is connected, and V = n, 則最小的邊數量為 n-1
- T
4. 有一 undirected graph, and V = n, 若 E >= n, 則此圖必 connected
- F
- 
### 表示方式
1. adjacency matrix
- 定義
- V = n, 宣告一二維陣列 A[n][n]
- 若 (vi, vj) 存在，則 A[i][j] = 1, 否則 A[i][j] = 0
- undirected graph
- ex.
- 
- digraph
- ex.
- 
2. adjacency list
- 定義
- V = n, 用 n 條 linked list 表示 graph
- linked list node structure
| Vertex | link |
| -------- | -------- |
- undirected graph
- 
- directed graph
- 
- 比較
- 求 graph 的邊的數量
- adjacency list : O(e)
- adjacency matrix : O(n^2)
- 找某個邊在 graph 中是否存在
- adjacency list : O(e)
- adjacency matrix : O(1)
- 適用的情境
- adjaceny list : 當邊的數量比 vertex 數量少或差不多，ex. tree
- adjacency matrix : 當邊的數量比 vertex 數量多很多，ex. complete graph
### traversal
1. DFS (Depth First Search)
- 定義
- 深度優先走訪
- 採用 stack
- 步驟
1. 選擇一個 node 為起點
2. 若 node 有分支，則往 node 的 child 走訪；若無分支，則回到 node 的上個 node，回到第一步
3. 持續做 1, 2，直到沒有未走訪過的 node 可以走訪
- ex.
- 
- 演算法
```java=
void dfs(int v) {
visited[v] = true; // visited = 存每個 node 是否已經被走訪
int[] adj = getAdj(v); // adj = v node 的所有相鄰 node 的 array
for (int i = 0;i < adj.length;i++) {
if (!visited[adj[i]]) {
dfs(adj[i]);
}
}
}
```
2. BFS (Breadth First Search)
- 定義
- 廣度優先走訪
- 採用 queue
- 步驟
1. 選擇一個 node 為起點，放入 queue
2. 將 node 從 queue 中刪除
3. 把 node 還未走訪過的 child，放入 queue
4. 將 queue 裡面的 node 重複做 1, 2, 3
- ex.
- 
- 演算法
```java=
void bfs(int v) {
// start from node v
int visited[v] = true; // visited = 存每個 node 是否已經被走訪
queue q = new queue();
q.enqueue(v);
while (!q.empty()) {
v = q.dequeue();
int[] adj = getAdj(v); // adj = v node 的所有相鄰 node 的 array
for (int i = 0;i < adj.length;i++) {
if (!visited[adj[i]]) {
q.enqueue(adj[i]);
visited[adj[i]] = true;
}
}
}
}
```
- level order traversal
- use bfs on binary tree
### spanning tree
- 定義
- 沒有 cycle
- 包含 graph 的所有頂點，且為 connected
- ex.
- 
- 其中一棵 spanning tree
- 
- 求法
- dfs
- bfs
- minimum cost spanning tree
- 定義
- 有一 connected graph，且 edge 上有加權成本
- 要找出成本總和最小的 spanning tree
- 求法
1. kruskal's
- 步驟
1. 挑出 graph 中最小成本邊
2. 若加入此邊不會產生 cycle，則將此邊加入 spanning tree
3. 重複 1,2，直到 spanning tree 有 n-1 個邊
- ex.
- 
- 
- time complexity
- O(eloge)
3. prim's
- 步驟
1. 有一空集合 U，用於儲存已挑選的 node
2. 隨機選一個 node 放入 U
3. 找出所有由已挑選和未挑選的 node 組成的邊，選出成本最小的邊
4. 將此邊的未挑選的 node 放入 U，並將其從已挑選的集合刪除
5. 重複 3,4，直到所有 node 都被放入 U
- ex.
- 
- 
- time complexity
- O(n^2)
5. sollion's
- 步驟
1. 將所有的 node 視為一棵 tree
2. 找出每棵 tree 的 min cost edge，且需檢查是否造成 cycle
3. 重複 2，直到剩下一棵 tree or 無邊可挑
- ex.
- 
- 比較
- kruskal's 適合 edge 少的 graph（ex. tree）
- prim's 適合 edge 多的 graph（ex. complete graph）
### shortest path problem
- one to all
- 定義
- 在一 digraph 中，求某一個 vertex 到 graph 中其他剩餘的 vertex 的各個最短路徑的距離
1. Dijkstra's
- 步驟
1. 宣告一二維陣列 cost[n][n]，存相鄰成本
2. 宣告一一維陣列 used[n]，存已經走訪過的頂點
3. 宣告一一維陣列 min_dist[n]，存起點 vertex 到其他 vertex 的最短路徑的距離
4. 每回合找出不存在於 used 中，且是 min_dist 最小值的 vertex
5. 確認是否可從選擇的 vertex X 到其他 vertex Y 的路徑成本小於目前 min_dist 的值，若有且 vertex Y 不在 used，就換掉
6. 總共做 n-1 回合
- ex.
- 
- note
- 不能有負邊
3. Bellman Ford
- 步驟
1. 宣告一二維陣列 cost[n][n]，存相鄰成本
2. 宣告一一維陣列 min_dist[n]，存該 vertex 到其他 vertex 的最短路徑的距離
3. 每一回合 X，就檢查從起點走 X 條路的路徑成本是否有小於 min_dist，若有就換掉
4. 共做 n-1 回合
- ex.
- 
- 紅色邊代表加入該邊會造成負循環
- note
- 不能有負循環
- all to all
1. Floyd Warshall
- 步驟
1. 宣告一二維陣列 cost[n][n]，存相鄰成本
2. 宣告一二維陣列 min_dist[n][n]，預設的值等於 cost 的值，存所有 vertex 到其他 vertex 的最短路徑的距離
3. 每回合 X，檢查是否從經過 vertex X 的路徑有小於目前 min_dist 的 value，若有就換掉
4. 共做 n 回合
- ex.
- 
- note
- 不能有負循環
## 問題
- 請同學有問題可以統一留在這邊，上課一起討論
Sign in with Wallet
Connect another wallet