# ==研究所 資料結構==


## ==各種資料結構比較==

## ==DFS、BFS==
## ==操作heap需要的時間==
## ==遞迴時間複雜度==


## ==dijkstra O(V^2)、bellman ford O(V^3)、floyd warshall O(V^3)==

## ==sort整理==

## ==insert in double link list==
:::info
要改四個pointer
:::

## ==DP==






## ==Binomial Heap==
https://hackmd.io/tCv57gtkQJGQxGM3TMo5aA?view

## fib heap==
https://hackmd.io/@wuboya/B1xRTOC24

## ==search==
### ==linear search==

### ==binary search==


## ==reduce==


## ==P 、 NP 、 NP complete 、 NP hard==






## ==KMP==


## ==dfs相關函數==

## ==dfn==
## ==low==


## ==各種遞迴方法特性==

## ==array、linklist、AVL tree時間複雜度比較==




## ==圖形的資料結構表示方式==



:::success
space complexity O(V^2)
:::
:::success
space complexity O(e)
:::

:::success
space complexity O(e)
:::



## ==集合==
:::info
1. 同一棵樹是一個集合
2. 以root作為集合代表
:::




## ==遞迴==

### ==C(m,n)==


### ==gcd==

## ==盒內塔 O(n^2)==

### ==排列==

## ==dijkstra==
## ==bellman ford==
## ==floyd warshall==
:::danger
A^k[i,j] = 利用上個矩陣，有經過點k的和沒經過點k的路取小值
:::
## ==hash==
## ==identifier density、load density==
identifier density => 已在表中識別字佔所有識別字的比例
load density => 已在表中識別字佔的hash table size的比例
## ==hash function design==

### ==middle square==


### ==division==

### ==floding addition==

### ==digital analysis==


## ==overflow的處理方法==

:::danger
1. 碰撞不一定會overflow
2. 用chain的話，可以用來做sort
:::

### ==linear probing==

:::info
有人了就往下一個放
:::
### ==quadratic probing==

:::info
先找(H(X)+i^2)%B 在找 (H(X)-i^2)%B

:::

### ==double hashing==


### ==chain 、close address mode、open address mode==
### ==rehashing==


## ==thread binary tree==




## ==多像式儲存方法==





## ==反轉linklist==

## ==合法的stack輸出==
:::danger
只看往下的
例如:13524
5->2間少了3不符合
:::
## ==DFS、BFS==

:::danger
DFS 1. 用stack 2. O(V+E)

BFS 1. 用queue 2. O(V+E)
:::


## ==合法的stack個數==



## ==stack計算後續式==
:::danger
1. 後續式用看的
如**遇到運算子**取**前兩個運算元**作計算
2. 前續式用看的
如連續**遇到兩個運算元**取**前面的運算子**作計算
:::

## ==infex轉postfix==
:::danger
> : PUSH()
<= : pop()
:::



## ==Puffman code、Optimal tree==
:::danger
* 具有最小加權的tree 稱做 Optimal tree
* 用 puffman 求 Optimal tree
:::


## ==Binary search tree==
:::danger
* 用 inorder 追蹤可以獲得從小到大的排序
:::

## ==AVL tree==
:::danger
* 一種Binary search tree加上平衡

* **刪除node => O(logn)**
* **插入node => O(logn)**

* **深度h**的AVL tree需要的**最少節點數** => F(h+2)-1
* **深度h**的AVL tree需要的**最多節點數** => (2^h)-1

:::


## ==AOV==
:::danger
拓樸排序
:::

## ==AOE==







## ==event最早最晚開始時間==
用點找

## ==activity最早最晚開始時間==
用邊找

## ==n0=n2+1==


# ==advance tree==
## ==double ended priority queue==
:::danger
* min-max=小大小大
* Deap=左小右大
* SMMH=左右夾起來
:::

## ==Deap==
:::danger
* 可插入
* 刪除最大或最小元素
* insert O(logn)
* delete O(logn)
:::
## ==insert Deap==
:::danger
1. 放到最後一個node
2. 和他的夥伴比較，小的放 min heap，大的放 max heap
3. 分別調整min heap、 max heap
:::

## ==Deap delete min==
:::danger
1. 把min元素移出，留下空位
2. min heap做調整
3. 條整後空位由last element插入
4. 和他的夥伴比較，小的放 min heap，大的放 max heap
5. 分別調整min heap、 max heap
:::

## ==min max heap==
:::danger

* insert O(logn)
* delete O(logn)
:::


