# DS2 單元1-5筆記
written by <`彭妍嘉 11227130`>
## 單元一 Priority Queue
:::spoiler Why? 為什麼平衡能提升效率？
維持平衡能有效降低樹的高度，進而提升像是 Insert 或 Delete 等操作的效率。
* 一般而言，這些操作的 Time Complexity 取決於「樹的高度」。
* 若樹不平衡，最壞情況下可能退化成類似 Linked List 的線性結構，導致插入、刪除、搜尋等操作都可能降至 $O(n)$。
:::
### 前置複習 Binary Tree 的背景知識
---
<div style="float: left; margin-right: 10px;">
<img src="https://hackmd.io/_uploads/B1ZNtN9cke.png" alt="Description" width="200" />
</div>
**Balanced Tree**
任何一個 node 的左子樹和右子樹高度差不超過1
**Complete Tree**
node 由上至下，左至右填滿，不可跳空。
**Full Binary Tree**
每個 node 要嘛沒有 children，要嘛就有 2 個 children，不會只有 1 個。 （不是全滿就全空）
### Heap 堆積
---
### **Heap 的種類**
* Min Heap
* Max Heap
### **Heap 的特性**
1. 屬於 Complete Tree，==由上而下，由左至右插入節點==。
:::info
好處：Complete 的特性可使資料更緊密。
:::
2. 每一條由根節點(Root)~葉節點(Leaf)的路徑滿足 Sorted List 的條件。（==每一根稻草都是排序的==）
:::info
像是 Min Heap 越上層的 Key 會越小；反之 Max Heap 則越上層越大。所以樹根不是最小就是最大。 :mega:
:::
### **如何建構與維護 Heap？**
---
**Insert （新增節點）** $O(\log n)$
主要分成兩個動作：
1. 將資料新增在 bottom 的位置 => 仍然符合 Complete Tree 的性質。
2. 呼叫 ReHeapUp 函式 => 使葉節點到根節點的路徑仍是排序的。
**Delete （刪除節點）** $O(\log n)$
通常是指移除根節點，像是在 Max Heap 中刪除 Priority 最高的根節點。而在實作層面，我們不會真的去「刪除」根節點，而是選擇把最後一個節點的資料「複製」到根節點，再去移除最後一個節點，這樣做的好處主要有兩個：
1. 維持 Complete Tree 的性質。
2. 提升效率。
以陣列實作的會話，最後一個元素剛好就位於陣列的尾端，用它來替換根節點可以提升「刪除」這個動作的效率，而不用重建整個樹的結構，只需要呼叫 ReHeapDown 這樣的函式去維持排序的性質就好。
因此可以歸結在實作 Heap 時，刪除節點主要分成三個動作：
1. 用最後一個元素替換根節點： Copy the bottom rightmost element to the root。
2. 刪除最後一個元素： Delete the bottom rightmost node。此時是semi-heap。
3. 恢復 Heap 的性質：呼叫 ReHeapDown。
另外，除了刪除根節點，有些狀況下我們也會需要去刪除內部節點，因此我們仍然需要去思考如何有效的維持整個 Heap 的結構，並達到刪除的動作。
### Heap 的實作
---
* `heapIsEmpty()`:
* `heapInsert(heapItemType& newItem)`:
* `heapDelete(heapItemType& rootItem)`:
* `heapReBilid(int root)`: 簡單來說就是==把 semi-heap => heap==，在這裡是將樹根的位置傳入函式。
* `heapItemType items[MaxHeap]`: 以陣列實作會是最簡單的。
* `size`: 紀錄資料筆數。
* `bottom`：==用來記錄下一個要新增資料的位置==。以 array 實作的話，bottom 的 index 剛好是資料量 (array size)。
:::success
semi-heap 是什麼？
:::spoiler
==除了 root ，左右子樹本身已符合 Heap 的結構==。因此需要 heapRebuild 來恢復整體的 Heap 性質。
:::
:::success
為什麼從最後一個內部節點往上呼叫 heapRebuild，比從根往下更好？
:::spoiler
==可以確保最大或最小值由下浮到樹根的位置==。如果由上而下去呼叫 heapRebuild 可能會無法讓最大或最小值在正確位置，又或著可能需要來來回回呼叫 heapRebuild 才能維護整個 heap 的結構。
:::
以陣列實作：
:::spoiler 課程投影片： Pseudocode of Insert, Delete and heapReBuild implementation
:::
以指標實作：
## 單元二 Variations of Heap 堆積的變形
* Doubled-ended Priority Queue
* 資料結構一： Min-max Heap
* 資料結構二： Doubled-ended Heap
* Forest (Union) of Heaps
* 資料結構一： Binomial Heap
* 資料結構二： Fibonacci Heap
### Min-max Heap 的概念
---
Min-max Heap 是一種同時能取得最大值和最小值的資料結構，常被用於實作 Doubled-ended Priority Queue。結合了 Min Heap 和 Max Heap 的特性，使我們可以在 $O(1)$ 時間內取得最大值和最小值。
**基本特性：**
* 交替層級的 min/max:
* 整棵樹依照層級(level)分成 min-level 和 max-level。
* 通常根節點視為 min-level (level 1)，它的子節點為 max-level (level 2)，再往下一層是 min-level，以此類推。
* min-level 上的節點 key 須小於或等於同層(其它祖先節點在 min-level）的值。
* max-level 上的節點 key 須大於或等於同層(其它祖先在 max-level) 的值。
* 維持 Complete Binary Tree:
* 與一般 Heap 一樣，Min-max Heap 也必須保持 Complete Binary Tree 的結構。
* 通常以 Array 實作最為方便，能直接透過索引計算 parent 和 child 的位置。
* 存取最小值與最大值:
* **最小值**：在根節點（level 1）。
* **最大值**：在根節點的子節點（level 2）。最常見的做法是檢查根節點的子節點（index = 1 與 2）來判斷哪個更大，也可能要再比對它們的孩子，但整體仍可在常數時間內找到最大值。
:::info
是可以第一層定義為 max-level 的，那結構就會稱作 Max-min Heap 而不是 Min-max Heap。
:::
:::success
如何判斷節點是在 min-level 還是 max-level？
::: spoiler
以 Min-max Heap 來說奇數層是 min-level；偶數層是 max-level。
* 取 $log$ 可以知道在哪一個 level
* 對 2 取餘數，判斷奇偶數 => 可知到底在 min-level 還是 max-level。
:::
:::success
怎麼知道現在的節點在哪一層？
:::
* search: how to find the level of the target key in binary tree?
* chatGPT 提供的做法（以 `array 實作`的話）：
看此節點的 index 是否大於「每一層中可容納的最大 index」
* 第 1 層只有 1 個節點（index = 0）。
* 第 2 層有 2 個節點（index = 1、2），因此此層的最大 index = 2。
* 第 3 層有 4 個節點（index = 3,4,5,6），此層的最大 index = 6。
* 第 4 層有 8 個節點（index = 7~14），最大 index = 14。
* 依此類推，每下一層可容納的節點數量是前一層的 2 倍。
如果 index 大於「目前層可容納的最大 index」那它可能在下一層。
``` cpp
// 回傳 array-based 結構中，index 所在的層級 (level)
// level 從 1 開始算起
int getLevelFromIndex(int index) {
if (index < 0) {
return -1; // 無效的 index
}
int level = 1; // 起始層級
int maxIndexInLevel = 0; // 第 1 層的最大 index 為 0 (只有 root)
// 若節點的 index 大於目前層可容納的最大 index，就往下一層擴充
while (index > maxIndexInLevel) {
// 下一層的節點數是目前層的 2 倍，因此
// 新的最大 index = (目前層的最大 index * 2) + 2
maxIndexInLevel = maxIndexInLevel * 2 + 2;
level++;
}
return level;
}
```
* 以 `array 實作`的話，知道 level 的另一個方法是用 index 取 $log$，讓 $level=⌊log2(index+1)⌋+1$。
``` cpp
#include <cmath>
#include <iostream>
// 計算節點所在層級
int getLevel(int index) {
return static_cast<int>(std::floor(std::log2(index + 1))) + 1;
}
// static_cast 類別轉換成 int
// std::floor() 無條件捨去或者也可以說向下取整數
```
* 以 `pointer 實作`的話，GeeksforGeeks 提供的兩種做法：
1. 遞迴寫法：
* base case： 沒找到（回傳 -1）、找到（回傳 level）
* 若還沒找到：先找左子樹，左子樹沒找到再遞迴去找右子樹。
``` cpp
// Recursive function to find the level of the target key
int getLevel(Node* root, int target, int level) {
if (root == nullptr) {
return -1;
}
// If the target key matches the current node's
// data, return the level
if (root->data == target) {
return level;
}
// Recursively call for left and right subtrees
int leftLevel = getLevel(root->left, target, level + 1);
if (leftLevel != -1) {
return leftLevel;
}
return getLevel(root->right, target, level + 1);
}
```
2. iterative 寫法 (結合 queue 去寫)：
* 酷酷的寫法，會把同一層的節點推入 queue，檢查是否符合目標 (target key)，若不符合會把小孩推到 queue 中，在下一回合逐層檢查。
* 來自 chatGPT 比較好的文字解釋：在每一層中，先處理該層所有節點，再將下一層的所有節點加入隊列，並將層級計數器加 1。一旦找到目標節點，即回傳其所在的層級；如果遍歷完所有節點仍找不到，則回傳 -1。
``` cpp
// Function to find the level of the target key
int getLevel(Node* root, int target) {
if (root == nullptr) {
return -1;
}
// Create a queue for level-order
// traversal
queue<Node*> q;
q.push(root);
int level = 1;
while (!q.empty()) {
int size = q.size();
// Process all nodes at the current level
for (int i = 0; i < size; i++) {
Node* curr = q.front();
q.pop();
// Check if the current node matches the target
if (curr->data == target) {
return level;
}
// Push the left and right children to the queue
if (curr->left != nullptr) {
q.push(curr->left);
}
if (curr->right != nullptr) {
q.push(curr->right);
}
}
level++;
}
return -1;
}
```
### Min-max Heap: Insert
---
實作流程：
1. 插入新元素於下一個可用位置
```
5 (0,min)
/ \
50 (1,max) 45 (2,max)
/ \ / \
10 (3,min) 12 (4,min) 18 (5,min) 20 (6,min)
|
2 (7, max) <-- 新插入
```
2. 判斷新節點所在的 level 是 min-level 還是 max-level
3. 與 parent 比較，決定是否要先交換
* 如果在 `min-level`：
* 若新節點的值「大於」它的 parent（parent 在 max-level），先交換。交換後，新節點跑到 max-level 的位置，接下來要以「max-level」的規則繼續 reheapUp（比較祖父節點等）。
* 若新節點的值「小於或等於」它的 parent，則不需要和 parent 交換，但還要檢查祖父節點是否也是 min-level；如果是，就做「min-level reheapUp」，確保它比同層級的祖先更小。
* 如果在 `max-level`：
* 若新節點的值「小於」它的 parent（parent 在 min-level），先交換。交換後，新節點跑到 min-level 的位置，接下來要以「min-level」的規則繼續 reheapUp。
* 若新節點的值「大於或等於」它的 parent，則不需要和 parent 交換，但還要檢查祖父節點（若是 max-level），做「max-level reheapUp」。
```
5 (0,min)
/ \
50 (1,max) 45 (2,max)
/ \ / \
2 (3,min) 12 (4,min) 18 (5,min) 20 (6,min)
|
10 (7, max)
```
（2 和 10 交換）
4. ReHeapUp（往上浮）
* 經過可能的初步交換後，==新節點會處於對應的 level（min 或 max）==。
* 這時，==依照該 level 的性質進行「ReHeapUp」==：
* 在 min-level 時，確保該節點比它的「min-level 祖先」更小（或等於）。
* 在 max-level 時，確保該節點比它的「max-level 祖先」更大（或等於）。
* 一路往上檢查，直到根節點或符合條件為止。
```
2 (0,min) <-- 2上升為根
/ \
50 (1,max) 45 (2,max)
/ \ / \
5 (3,min) 12 (4,min) 18 (5,min) 20 (6,min)
|
10 (7,max) <-- 之前被換下來的 10 就不用管了
```
::: success
如何知道祖父節點的 index？
:::spoiler
special case: index 0~2 無祖父節點
:::
::: success
如何知道孫子節點的 index？
::: spoiler
1. 子節點 index：
* 左子 = 2*i + 1
* 右子 = 2*i + 2
2. 孫節點 index：
如果我們想找節點 i 的孫節點，那就是找「i 的孩子們」的孩子：
* 節點 i 的 左子 = 2*i + 1
* 其 左子 = 2*(2*i + 1) + 1 = 4*i + 3
* 其 右子 = 2*(2*i + 1) + 2 = 4*i + 4
* 節點 i 的 右子 = 2*i + 2
* 其 左子 = 2*(2*i + 2) + 1 = 4*i + 5
* 其 右子 = 2*(2*i + 2) + 2 = 4*i + 6
:::
練習：
### Min-max Heap: Delete
---
當我們執行 Delete（無論是刪除最小值或最大值），通常會把最後一個元素移到被刪除的節點位置（維持 Complete Binary Tree），接著需要從這個位置開始「往下」檢查並修正，以恢復 Min-max Heap 的正確性。以下是刪除的兩種情況：
實作流程：
1. Delete the Smallest
* 找到最小值
* min-level 的根節點 (root) 即是整個 Heap 的最小值。
* 用最後一個元素替換根節點
* 用「最後一個葉節點」(array-based 時即陣列尾端) 來填補根節點位置，並將 Heap size 減 1。
* 執行 ReHeapDown（針對 min-level）
* 比較該節點與其較小的子節點（子節點在 max-level）。
* 如果子節點比 root 節點小，則交換兩者，讓較小的值往上移。
* 接著，針對 min-level （孫節點）去往下執行檢查，直到到達葉節點或已符合 min-level 規則為止。
2. Delete the Largest
* 找到最大值
* 通常最大值位於第二層（max-level），可直接檢查根節點的左右子節點（在 array-based 實作中，分別位於 index 1 與 2），選出其中較大的值。
* 用最後一個元素替換最大值節點
* 把 Heap 最後一個葉節點取出，放到最大值所在的位置，Heap 大小減 1。
* 執行 ReHeapDown（針對 max-level）
* 比較該節點與其較大的子節點（子節點在 min-level）。
* 如果子節點比 root 節點大，則交換兩者，讓較大的值往上移。
* 接著，針對 max-level （孫節點）去往下執行檢查，直到到達葉節點或已符合 max-level 規則為止。
::: danger
`special case`: 當今天已經換到 max-level 的最後一層，且這個最後一層 max-level 底下還有一層 min-level 的 node （葉節點）就需要特別去比較。
因為 leaf node 有可能比在 max-level 的節點還要大，故需要檢查是否要交換。
:::
::: spoiler 投影片的練習題
:::
### Double-ended Heap (DEAP) 的概念
什麼是 DEAP?
* DEAP（Double-Ended Priority Queue） 是一種特殊的**優先佇列（Priority Queue）**，同時支援：
* 快速獲取最小值（min）
* 快速獲取最大值（max）
**基本特性：**
1. 是一棵 Complete binary Tree。
2. Root 不儲存資料。
3. 左子樹是 Min Heap 右子樹是 Max Heap。
4. 若節點 i 在 min-heap 中，則其必小於等於其在 max-heap 對應點 j (i <= j)，若沒有對應的節點則取其 parent 為對應點。
**DEAP （雙向堆積）的應用**
1. **External Sort** （外部排序）（Quicksort + Heapsort + DEAP）
* 在外部排序（==External Sort==） 中，DEAP 可以幫助管理大量存儲在磁碟中的數據。
* Quicksort（快速排序） 用來切割數據（pivot selection）。
* Heapsort 幫助合併排序後的區塊。
* DEAP 負責快速找到最小值與最大值，加速合併步驟。
3. **Mergeable Priority Queue**
* 支援**合併** **merge** 操作的優先佇列，能夠有效的合併兩個工作佇列。
-> 當多個伺服器處理請求時，可動態調整工作量；或是當其中一個廚師離開，需要將他的任務佇列合併到另一個廚師。
* 主要用於負載平衡(==Load Balance==)與任務調度（Job Scheduling）。
-> 像是當某台伺服器當機時，需將該伺服器的工作佇列合併至其他伺服器。
::: success
哪些資料結構支援 Priority Queue 的合併功能？
:::spoiler
| 結構 | 合併時間複雜度 |
| -------- | -------- |
| Binomial Heap | $O(\log n)$ |
| Fibonacci Heap | $O(1)$ |
:::
### DEAP: Insert
---
實作流程：
1. 在 bottom 插入新節點，索引為 index = size（當前 DEAP 的大小）。
2. 和對應節點比較，如果對應節點不存在則與其父節點比較，使其符合 Min Tree 或 Max Tree 得特性。
3. 接著將新節點依照其所在的子數特性做 ReHeapUp，恢復堆的特性。
:::success
怎麼找到對應的節點？
::: spoiler
其實仔細觀察是有規律的：
像是 index 10 在左子樹且在 level 4，index 10 再加 4 是他的對應 index 14，index 4 在 level 3 ，index 4 再加 2 是他的對應 index 6，可以發現如果在左子樹，其 index **加上** 某種值可以得到對應的索引；反之，如果在右子樹則會**減掉**某種值得到對應的索引。而那個「某種值」正好有某種規律跟所在的 level 有關：
level 2 的某種值是 $2^0$
level 3 的某種值是 $2^1$
level 4 的某種值是 $2^2$
以此類推，level - 2 會是其次方數
:::
:::success
怎麼知道節點在左子樹(Min Heap)還是右子樹(Max Heap)？
::: spoiler
我看的是在那層的左半邊還是右半邊，因此我找到那層的起點 index 跟**最大節點數**（以 level 3 來說，最大節點數是4，下一層是8），然後看該節點是**小於等於**`起點 index + 最大節點數 / 2 - 1` 還是**大於**，來區分他在左半部還是右半部。
:::
``` c++
void DEAP::Add(int k, int idx) {
// root is empty
if (size == 0) {
heap.push_back(HeapNode(-1, -1));
size++;
}
// insert node at bottom
heap.push_back(HeapNode(k, idx));
int cur_place = size;
if (cur_place == 1) {
size++;
return ;
}
if (cur_place == 2) {
if (heap.at(1).key > heap.at(2).key)
swap(heap.at(1), heap.at(2));
size++;
return;
}
// compare with corresponding index
int co_index = GetCoIndex(cur_place);
// find parent if corresponding index does not exist
if (co_index >= size)
co_index = (co_index - 1) / 2;
if (IsLeftTree(cur_place)) {
if (heap.at(cur_place).key > heap.at(co_index).key) {
swap(heap.at(cur_place), heap.at(co_index));
MaxReHeapUp(co_index);
}
else {
MinReHeapUp(cur_place);
}
}
else {
// Is right subtree
if (heap.at(cur_place).key < heap.at(co_index).key) {
swap(heap.at(cur_place), heap.at(co_index));
MinReHeapUp(co_index);
}
else {
MaxReHeapUp(cur_place);
}
}
size++;
}
```
:::info
插入的時間複雜度為 $O(\log n)$，但取得最小或最大值僅需 $O(1)$。
:::
### DEAP: Delete
---
1. 拿 bottom 去替換要刪的節點。
2. size 減一，把 bottom 刪掉。
3. 新節點先往下去做ReHeapDown，==這裡是先不用和對應節點比較做交換的！==
4. 假設要刪的節點在 Min Heap，則他會一路往下找比較小的節點去交換；在 Max Heap 則會一路往下找比較大的交換使其符合 Max Heap 的特性。
6. 接著會和對應節點比較看要不要交換，對應節點不存在會和其父節點比較。
7. 依照新節點所在位置去做 Min Heap 或 Max Heap 的 HeapReBuild 以恢復整體堆的特性。
:::danger
迷之 Special case:
22是已經 ReHeapDown 到最底部的狀態，但此時還沒結束...
當今天換到底部的節點是 Max Heap 的 leaf node，會需要==檢查對應節點的最大小孩==，當對應節點的最大小孩比新節點還要大，則需要再做交換(因為左半子樹是屬於 Min Heap 其 Key 一定會小於右邊的 Max Heap)。
:::
### Binomial Heap 的概念
---
Binomial Heap 是一種用於實現 Priority Queue（優先佇列） 的資料結構，主要**由多棵 Binomial Tree（雙項樹）** 組成，**每一棵樹的 order（階數） 互不相同**。它的特點是可以在 $O(\log n)$ 的時間內完成 **「合併（Merge）」** 、「插入（Insert）」、「刪除最小值（DeleteMin）」等操作，特別**適合需要頻繁合併多個優先佇列的場景**。
**Binomial Tree 的定義**
* $B_0$：只有一個節點的樹。
* $B_k$（order 為k）：由兩棵 order 為 k−1 的 Binomial Tree 合併而成，其中一棵作為另一棵的最左子樹。
:::info
What are u talking about?
::: spoiler 舉例說明
$B_1$ 由兩個 $B_0$ 合併而成：
取兩個單一節點的樹（各是 $B_0$）。選其中一個作「整棵新樹」的根節點，另一個變成它的「左子樹」。新的樹就有 2 個節點（root + 1 個子節點），這就是 $B_1$。
:::
**Binomial Heap 的特性**
1. 由 Binomial Trees 組成。
2. 而每個 Binomial Tree 都符合 Min Heap 的特性。
3. ==階數 (order) 都不同==，同一個 Binomial Tree 中不會出現相同階數。
4. ==相同階數的 Binomial Tree 可以被合併 (**Merged**)==。
:::info
關於 Binomial Tree 的 order
::: spoiler
order = 0（B₀）：只有一個節點。
order = 1（B₁）：根節點有 1 個子節點，共 2 個節點。
order = 2（B₂）：根節點有 2 個子節點，共 4 個節點。
order = 3（B₃）：根節點有 3 個子節點，共 8 個節點。
一般公式：
一棵 order = k 的 Binomial Tree 共有 $2^k$ 個節點。
高度（height）為 k。
根節點的 degree 也是 k，其子節點按順序分別為 order 𝑘 − 1，𝑘 − 2 ...，0 的樹。
:::
另外，==Binomial Heap 的結構對應二進位展開==，它會形成一個唯一的結構。也就是說若有 n 個節點，則 Binomial Heap 中的樹形結構可視為對應 n 的二進位展開。例如：
n = 13 = $2^3$ + $2^2$ + $2^0$
就對應於一棵 $B_0$，一棵 $B_2$，一棵 $B_3$ 所形成的 Binomial Heap。
:::info
head 會指向鏈結串列的頭也就是 k 值最小的 Binomial Tree，而在鏈結串列上的每一個元素都是 Binomial Tree 的樹根。
:::
同一個 root 的子樹每種 k 值只能出現一次。
### Binomial Heap - Merge 合併
**Merge 的目的與前提**
`目的`：將兩個或多個 Binomial Heap 合併成一個。
`前提`：
1. 每個 Heap 內的 Binomial Trees 已依 order（階數） 排序。
2. 同一個 Heap 中，不存在兩棵相同 order 的樹。
**Merge 的步驟**
1. 將兩個根鏈結串列（Root List）合併
* 把 Heap A 和 Heap B 的根節點鏈結串列串起來，形成一條 order 由小到大排序的串列。
* ==需保證根節點按照 order 由小到大排列==。
2. 從左到右掃描，把相同 order 的 Binomial Trees 合併
* 令目前指標為 cur，從 串列**最左走到最右**:
* 若 cur 所在的樹與下一棵樹的 order 不同 → 直接往右移。
* 若 cur 與下一棵樹的 order 相同 → 執行「鏈結（Link）」，將兩棵樹合併成一棵更高階的樹（order + 1）。
* **較小根值的那棵成為新樹的根，另一棵的 root 變成它的最左子樹**。
* 將合併後的新樹（order+1）插回串列相應位置，並注意是否與下個節點仍有相同 order。
* 若合併後仍發現相同 order → 繼續合併，直到沒有重複 order 為止。
* 如果合併很多棵樹，==遇到多餘2個 Binomial Tree order 相同，則優先選擇兩個根節點較小的 Tree 合併==。
3. 最終串列
* 當走到串列最右端，不再有兩棵相同 order 的 Binomial Tree。
* 這個新串列即為 合併後的 Binomial Heap。
### Binomial Heap - Insert 插入
---
Binomial Heap 插入新節點其實就呼叫 Merge function 就好：
### Binomial Heap - Delete 刪除
---
走訪鏈結串列找到值最小的 root 刪除，並把欲刪除節點的所有小孩加到鏈結串列，接著呼叫 Merge 合併相同 order 的 Binomial Tree。
:::info
Binomial Tree 有一個很大的缺點就是比較缺乏彈性，較難去刪除任一節點，因為會破壞其結構。
:::
### Fibonacci Heap 的概念
---
## 單元三 由下而上成長的平衡二元樹
Heap 不適合拿來做搜尋
### 搜尋的原理
sorted array based 的 Retrieval 會寫 $O (\log n)$ 是因為它可以用二分搜。
:::success
既然用 BST 也可以有「搜尋」的功能，那為什麼我們還需要其他工具來實作呢？
::: spoiler
因為 BST 的樹高是未必有保障的，它有可能出現歪斜樹 (skewed binary tree)，也就是 Worst case，讓樹高是 n，退化成線性結構。
而這個樹的結構很取決於「插入」和「刪除」的順序。
這也就是為什麼我們會盡量想讓樹保持平衡。
:::
### Balanced BST 平衡二元搜尋樹
---
常見的 Balanced BST:
* 2-3 樹
* 2-3-4 樹
* 以上是同家族（一個節點可以多於一個 key）
* 以下是另一個家族（一個節點一個 key）
* AVL 樹
* Red-Black 樹
### 2-3 樹的概念
---
**2-3 樹的基本特性**
* 每個內部節點（internal node）可能是：
* 2-node：1 個 key + 2 個子樹
* 3-node：2 個 key + 3 個子樹
* 所有外部節點（leaf node）都在同一層 → 樹的高度維持平衡。
* Data is stored in sorted order.
* Always insertion is done at leaf.
| 圖(a) 1 Key | 圖(b) 2 Key |
|---|---|
| |  |
:::success
為什麼 2-3 Tree 不會比最小高度的 Binary Tree 更高？
:::spoiler
因為2-3樹每個節點能容納更多子樹 (一個節點最多可以有兩個 key)，導致樹的高度成長更慢；而且它的葉節點一定都在同一層。其樹高必定不會高過最多只能容納兩個子樹的 Binary Tree 的最小高度。
:::info
2-3 樹的 Worst case 剛好是 BST 的 Best case。
:::
:::success
怎麼走訪 2-3 樹？
:::spoiler
類似 inorder traversal：
* 2-node：左子樹 → key → 右子樹。
* 3-node：左子樹 → key1 → 中子樹 → key2 → 右子樹。
最後可得到依鍵值排序（ascending order）的序列。
:::
另外，degree 代表 number of children。
### 2-3 樹 Insert
---
**Insertion 的步驟**
1. 遍歷找到應插入的葉節點
* 從根節點開始，根據資料值大小一路比較，直到抵達要插入新資料的葉節點。
2. 葉節點為 2-node（只有一個資料項）
* 直接將新資料插入該葉節點，使其成為 3-node（含兩個資料項）。
→ 這是基本情況，插入完成，不需要進一步調整。
3. 葉節點已為 3-node（已有兩個資料項）
* 將原有的第一個資料項（d1）、新資料項（item）與第二個資料項（d2）進行排序。
* 排序後，取中間值作為「上推值」，將其上推到父節點。
* 同時，將排序後的 d1 與 d2 分別放入兩個新的節點中（即對原來的葉節點進行分裂）。
4. 上推及父節點的處理
* 若父節點接收到上推的中間值後也變成 3-node（即已有兩個資料項），則重複第 3 步驟：
* 將父節點進行分裂，並將其中間值上推到更上層的節點。
* 此過程可能一路遞迴，直到找到一個未滿的父節點，或是最終需要分裂根節點，從而增加樹的高度。
**2-3 樹的 Insertion 有三個 case:**
`case1:` Node 只有1個 Key，那就插入 NewItem 變成第二個 Key。
:::spoiler 圖示
:::
`case2:` 欲插入的 Node 已經有兩個 Key，而它的 Parent 只有一個 Key。那就將中間值上移到 Parent，並且將最大和最小值分開，變成兩個不同的 Node。
:::spoiler 圖示
:::
`case3:`欲插入的 Node 已經有兩個 Key，而它的 Parent 也有兩個 Key → 父節點也滿則繼續分裂，可能一路到 root (若根節點也滿，就再分裂根，樹高增加 1)。
:::spoiler 圖示
:::
**練習**
:::spoiler 過程
:::
### 2-3 樹 Delete
---
**基本概念**
2-3 樹在每次 delete 資料後，仍須保持其原本的特性：
1. 所有葉節點都在同一層 → Balanced Tree。
2. 節點最多在兩個 key，最少一個 key。
當刪除後節點出現 empty node，則需透過 redistribute 或 merge 進行調整。
**Delete 的流程**
**Case A: 欲刪除的 item 在 leaf node**
1. Locate the leaf node containing the target item。
2. Remove 該 item。
* 若該 leaf node 仍有 1 個 key，則完成 delete。
* 若該 leaf node 變成空 (0 keys)，則必須做 redistribute 或 merge（見下方「空節點修正」）。
**Case B: 欲刪除的 item 在 internal node**
1. **`Swap`**：找到該 internal node 欲刪除 item 的 **predecessor**（==左子樹中最大的 key==）或 **successor**（==右子樹中最小的 key==），將其值交換到 internal node。
2. 接著在那個 leaf node 上執行刪除（就變成「Case A」的情況），刪除後若產生空 leaf node，同樣進行「空節點修正」。
3. 
:::success
關於刪掉變空的處理：
刪掉變空 → 先借 key，不行再合併 → 合併會讓 parent 變空，再繼續修上去
:::
:::spoiler 中序後繼者
最中間的下一個。
像 34 的 inorder successor 是 35；36 的 inorder successor 是 37。
:::
:::spoiler 具體 2-3 Delete 的步驟
**【Step 1】 先找 Target Key**
1. 從 Root 開始搜尋：
* 依照 2‑3 Tree 的搜尋規則，從 root 向下尋找包含目標 key 的 node。
* 若找到的 key 位於 internal node，則記錄該位置（待後續處理）。
**【Step 2】 將 Internal Node 的 Key 用 inorder successor 轉移至 Leaf Node**
（只有當目標 key 位於 internal node 時才會這樣做）
1. 選擇交換對象：
* 找到目標 key 的 inorder successor
2. 執行交換：
* 將 internal node 中的目標 key 與選定的 successor 交換，使目標 key 移至 leaf node。
* 這樣可以將刪除操作簡化為在 leaf node 中刪除。
**【Step 3】 在 Leaf Node 中刪除目標 Key**
1. 直接刪除：
* 在位於 leaf node 的目標 key 上直接執行刪除操作。
2. 檢查是否下溢 (Underflow)：
* 刪除後，若該 leaf node 仍保有至少 1 個 key，則操作完成。
* 如果刪除後該 leaf node 變成空（即無任何 key），則進入下溢修正。
**【Step 4】 修正 Underflow（下溢）**
當某個 node（leaf 或因交換後的 leaf）在刪除後變空時，需要進行以下兩種修正之一：
**A. Redistribute（重新分配）**
1. 檢查 Sibling Nodes：
* 找出空 node 的相鄰 sibling（左邊或右邊）。
2. 判斷 Sibling Key 數量：
* 若某一 sibling 至少有 2 個 keys，則可從該 sibling 借用一個 key。
3. 調整 Parent Node：
* 同時調整父 node 中的 key，使借用後的分布保持正確的順序。
**B. Merge（合併）**
1. 當所有 Sibling 均只有 1 個 key：
* 將空 node 與相鄰的 sibling 合併，同時從父 node 下移一個 key，並合併到新形成的 node 中。
2. 更新 Parent Node：
* 合併後，父 node 將失去一個 key和一個 child，可能會導致父 node 下溢，則必須向上遞迴處理，直到整棵樹恢復平衡。
**【Step 5】 更新和調整 Tree Structure**
1. 自底向上遞迴修正：
* 如果因 merge 或 redistribute 使得父 node 失去 key而下溢，則對父 node重複 Step 4 的修正步驟。
2. 處理 Root 下溢：
* 如果最終 root 變成空且只有一個 child，則讓該 child 成為新的 root（樹高度降低 1）。
3. 最終驗證：
* 確認所有 leaf nodes 均位於同一高度，且每個 node 都滿足 2‑3 Tree 的結構要求（除了 root 之外，每個 node 至少有 1 個 key）。
:::
:::spoiler 課程投影片
1. `2-3 Tree is a compromise`
* 2-3 Tree 在實作上做出了一種折衷設計：每個 node 可以有 1 或 2 個 keys (對應到 2-node 或 3-node)，透過插入、分裂（split）、合併（merge）等機制來維持平衡。
* 好處是它能避免像一般 BST 那樣可能退化成一條長鏈。
2. `Not more efficient than a BST of minimum height`
* 2-3 Tree 雖然通常「比較矮」（階層較少），但其搜尋效率並不一定比一棵擁有相同高度的 minimum-height BST 更快。
* 原因在於 node 內可能需要進行額外比較（extra comparisons）。
3. `Extra comparisons in a 3-node`
* 2-3 Tree 的一個 node 最多包含 2 個 keys (3-node)，因此每次搜尋時可能需要在 node 內進行 2 次比較才能決定下一步走向。
* 這些額外比較會抵消 2-3 Tree 因「樹較矮」所帶來的好處。
4. `Maintaining the balance of a 2-3 tree is relatively easy`
* 2-3 Tree 透過明確的規則（split、merge、redistribute）來維持平衡，實作起來相對容易，不易退化。
5. `Maintaining the balance of a BST is difficult`
* 一般的 BST 如果沒有自平衡機制（例如 AVL 或 Red-Black Tree），隨著插入或刪除可能出現嚴重偏斜，導致搜尋效率大幅下降。
* 這也是 2-3 Tree 被提出的原因之一，以提供一種不易失衡的樹結構。
:::
### 2-3-4 Tree 的概念
---
**基本概念**
2-3-4 tree 是一種自平衡的搜尋樹，本質上是一種 order-4（最多可以有四個子節點） 的 Banlance tree。樹中的每個 node 可以包含 1、2 或 3 個 keys，分別對應到 2、3 或 4 個 children。在進行 insert 時，**核心策略是在從 root 到 leaf 的路徑上，遇到任何 4-node（即含有 3 個 keys 的 node）時，就先進行 split**。這種自上而下（top-down）的做法可以避免回溯，並確保在到達 leaf 時有足夠空間插入新 key。
* 每個 node 可以有 1、2、3 個 keys，對應為 2-node、3-node、4-node。
* 所有 keys 都儲存在 leaf。
* 樹是 balanced 的，每個 leaf 到 root 的距離都一樣。
### 2-3-4 樹的 insert
---
:::info
2-3-4 樹為了避免由下往上的走訪，在由上而下走訪到 4-node 就會先分裂。
:::
1. `檢查 Root`
* 如果 root 為 4-node，必須先對其進行 split。
* split 的操作：
* 假設一個 4-node 包含的 keys 為 [A, B, C]（已排序）。
* 將中間的 key B promote 到其 parent；若該 node 為 root，則建立一個新 root 並將 B 放入其中。
* 將剩餘的 keys 分別放入兩個新 node，一個包含 A，另一個包含 C。
2. `遍歷樹`
* 從 root 開始，尋找適合插入新 key 的 leaf。
* 在下降過程中，若遇到 4-node，立即對其進行 split。
* 這樣可確保沿途所有 node 都不是滿的，當到達 leaf 時，就有空間直接插入新 key。
3. `在 Leaf 中插入新 Key`
* 到達 leaf 後，將新 key 按照順序插入到該 node 中。
* 若該 leaf 為 2-node，插入後會變成 3-node，這在 2-3-4 tree 中是允許的。
4. `維持樹的平衡`
* 由於在下降過程中持續進行 split，因此樹的結構始終保持平衡。
* 整個過程無需回溯調整，確保 insert 操作的時間複雜度為 O(log n)。
```
function insert(key):
# 步驟 1: 如果 root 是 4-node，先進行 split
if root is a 4-node:
split(root)
current = root
# 步驟 2: 從 root 遍歷到正確的 leaf
while current is not a leaf:
if current is a 4-node:
split(current)
# 根據 key 的值選擇合適的子 node
current = select_child(current, key)
# 步驟 3: 在 leaf 中以排序順序插入 key
insert_into_node(current, key)
```
### 2-3-4 樹 Delete
---
[讚讚的教學網址](https://sites.google.com/view/zsgititit/home/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B-%E4%BD%BF%E7%94%A8python/2-3-tree2-3-4-tree%E8%88%87b-tree)
### 2-3-4 樹的總結
---
:::success
2-3-4 tree 比 2-3 tree 更有效率，因為只需要走一遍從 root 到 leaf 就能完成 insert 或 delete。
Insertion/deletion algorithms for a 2-3-4 tree require ==fewer steps== than those for a 2-3 tree
* 2-3 tree 的刪除是 bottom-up，可能要刪完再補上來，多次調整。
* 2-3-4 tree 採用 top-down 策略，在走下去之前就先解決潛在問題（例如遇到 2-node 就先合併或借 key），所以「一次走到底」就可以完成操作。
:::
* A 2-3-4 tree is always balanced
* A 2-3-4 tree requires more storage than a binary search tree
* 多了 storage，但換來更快的操作
* 雖然節點內部空間變大，但 height 會變小（因為每個節點能承載更多 key）
* 這是一種以空間換取效率的設計
* Allowing nodes with more data and children is counterproductive (反而沒效率), unless the tree is in external storage
* 如果你是在 RAM 中操作資料，那麼 node 放太多 key 或 child 是「沒效率的」
* 因為 CPU cache/pointer 操作對這種大 node 的存取成本高
* 但如果是在 external storage（例如硬碟、資料庫），就反而適合這樣的設計
## 單元四 由上而下成長的平衡樹
### BST 的複習
---
### AVL Tree 的基本概念
---
AVL Tree 是一種 Binary Search Tree 的實作方式，最大的差別是他會保持平衡，來避免 BST 的 worst case，也就是歪斜樹的狀況。
**AVL Tree 的基本特性：**
對每個節點來說：
1. 左右子樹高度差不超過1。
2. 會透過旋轉(rotate)直至樹平衡(balance)。
**Balance Facotr(BF，平衡係數)：**
每個節點的平衡係數 = 左子樹高 - 右子樹高。
平衡係數可以用來檢驗 AVL Tree 是否平衡，任何一個節點的 BF 絕對值不會超過1。
### AVL Tree Rotation
旋轉的意義：
AVL tree 的旋轉，是把不平衡的子樹重新「接線」，讓高的一邊變低，整棵樹保持在左右高度差最多 ±1，這樣資料結構查找就不會變慢。
:::info
rotation 前與後的樹，整個 tree的 in-order traversal 相同 。
:::
旋轉又分兩種：
1. single rotation 單旋。
2. double rotation 複（雙）旋。
==看此新點在此不平衡之處的哪個方向== 又4種case來做調整 :
* 插入點的方向是「左左」→ LL → 用 RightRotate
* 插入點的方向是「右右」→ RR → 用 LeftRotate
* 插入點的方向是「左右」→ LR → 先左再右
* 插入點的方向是「右左」→ RL → 先右再左
:::success
看插入點相對於第一個不平衡節點的位置是哪個方向（左 or 右 → 左 or 右），就能知道是 LL / RR / LR / RL，然後套對應的旋轉。
:::
:::info
旋轉的原理：
1. 中間 key value 往上拉，小的放左邊，大的放右邊。
2. 孤立的子樹依其 key value 連結至適當位置。
:::
:::info
第一個不平衡的節點我們習慣命名為 x。
:::
#### LL：進行 Right Rotation 右旋
---
新節點插在「**不平衡節點的左子節點的左子樹**」
```
30 (x) ← 這就是第一個出現「左右高度差 > 1」的不平衡節點
/
20 (y) ← 它的左子節點
/
10 ← 新插入的節點
```
* 方向：「左」→「左」 → LL
* 解法：RightRotate(30)
```c++
Treenode* RotateRight (Treenode* x) {
Treenode* y = x->left;
x->left = y->right;
y->right = x;
return y;
}
```
:::success
為什麼是把x的左邊接y的右邊?
:::spoiler
根據 Binary Search Tree 的排序性質，剛剛好符合左小右大。
:::
#### RR：Left Rotation 左旋
---
新節點插在「**不平衡節點的右子節點的右邊**」
```
10
\
20 ← 不平衡節點
\
30 ← 插入點（在右的右邊）
```
* 方向：「右」→「右」 → RR
* 解法：LeftRotate(10)
```c++
Treenode* RotateLeft (Treenode* x) {
Treenode* y = x->right;
x->right = y->left;
y->left = x;
return y;
}
```
:::info
單旋完的樹高只會 shorter or equal
:::
#### LR：先左旋再右旋
---
新節點插在「**不平衡節點的左子節點的右邊**」
```
30 (x) ← 不平衡節點
/
10 (y) ← 左子節點
\
20 ← 插入點（在左的右邊）
```
* 方向：「左」→「右」 → LR
* 解法：**先讓這個樹變成 LL 的結構，再 RightRotate**。
* LeftRotate(10)
* RightRotate(30)
```c++
Treenode* RotateLR(Treenode* x) {
x->left = LeftRotate(x->left); // 先變 LL
return RightRotate(x); // 再把 x 右旋
}
```
#### RL：先右旋再左旋
---
新節點插在「**不平衡節點的右子節點的左邊**」
```
10
\
30 ← 不平衡節點
/
20 ← 插入點（在右的左邊）
```
* 方向：「右」→「左」 → RL
* 解法： **先讓這個樹變成 RR 的結構，再 LeftRotate**。
* RightRotate(30)
* LeftRotate(10)
```c++
Treenode* RotateRL(Treenode* x) {
x->right = RightRotate(x->right); // 先變 RR
return LeftRotate(x); // 再把 x 左旋
}
```
:::info
複旋完的樹高只會 shorter
:::
### AVL Tree Insertion
---
AVL tree 插入後，從新節點一路往上檢查平衡，一旦找到不平衡，就根據情況做旋轉（單旋或雙旋），旋轉一次就搞定，整棵樹又會恢復平衡了。
**步驟：**
1. 就像普通的 Binary Search Tree 一樣，照順序插進去，插在樹的「最底端」。
2. 插入後從該節點一路往上爬，每一層都算一次左右子樹的高度差（Balance Factor）：
* 如果平衡（差值 ≤ 1）：沒事，繼續往上檢查。
* 如果不平衡：馬上處理！
→ 根據是哪一種失衡（LL、RR、LR、RL）做旋轉來「搬動節點」讓樹重新平衡。
3. ==只需要處理**一次**旋轉即恢復平衡==。
:::info
重點來了！AVL tree 只需要對最底下那個不平衡點做一次旋轉，樹就會重新平衡，不需要一路旋轉到 root。
:::
``` c++
Treenode* Insert(Treenode* node , Data a_school) {
if (node == nullptr) {
node = new Treenode();
node->sameSchool.push_back(a_school);
return node;
}
if (a_school.name > node->sameSchool[0].name) {
node->right = Insert(node->right,a_school);
} else if (a_school.name < node->sameSchool[0].name) {
node->left = Insert(node->left,a_school);
} else if (a_school.name == node->sameSchool[0].name) {
node->sameSchool.push_back(a_school);
return node;
}
node = BalanceTree(node);
return node;
}
```
``` c++
Treenode* BalanceTree (Treenode* node) {
if (node == nullptr) {
return node;
}
// 左邊高：LL, LR
if (BalanceFactor(node) > 1) {
if (BalanceFactor(node->left) >= 0) {
return RightRotate(node); // LL
}
else {
return RotateLR(node); // LR
}
} else if (BalanceFactor(node) < -1) {
// 右邊高: RR, RL
if(BalanceFactor(node->right) <= 0) {
return LeftRotate(node); // RR
}
else {
return RotateRL(node); // RL
}
}
return node;
}
```
### AVL Tree Delete
---
分成兩階段：
1. 用 Binary Search Tree 的方式刪除節點
* 兩個小孩：拿 inorder successor 去補。
* 一個小孩：拿唯一的小孩補。
* 沒小孩：直接刪。
2. 一路往上檢查 BF 如果不合格做旋轉。
### Red-Black Tree 紅黑樹
---
紅黑樹是一種 self-balancing binary search tree，使用節點顏色（紅 / 黑）控制樹的平衡結構。
* 紅黑樹 = 用 binary search tree 來實作 2-3-4 tree 的方式
* Represents each 3-node and 4-node in a 2-3-4 tree → 紅黑樹會把 2-3-4 tree 的多 key 節點「轉換」成紅 + 黑節點組合
* Maybe skewed ← needs rotation like AVL tree → 插入可能讓紅黑樹失衡（傾斜），所以也需要旋轉修正
* ==Has the advantages of a 2-3-4 tree, without the storage overhead==
* 所以紅黑樹 = 拿到了 2-3-4 tree 的平衡性優點
* 又避免了儲存結構複雜的缺點
### 2-3-4 樹怎麼轉成 Red-Black Tree
---
**Case1**: 4 node 3 key
:::info
2 個 red pointer。
:::
:::success
* 每個從根節點到葉節點的支線==其 black pointer 數量是一樣的==。
* 而黑色 pointer 的個數剛好對應了 2-3-4 樹的樹高。
* 每個分支 black pointer 數量一樣 + red pointer 不連續的性質讓紅黑樹高度最多是 2-3-4 Tree 的兩倍。
:::
**Case2**: 3 node 2 key
:::info
1 個 red pointer，1 個 black pointer。
有兩種可能，看大的在上面還是小的在上面。
:::
Ans: 8 (2^3，每個 three node 的有兩個可能)
**Case2**: 2 node 1 key
:::info
2 個 black pointer。
:::
### Red-Black Tree: Insertion
---
* 如果一個節點有兩個紅色子 → 視為 4-node，要 split（換色），這會發生在插入過程中。
* 插入的新節點一律設為紅色。
* 若造成連續紅 → 根據插入方向和叔叔顏色做 旋轉或換色。
:::info
The balance of RB tree is sensitive to insertion order
:::
| Case | 處理方式 |
| -------- | -------- |
| 叔叔是紅 |只變色，父叔變黑，祖父節點為紅色。（Case 1，==但是還是要往上去檢查==） |
| 叔叔是黑 + 外側插入 | 變色(不平衡的節點與其子節點顏色對調) + 單旋轉（Case 2)|
| 叔叔是黑 + 內側插入 | 變色(不平衡的節點與其子節點顏色對調) + 雙旋轉（Case 3） |
例子： +15, +85, +10, +70, +20, +60, +30, +50, +65, +80, +90, +40, +5, +55
### Red-Black Tree & AVL Tree 的比較
---
::: info
Red-Black Tree：插入刪除快，查找略慢但夠穩定
AVL Tree：查找快，刪除慢，適合查詢導向應用
:::
如果升序插入1-10到 Red-Black Tree & AVL Tree：
#### 📊 表格比較
| 比較項目 | 🔴 Red-Black Tree | 🟢 AVL Tree |
|-----------------------|--------------------------------------------------|--------------------------------------------------|
| 📐 平衡方式 | 顏色規則維持近似平衡（紅 / 黑） | 使用平衡因子（左右子樹高度差）嚴格平衡 |
| 📏 平衡程度 | 沒那麼平衡（最多比理想高度高兩倍） | ==更接近完全平衡，這也是為什麼在 Search （搜尋） 時 AVL 更吃香== |
| 🔁 插入／刪除效率 | ==插入/刪除操作較快==，最多 O(log n) 次旋轉 | 插入最多旋轉 1 次，刪除複雜，可能多次旋轉 |
| 🚀 查找效率 | 較慢（因為樹高較高） | ==較快（因為更平衡）== |
| ⚙️ 旋轉次數（插入） | 最多 2 次 | 最多 1 次 |
| ⚙️ 旋轉次數（刪除） | 較少，操作簡單 | 較多，邏輯複雜 (在動態環境表現較不好) |
| 📦 結構儲存開銷 | 每個節點需記錄顏色（紅 / 黑） | 每個節點需記錄平衡因子或高度 |
| 📚 適用場景 | 插入/刪除頻繁的資料結構（如 STL map/set） | 查詢為主的資料結構（如資料庫索引） |
---
✅ 優缺點整理
🔴 Red-Black Tree
- ✅ 插入與刪除成本低、效率穩定
- ✅ 實作不需記錄高度，只需記錄顏色
- ❌ 查找效率略低（因為樹高較大）
- ❌ 相對不那麼平衡
🟢 AVL Tree
- ✅ 保證更平衡 → 查找速度快
- ✅ 適合查詢密集的應用
- ❌ 刪除較複雜，需多次旋轉
- ❌ 實作需要追蹤平衡因子或高度
### Red-Black Tree Delete
---
分成兩階段：
1. 用 Binary Search Tree 的方式刪除節點
* 兩個小孩：拿 inorder successor 去補。
* 一個小孩：拿唯一的小孩補。
* 沒小孩：直接刪。
2. 如果刪掉的是黑色節點 → 啟動 Fix-up（補黑）機制
➤ 目的：維持紅黑樹的「黑高度一致」規則
## 單元五 Hash 雜湊
**基本概念**
Hash 是一種將資料的 key 經由 hash function 映射成陣列中的 index，讓我們可以在幾乎固定的時間內（O(1)）快速存取、插入或刪除資料的技術。
它就像一個自動分配置物櫃的系統，不需要一個個搜尋，只要知道 key，就能直接找到對應的位置。若兩個不同的 key 映射到同一個位置，就稱為 collision，這時就需要特別的處理方式（如 chaining 或 probing）來解決。
Perfect hash 是理論中的理想情況，現實中我們通常要處理 collision（碰撞）。
:::success
定義：什麼是 Collision？
:::spoiler
`當不同的 key 經過 hash function 被分配到相同位置時，就發生 collision。`
Collision occurs when a hash function maps two or more different search keys
→ into the same array location
白話：不同的 key 經過 hash function 結果一樣 → 撞在同一格。
就像兩個人都把東西塞進了編號 42 的置物櫃。
鴿籠原理（確定會發生）
- n 個人放進 m 格 → 若 n > m，就必定有 collision。
8 號就是 collision 的例子。
:::
**Hash Function 的特性**
1. Assign each search key to a single location （這是 hash function 最基本要做到的事！）→ 每個 key 都被映射到唯一一個位置（index）。
2. Easy and fast to compute （要簡單快速）
3. Places items evenly throughout the table
→ 要平均分布（避免聚集）。
→ 不平均會讓某些位置容易發生 collision，影響效率。
4. Involves the entire search key
5. Uses a prime base if using modulo
→ 如果你在設計 hash function 的時候有用到「%（取餘數）」這種運算，
那你選的 除數（也就是 table size）應該是一個質數（prime number）。
→ 如果你選的不是質數，很多有規律的 key 會全部撞在一起。
**Collision resolution schemes（碰撞解決策略）**
:::info
Assign distinct locations to the collided items
就是想辦法讓撞在一起的資料，也能找到其他空位放進去。
:::
**常見簡單 hash function 設計法：**
1. **Digit Selection**
- 只取 key 的某些位數
- 缺點：分布容易不平均，發生碰撞機率高
2. **Folding**
- 把 key 分段後相加
- 可利用整個 key 的資訊，分布較平均
3. **Modulo Arithmetic（取模法）**
直接把整個數字 key 做 % table_size
常搭配 folding 的總和來用（更平均）
:::success
✅ 重點提醒：
使用 % 時，建議 table size 為==質數== → 分布較均勻。
:::
4. Converting Character Strings
- 📌 目的
將字串型的 key（如學號、名字）轉換為整數後才能做 hash。
- 🧠 方法：Positional Sum（位置加權總和）
將每個字元轉成 ASCII 整數後，乘上對應的權重（通常是以 2⁸ = 256 為 base），再相加。(每個 ASCII 字元佔 1 byte（8 bits）
- 像是："104"
是「像十進位那樣，做一種 base-256 的進位加總」，前面的數字對應 ASCII 碼。
= 49 × 28² + 48 × 28¹ + 52 × 28⁰
最後可能再取 module 得到 index。
---
→ 用每三位做 folding（前3+中3+後2）再取 7 的餘數。
### 怎麼解決 Collision?
---
#### 1️⃣ Open Addressing（開放定址法）
- 當發生碰撞時，**嘗試找下一個空位**（probe for an empty location）
- 常見的探測(**Probe**)方式：
- 線性探測（Linear Probing）
- 二次探測（Quadratic Probing）
- 雙重雜湊（Double Hashing）
- 缺點：
- **資料越多，碰撞越頻繁**
- 若 table 滿了，需 **增加 table size 並重新 hash 所有項目**
:::success
Probe 是什麼？
::: spoiler
在 open addressing 中，當你要插入的 位置已經被佔走，
就要「probe」（探測）下一個可用的位置，直到找到空位。
:::
---
#### 2️⃣ Restructuring the Hash Table（重構雜湊表）
- 允許一個位置存放 **不只一筆資料**（如用 linked list）
- 常見方式：
- **Chaining**（鏈結法）：每個位置是一個 linked list
- 優點：
- 插入簡單，不需重新安排整個表
- 缺點：
- 可能增加記憶體使用量與搜尋時間
### Linear Probing
---
1. **將學號數字加總：**
`1+0+0+2+7+1+4+6 = 21`
2. **計算 Hash index：**
`21 % 7 = 0` → 嘗試插入位置 `index 0`
3. **index 0 已被佔用（10027112）**
→ 繼續 probe `index 1`（也被佔）
→ 再 probe `index 2`，也被佔
→ 插入到下一個空位 `index 3`
:::success
什麼是 Number of Probes？
:::spoiler
==插入（或查找）一筆資料時，總共嘗試了幾個位置才成功==。
如果這格是空的 ➝ 成功，probes = 1
如果這格有人了 ➝ 繼續下一格
每往下一格，多算一次 probe，直到找到空格。
:::
:::success
Load Factor 是什麼？
:::spoiler
Load Factor（α） = 放進去的元素數量 ÷ Hash table 的總容量
以圖中為例：
有 6 個元素，Hash table 大小是 7
α = 6 / 7 ≈ 0.857
:::
:::success
Load Factor 有什麼影響？
:::spoiler
✅ 負載因子越小 → 碰撞機率越低 → 插入／查找速度快
❌ 負載因子接近 1 → 表示 table 幾乎滿了 → 碰撞變多，探查次數變多（慢！）
:::
:::success
Primary Clustering 是什麼？
:::spoiler
**Primary Clustering 意思：具有相同 Hashing Address 之 Data 容易占用相鄰的 Buckets 存放，形成群聚現象**
Primary Clustering 是在 Linear Probing 的 collision resolution 方法中，當多個元素碰撞後，被放到相鄰位置時，會形成一段連續的「鏈」狀區塊，新的元素如果也撞進來，就會往後塞，鏈越來越長，查找、插入效率會下降。
:::
| 名稱 | 意思 |
|--------------------|----------------------------------------------------------------------|
| **Load Factor α** | 裝滿程度（= 元素數 / 表格大小），影響碰撞機率與查找/插入效率 |
| **Primary Clustering** | Linear probing 特有問題，碰撞元素會「黏成一團」，導致探查越來越慢 |
📌 延伸補充
- **Load Factor** 越高（接近 1），**碰撞機率上升**
- **Primary Clustering** 發生時會產生長鏈，建議：
- 使用 **Quadratic Probing** 或 **Double Hashing**
- 或在 Load Factor 高時進行 **Resize**
:::info
🔍 探查的邏輯是：
從 hash(key) 算出的 index 開始找（比如從 index 0）
一格一格往後看
如果遇到：
✔️ 有資料 → 看是不是我們要找的（不是就繼續）
❌ 完全空的格子 → 結束查找，資料「不在表中」
:::
::: success
為什麼「完全空」可以代表找不到？
因為 Linear Probing 插入時一定是「填在最早能填的空格」
也就是說：
如果這筆資料真的存在，那麼它「一定會出現在這個空格之前」！
:::
**Linear Probing 的主要兩大問題**
1. **Primary Clustering 主要群聚**
Primary Clustering 是線性探查特有的問題，指的是：
* 元素會「黏成一團」：因為線性探查會找下一格，碰撞發生時新元素就被塞到下一格 → 越來越多元素會聚集在一起
* 這團會越來越大（cluster 擴張）
* 結果是：
* 越大的群 會導致你需要越多次探查（long probing sequences）
* 探查行為會變得像 sequential search → 效率大幅下降
2. **Delete Problem**
在 Linear Probing 中，如果發生碰撞，我們會往後一格一格找空位插入。
**例子**：
| Index | Data |
|-------|--------|
| 0 | 1001 |
| 1 | 1015 |
| 2 | 1022 |
| 3 | **空的**（❗已刪除） |
| 4 | 1048 |
**問題描述**
現在要找資料 `1048`，經過 Hash 計算從 `Index 0` 開始找：
- Index 0 → 不是
- Index 1 → 不是
- Index 2 → 不是
- Index 3 → **空的！** → ❗**錯誤地認為找不到 1048**
實際上，1048 還在 Index 4，只是中間出現了一個被刪除的空格，讓搜尋過早結束。
**為什麼會這樣？**
因為在刪除資料時，**直接將欄位設為 empty**，導致搜尋時誤以為 key 不存在。
**解決方法：使用「刪除標記」**
刪除資料時，不是真的清空欄位，而是做一個「deleted 標記」：
```text
[3] = deleted
```
### Quadratic probing
---
📌 定義
Quadratic Probing 是一種 **Open Addressing**（開放定址）策略，
用來解決 Hash Table 中的碰撞（collision）問題。
當插入資料時發生碰撞，Quadratic Probing 會依照==平方距離==繼續往後找：
（original）
(collision: 放在 5 + 1^2 的位子)
(collision: 放在 5 + 2^2 的位子，但因為超過 hash table size 故 module 7 得到 2，放在 2 的位子)
| i | 探測公式 | 結果 | 結果是否佔用？ |
|----|-----------------------------------|------|----------------------|
| 1 | (5 + 1²) % 7 = 6 | [6] | ❌ 已佔用 |
| 2 | (5 + 2²) % 7 = 9 % 7 = 2 | [2] | ❌ 已佔用 |
| 3 | (5 + 3²) % 7 = 14 % 7 = 0 | [0] | ❌ 已佔用 |
| 4 | (5 + 4²) % 7 = 21 % 7 = 0 | [0] | ❌ 又是同一格 |
| 5 | (5 + 5²) % 7 = 30 % 7 = 2 | [2] | ❌ 又是同一格 |
| 6 | (5 + 6²) % 7 = 41 % 7 = 6 | [6] | ❌ 又是同一格 |
| 7 | (5 + 7²) % 7 = 54 % 7 = 5 | [5] | ❌ 又是同一格（原始） |
:::danger
Quadratic probing 的缺點，有可能怎麼算都無法找到可以插入的地方（可能產生 infinite loop）。
為此會設置 overflow 的區域，去儲存這樣的 case。
:::
為了保證 Quadratic Probing 能探查整個表格（不漏位）：
- Table size 應選為 **質數（prime number）**
- 或者限制 load factor α < 0.5 （如果 Load facotr > 0.5 代表效率已經不太好了）
**Quadratic probing 的兩大問題**
🔷 **Probing sequence may ==not== visit every location**
- 使用 Quadratic Probing 時，**不是所有位置都會被訪問到**。
- 若 table size 設置不當（例如不是質數），可能無法探查整個表。
🔶 **Secondary Clustering**（二次集群問題）
* 當兩個不同的 key 被 hash 到同一個初始位置時（例如都被 hash 到 index 4），它們後續的 probing sequence 是一樣的。
* 也就是說：
* key1 碰撞 → 試下一個位置 → 如果還是碰撞 → 繼續依樣的路線（如 +1², +2², +3²…）
* key2 落在同樣的位置 → 它的探查路線完全跟 key1 一樣
* 結果就是： 這些不同的 key 後來都探查相同的 sequence，如果其中某個 key 插入成功，其他 key 也很容易「一路撞下去」，形成「局部的擁擠」：clustering（集群）
:::spoiler 例子
假設我們用一個大小為 13 的 hash table（索引從 0 ~ 12）
tableSize = 13
key1 = 18
key2 = 31
* Step 1：兩個 key 都 hash 到同一個位置
h(18) = 18 % 13 = 5
h(31) = 31 % 13 = 5
* Step 2：發生碰撞，開始 quadratic probing
| i | 18 的位置 `(5 + i²) % 13` | 31 的位置 `(5 + i²) % 13` |
|---|----------------------------|----------------------------|
| 0 | 5 | 5 |
| 1 | 6 | 6 |
| 2 | 9 | 9 |
| 3 | 1 | 1 |
雖然 key1 和 key2 是完全不同的值，但它們「被 hash 到同樣的位置」，導致後續的 探查順序一模一樣。
:::
---
### Linear probing 和 Quadratic probing 的共同特點
* 都屬於 open addressing 的 collision resolution 方法
* 🔑 **Key-independent probing sequences**
:::success
Key-independent probing sequence 是什麼？
:::spoiler
Key-independent probing sequence 指的是：
無論你插入的 key 是什麼，只要它們一開始碰撞在同一個位置，它們後續的 probing 探查順序就會一模一樣。
==只與原本的 index 有關，而不是與 key 本身有關==
:::
👉 以 Quadratic probing 為例：
假設兩個 key 經過 hash function 都落在 index 5，然後我們使用 quadratic probing：
(5 + 1²) % 13 → 6
(5 + 2²) % 13 → 9
(5 + 3²) % 13 → 1
...
不管是 key = 18 還是 key = 31，只要它們初始位置是同一個，接下來的檢查順序就是固定的、不依賴 key 的內容，這就叫做 key-independent。
🧠 小結
Linear probing：+1, +2, +3... → key-independent
Quadratic probing：+1², +2², +3²... → key-independent
因為都只與原本的 index 有關，而不是與 key 本身有關，所以叫 key-independent probing sequences。
### Double Hashing
---
📌 特點
- **使用兩個 hash function**：`h₁(key)` 和 `h₂(key)`
- **Probing sequence 是 key-dependent**，每個 key 都有自己的跳躍步伐
- 可 **避免 primary clustering 與 secondary clustering**
📐 使用方式
- `h₁(key)` 決定初始位置（first location）
- `h₂(key)` 決定步進大小（step size）
✅ 條件限制
- `h₁ ≠ h₂`：兩個 hash function 要不同
- `h₂(key) > 0`：步進大小不能為 0
- 最好讓 `h₂(key)` 和 table size **互質**，才能保證每一格都能訪問
:::info
Primary Hash Function：h1 = sum % 7
Secondary Hash Function（Step size）：h2(key) = 5 - (sum % 5)，5 是自訂的，整個 h2 都可以自訂。
:::
sum = 15， h1(15) = 15 % 7 = 1 h2(1) = 5 - (15 % 5) = 5
index 1 發生 collision 用 h2 去計算 step size，結果是放在 1 + 5 的位置。
h1(36) = 36 % 7 = 1
h2(1) = 5 - (36 % 5) = 4
結果：放在 1 + 4 = 5 的位置。
h1(36) = 36 % 7 = 1
h2(1) = 5 - 36 % 7 = 4
1 + 4 的位置仍然發生 collision，因此會再加 4，放在 9 的位子。
:::info
當 table size 和 step size 互相為質數關係，他的 probing sequence 會走訪 hash table 中的每個位子。
這也是為什麼 table size 會要求是質數。
:::
### Restructuring the Hash Table
---
📦 **Buckets**
- 每個位置是一個「小型陣列」
- 多個項目可存入同一位置的 array 中
- 缺點：需預留空間，可能會浪費空間
🔗 **Separate Chaining**
- 每個位置是一個 linked list
- 每次碰撞就往該位置的 list 加入新項目
- 優點：
- ✅ 可處理任何數量的碰撞
- ✅ linked list 可動態成長
- ✅ 不需重新 hash 或擴大 table
- Worst-case 時間複雜度：$O(n)$
- 如果所有 key 都 hash 到同一個位置，linked list 會變得很長
- 查找時間會退化到線性 $O(n)$，等於暴力搜尋
📌 **特點比較**
| 方法 | 結構 | 優點 | 缺點 |
|------------------|---------------|-------------------------------|------------------|
| Buckets | Array | 結構簡單 | 預設空間固定 |
| Separate Chaining| Linked List | 動態處理碰撞、空間彈性好 | 每次查找需遍歷鏈結 |
📦 + 🔗 **Buckets + Separate Chaining**
- 缺點：
- 需要做記憶體管理，可能像前一個節點的 array 中有某一筆資料被刪除，需要把後一個節點的資料往前搬，提升查找效率。
- Worst-case 時間複雜度：$O(n)$
- 如果所有 key 都 hash 到同一個位置，linked list 會變得很長
- 查找時間會退化到線性 $O(n)$，等於暴力搜尋
### Hash Table 的效率評估
1️⃣ Load Factor α（裝填因子）
* **定義**：
$$
\alpha = \frac{\text{目前表中項目數}}{\text{Hash Table 的大小}}
$$
* 意義：
* 用來衡量 Hash Table 裡「有多滿」
* α 越接近 1，代表越滿，碰撞（collision）越可能發生，效率會下降
2️⃣ 取決於 search 有沒成功：
- 如果沒有成功就會花很多額外的時間
:::success
如何計算平均比較次數？
:::spoiler
Hashing: Average Number of Comparisons (Separate Chaining)
- 若 key 不存在，仍需遍歷整條 linked list 才能確定。
- 比較次數 = 每條 list 的長度
- 平均比較次數 = 所有桶子長度總和 / table size
例子分析：
| index | list 長度 | comparisons |
|-------|------------|-------------|
| [0] | 2 | 2 |
| [1] | 0 | 0 |
| [2] | 1 | 1 |
| [3] | 3 | 3 |
| [4] | 3 | 3 |
| [5] | 2 | 2 |
| [6] | 3 | 3 |
**平均比較次數**：14 / 7 = **2**
:::
### 不適合用 Hash 的例子
---
Hash Table 雖然對「精準搜尋（search）」很快，但對以下操作不適合：
🔁 Traversal
- **目標**：以「排序順序」訪問所有資料
- **困難點**：Hash Table 本身沒有保持順序 → 必須掃描整個 table 並排序，效率差。
- **適合的資料結構**：BST 家族
📍 NN Search（Nearest Neighbor Search）
- **目標**：找出具有最大或最小 key 的項目
- **困難點**：無法保證順序，只能全表掃描比較大小。
- **適合的資料結構**：Heap
🔍 Range Query
- **目標**：找出 key 介於兩個值之間的所有項目（e.g., key ∈ [20, 50]）
- **困難點**：Hash 無法用範圍直接鎖定 → 只能逐個查。
- **適合的資料結構**：BST 家族
### 📊 Data with Multiple Organizations
---
許多應用需要一種資料組織方式能 **同時支援不同的資料操作任務**。
1. **Several Independent Data Structures**
- **缺點**：
- 無法同時有效支援所有操作（效率差）
- 會造成空間浪費（資料重複存多份）
2. **Inter-dependent Data Structures（互相依賴的資料結構）**
- ✅ 提供一種更有效率的方式來同時支援不同操作需求
- **例如**：可以設計一種結構，既能快速搜尋（像 Hash Table），又能支援排序（像 Binary Search Tree）
- ✅ 可以減少重複儲存，增加整體效率
### 📌 Hashing Summary
---
一個好的 hash function 應該：
- **運算簡單且快速**
- **能夠平均地（evenly）分散** search keys 到 hash table 中，避免太多 collision
#### ❗ Collision 是什麼？
- 當 **兩個不同的 search key** 被 hash 到 **同一個位置** 時，就發生 collision。
#### ⚠️ Hashing 的限制
- 無法有效支援「需要排序（ordered）」的操作，例如：
- 排序（sorted output）
- 範圍查詢（range query）
- 最小 / 最大查詢
#### ✅ Hashing 比 balanced search tree 更快的情況：
1. **不需要遍歷（Traversal）**
2. **資料筆數是已知的（Maximum number of items is known）**
3. **有足夠空間（Ample storage is available）**
### Hash Join
💡 **觀念：什麼是 Join？**
- **Join 是資料庫中的一種重要操作**
- 用來將兩個表格（tables）根據一個「共同欄位」合併起來
🧠 **Hash Join 怎麼做？**
1. **從一張表開始建立 hash table**（例如右邊 Maintenance）
2. 把另一張表（例如左邊 Accidents）的對應欄位（`license`）拿來查詢 hash table
3. 如果 match，就 join 兩列資料
✅ Hash Join 的優點
比 nested loop join 更快
適合處理大量資料
較不受資料順序影響
Hash Join 比較次數計算
**為什麼會是 `2*2 + 2*1 + 2*2 = 10 comparisons`？**
| Accidents 中的 license | Hash Bucket 位置 | Bucket 長度 | Probes 次數 |
|------------------------|------------------|--------------|----------|
| MXT-612 | [0] | 2 | 2 |
| LCD-123 | [0] | 2 | 2 |
| KIA-214 | [1] | 1 | 1 |
| LKK-100 | [1] | 1 | 1 |
| NCC-719 | [2] | 2 | 2 |
| MXT-500 | [2] | 2 | 2 |
總比較次數為：10
### Count-Min Sketch
---
🧠 **Count-Min Sketch 是什麼？**
Count-Min Sketch 是一種用來**估算資料出現頻率 frequency**的資料結構，它是一個**近似**計數工具，==不保證完全正確，但絕對不會低估（只會高估一點點）==
記憶體用量非常小，適合處理像是網站流量統計、熱門搜尋關鍵字這種「資料量很大」的情境
例子：
1. 資料輸入
輸入字串：`C A B A B E F G`
對應的 key：`3 1 2 1 2 5 6 7`
2. Hash Function
- H1 = `(key × 2) % 7`
- H2 = `(key + 3) % 5`
3. 操作方式
每加入一個 key：
- H1 與 H2 對應位置的 counter 各 +1
- 查詢次數時：
- 用相同的 hash function 找位置
- **取兩個 counter 的最小值**
4. 查詢結果舉例
| 字母 | key | H1位置 | H2位置 | H1值 | H2值 | 預估出現次數 |
|------|-----|--------|--------|------|------|----------------|
| A | 1 | 2 | 4 | 2 | 3 | min(2, 3) = 2 |
| B | 2 | 4 | 0 | 2 | 3 | min(2, 3) = 2 |
| C | 3 | 6 | 1 | 1 | 1 | min(1, 1) = 1 |
| D | 4 | 1 | 2 | 0 | 0 | min(0, 0) = 0 |
訂正：
| k（放入 item 數） | 無 collision 機率 | collision 機率 |
|------------------|--------------------------|--------------------|
| 2 | 11/12 = 0.9167 | 8.3% |
| 3 | (11/12) × (10/12) ≈ 0.7639 | 23.6% |
| 4 | ≈ 0.5729 | 42.7% |
| 5 | ≈ 0.3819 | **61.8%** |
A: 2.9
11 * 19 + 1 *81
## 一些期中線上測驗的複習
Huffman tree 的 root 是由所有子節點合併出來的，不是原始某個 character。
Huffman tree 不是 balanced binary tree。可能是非常不平衡的，根據字元出現的頻率來決定深度。
| Algorithm | Best Case | Average Case | Worst Case | Space Complexity | Stable |
|---------------|---------------|----------------|----------------|------------------|--------|
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ❌ |
| Quicksort | O(n log n) | O(n log n) | ==O(n²)== | O(log n) | ❌ |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✅ |
| Heap Operation | Time Complexity |
|------------------------|------------------|
| Insert | O(log n) |
| Find Min / Max | O(1) |
| Delete Min / Max | O(log n) |
| Build Heap (heapify) | O(n) |
| Merge (Two Heaps) | O(log n) for Binomial or Fibonacci|
Sign in with Wallet
Connect another wallet