[toc]
# 樹與二元樹
## Tree
### Tree 定義
由 $\ge 1$ 個 nodes 所形成之集合，不可以為空，並且滿足
- 至少有一個特殊 node 稱為 root
- 其餘 node 分為 $T_1、T_2、T_3 \ ...\ T_m$ 之互斥集合，即為 root 之子樹
### Tree 表示方式
- **用 linked list**
| data | link 1 | link 2 | link 3 | ... | link k |
|--|--|--|--|--|--|
:::danger
極度浪費 linking space
共 $n*k$ 個 link ，有用的只有 $n-1$ 個
:::
- **Leftmost Child Next Right Sibling**
- 左子右兄弟 (Tree 化為 Binary Tree)
- | data | child | sibling |
|--|--|--|
- **括號法**
以 父(子子子子子...) 的方法，可以 nested
### Tree 其他考題
- node level 值
- root level 為 1
- forest 是由 $\ge 0$ 棵互斥的 trees 所形成的集合 (forest 可以為空)
## Binary Tree
### Binary Tree 定義
可以為空，若不為空，則滿足
- 有 root 及 左右子樹
- 左右子樹也是 Binary Tree
### Binary Tree 種類
- Skewed Binary Tree
- Left Skewed Binary Tree
- Right Skewed Binary Tree
- Full Binary Tree
- 具有最多 node 數
- Complete Binary Tree
- 高度 k，總 node 數為 n，滿足 $2^{k-1}-1\lt n \le 2^{k}-1$
- node 編號要由上而下，由左而右依序增長
- 一個 Complete Binary Tree 具有 n 個 nodes，若某 node 編號為 i
- 其左子點編號為 $2i$
- 其右子點編號為 $2i+1$
- 其父點編號為 $[\frac{i}{2}]$ (若 $[\frac{i}{2}] \lt 1$ 則無父點)
- Strict Binary Tree
- Binary Tree 中，任何 non leaf 皆有 2 個子點，即 $n_1 = 0$
### Binary Tree 實作
- 利用 array
- 作法 : 若 Binary Tree 高度為 k，則準備一個一維陣列 $A = array[1 ... 2^{k}-1]$，將各個 node 仿照 Full Binary Tree node 的編號，將 node data 填入 A 對應的表格中
- 優點 :
- 易於存取左右子點及父點
- 對於 Full Binary Tree 或 Complete Binary Tree 而言，無儲存空間浪費
- 缺點 :
- node 之插入、刪除不便
- 對於 Skewed Binary Tree 的儲存極為浪費空間(浪費 $2^k-1-k$ 格)
- 利用 link list 表示
- 作法 :
| Lchild | Data | Rchild |
|---|---|---|
- 優點 :
- node 之插入、刪除較為方便
- 對於 Skewed Binary Tree 儲存較 array 省空間
- 缺點 :
- 不易存取父點
- link 之空間浪費約 50% ($2n-(n-1)$)
### Binary Tree 追蹤
- Preorder
```cpp=
Preorder(BinaryTree T) {
if (T != NULL) {
print(T -> data);
Preorder(T -> leftChild);
Preorder(T -> rightChild);
}
}
```
- Inorder
```cpp=
Inorder (BinaryTree T) {
if (T != NULL) {
Inorder(T -> leftChild);
print(T -> data);
Inorder(T -> rightChild);
}
}
```
### Binary Tree 複製
```cpp=
CopyTree(node origin) {
if (origin == NULL)
return NULL;
else {
t = new_node();
t -> data = origin -> data;
t -> leftChild = CopyTree(origin -> leftChild);
t -> rightChild = CopyTree(origin -> rightChild);
}
}
```
### Binary Tree 比較
```cpp=
bool answer = false;
Equal(BinaryTree S, BinaryTree T) {
if (S == NULL && T == NULL)
return true;
else if (S != NULL && T != NULL) {
if (S -> data == T -> data) {
if (Equal(S -> leftChild, T -> leftChild))
answer = Equal(S -> rightChild, T -> rightChild);
}
}
return answer;
}
```
### Binary Tree 數 node
```cpp=
CountNodes(BinaryTree T) {
if (T == NULL)
return 0;
else {
int n1 = CountNodes(T -> leftChild);
int n2 = CountNodes(T -> rightChild);
return n1+n2+1;
}
}
```
### Binary Tree 樹高
```cpp=
TreeHeight(BinaryTree T) {
if (T == NULL)
return 0;
else {
int n1 = TreeHeight(T -> leftChild);
int n2 = TreeHeight(T -> rightChild);
return max(n1, n2)+1;
}
}
```
### Binary Tree 葉子數
```cpp=
TreeLeaves(BinaryTree T) {
if (T == NULL)
return 0;
else {
int n1 = TreeLeaves(T -> leftChild);
int n2 = TreeLeaves(T -> rightChild);
if (n1+n2 > 0)
return n1+n2;
else
return 1;
}
}
```
### Binary Tree 交換
```cpp=
SwapTree(BinaryTree T) {
if (T != NULL) {
SwapTree(T -> leftChild);
SwapTree(T -> rightChild);
temp = T -> leftChild;
T -> leftChild = T -> rightChild;
T -> rightChild = temp;
}
}
```
### Binary Tree 算算式
```cpp=
struct Node{
leftChild;
rightChild;
data;
answer;
}
ExprBT(BinaryTree T) {
if (T != NULL) {
ExprBT(T -> leftChild);
ExprBT(T -> rightChild);
switch(data) {
case "+" :
T -> answer = (T -> leftchild) -> answer + (T -> rightChild) -> answer;
break;
case "-" :
T -> answer = (T -> leftchild) -> answer - (T -> rightChild) -> answer;
break;
case "*" :
T -> answer = (T -> leftchild) -> answer * (T -> rightChild) -> answer;
break;
case "/" :
T -> answer = (T -> leftchild) -> answer / (T -> rightChild) -> answer;
break;
case "^" :
T -> answer = (T -> leftchild) -> answer ^ (T -> rightChild) -> answer;
break;
case "operand" :
T -> answer = int(operand);
}
}
}
```
### Binary Tree 排序
- Heap Sort
- Search Tree
- Binary Search Tree
- m-way Search Tree
- AVL Tree
- B Tree
- B+ Tree
### Binary Tree 和其他資料結構轉換
- Binary Tree 化為 Tree
步驟為 :
1. 逆時針轉 45 度，即右子點均向上拉成為父點之次右兄弟
2. 補足父、子之 links
3. 刪除 sibling 間的 link
- Tree 化為 Binary Tree
步驟為 :
1. 建立 sibling 之間的 links
2. 除了 Leftmost Child 的 link，刪掉其他父與子的 links
3. 順時針轉 45 度，即保留的 Leftmost Child 當左子點， Next Right Sibling 當右子點
- Forest 化為 Binary Tree
步驟為 :
1. 將 Forest 中每棵 Tree 化為 Binary Tree
2. 將各個 Binary Tree 之 root 們視為 siling，建立平行 links
3. 將這些 roots 順時針旋轉 45 度，其餘不變
- Binary Tree 化為 Forest
步驟為 :
1. 將 Binary Tree root 之右子點 link 上所有 node 均向上拉形成 root 之 sibing
2. 刪除 roots 間的 links，得到多棵 Binary Tree
3. 每個 Binary Tree 再化為 Tree
### Binary Tree 其他考題
- Binary Tree 與 Tree 之比較
| Tree | Binary Tree |
| -------- | -------- |
| 不可以為空 | 可以為空 |
| node degree $\ge 0$ 即可 | $2 \ge$ node degree $\ge 0$ |
| 子樹之間無次序或左右之分 | 子樹之間有左右之分 |
- Binary Tree 三個基本定理
- 二元樹中第 i level 最多 node 數為 $2^{i-1}$
- 高度為 k 之 tree 的 node 數最多為 $2^k-1$
- 給予一個非空的 Binary Tree，若 leaf 個數有 $n_0$ 個，degree-2 的 node 數為 $n_2$ 個，則滿足 $n_0 = n_2 + 1$
- n 個 nodes 可以形成的不同 Binary Tree 個數為 $\frac{1}{n+1}\binom{2n}{n}$
## Binary Search Tree (BST)
### Binary Search Tree 定義
是一個 Binary Tree，若不為空，則滿足
- 左子樹所有 node 均小於 root
- 右子樹所有 node 均大於 root
- 左右子樹亦是 Binary Search Tree
### Binary Search Tree 排序
步驟為
1. 將 Input Data 建成 Binary Search Tree
2. 對 Binary Search Tree 進行 Inorder 追蹤，得出由小到大的排序
### Binary Search Tree 建立
受到 Input Data 的順序影響，若 Input Data 的順序為
- 小到大 $\rightarrow$ Right Skewed Binary Search Tree
- 大到小 $\rightarrow$ Left Skewed Binary Search Tree
### Binary Search Tree 中刪除某元素 x
步驟為
1. 先 search for x
2. 分成下列 cases
- case 1 : x 是 leaf，則刪 x
- case 2 : x 是 degree-1 的 node，則將 x 的父點原先指向 x 的 pointer 指向 x 的子點，再刪 x
- case 3 : x 是 degree-2 的 node，則以 x 左子樹的最大值或 x 右子樹的最小值取代 x，再回到 case 1 或 case 2
> 平均時間複雜度為 $T(n) = O(logn)$
> 但若為 Skewed Binary Search Tree，則時間複雜度為 $T(n) = O(n)$
### Binary Search Tree 中搜尋某元素 x
```cpp=
Search(BinaryTree T, int x) {
if (T != NULL) {
switch(CompareValue(T -> data, x)) {
case "=" :
return true;
case "<" :
return Search(T -> rightChild, x);
case ">" :
return Search(T -> leftChild, x);
}
}else
return false;
}
```
> 若為 AVL Tree、Red Black Tree、Full Binary Tree 或 Complete Binary Tree 等高度最小化的樹時，則時間複雜度為 $T(n) = O(logn)$
> 但若為 Skewed Binary Search Tree，則時間複雜度為 $T(n) = O(n)$
### Binary Search Tree 找出第 i 小的元素
| Lsize | Lchild | Data | Rchild |
|--|--|--|--|
Lsize 主要功能為記 node 左子樹的 node 個數
```cpp=
struct node {
leftChild;
lsize;
data;
rightChild;
}
SearchiSmall(BinaryTree T, int i) {
if (T != NULL) {
int k = (T -> lsize) + 1;
if (i == k)
return T -> data;
else if (i < k)
return SearchiSmall(T, i);
else
return SearchiSmall(T, i-k);
}
}
```
## Thread Binary Tree
### Thread Binary Tree 定義
Binary Tree 具有 n 個 nodes，以 link list 表示，會有 n+1 條 null links，為了充分利用這些 null links，所以會將這些 null links 視為 Thread Pointer，改成指向其他 node
一般而言，是以 Inorder 順序為規範，Thread Pointer 如下 :
- 若 x $\rightarrow$ Lchild 為 null，則此 pointer 當作左引線，改指向 Inorder 順序中 x 的前一個 node
- 若 x $\rightarrow$ Rchild 為 null，則此 pointer 當作右引線，改指向 Inorder 順序中 x 的後一個 node
### Thread Binary Tree 實作
| Left Thread | Lchild | Data | Rchild | Right Thread |
| -------- | -------- | -------- |--|--|
Left Thread :
- true : 表 Lchild 為 Left Thread
- false : 表 Lchild 為 Lchild
Right Thread :
- true : 表 Rchild 為 Right Thread
- false : 表 Rchild 為 Rchild
會額外加一個 Head node 不存在 Data，Head node 規定如下 :
- case 1 : 空樹
| True | Lchild | Data | Rchild | True |
|--|--|--|--|--|
- case 2 : 非空樹
| False | Lchild | Data | Rchild | False |
|--|--|--|--|--|
### Thread Binary Tree 中找 Inorder 順序裡 x 的下一個元素
步驟為 :
1. 若 x 的 Right Thread 為 true，則 x 的 Rchild 即是
2. 若 x 的 Right Thread 為 flase，則沿著 x 的右子點往左下尋找，直到某個 node 的 Left Thread 是 true 為止，則為該 node
```cpp=
Insuc(node x) {
temp = x -> Rchild;
if (! x -> RightThread) {
while(! temp -> LeftThread)
temp = temp -> Lchild;
}
return temp -> data;
}
```
### Thread Binary Tree 中找 Inorder 順序裡 x 的上一個元素
步驟為 :
1. 若 x 的 Left Thread 為 true，則 x 的 Lchild 即是
2. 若 x 的 Left Thread 為 flase，則沿著 x 的左子點往右下尋找，直到某個 node 的 Right Thread 是 true 為止，則為該 node
```cpp=
Inpre(node x) {
temp = x -> Lchild;
if (! x -> LeftThread) {
while(! temp -> RightThread)
temp = temp -> Rchild;
}
return temp -> data;
}
```
### Thread Binary Tree 簡化 Inorder 追蹤
從 Head node 開始，不斷地問 x 的下一個元素，直到又回到 Head 為止
```cpp=
Inorder(node n) {
temp = n;
repeat :
temp = Insuc(temp);
if (temp != n)
print(temp -> data);
until (temp == n);
}
```
### Thread Binary Tree 中在 s 的右子點插入元素 x
分為兩個 case
- case 1 : 若 s 原本無右子點
步驟為 :
1. 將元素 x 的 Right Thread 指向 s 的 Right Thread (Right Thread 為 true)
2. 將元素 x 的 Left Child 指向 s (Left Thread 為 false)
3. 將 s 的 Right Child 指向 x
- case 2 : 若 s 原本有右子點
步驟為 :
1. 將元素 x 的 Right Child 指向 s 的Right Child (Right Thread 為 false)
2. 將元素 x 的 Left Thread 指向 s (Left Thread 為 true)
3. 將 s 的 Right Child 指向 x
4. 將 s 的右子樹中最左邊 node 的 Left Thread 指向元素 x
```cpp=
Insert(s, t : nodes of thread binary tree) {
t -> RightThread = s -> RightThread;
t -> Rchild = s -> Rchild;
s -> RightThread = false;
s -> Rchild = t;
t -> LeftThread = true;
t -> Lchild = s;
if (t -> RightThread) {
temp = Insuc(t);
temp -> Lchild = t;
}
}
```
## Heap
### Heap 定義
可分為 Max-Heap 及 Min-Heap
- Max-Heap :
- 是一個 Complete Binary Tree
- 所有父點均 $\ge$ 其子點
- root 具有最大值
- Min-Heap :
- 是一個 Complete Binary Tree
- 所有父點均 $\le$ 其子點
- root 具有最小值
### Heap 建立
方法有兩種
- Top-Down 法 (慢)
- 作法 : 依序執行插入某元素 x 的動作，逐步建立 Heap，而在每一中間過程之後，均維持是 Heap 的性質
- > $T(n) = O(nlogn)$
- Bottom-Up 法 (快)
- 作法 :
- 將 Input Data 以 Complete Binary Tree 方式呈現
- 從 the last parent 開始，往回各個父點依序調整每棵子樹成為 Heap，直到調到 root 為止
- code
```cpp=
CreateHeap(Tree T, int n) {
for i = n/2 to 1
Adjust(T, i, n);
}
Adjust(Tree T, int i, int n) {
k = T[i];
j = 2*i;
while(j <= n) {
if (j < n) {
if (T[j+1] > T[j])
j ++;
}
if (T[j] <= k)
break;
else {
T[j/2] = T[j];
j *= 2;
}
}
T[j/2] = k;
}
```
- > $T(n) = O(n)$
### Heap 中插入某元素 x (Max-Heap 為例)
步驟為 :
1. x 先暫置於 the last node 的下一個位置
2. x 往上挑戰父點，直到無父點或挑戰失敗為止
> $T(n) = O(logn)$
### Heap 中刪除某元素 x (Max-Heap 為例)
步驟為 :
1. 移走 root 的 Data
2. 將 the last node x 刪掉，並將 x 暫置於 root 位置
3. x 自 root 向下調整，直到符合 Heap 為止
> $T(n) = O(logn)$
### Heap 中刪除最大元素 (Max-Heap 為例)
```cpp=
DeleteHeap(Tree T, int n) {
item = T[1];
T[1] = T[n];
n --;
Adjust(T, 1, n);
return item;
}
Adjust(Tree T, int i, int n) {
k = T[i];
j = 2*i;
while(j <= n) {
if (j < n) {
if (T[j+1] > T[j])
j ++;
}
if (T[j] <= k)
break;
else {
T[j/2] = T[j];
j *= 2;
}
}
T[j/2] = k;
}
```
> $T(n) = O(lgn)$
### Heap 應用
- Heap Sort
- Priority Queue 最適合的 Data Structure
- | Operation | Time |
| -------- | -------- |
| Insert x | $O(logn)$ |
| Delete max (或 min) | $O(logn)$ |
| Search max (或 min) | $O(1)$ |
| Create Heap | $O(n)$ |
| Merge two Heap into a Heap ($O(2n)$) | $O(n)$ |
| Increase (Decrease) key of node | $O(logn)$ |
| Search for x | $O(n)$ |
| Delete x | $O(logn)$ |
### Heap 其他考題
- Heap 適合用 array 儲存
## Disjoint Set
### Disjoint Set 定義
一組互斥之集合組成
### Disjoint Set 表示方式
每個 set 利用 Tree 結構表示，即從 set 中任取一做為 Tree 的 root，其餘為他的子點
- 用 link list
- | Data | Parent |
|--|--|
- 用 array
- | Index | Data | Parent |
| -------- | -------- | -------- |
| 1 | 1 | 0 |
| 2 | 2 | 1 |
| 3 | 3 | 1 |
| 4 | 4 | 5 |
| 5 | 5 | 0 |
| 6 | 6 | 5 |
| 7 | 7 | 0 |
| 8 | 8 | 7 |
| 9 | 9 | 5 |
| 10 | 10 | 7 |
### Disjoint Set 應用
- Kruskal's Algorithm 中判斷邊 (u, v) 加入 Spanning Tree 中是否形成 cycle
- 根據等價配對資訊，求出等價集合
- 求 Directed Graph 中的 Connected Component 之方法之一
### Disjoint Set 尋找運作之組合討論
兩個基本操作 :
union(i, j) $\rightarrow$ 聯集 $set_i$ 與 $set_j$
find(x) $\rightarrow$ 找出 x 元素所在的 set 的 root，傳回那個 root
- [組合一] 任意的 union(i, j) 及 simpleFind(x)
```cpp=
//任意的 union(i, j)
union(i, j) {
j -> parent = i;
}
```
```cpp=
// simpleFind(x)
simpleFind(x) {
temp = x;
while(temp -> parent != temp) {
temp = temp -> parent;
}
return temp;
}
```
> $Union : T(n) = O(1)$
> $Find : T(n) = O(n)$
- [組合二] union_by_height(i, j) 及 simpleFind(x)
樹高較高者作為新樹的 root，另一個 set 作為其子樹
若高度相同，則做任意 union
```cpp=
union_by_height(i, j) {
if (Height(i) >= Height(j)) {
if (Height(i) == Height(j))
i ++:
j -> parent = i;
}else
i -> parent = j;
}
```
```cpp=
// simpleFind(x)
simpleFind(x) {
temp = x;
while(temp -> parent != temp) {
temp = temp -> parent;
}
return temp;
}
```
> $Union\_By\_Height : T(n) = O(1)$
> $Find : T(n) = O(lgn)$
- [組合三] union_by_height(i, j) 及 Find_with_path_compression(x)
除了找出 x 所在 set 之 root 外，另外會將 x 的 parent links 上所有 nodes (包含 x，但不包含 root) 的 parent 指標均改成指向 root (即做了路徑壓縮)
```cpp=
union_by_height(i, j) {
if (Height(i) >= Height(j)) {
if (Height(i) == Height(j))
i ++:
j -> parent = i;
}else
i -> parent = j;
}
```
```cpp=
Find_with_path_compression(x) {
if (x != x -> parent)
x -> parent = Find_with_path_compression(x -> parent);
return x -> parent;
}
```
> $Union\_By\_Height : T(n) = O(1)$
> $Find\_with\_path\_compression : T(n) = O(\alpha(m,n))趨近於O(1)$
Sign in with Wallet
Connect another wallet