## ==insert number in min max heap==
:::danger
1. 先和父親比，看父親在min層還是max層選擇是否和孩子交換
2. 之後隔代比較進行調整
:::

## ==delete min number in min max heap==
:::danger
1. 拿走最小值
2. 最後一個node放到root
3. 慢慢往下調整成min max heap
:::


## ==SMMH==

## ==insert number in SMMH==
:::danger
1. 放到最後的node
2. 慢慢調整成SMMH
:::

## ==delete number in SMMH==
:::danger
1. 拿走最小值 設為E
3. 慢慢調整成SMMH
2. 最後一個node放到E

:::


## ==extended binary tree==


## ==E = I + 2n==


## ==m-way search tree==


## ==B tree==
:::danger
* 是平衡的
* 2-3 tree是degree只有 2 or 3的B tree
:::


## ==insert B tree==
:::danger
一路往上檢查有無overflow
有的話斷裂
:::


## ==delete B tree 要刪的node**在 leaf**==
:::danger
要刪的node在 leaf
1. 檢查有無underflow 沒有的話直接刪
2. 有underflow => 用rotation => 不能rotation用combine
:::

## ==delete B tree 要刪的node***不在 leaf***==
:::danger
要刪的node***不在 leaf***
1. 刪除該node
2. 把右子樹的最大值or左子樹的最小值換上去
3. 等於換上去的地方的leaf被刪除了
4. 做delete B tree 要刪的node在 leaf
:::

## ==insert delete B tree讀幾次disk==


## ==red black tree==


## ==平衡的tree==

## ==insert red black tree==

:::danger
1. root定為黑
1. 要插的點為紅色
2. rotation做平衡加上顏色設定
3. 有做過rotation的如果要insert要做顏色轉換 r->b b->r
:::



## ==OBST==

## ==OBST搜尋成本==


## ==求OBST==
:::danger
1. 公式
:::

:::danger
2. 求w(i,j)
第一列 w00 w11 w22 w33 w44 會等於每個外部node加權值
:::


w01 3個相加

w02 5個相加

以此類推

:::danger
3. 公式求c(i,j)， r(i,j)
:::



:::danger
4. 畫出OBST 要查a3 a4的OBST要看c(2,4)的root
:::


# ==sort==
## ==sort整理==

## ==linear time sorting method==
:::info
1. 不是用 comparison base 的，有機會到 O(1)
:::


## ==radix sort、bucket sort==
:::info
1. stable
2. LSD radix sort == radix sort
3. MSD radix sort == bucket sort
:::


## ==LSD radix sort == radix sort==
:::info
1. 從最低位數開始
2. 要做多次的分派和合併
:::




## ==MSD radix sort == bucket sort==
:::info
1. 從最高位數開始
2. 只要做1次的分派和合併
3. 因為每個 bucket內會自己排序
:::



## ==counting sort==
:::info
1. stable
:::


## ==quick sort==

:::info
1. unstable
2. Best O(nlogn) => 恰好分兩半
2. ***avg O(nlogn)***
4. worst O(n^2) => pk恰好是min 或max造成分割無效果(已經排好續的也是)
:::

:::danger
pass 1
1. 最左當pivot
2. i 從左往右找>=的
3. j 從右往左找<=的
4. i j 交換
5. 重複直到 i j 交會
6. 把pivot和j的位置互換
7. 此時 pivot的左邊都是<=他的
8. 右邊都是 >= 他的

遞迴
quicksort(list,left,j-1)
quicksort(list,j+1,right)

:::






## ==heap sort==
:::info
1. unstable
2. best/avg/worst 都是 O(nlogn)
3. asymptotically optimal => 漸進最佳 => 在 worst case 是 O(nlogn) 的
4. asymptotically optimal 只有 merge sort 和 heap sort
5. 空間複雜度和初等排序一樣，都是O(1)
:::




## ==merge sort==
:::info
1. stable
2. best/avg/worst 都是 O(nlogn)
3. asymptotically optimal => 漸進最佳 => 在 worst case 是 O(nlogn) 的
4. asymptotically optimal 只有 merge sort 和 heap sort
:::









## ==insertion sort==
:::info
1. **stable**
2. best O(n)
3. worst O(n^2)
4. 初等排序space都是O(1)
:::




## ==selection sort==
:::info
1. unstable
2. best、worst、avg都是O(n^2)
3. 初等排序space都是O(1)
:::




## ==bubble sort==
:::info
1. stable
2. best O(n)
3. worst avg O(n^2)
:::




## ==shell sort==
:::info
1. unstable
2. worst avg : O(n^2)
:::