112考資工研究所時寫的筆記，有錯歡迎留言指正
內文有引用他人筆記/教材/文章的地方
若有侵權十分抱歉，告知後將立刻撤除

Basic concept
Array
Stack & Queue
Linked list
Tree & Binary Tree
Graph
Sorting
Hashing
高等樹
補充

Basic concept

太基本了，幾乎都是algo的東西，skip

Array

算幾題array和位址的轉換(2d array很多陷阱)就差不多了
row major 和 column major 算出來結果可能都可以，答案就會不只一個

Stack & Queue

queue & stack的實作應該可以跳過 (算都會了吧?)
考過不只一次，不看根本不會
- infix to prefix using stack
- infix to postfix using stack
postfix 用stack運算結果
- 歷屆16, 19

Linked list

Sparse matrix (p141)有點常考
Generalized list (p149)
- 挺煩人的，很容易忘

Tree & Binary Tree

Define:
- $n :$ 全部node個數
- $n_{0} :$ deg(v)=0的node個數
- $n_{1} :$ deg(v)=1的node個數
- $n_{2} :$ deg(v)=2的node個數
- 重要定理
  $: n_{0} = n_{2} + 1$
  - proof:
    $n = n_{0} + n_{1} + n_{2} = 1 + n 1 + 2 n_{2}$
  - 三種node合=從deg記算的node數，+1為沒被算入的root(沒人存他)
Complete Binary tree
- 簡單來說就是，由上到下由左到右長
Full Binary tree
- 定義一:
  - 剛好把leaf那層長滿，每片數葉深度都一樣
  - 深度為h的full binary tree，node必為
    $2^{h} - 1$
- 定義二:
  - 除了葉子以外的節點 (internal node) degree皆為n (n在binary tree中為2)
- 兩個定義的tree會長得很不一樣，需看題目怎麼定義
把BST用inorder輸出，即為排序好的結果
Thread Binary Tree (p182)
- 看一下線怎麼連，code先skip
Leftmost child next right sibling (p187)
- 留左邊child的link，其他砍掉，同層連起來，旋轉45度 (很抽象)
森林轉成樹 (p188)
- root連在一起，旋轉一下
Inorder, preorder, postorder熟到爛掉，skip
- 記得一定要有Inorder才能決定唯一tree (preorder, postorder無法唯一決定)
n個node的binary tree有
$\frac{1}{n + 1} (\binom{2 n}{n})$ 種 (catalan number)
計算某條件下(ex. deg=i的node有幾個)的internal node/leaf數量，把branch數量也拿來列式 (歷屆5,6)
Heapify整棵是亂的樹 (歷屆38)
- 從root開始，廣度優先檢查node是否符合heap規則(可能是min or max當parent)
Heap可以在O(n)時間內建好
- from mega ch5 tree
- stackoverflow說明
- 但是把每個node刪除/提取出，還是需要
  $O (n \lg n)$

Graph

edge種類(DFS後，把edge分成4種)
1. Tree: Edges in the DFS forest
2. Back: From descendant to ancestor when explored (include self loop)
3. Forward: From ancestor to descendant when explored (exclude tree edge)
4. Cross: Others (no ancestor-descendant relation)
- 無向圖只有tree edge, back edge而已!
articulation point (cut vertex)
- 移出該vertex後，會導致圖變為disconnected，稱作articulation point
- 尋找articulation point的演算法
  - Remove v from graph
  - See if the graph remains connected (BFS or DFS)
  - Add v back to the graph
adjacency matrix vs transitive closure
- adjacency matrix對角線是0，transitive closure對角線是1
- adjacency matrix紀錄點之間的距離
- transitive closure紀錄的是"能到達為1，不能到達為0"
AOE network (activity on edge network)
- 以p297 試題50為例
- 先算出每個node最早發生時間，反推可得最晚發生時間，兩個時間可以註記在node上
- critial path length即為最後一個node(event)的數字
- 用看的找出critical path (看一下length是不是跟上面一樣!)
- event最早完成時間就是activity的earlist start time
- event最晚完成時間減去活動長度即為activity的latest start time
- 我還是拍影片好了

Sorting

