---
# System prepended metadata

title: '==研究所 資料結構=='

---

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

![image](https://hackmd.io/_uploads/BkXyvITU1g.png)
![image](https://hackmd.io/_uploads/Hy24Cbiukx.png)

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

![image](https://hackmd.io/_uploads/HJnvM3LI1g.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)
## ==DFS、BFS==
![image](https://hackmd.io/_uploads/rJeiAx5vkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
## ==操作heap需要的時間==
![image](https://hackmd.io/_uploads/r1K3zQ4Uyx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
## ==遞迴時間複雜度==

![image](https://hackmd.io/_uploads/BJQ4LIp8Jl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

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

![image](https://hackmd.io/_uploads/H1ueV7bUke.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
## ==sort整理==
![image](https://hackmd.io/_uploads/Hk2-RA38Jx.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

## ==insert in double link list==
:::info
要改四個pointer
:::
![image](https://hackmd.io/_uploads/ByitJLaLkl.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

![image](https://hackmd.io/_uploads/B107xIaUkx.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)
## ==DP==
![image](https://hackmd.io/_uploads/SJvYYH6vJx.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

![image](https://hackmd.io/_uploads/B1QctS6Dkx.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

![image](https://hackmd.io/_uploads/ryTqFBaPyg.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

![image](https://hackmd.io/_uploads/H1FIirRDkx.png)
![image](https://hackmd.io/_uploads/BJ_ptyKIyg.png)

![image](https://hackmd.io/_uploads/BkbDjSAw1e.png)
![image](https://hackmd.io/_uploads/BJ_ptyKIyg.png)

![image](https://hackmd.io/_uploads/ryqwsB0Dyx.png)
![image](https://hackmd.io/_uploads/BJ_ptyKIyg.png)

![image](https://hackmd.io/_uploads/SJzdsSCD1l.png)
![image](https://hackmd.io/_uploads/BJ_ptyKIyg.png)
## ==Binomial Heap==
https://hackmd.io/tCv57gtkQJGQxGM3TMo5aA?view
![image](https://hackmd.io/_uploads/BJ_ptyKIyg.png)

## fib heap==
https://hackmd.io/@wuboya/B1xRTOC24
![image](https://hackmd.io/_uploads/BJ_ptyKIyg.png)

## ==search==
### ==linear search==
![image](https://hackmd.io/_uploads/SJVutpnIyl.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

### ==binary search==
![image](https://hackmd.io/_uploads/H1hqtTnU1g.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

![image](https://hackmd.io/_uploads/Bkv75T2LJx.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)



## ==reduce==
![image](https://hackmd.io/_uploads/ryt7bxuP1e.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

![image](https://hackmd.io/_uploads/SJJ8-g_vyl.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

## ==P 、 NP 、 NP complete 、 NP hard==
![image](https://hackmd.io/_uploads/Syfcbl_v1e.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)


![image](https://hackmd.io/_uploads/SkfNyxdvkx.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

![image](https://hackmd.io/_uploads/SJhNlgOwyg.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

![image](https://hackmd.io/_uploads/HkNvQeuvkx.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

![image](https://hackmd.io/_uploads/B14gfluvyx.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

![image](https://hackmd.io/_uploads/HyVVGl_wkg.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)



## ==KMP==
![image](https://hackmd.io/_uploads/B1JQMcLvJg.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

![image](https://hackmd.io/_uploads/r1KNfqUPJl.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)


## ==dfs相關函數==
![image](https://hackmd.io/_uploads/S1zQoH0vye.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

## ==dfn==
![image](https://hackmd.io/_uploads/HJO39rCPJl.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)
## ==low==

![image](https://hackmd.io/_uploads/Sk_A5HCw1e.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)



## ==各種遞迴方法特性==
![image](https://hackmd.io/_uploads/HJnIqzIIyl.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)


## ==array、linklist、AVL tree時間複雜度比較==
![image](https://hackmd.io/_uploads/HJT883bSkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/B1Va8hZHyg.png)
![image](https://hackmd.io/_uploads/S1u0InbrJg.png)
![image](https://hackmd.io/_uploads/r151v3ZBJl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rJuanGILJg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/HyE1pGL81l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

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

![image](https://hackmd.io/_uploads/B1JBpGLUyl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/r1Vo7mE8ye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rkDlVmNI1e.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
:::success
space complexity O(V^2)
:::
![image](https://hackmd.io/_uploads/HyJHrmE8kl.png)
:::success
space complexity O(e)
:::
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rk1rPQVU1e.png)
:::success
space complexity O(e)
:::
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/S1O-vQNIyg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/Bka8DXV81g.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==集合==
:::info
1. 同一棵樹是一個集合
2. 以root作為集合代表
:::
![image](https://hackmd.io/_uploads/HJ-Y7btDyl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BJTvQ-FDJg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/B17p7-KPkx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/SJHPEbFwye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==遞迴==

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

![image](https://hackmd.io/_uploads/S1W04Nb8kg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

### ==gcd==
![image](https://hackmd.io/_uploads/Bk-9NVbIyg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==盒內塔 O(n^2)==
![image](https://hackmd.io/_uploads/rJTwXEZ8kg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

### ==排列==
![image](https://hackmd.io/_uploads/HkEAWEW81g.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)


## ==dijkstra==
![image](https://hackmd.io/_uploads/SkIR8XWU1x.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
## ==bellman ford==
![image](https://hackmd.io/_uploads/Skf7PQZUJl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
![image](https://hackmd.io/_uploads/Hkg4vmZLJg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
## ==floyd warshall==
:::danger
A^k[i,j] = 利用上個矩陣，有經過點k的和沒經過點k的路取小值
:::
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
![image](https://hackmd.io/_uploads/SyMicQbUJx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
![image](https://hackmd.io/_uploads/r1MD5mWIyg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
## ==hash==
## ==identifier density、load density==
identifier density => 已在表中識別字佔所有識別字的比例
load density => 已在表中識別字佔的hash table size的比例
![image](https://hackmd.io/_uploads/SybfgmbIke.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
## ==hash function design==


![image](https://hackmd.io/_uploads/Syuyuf-81g.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
### ==middle square==

![image](https://hackmd.io/_uploads/rkCNuzbUye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

### ==division==

![image](https://hackmd.io/_uploads/BJeDufZUkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
### ==floding addition==

![image](https://hackmd.io/_uploads/HJ5t_Mb8Je.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
### ==digital analysis==

![image](https://hackmd.io/_uploads/rkYjuGWIJx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

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

:::danger
1. 碰撞不一定會overflow
2. 用chain的話，可以用來做sort
:::
![image](https://hackmd.io/_uploads/ByuuYRx8kg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

### ==linear probing==

![image](https://hackmd.io/_uploads/ByvTFAlIkl.png)
:::info
有人了就往下一個放
:::
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
![image](https://hackmd.io/_uploads/B1sH90gL1l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
### ==quadratic probing==

![image](https://hackmd.io/_uploads/S1ePqRx81x.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
:::info
先找(H(X)+i^2)%B 在找 (H(X)-i^2)%B
![image](https://hackmd.io/_uploads/SybW6Rg8Jl.png)

:::
![image](https://hackmd.io/_uploads/BJ995Cx81l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

### ==double hashing==

![image](https://hackmd.io/_uploads/r1BHiRgU1l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/SyULs0xU1e.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
### ==chain 、close address mode、open address mode==
![image](https://hackmd.io/_uploads/SJT9jAlL1g.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
### ==rehashing==

![image](https://hackmd.io/_uploads/S1Q0Iz-Iye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==thread binary tree==
![image](https://hackmd.io/_uploads/B1aQno9ryx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/Hy_V3jcHyl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BJNrRi5Bke.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/SJMERjcSyl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)



## ==多像式儲存方法==
![image](https://hackmd.io/_uploads/r1h0e6QVJe.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/HyLZ-67V1e.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/r1vv-6m4ke.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/H1tvGaQNJx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/Bk2_fa74kl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==反轉linklist==
![image](https://hackmd.io/_uploads/SJ6YQpQ4Jl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==合法的stack輸出==
:::danger
只看往下的
例如:13524
    5->2間少了3不符合
:::
![image](https://hackmd.io/_uploads/rktB3cLVJe.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
## ==DFS、BFS==
![image](https://hackmd.io/_uploads/rJeiAx5vkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

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

BFS 1. 用queue 2. O(V+E)
:::
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
![image](https://hackmd.io/_uploads/Bk3qgjqrkg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BycsljqSyl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)


## ==合法的stack個數==
![image](https://hackmd.io/_uploads/r19x69U4kl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BJOWaqINke.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BkUzacLV1g.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==stack計算後續式==
:::danger
1. 後續式用看的
    如**遇到運算子**取**前兩個運算元**作計算
2. 前續式用看的
    如連續**遇到兩個運算元**取**前面的運算子**作計算
:::
![image](https://hackmd.io/_uploads/B1nfy0IVyl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==infex轉postfix==
:::danger
     >  : PUSH()
     <= : pop()
:::
![image](https://hackmd.io/_uploads/rJHAzRLNye.png)
![image](https://hackmd.io/_uploads/Sy8k7R84Je.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/Hk1-mCLVJx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/HkhW7CLEye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)


## ==Puffman code、Optimal  tree==
:::danger
* 具有最小加權的tree 稱做 Optimal  tree
* 用 puffman 求 Optimal  tree
:::
![image](https://hackmd.io/_uploads/SynpQhZH1l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/r1ll4nZryg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)


## ==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

:::

![image](https://hackmd.io/_uploads/BJjBdp9Eye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)



## ==AOV==
:::danger
拓樸排序
:::
![image](https://hackmd.io/_uploads/BJWxTaqNye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==AOE==
![image](https://hackmd.io/_uploads/rJgFjM-8kg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/r1XuiGWUkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/S1p1nzWIye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/Syqe3zZIkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/SkW7TMZLkg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/Hk0d4QLLyg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/HkPWwKG_Jl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==event最早最晚開始時間==
用點找
![image](https://hackmd.io/_uploads/H1kEpM-IJe.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==activity最早最晚開始時間==
用邊找
![image](https://hackmd.io/_uploads/SJwv6z-81l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)



## ==n0=n2+1==

![image](https://hackmd.io/_uploads/BkHsnQpVkx.png)
![image](https://hackmd.io/_uploads/BkJnTQpE1x.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

# ==advance tree==
## ==double ended priority queue==
:::danger
* min-max=小大小大
* Deap=左小右大
* SMMH=左右夾起來
:::
![image](https://hackmd.io/_uploads/B1sT2ibryg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==Deap==
:::danger
* 可插入
* 刪除最大或最小元素
* insert O(logn)
* delete O(logn)
:::
![image](https://hackmd.io/_uploads/rkfUmOWrJl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
## ==insert Deap==
:::danger
1. 放到最後一個node
2. 和他的夥伴比較，小的放 min heap，大的放 max heap
3. 分別調整min heap、 max heap
:::
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
![image](https://hackmd.io/_uploads/SygrFBzLkg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==Deap delete min==
:::danger
1. 把min元素移出，留下空位
2. min heap做調整
3. 條整後空位由last element插入
4. 和他的夥伴比較，小的放 min heap，大的放 max heap
5. 分別調整min heap、 max heap
:::
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
![image](https://hackmd.io/_uploads/rJlSqHz81g.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

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

* insert O(logn)
* delete O(logn)
:::
![image](https://hackmd.io/_uploads/SJrzPiZSJl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/SyS2PoWHke.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==insert number in min max heap==
:::danger
1. 先和父親比，看父親在min層還是max層選擇是否和孩子交換
2. 之後隔代比較進行調整
:::
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==delete min number in min max heap==
:::danger
1. 拿走最小值
2. 最後一個node放到root
3. 慢慢往下調整成min max heap
:::
![image](https://hackmd.io/_uploads/H10z2oWBkx.png)

![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==SMMH==
![image](https://hackmd.io/_uploads/rkqgkh-Bye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
![image](https://hackmd.io/_uploads/SJXuHEFryl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==insert number in SMMH==
:::danger
1. 放到最後的node
2. 慢慢調整成SMMH
:::
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
![image](https://hackmd.io/_uploads/ryEsjBG8kl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

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

:::
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/HJqYsBGL1l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==extended binary tree==

![image](https://hackmd.io/_uploads/B1L3l2-Ske.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

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

![image](https://hackmd.io/_uploads/By4hbnZHJl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)


## ==m-way search tree==

![image](https://hackmd.io/_uploads/SksJopbB1l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==B tree==
:::danger
* 是平衡的
* 2-3 tree是degree只有 2 or 3的B tree
:::
![image](https://hackmd.io/_uploads/SJwvja-Hye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/B1-XhT-HJl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==insert B tree==
:::danger
一路往上檢查有無overflow
有的話斷裂
:::
![image](https://hackmd.io/_uploads/Sky3ha-rJx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BJquh6brye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

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

![image](https://hackmd.io/_uploads/HkfogAZHJl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
## ==delete B tree 要刪的node***不在 leaf***==
:::danger
要刪的node***不在 leaf***
1. 刪除該node
2. 把右子樹的最大值or左子樹的最小值換上去
3. 等於換上去的地方的leaf被刪除了
4. 做delete B tree 要刪的node在 leaf
:::
![image](https://hackmd.io/_uploads/SyrN7RZS1g.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==insert delete B tree讀幾次disk==
![image](https://hackmd.io/_uploads/BkVUVAZS1x.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/S1DXNCZS1g.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==red black tree==

![image](https://hackmd.io/_uploads/HJz1-vfBJg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==平衡的tree==
![image](https://hackmd.io/_uploads/S1oZWvGS1x.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==insert red black tree==
![image](https://hackmd.io/_uploads/B1EnAtFL1g.png)

:::danger
1. root定為黑
1. 要插的點為紅色
2. rotation做平衡加上顏色設定
3. 有做過rotation的如果要insert要做顏色轉換 r->b b->r
:::
![image](https://hackmd.io/_uploads/r18UQDGHke.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rk9O7Dzrkg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rJ7YNvzryx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==OBST==
![image](https://hackmd.io/_uploads/BJRqrPGSJx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==OBST搜尋成本==
![image](https://hackmd.io/_uploads/Hk92rDzB1x.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rJA1LwGryg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==求OBST==
:::danger
1. 公式
:::
![image](https://hackmd.io/_uploads/B1n2_DfH1l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
![image](https://hackmd.io/_uploads/By6CtPMS1e.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
![image](https://hackmd.io/_uploads/ryUbcwzHke.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

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

![image](https://hackmd.io/_uploads/B1CGFDGBJe.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

w01 3個相加
![image](https://hackmd.io/_uploads/H1fZowzByg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

w02 5個相加
![image](https://hackmd.io/_uploads/SJxEoDGH1e.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

以此類推

:::danger
3. 公式求c(i,j)， r(i,j)
:::
![image](https://hackmd.io/_uploads/B17jiDzHyx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BJ1_oPfS1x.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/HyM6iPGr1e.png)
![image](https://hackmd.io/_uploads/B1e0iwfHJx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

:::danger
4. 畫出OBST 要查a3 a4的OBST要看c(2,4)的root
:::
![image](https://hackmd.io/_uploads/HyfZkdMHyx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rkHcCvGr1g.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)



# ==sort==
## ==sort整理==
![image](https://hackmd.io/_uploads/Hk2-RA38Jx.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)

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

![image](https://hackmd.io/_uploads/Bkd603Dw1g.png)
![image](https://hackmd.io/_uploads/r1u_kizVke.png)


## ==radix sort、bucket sort==
:::info
1. stable
2. LSD radix sort == radix sort
3. MSD radix sort == bucket sort
:::
![image](https://hackmd.io/_uploads/Byupe6vD1x.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/r1u_kizVke.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==LSD radix sort == radix sort==
:::info
1. 從最低位數開始
2. 要做多次的分派和合併
:::
![image](https://hackmd.io/_uploads/HJyfZaPDkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BypOW6wPyl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rJRYWpDPyl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BkMnb6wPJl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==MSD radix sort == bucket sort==
:::info
1. 從最高位數開始
2. 只要做1次的分派和合併
3. 因為每個 bucket內會自己排序
:::
![image](https://hackmd.io/_uploads/Bk5OGpwPJe.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BJhFGTwv1g.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rkvqGTDw1l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)



## ==counting sort==
:::info
1. stable
:::
![image](https://hackmd.io/_uploads/BJ85BTvD1l.png)

![image](https://hackmd.io/_uploads/BkwsH6wv1e.png)
![image](https://hackmd.io/_uploads/Skg6BTDvyl.png)


## ==quick sort==

:::info
1. unstable
2. Best O(nlogn) => 恰好分兩半
2. ***avg O(nlogn)***
4. worst O(n^2) => pk恰好是min 或max造成分割無效果(已經排好續的也是)
:::
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
![image](https://hackmd.io/_uploads/ryTRunDDyx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

:::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)

:::
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)


![image](https://hackmd.io/_uploads/SJ8MmhcHkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/SkhkrncBye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/HydSS3qS1e.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)


![image](https://hackmd.io/_uploads/rJ0OB35Hkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/ByRpBh5Byx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)


## ==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)
:::
![image](https://hackmd.io/_uploads/S1u8ewrvJl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/SyrdxvBDJg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/SkrtgvSPkx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/Hy15ePHDye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==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
:::
![image](https://hackmd.io/_uploads/SySijnDPkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/ryj2snDvkg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rJyDhnDvkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/ByQZA3vPyl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/S1rai3wvke.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/S1xAs3vPkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/SJ80shwD1e.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BksGn3vD1x.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BkY43nww1l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)


## ==insertion sort==
:::info
1. **stable**
2. best O(n)
3. worst O(n^2)
4. 初等排序space都是O(1)
:::
![image](https://hackmd.io/_uploads/HysnijPDkx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/S1WkhivP1g.png)
![image](https://hackmd.io/_uploads/SyAk2oPD1l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)


![image](https://hackmd.io/_uploads/Hksm2jPwyg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rkpOTswPyx.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

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

![image](https://hackmd.io/_uploads/HyZeTovwye.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rJQYEnDw1l.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/HkdEaswv1x.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==bubble sort==
:::info
1. stable
2. best O(n)
3. worst avg O(n^2)
:::
![image](https://hackmd.io/_uploads/BktMkhPDyl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/rkrOJnvDkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/ryboynvDyl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/r1U3J2DDJl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

## ==shell sort==
:::info
1. unstable
2. worst avg : O(n^2)
:::
![image](https://hackmd.io/_uploads/BJc5BhwvJg.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/BJkIInDD1g.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/SJ3KL2ww1x.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)

![image](https://hackmd.io/_uploads/B1xoU3vwkl.png)
![image](https://hackmd.io/_uploads/r1pbZaQNkg.png)
