# 資料結構 Data Structure (CSIE-2B)
###### tags: `courses meow` `CSIE-2B` `Data Structure` `2020 Autumn`

:::success
:::spoiler Click to open TOC
[TOC]
:::

## Binary Tree

### 定義
- 每個節點分支度(tree's degree)最高為二
- 分支具有左右順序，不可隨意調換
- 分支通常稱為左子樹(left subtree)和右子樹(right subtree)
- 節點數
- 深度(level)為$k$的二元樹，至多有$2^{k-1}$個節點
- 定義根結點(root)深度為1
- 第$i$層，至多有$2^{i-1}$個節點
- 設葉節點為$n_0$，分支度為2的節點為$n_2$，則$n_0=n_2+1$

- [二元樹節點證明](https://patroclus.pixnet.net/blog/post/249101409-%E6%9C%89%E8%B6%A3%E7%9A%84%E4%BA%8C%E5%85%83%E6%A8%B9%E8%AD%89%E6%98%8E%E9%A1%8Cn0-%3D-n2-%2B-1)
### 特殊類型
- 完滿二元樹(Full binary Tree)
- 一棵高度為$k$的樹，且此樹含有$2^{k-1}$個節點，則為完滿二元樹
- 完全二元樹(Complete binary Tree)
- 除了最後一階層的節點都必須填滿，且最後一層必須由左至右填滿
- 有$n$個節點的完滿二元樹，其樹高為$⸢log_2(n+1)⸣$
- 嚴格二元樹(Strictly binary tree)
- 每一個節點都有兩個子節點或沒有節點
- 歪斜二元樹(Skewed binary tree)
- 所有節點都只有同一邊的子節點
- 平衡二元樹(ballanced tree)
- 所有葉節點在同一階層

> * 完滿二元樹必定為完全二元樹
> * 完滿二元樹必定為嚴格二元樹
> * 完全二元樹不一定是嚴格二元樹

### 實作
- 陣列(Array)
- 優點是容易實作
- 陣列index為 $i$
- 根結點(root)位置為$0$
- 父節點(parent)位置為$(i-1)/2$
- 左子節點(left child)位置為$2^*i+1$
- 右子節點(right child)位置為$2^*i+2$
- 缺點是如果二元樹長得很稀缺，則會相當耗費記憶體空間
- 適合用於完滿二元樹和完整二元樹
- 不適合用作歪斜二元樹
- 另一個缺點是如果要刪除節點則需要搬移許多節點
- 連結串列(Linked list)
- 以指標指向父節點和子節點
- 易於新增或是刪除節點

### 走訪(Traversal)
- 深度優先走訪
- 深度優先走訪是透過決定向左或向右走，直到走到盡頭
- 是一種遞迴走訪
- 拜訪每個節點各一次，總共可以有$3!=6$次
- VLR
- VRL
- LRV
- LVR
- RLV
- RVL
- 規定要先走左子樹再走右子樹，則有3種結果
- VLR(Preorder)
- 根節點 -> 左節點 -> 右節點
- 可用來表示前序運算式
- :::info
:::spoiler Click to open the code

                void Preorder(tree_node *node)
                {
                    print(node -> data)
                    if(node -> left != NULL)
                        Preorder(tree_node -> left)
                    if(node -> right != NULL)  
                        Preorder(tree_node -> right)
                }

:::

- LVR(Inorder)
- 左節點 -> 根結點 -> 右節點
- 可用來表示中序運算式
- :::info
:::spoiler Click to open the code

                void Inorder(tree_node *node)
                {
                    if(node -> left != NULL)
                        Inorder(tree_node -> left)
                    print(node -> data)
                    if(node -> right != NULL)   
                        Inorder(tree_node -> right)
                }

:::

- VRL(Postorder)
- 左節點 -> 右節點 -> 根結點
- 可用來表示後序運算式
- :::info
:::spoiler Click to open the code

                void Postorder(tree_node *node)
                {
                    if(node -> left != NULL)
                        Postorder(tree_node -> left)
                    if(node -> right != NULL)  
                        Postorder(tree_node -> right)
                    print(node -> data)
                }

:::

:::success
:::

:::warning
* 只有Preorder跟Postorder無法定義一棵樹
* 在表示運算式時，不可以把括號寫出來(小心TA扣分)
:::

### 應用
> 對節點定義一個標記函式，使節點儲存特定資料
- 二元搜尋樹(Binary Search Tree)
- 也稱為有序二元樹（ordered binary tree）或排序二元樹（sorted binary tree）
- 符合以下性質
- 每個節點的值(key)皆不同
- 左子樹任意節點之值皆小於跟節點之值(若左子樹不為空)
- 右子樹任意節點之值皆大於跟節點之值(若右子樹不為空)
- 任意左子樹和右子樹也皆為二元搜尋樹
- 優點
- 容易實做
- 進行插入和尋找時的時間複雜度較小
- 插入($O(n)$,n = 樹高)
- 尋找($O(n)$,n = 樹高)
:::Info
:::Spoiler
:::
- 霍夫曼樹(Huffman tree)
- 二元堆積

## Graph

### 定義
- 一個圖應包含兩個元素
- 點? ， 此集合不可為空，且為有限
- 邊，連接點
- 有向與無向圖
- 有向圖(Directed graph)
- 圖的邊有方向性
- 邊用<v,n>表示
- v,n之間有方向性，即圖之間同時有v向n的邊和n向v的邊，則會有<v,n>、<n,v>兩個元素
- <v,n>可被敘述為
- v is adjacent to u
- u is adjacent from v
- the edge <v,u> is incident to v and u
- 無向圖(Undirected graph)
- 圖的邊無方向性
- 邊用(v,n)表示
- (v,n)可被敘述為
- u and v are adjacent
- (u,v) is incident on vertices u and v

#### Euler's Solution

### Adjacency Matrix

- 會是一個n*n方陣(n為點數)
- 若為無向圖則
- 矩陣圖會對稱
- 對角線皆為0(自己對到自己)
- 特點
- 適合存點跟邊的數量不差太多
- 需要點平方大的空間(n^2)

### Adjacency Lists

- 適合存點多但邊不多的圖

### Spanning Tree
- 把一個 graph 刪除一些邊，直到變成一個樹

### Kruskal
> 加 edge
- 將所有的邊用成本來排序
- 每次選成本最低的邊，若加上此點不會產生迴圈就加，若會就遺棄

### prim's
> 加 vertex
- Greedy 式的演算法
- 從隨便一個點開始
- 從跟目前的spanning tree 相連的邊中，選最短的邊。加上去

## Sorting

### types

#### stable
- 同樣的 element 本來在前面的還是在前面

#### Internal sorting

#### External sorting

### sorting methods
- Bubble sort
- swap
- insertion sort
- insert
- selection sort
- select the most-small one and swap
- quick sort
- merge sort
- heap sort
-
### Bubble Sort
<!--Use $ sign for latex --> <!--It's soooo cool-->
- $O(n^2)$
- 將兩個相鄰的元素相比，若前面比後面大，則調換位置
- 做完第一次後，最大的元素將在最後面
- 將每個元素做上述的動作，因此要做 $n^2$ 次

### Quick Sort

- 最糟狀況為 $n^2$，但發生機率極低，通常是 $nlog_2n$
- 將大問題分割成小問題處理
- 每次選取一個數做基準(通常直接選第一個數)
- 比基準大的排後面，比基準小的排前面
- 重複做到無數可排
- 是二元搜尋樹的一種空間最佳化版本
- 不直接建樹出來，而是快速排序組織資料集到一個隱含的樹當中
- 使用兩個指標實作
- 一個指標從最前面開始，找比基準大的數
- 一個指標從最後面開始，找比基準小的數
- 當兩個指標都找到時
- 兩個數交換
- 一直重複直到兩個指標交叉
- 交叉的位置即基準的位置

:::info
:::spoiler Click to open code

quickSort(array[0 ~ N]):
	if (array.size == 1):
		return
	pivot = array[0]
	i = 0
	j = N
	while (i <= j):
		if (array[i] <= pivot): i++
		if (array[j] > pivot): j++
		if (array[i] > pivot && array[j] <= pivot):
			swap(array[i], array[j])
	swap(array[0], array[i])
	quicksort(array[0 ~ N/2])
	quicksort(array[N/2 ~ N])

:::

### Heap Sort

- $O(nlog_2n)$
- 保證子節點資料比父節點小
- 每次資料存入時，跟父節點比較，若比父節點大則交換
- 樹中不能保證左右節點之資料誰大誰小
- 要排序時，將資料依序從根結點拔出，拔出後再次跟子節點比較，保證每次根節點資料為最大

### Merge Sort

- $O(nlog_2n)$
- 每次抓兩組資料做比較，比較完再兩兩比較，直到全部比完

## Multi-way search tree
- General特性
- 每個 Node 中
- 至少有一個 data
- 有 (1 + data數量) 個 Child
- data 與 Child 指標交錯
- ```
node(*ptr, data, *ptr, data, *ptr)

	- 每個 Child 的大小介在左右兩個data之間
- M-way search tree
	- 每個 node 的 degree 為 M
	- <=>每個 node 有 M 個 child
	- <=>每個 node 有 M-1 個 data

## B-Tree
> Balanced Multi-way Search Tree