證明用comparison為基礎的排序至少都要nlgn的時間:
- 說明decision tree高度為
  $⌈ \log_{2} n! ⌉ + 1$

穩定排序: 插入、泡泡、融合、基數 (insertion, bubble, merge, radix)
不穩定排序(也可記排除上面那些): 選擇、快速、堆積 (selection, quick, heap)

Insertion sort

不斷把尚未sort的item插入前面已經sort好的部分

Stable
Space complexity:
$O (1)$
Time complexity:
- Worst:
  $O (n^{2})$
- Avg:
  $O (n^{2})$












void InsertionSort(int *arr, int size){

    for (int i = 1; i < size; i++) {
        int key = arr[i];
        int j = i - 1;
        while (key < arr[j] && j >= 0) {
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = key;
    }
}

參考
Comparison Sort: Insertion Sort(插入排序法)
Rust Algorithm Club

Selection sort

一直把最小的抓下來放

Unstable
Space complexity:
$O (1)$
Time complexity:
- Worst:
  $O (n^{2})$
- Avg:
  $O (n^{2})$









void selection_sort(int array[], int n) {
    for (int i=0; i<n-1; i++) {
        int min_idx = i;
        for (int j=i+1; j<n; j++)
            if (array[j] < array[min_idx])
                min_idx = j;
        swap(array, min_idx, i);
    }
}

參考
Rust Algorithm Club
C/C++ selection sort 選擇排序法

Bubble sort(sinking sort)

比較兩個相鄰元素，若首個元素比次個元素大，置換兩者的位置。
依序對相鄰元素執行步驟一，直到抵達序列頂端，此時頂端元素排序完成。
重複步驟 1 - 2 的整個序列疊代，直到任何一次疊代沒有執行元素置換。
當然也可以如下程式，直接疊代n次後停止

stable
Space complexity:
$O (1)$
Time complexity:
- Worst:
  $O (n^{2})$
- Avg:
  $O (n^{2})$




for(i = n-1; i > 0; i--)
    for(j = 0; j <= i-1; j++)
        if( A[j] > A[j+1])
            swap(A, j, j+1);

參考
[C++] 氣泡排序法(Bubble sort)

Quick sort

畫sort過程必考，看講義316說明和範例很容易懂

Unstable
Space complexity:
$O (n)$
Time complexity:
- Worst:
  $O (n^{2})$
- Avg:
  $O (n \log n)$




















int Partition(int *arr, int front, int end){
    int pivot = arr[end];
    int i = front -1;
    for (int j = front; j < end; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    i++;
    swap(&arr[i], &arr[end]);
    return i;
}
void QuickSort(int *arr, int front, int end){
    if (front < end) {
        int pivot = Partition(arr, front, end);
        QuickSort(arr, front, pivot - 1);
        QuickSort(arr, pivot + 1, end);
    }
}

參考
Comparison Sort: Quick Sort(快速排序法)

Merge sort

合併過程必考，講義322,324分別為兩種(Iterative/Recursive)合併方法

stable
Space complexity:
$O (n)$
Time complexity:
- Worst:
  $O (n \log n)$
- Avg:
  $O (n \log n)$



































void Merge(std::vector<int> &Array, int front, int mid, int end){

    // 利用 std::vector 的constructor, 
    // 把array[front]~array[mid]放進 LeftSub[]
    // 把array[mid+1]~array[end]放進 RightSub[]
    std::vector<int> LeftSub(Array.begin()+front, Array.begin()+mid+1),
                     RightSub(Array.begin()+mid+1, Array.begin()+end+1);

    LeftSub.insert(LeftSub.end(), Max);  // 在LeftSub尾端加入Max元素(sentinel)
    RightSub.insert(RightSub.end(), Max);// 在RightSub尾端加入Max元素(sentinel)

    int idxLeft = 0, idxRight = 0;

    for (int i = front; i <= end; i++) {

        if (LeftSub[idxLeft] <= RightSub[idxRight] ) {
            Array[i] = LeftSub[idxLeft];
            idxLeft++;
        }
        else{
            Array[i] = RightSub[idxRight];
            idxRight++;
        }
    }
}

void MergeSort(std::vector<int> &array, int front, int end){
                                         // front與end為矩陣範圍
    if (front < end) {                   // 表示目前的矩陣範圍是有效的
        int mid = (front+end)/2;         // mid即是將矩陣對半分的index
        MergeSort(array, front, mid);    // 繼續divide矩陣的前半段subarray
        MergeSort(array, mid+1, end);    // 繼續divide矩陣的後半段subarray
        Merge(array, front, mid, end);   // 將兩個subarray做比較, 並合併出排序後的矩陣
    }
}

參考
Comparison Sort: Merge Sort(合併排序法)

Heap sort

最重要的是了解抽走max/min後怎麼把樹重新Heapify，下面連結講的很清楚
尚未建成max-heap前，到建成第一個max-heap的過程也要會(參考講義)
特別注意：在同一個subtree裡，leftchild(index(2i))與rightchild(index(2i+1))的「數值」大小順序不重要，只要和root(index(i))比較即可。

Unstable
Space complexity:
$O (1)$
Time complexity:
- Worst:
  $O (n \log n)$
- Avg:
  $O (n \log n)$


// Code超複雜 跳過 ^_^

參考
Comparison Sort: Heap Sort(堆積排序法)

Bucket sort

mega筆記 ch5.Tree說bucket sort為Radix sort的MSD版
Rusk algorithm club說bucket sort是先裝入桶子在用insertion sort排序
- ex: 1~100, 101~200…901~1000 假設共r=10桶
- 數字如果平均分散在這個範圍內，每個桶只會有n/10筆資料
- 每個桶用insertion sort，這邊需假設資料小到能
  $O (n / r)$ 時間完成
- 把資料串回來，需要
Space complexity:
$O (n \times r)$
Time complexity:
- Worst:
  $O (n^{2})$ 當所有人擠同一個桶子
- Avg:
  $O (n + r)$
- d: max number digit / r: buckets

Radix sort

主要有MSD/LSD兩種，差別在從最大or最小的digit開始分類
- 講義p.330有分類過程，務必看過
  桶子是FIFO
MSD: unstable, LSD: stable
Space complexity:
$O (n \times r)$
Time complexity:
- Worst:
  $O (d \times (n + r))$
- Avg:
  $O (d \times (n + r))$
- d: max number digit / r: buckets


// 我賭不會考 考了應該也憑感覺寫得出來吧(記得桶子用Queue做!!!)

參考

線性排序比較 Radix sort / bucket sort / counting sort

Hashing

名詞解釋
- bucket
  - 分成幾個單位(ex. mod 5就是5個bucket)
- slot
  - 每單位可放幾個record
- load density (factor)
  - n=放入hash的變數各數
  - sb=hash table的容量大小
  - $α = \frac{n}{s b}$ ，可以視為平均一個bucket中有幾個人
- collision
  - 兩個不同字進到同個桶中
- overflow
  - collision且桶子滿了(no more slots)
- perfect hashing
  - 保證不會有collision發生的hashing function
overflow handing
- Linear probing
  - 一個bucket滿了，去下一個bucket放
- Quadratic probing
  - 如果經過h(x)算出的位置滿了，重算公式如下
  - $h (x) \pm i^{2}$ ，如果還是滿的，i++
- double hashing
  - 如果經過h(x)算出的位置滿了，重算公式如下
  - $h (x) + i * f (i)$ ，如果還是滿的，把
    $i + 1$ 再算一次
    - ex. f(i)=(7-x%7)
    - h(41)+1*f(1)=h(41)+1*(7-41%7) –->滿的話繼續往下算
    - h(41)+2*f(2)=h(41)+2*(7-41%7)
    - 以此類推

高等樹

Mega大筆記

Double-Ended priority queue

Time complexity
- Insertion:
  $O (\lg n)$
- Delete min/max:
  $O (\lg n)$
- find min/max:
  $O (\lg n)$
皆為Complete (binary) tree
以下三種都是這種queue
- Min-max heap
- Deap (Double-Ended-Heap)
- Symmetric min-max heap (SMMH)

Min-Max heap

一種Double-Ended priority queue
定義
- Complete Binary Tree
- Tree level被分為min level和max level
- 若某節點位於min(max) level，則以該點為根的子樹中，他的權重為最小(大)值。
- 第一層(root)必須為min level
完整介紹 & Insert & Delete
- 看圖弄懂流程就好，文章廢話太多了
- delete 有分delete min和delete max，略有不同
- Mega大筆記中，insert的圖示有誤，正確請參考文章

Deap (Double-Ended-Heap)

定義
- 一棵Complete Binary Tree
- root不儲存任何資料
- root的左子樹是min-heap ; 右子樹則為max-heap
- 在root左子上的任一點 i，令 j 為他在右子樹中對應的節點，i 點的權重必須小於 j 點的權重。(p.s 若無對應點則取其父點)
完整介紹 & Insert & Delete (Deap在比較下面，文章中很多廢話自行跳過)
- insert的"對應點"概念，看書很容易理解
- 其他說明都看這篇文章

SMMH (Symmetric min-max heap)

定義
是一個Complete Binary Tree，Root不存Data，滿足:
1. 左兄弟 ≤ 右兄弟 (近兄弟)
2. 節點x的祖父的左子點必須 ≤ x
3. 節點x的祖父的右子點必須 ≥ x
  對於節點i來說，i的左子點是i的子樹中的最小值(不含i)。
  對於節點i來說，i的右子點是i的子樹中的最大值(不含i)。
刪除插入文字敘述
刪除

Extended Binary Tree

External Node = Failure Node, 數量為internal node+1
E: External path length
I: Internal path length
N: Internal Node
$E = I + 2 N$
完整介紹

Minimal Weighted External path length

三種求法
- 最常見: Huffman algo
  $O (n \lg n)$
- 暴力
- DP
完整介紹

Optimal Binary search tree (OBST)

略，見algo筆記

AVL tree

高度平衡樹，
$| h_{L} - h_{R} | \leq 1$
AVL定理
- 證明在連結最下面
- Let 形成高度h的AVL Tree所需最少的節點數為
  $a_{h}$
  - $a_{h} = a_{h - 1} + a_{h - 2} + 1$
  - $a_{h} = F_{h + 2} - 1$ ，其中
    $F$ 為費式數列，這裡令h=0為root height
insert & 完整介紹: 見陳宜欣Slides
delete

B tree

B tree is a balanced m-way search tree
- 令
  $t = ⌈ \frac{m}{2} ⌉$
- 2
  $\leq$ deg(root)
  $\leq$ m
- $t \leq$ deg(node)
  $\leq m$
- 1
  $\leq$ root's key
  $\leq$ 2t-1
- t
  $\leq$ node's key
  $\leq$ 2t-1
一個m階的B樹具有如下幾個特徵：
1. 根結點至少有兩個子女。
2. 每個中間節點都包含k-1個元素和k個孩子，其中 m/2 <= k <= m
3. 每一個葉子節點都包含k-1個元素，其中 m/2 <= k <= m
4. 所有的葉子結點都位於同一層。
5. 每個節點中的元素從小到大排列，節點當中k-1個元素正好是k個孩子包含的元素的值域分劃
Insert & delete: 陳宜欣Slides session 10

2-3 tree

B tree of order 3 = 3 way B tree
內部結點degree為2 or 3
degree=child數目，一個key的node有兩個child，兩個key的node有三個child
所有外部結點位於同階層
令2-3 tree height = h，internal node = n
- $\log_{3} (n - 1) \leq h \leq \log_{2} (n - 1)$
Insertion
Delete: 看課本(也有影片，但課本講得比較好)

2-3-4 tree

B tree of order 4 = 4 way B tree
有時簡稱2-4 tree
內部結點degree為2, 3 or 4
insert還是會從最上面開始，比較大小決定往左or右放
Insert & Delete
TOP-Down & Bottom up 解法 (包含insert, delete)
刪除非常混亂，別的影片這樣講但我沒懂

B+ tree

很類似B tree，差在B+ tree leaf層才有完整資料，上面都是index，為的是降低IO次數
不是每次insert都需在non-leaf node留下自己的index，只有split後，才需要留
split可以想成依照B tree規則先把資料弄上去，再把資料往下放到右子樹的最小值

以下為交大104資演:

ans:

參考mega ch9 advance tree筆記
其他參考: hackmd
B+ tree visualization

red-black tree

五條規則
- 樹上的每個節點 (node) 只能是紅色或黑色
- 根節點 (root) 一定要是黑色
- 葉節點 (leaf) 一定要是黑色的空值 (NULL)
- 紅色節點的兩個子節點 (child) 一定要是黑色 (亦即不能有兩個紅色節點相連，注意：黑色節點的子節點顏色沒有限制)
- 從任何節點出發，其下至葉節點所有路徑的黑色節點數目要相同
2-3-4 tree to red-black tree
insert
delete
看印度人講比較快
其他資源

Union set

以下code使用union by rank with path compression



















def Make_set(x):
    x.parent=x
    x.rank=0
    
def Find_set(x):
    if x==x.parent:
        return x
    return find_set(x.parent)

def Union(x,y):
    Link(Find_set(x), Find_set(y))
    
def Link(x,y):
    if x.rank > y.rank:
        y.parent=x
    else:
        x.parent=y
        if x.rank == y.rank:
            y.rank++

說明
複雜度:
- Union:
  $O (1)$
- Find (with union by rank):
  $O (α (n)) \approx O (1)$
另外有union by height , union by size，兩者導致union & find會有
$O (\lg n)$
- ref, ref2比較詳細, ref3, ref4
參考台大102資演題目，當作練習

leftist tree

左傾樹
說明

建議自己畫左傾樹插入1~10，用下面工具比對步驟是否正確，才算完全懂
visualization

Binomial queue

影片講得不錯
 圖解

Binomial heap, Fibonacci heap

別人的筆記

圖片來源:高等樹筆記

補充

In-place algorithm (重要)
Build heap只需要
$O (n)$ 就能完成，而非
$O (n \lg n)$ !!!
- 複雜度O(n)證明: 最後一個父點所在的layer最多有n/4 nodes，他們最多會往下移動1；再上一層最多有n/8 nodes，他們最多往下移動2；… Top node最多往下移動h (ref)
merge two heap:
$O (n)$
- insert, delete都是
  $O (\lg n)$
merge two leftist tree:
$O (\lg n)$
Binary search tree如果不平衡，每次插入/查詢可達
$O (n)$

Fibonacci search, ref2 (還沒看，但感覺很厲害)

以108清大計科為例: 對1,2,3…16的sequence分別搜尋2, 10, 15所需次數

before search, construct Fn and searched sequence A[]

Fibonacci 
k : 0 1 2 3 4 5 6 7  8
Fk: 0 1 1 2 3 5 8 13 21

A[]
i   : 0 1 2 3 4 5 6 7 8  9 10 11 12 13 14 15
A[i]: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

n = last index of A[] = 15
k=8 (the kth Fibonacci number >= A[n])
offset = -1

search 2:
i = min(-1+F(8-2), 15) = min(-1+8, 15) = 7
2<A[7] --> k = 8-2 = 6
i = min(-1+F(6-2), 15) = min(-1+3, 15) = 2
2<A[2] --> k = 6-2 = 4
i = min(-1+F(4-2), 15) = min(-1+1, 15) = 0
A[0]<2 --> k = 4-1 = 3, offset = i = 0
i = min(0+F(3-2), 15) = min(0+1, 15) = 1
A[1]=2 , Find!

search 10:
i = min(-1+8, 15) = 7
A[7]<10 --> k = 8-1 = 7, offset = 7
i = min(7+5, 15) = 12
10<A[12] --> k =7-2 = 5
i = min(7+2,15) = 9
A[9]=10, Find!

search 15:
i = min(-1+8, 15) = 7
A[7]<15 --> k = 8-1 = 7, offset = 7
i = min(7+5, 15) = 12
A[12]<15 --> k = 7-1=6, offset = 12
i = min(12+3, 15) = 15
15<A[15] --> k = 6-2 =4
i = min(12+1, 15) = 13
A[13]<15 --> k = 4-1 = 3, offset = 13
i = min(13+1, 15) = 14
A[14] = 15, Find!