---
title: 'Tree'
disqus: hackmd
---
---
索引
[TOC]
---
Tree
===
* 由至少 1 個 Node 構成之集合，**不可為空**
* 其餘 Nodes 分成 T~1~ ~ T~m~ **互斥集合** (各自也是一棵樹A,B,C)
* Binary Tree 是 Tree 的一種，請不要搞混
```graphviz
digraph graphname{
1 [label="Root"];
2 [label="A"];
3 [label="B"];
4 [label="D"];
5 [label="E"];
6 [label="F"];
7 [label="G"];
8 [label="H"];
9 [label="C"];
1 -> 2 [label=" T1", fontcolor=red]
1 -> 3 [label=" T2", fontcolor=red]
1 -> 9 [label=" T3", fontcolor=red]
2 -> 4
2 -> 5
3 -> 6
3 -> 7
9 -> 8
}
```
---
## Terminology of Tree
> [color=#52d356]**分支 Branch**
>* 分支度：Degree
>* 樹的分支度：Degree of Tree **(對整顆樹而言)**
:::info
整棵樹裡 $Degree$ 數最大的即是 $Degree\ of\ Tree$
$Branch$ 數 $=$ 所有 $Degree 合 = 節點數 - 1$ $( 因為無\ branch\ 到\ Root )$
:::
```graphviz
digraph graphname{
1 [label="Deg:2"];
2 [label="Deg:2"];
3 [label="Deg:3 = Degree of Tree" , fontcolor=Red] ;
4 [label="Deg:0"];
5 [label="Deg:0"];
6 [label="Deg:0"];
7 [label="Deg:0"];
8 [label="Deg:0"];
1 -> 2
1 -> 3
2 -> 4
2 -> 5
3 -> 6
3 -> 7
3 -> 8
}
```
> [color=#52d356]**節點 Node**
>* 樹葉、終端節點：Leaf、Ternimal Node
>* 非樹葉、非終端節點：Non-Leaf Node、Nonternimal Node
>* 上父點、下子點：Parent、Child
>* 左兒子、右兒子：Left Child、Right Child
>* 左右兄弟：Sibling
>* 祖先：Ancestors
>* 叔父：Uncle ( Parent 的 Sibling )
>* 孫子：Grandchild
:::info
樹葉 = Degree-0 Node
Node總數 = Nodes (個人定義)
上父、下子 只是個人方便記憶使用
:::
> [color=#52d356]**外型**
>* 階級：Level
>* 高度、深度：Height、Depth **(對整顆樹而言)**
:::info
整棵樹裡 Level 數最大的即是 Height、Depth :mega:
:::
```graphviz
digraph graphname{
1 [label="Root"];
2 [label="A"];
3 [label="B"];
4 [label="D"];
5 [label="E"];
9 [label="C"];
10 [label="Height = 3 (1為起點)",shape=box,fontcolor=blue];
1 -> 2
1 -> 3
1 -> 9
2 -> 4
2 -> 5
}
```
>[color=#52d356]* 森林：Forest
:::info
N互斥樹的集合 (N>=0)
森林可以為空，即一棵樹都沒有 :mega:
:::
```graphviz
digraph graphname{
2 [label="A"];
3 [label="B"];
4 [label="D"];
5 [label="E"];
6 [label="F"];
7 [label="G"];
8 [label="H"];
9 [label="C"];
1 [label="3顆互斥樹集合",shape=box,fontcolor=blue];
2 -> 4
2 -> 5
3 -> 6
3 -> 7
9 -> 8
}
```
>各名詞之詳細定義網路上皆有，不再贅述
>[time=Sat, May 4, 2019 4:57 PM]
>
---
## Tree Representation in C
### Linked List
>[color=#44e002] 1. 找出 Degree of Tree
> 2. 設置相同數目的 Link 欄位在 Node Structure 裡面
> 3. 依序將 Link 連結至該 Node 之 Child
> 4. 未使用之 Link 指向 `NULL` (紅圈處)
>
| 優點 | 缺點 | 解決辦法 |
|:------:|:-----------:|:-----:|
| 無明顯優點 | 未使用之 Link 佔據太多，浪費記憶體空間 |使用二元樹(Binary Tree)
> [color=#] **浪費比例：**
>
假設 $Tree\ Degree\ = k\ , Nodes = n$
1. 總共有 $k*n$ 條 $Links$
2. 使用的 $Links$ 數
= $n-1$ ( n 個 nodes 除了 Root 沒有 Link 指向)
3. 未使用 $Links$ 數
= $kn - (n-1) = kn-n+1$
4. 未使用之比例 = 未使用/總共
= $\frac{kn-(n-1)}{kn}$
= $\frac{kn-n+1}{kn}$
≒ $\frac{kn-n}{kn}$
= $\frac{k-1}{k}$
5. 則有 $\frac{k-1}{k}$ 比例為空欄位
> **解決辦法：**
>
:::info
為有效判斷資料大小、故無法使用 $Degree\ =\ 1$ 之 $Tree$
所以使用 $Degree\ of\ tree$ 為 $2$ 之樹為最佳效率
$\frac{k-1}{k}$ 之最低值為 $當\ k=2 → \frac{(2-1)}{2} = 50\%$
:::
<font color=red>而 $Degree\ of\ tree$ 為 $2$ 之樹 即是 $Binary\ Tree$</font>
---
### Child - Sibling
to be continued
---
### [Brackets](https://www.geeksforgeeks.org/binary-tree-string-brackets/)
to be continued
---
## Disjoint Set in C
* 了解樹是由一群 **互斥的集合** 所組成後，我們來探討如何在程式裡面表達該集合們
:::info
**Def**
* $S_1$ = { $1,3,5,7$ }
* $S_2$ = { $2,4,8$ }
* $S_3$ = { $6,9,10$ }
:::
* 接著將每一個 Set 以 Tree 來表達，以方便作為建立資料的參考
* 每個 Node 的位置沒有一定，只要確保他們都在同一集合 (Tree) 裡即可
```graphviz
graph graphname{
1--3
1--5
1--7
2--4
2--8
6--9
6--10
}
```
---
### Linked List
* 我們將 Node 之間的關係想像成這樣
**Set1**
```
Node 9 ->NextNode = Node 6
Node 10->NextNode = Node 6
```
**Set2**
```
Node 4->NextNode = Node 2
Node 8->NextNode = Node 2
```
**Set3**
```
Node 3->NextNode = Node 1
Node 5->NextNode = Node 1
Node 7->NextNode = Node 1
```
---
### Array
* 我們將 Node 之間的關係想像成這樣，並將各 Node 的編號與 Data 設為一樣
```graphviz
graph graphname{
3--1
3--5
3--7
4--2
4--8
9--6
9--10
}
```
* 使用一個二維陣列來表達，直覺方便性我們捨棄了兩個首空間 [0][0],[1][0]
* 依照 Tree 的畫法 3 , 4 , 9 分別是該樹的樹根，所以當我們尋找這 3 個 Node 的 Parent 時，會將該值改成該顆樹的 Node 數量，並加上負號表示他是 Root
* [0][1] 表示 Node 1 的 Data 為 1
* [1][3] 表示 Node 3 的 Parent 但他是 root 所以以負號表示、Node 3 的數共有 4 個 Nodes
> [color=#c4674a] 早期版本 Root Parent 的表達方式
> Index 從 0 開始：Null
> Index 從 1 開始：-1
---
### Application
* Kruskals's Algo. 判斷 Sapnning Tree
* 根據 等價關係 找出 等位集合
* 在離散數學中的定理都適用於此
---
## Union & Find
* 在集合若想合併 (聯集) ，以 Tree 為方向思考，合併出來的 Height 將因合併條件不同導致影響到 Find 效率，以下探討關於 Union 的幾種方法及其 Time Complexity
### 1. Simple Union
* Union(3,4) 隨機選取一 Tree 的 Root 作為另一顆的 Child
```graphviz
graph graphname{
3--1
3--5
3--7
4--2
4--8
}
```
* 選取 Root 3 作為 Root 4 的 Child
```graphviz
graph graphname{
3--1
3--5
3--7
3--
4--2
4--8
}
```
:::warning
**Time Complexity：**
很明顯合併時間為固定的常數時間 **O(1)**
:::
#### Find 對於 Simple Union
> [color=#52d356]定義此章節的 **Find** ：從 Leaf 依序向上搜尋至 Root 一次的過程
* 考慮以下 Tree
```graphviz
graph graphname{
1
2
3
4
}
```
**Best Case 下的 Simple Union**
* Union(1,2) 選取 1 作為 2 的 Child
```graphviz
graph graphname{
2--1
3
4
}
```
* Union(2,3) 選取 3 作為 2 的 Child
```graphviz
graph graphname{
2--1
2--3
4
}
```
* Union(2,4) 選取 4 作為 2 的 Child
```graphviz
graph graphname{
2--1
2--3
2--4
}
```
**Worst Case 下的 Simple Union**
* Union(1,2) 選取 1 作為 2 的 Child
```graphviz
graph graphname{
2--1
3
4
}
```
* Union(2,3) 選取 2 作為 3 的 Child
```graphviz
graph graphname{
2--1
3--2
4
}
```
* Union(3,4) 選取 3 作為 4 的 Child，Height 將與資料量 n 一樣
```graphviz
graph graphname{
4--3--2--1
}
```
:::warning
**Time Complexity：O(n)**
:::
---
### 2. Union by Height
> [color=#52d356] **Def：樹高起始點 0**
* 這次依據 Height 作為合併的條件，從上述可得 n 筆資料需要進行 n-1 次 Union，則 Height = $log_2n$
* 設 n = 2
```graphviz
graph graphname{
1
2
}
```
* 第一次 Union(1,2) Height = $log_22 = 1$
```graphviz
graph graphname{
1--2
}
```
### 3. Union by Size
* 藉由
###### tags: `Data Structure`
Sign in with Wallet
Connect another wallet