---
# System prepended metadata

title: DS2 單元1-5

---

# 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 的條件。（==每一根稻草都是排序的==）
 ![Screenshot 2025-02-25 at 2.35.14 AM](https://hackmd.io/_uploads/BJglhNc91x.png =500x400)
     :::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 
![Screenshot 2025-02-27 at 3.55.52 AM](https://hackmd.io/_uploads/HJArGlpqyg.png)
![Screenshot 2025-02-27 at 4.02.38 AM](https://hackmd.io/_uploads/rklBwe6qJl.png)
![Screenshot 2025-02-27 at 4.06.40 AM](https://hackmd.io/_uploads/ByxBDea5Jx.png)
:::
以指標實作：

## 單元二 Variations of Heap 堆積的變形

* Doubled-ended Priority Queue
    * 資料結構一： Min-max Heap
    * 資料結構二： Doubled-ended Heap
* Forest (Union) of Heaps
    * 資料結構一： Binomial Heap
    * 資料結構二： Fibonacci Heap

![Screenshot 2025-03-21 at 10.23.16 PM](https://hackmd.io/_uploads/SJRD8xsh1x.png =90%x)


### 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）來判斷哪個更大，也可能要再比對它們的孩子，但整體仍可在常數時間內找到最大值。

![Screenshot 2025-02-28 at 4.09.08 PM](https://hackmd.io/_uploads/H1eVye1iyx.png)

:::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。
  
  ![Screenshot 2025-02-28 at 7.46.13 PM](https://hackmd.io/_uploads/BytNfQyjJx.png)
:::
:::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 無祖父節點
![Screenshot 2025-03-01 at 12.45.02 AM](https://hackmd.io/_uploads/BkAGuP1jJl.png)
:::

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

![Screenshot 2025-03-01 at 12.52.03 AM](https://hackmd.io/_uploads/B1e6KDyiyl.png)

:::

練習：
![Screenshot 2025-02-28 at 6.16.23 PM](https://hackmd.io/_uploads/HkrW6Zyokx.png)
![IMG_94A05249E91F-1](https://hackmd.io/_uploads/HJffyz1jyx.jpg)

### 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 規則為止。
        ![Screenshot 2025-02-28 at 6.54.01 PM](https://hackmd.io/_uploads/rJ_RHfkjyl.png)![Screenshot 2025-02-28 at 6.58.02 PM](https://hackmd.io/_uploads/HJapIM1okx.png)

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 的節點還要大，故需要檢查是否要交換。
        :::
        ![Screenshot 2025-02-28 at 7.18.50 PM](https://hackmd.io/_uploads/Sk5iiGkoJl.png)

::: spoiler 投影片的練習題
![IMG_20D98A886F9C-1](https://hackmd.io/_uploads/ByrrAG1syg.jpg)
![IMG_0A97A08210FF-1](https://hackmd.io/_uploads/HJCrCG1iJg.jpg)
:::

### 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
---
![Screenshot 2025-03-20 at 10.24.55 PM](https://hackmd.io/_uploads/rJLLSiK3ye.png)

實作流程：
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 會是其次方數

![Screenshot 2025-03-20 at 11.02.21 PM](https://hackmd.io/_uploads/rk9bCoYhJl.png)
![Screenshot 2025-03-20 at 11.12.45 PM](https://hackmd.io/_uploads/r1OOghY2yx.png)
:::

:::success
怎麼知道節點在左子樹(Min Heap)還是右子樹(Max Heap)？
::: spoiler
我看的是在那層的左半邊還是右半邊，因此我找到那層的起點 index 跟**最大節點數**（以 level 3 來說，最大節點數是4，下一層是8），然後看該節點是**小於等於**`起點 index + 最大節點數 / 2 - 1` 還是**大於**，來區分他在左半部還是右半部。
![Screenshot 2025-03-20 at 11.37.44 PM](https://hackmd.io/_uploads/rJ4L82Fhkx.png)

:::

``` 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:
![Screenshot 2025-03-21 at 12.09.49 AM](https://hackmd.io/_uploads/BkoCa3K3kx.png)
22是已經 ReHeapDown 到最底部的狀態，但此時還沒結束...
當今天換到底部的節點是 Max Heap 的 leaf node，會需要==檢查對應節點的最大小孩==，當對應節點的最大小孩比新節點還要大，則需要再做交換(因為左半子樹是屬於 Min Heap 其 Key 一定會小於右邊的 Max Heap)。
![Screenshot 2025-03-21 at 12.11.47 AM](https://hackmd.io/_uploads/BJJIC3t31l.png)

:::

### 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$。
![IMG_F2B384CA8BD5-1](https://hackmd.io/_uploads/Hk1Rv0Fhke.jpg =50%x)
:::

**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。

![Screenshot 2025-03-17 at 11.07.57 PM](https://hackmd.io/_uploads/BJjA9nShJe.png)

:::info
head 會指向鏈結串列的頭也就是 k 值最小的 Binomial Tree，而在鏈結串列上的每一個元素都是 Binomial Tree 的樹根。
:::
![Screenshot 2025-03-21 at 1.04.33 AM](https://hackmd.io/_uploads/HkCscTYhke.png)

同一個 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 就好：
![Screenshot 2025-03-21 at 9.38.12 PM](https://hackmd.io/_uploads/BJWCoyohkl.png)
![Screenshot 2025-03-21 at 10.02.31 PM](https://hackmd.io/_uploads/rJrt-lshkl.png)
![IMG_71B9E91814F4-1](https://hackmd.io/_uploads/r1fT-xshJx.jpg)


### Binomial Heap - Delete 刪除
---
走訪鏈結串列找到值最小的 root 刪除，並把欲刪除節點的所有小孩加到鏈結串列，接著呼叫 Merge 合併相同 order 的 Binomial Tree。

:::info
Binomial Tree 有一個很大的缺點就是比較缺乏彈性，較難去刪除任一節點，因為會破壞其結構。
:::
![Screenshot 2025-03-21 at 9.48.24 PM](https://hackmd.io/_uploads/HJHNCksnye.png)
![IMG_E59D9679DF6F-1](https://hackmd.io/_uploads/SkywSgj3Je.jpg)

### Fibonacci Heap 的概念
---
![Screenshot 2025-03-21 at 10.29.33 PM](https://hackmd.io/_uploads/rJBwdlj31x.png)

## 單元三 由下而上成長的平衡二元樹
Heap 不適合拿來做搜尋
### 搜尋的原理


![Screenshot 2025-03-22 at 12.05.46 AM](https://hackmd.io/_uploads/BkwD0bjnkl.png)
sorted array based 的 Retrieval 會寫 $O (\log n)$ 是因為它可以用二分搜。

:::success
既然用 BST 也可以有「搜尋」的功能，那為什麼我們還需要其他工具來實作呢？
::: spoiler
因為 BST 的樹高是未必有保障的，它有可能出現歪斜樹 (skewed binary tree)，也就是 Worst case，讓樹高是 n，退化成線性結構。
而這個樹的結構很取決於「插入」和「刪除」的順序。
![Screenshot 2025-03-22 at 12.14.55 AM](https://hackmd.io/_uploads/H13KgMj2kg.png)
這也就是為什麼我們會盡量想讓樹保持平衡。
:::

### 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 |
|---|---|
|![Screenshot 2025-03-22 at 3.39.57 AM](https://hackmd.io/_uploads/Byxilronyl.png =90%x) | ![Screenshot 2025-03-22 at 3.40.48 AM](https://hackmd.io/_uploads/HJ66lBsh1l.png =110%x) |

:::success
為什麼 2-3 Tree 不會比最小高度的 Binary Tree 更高？
:::spoiler
因為2-3樹每個節點能容納更多子樹 (一個節點最多可以有兩個 key)，導致樹的高度成長更慢；而且它的葉節點一定都在同一層。其樹高必定不會高過最多只能容納兩個子樹的 Binary Tree 的最小高度。
:::info
2-3 樹的 Worst case 剛好是 BST 的 Best case。
:::
![Screenshot 2025-03-22 at 3.47.16 AM](https://hackmd.io/_uploads/H1X8fSo2kx.png)

:::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 步驟：
    * 將父節點進行分裂，並將其中間值上推到更上層的節點。
    * 此過程可能一路遞迴，直到找到一個未滿的父節點，或是最終需要分裂根節點，從而增加樹的高度。
![Screenshot 2025-03-22 at 4.52.15 PM](https://hackmd.io/_uploads/BJprqg23yl.png)

**2-3 樹的 Insertion 有三個 case:**
`case1:` Node 只有1個 Key，那就插入 NewItem 變成第二個 Key。
:::spoiler 圖示
![Screenshot 2025-03-22 at 4.59.37 PM](https://hackmd.io/_uploads/rkUb3lh3kl.png)
:::
`case2:` 欲插入的 Node 已經有兩個 Key，而它的 Parent 只有一個 Key。那就將中間值上移到 Parent，並且將最大和最小值分開，變成兩個不同的 Node。
:::spoiler 圖示
![Screenshot 2025-03-22 at 5.01.56 PM](https://hackmd.io/_uploads/HJWqnlh31x.png =50%x)
:::
`case3:`欲插入的 Node 已經有兩個 Key，而它的 Parent 也有兩個 Key → 父節點也滿則繼續分裂，可能一路到 root (若根節點也滿，就再分裂根，樹高增加 1)。
:::spoiler 圖示
![Screenshot 2025-03-22 at 5.13.19 PM](https://hackmd.io/_uploads/ByenNk-2h1g.png =50%x)

:::

**練習**
![Screenshot 2025-03-22 at 4.03.06 AM](https://hackmd.io/_uploads/BJYZIBs21g.png =60%x)
:::spoiler 過程
![IMG_8FFE47DDEEEA-1 3](https://hackmd.io/_uploads/ryJqlZhh1l.jpg)
:::

### 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. ![Screenshot 2025-03-31 at 1.27.26 AM](https://hackmd.io/_uploads/By5-kZPayx.png)

:::success
關於刪掉變空的處理：
刪掉變空 → 先借 key，不行再合併 → 合併會讓 parent 變空，再繼續修上去
:::
:::spoiler 中序後繼者
最中間的下一個。
像 34 的 inorder successor 是 35；36 的 inorder successor 是 37。

![Screenshot 2025-03-31 at 1.33.47 AM](https://hackmd.io/_uploads/rkYKgZv6yx.png)
:::

:::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 課程投影片
![Screenshot 2025-03-31 at 3.08.32 AM](https://hackmd.io/_uploads/Bk-TIMD61g.png)

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。
![Screenshot 2025-04-01 at 2.14.45 AM](https://hackmd.io/_uploads/Sk4sjIdTke.png)

* 每個 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 就會先分裂。
:::
![Screenshot 2025-04-05 at 3.13.37 AM](https://hackmd.io/_uploads/HyRvyhT6Jx.png)

![Screenshot 2025-04-05 at 3.12.56 AM](https://hackmd.io/_uploads/rJ8By366yx.png)

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（例如硬碟、資料庫），就反而適合這樣的設計
![Screenshot 2025-04-05 at 2.44.41 AM](https://hackmd.io/_uploads/ryBsdipake.png)

## 單元四 由上而下成長的平衡樹

### 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。
![Screenshot 2025-03-27 at 10.05.52 PM](https://hackmd.io/_uploads/rksHjRz6Jx.png)
![Screenshot 2025-03-27 at 11.25.10 PM](https://hackmd.io/_uploads/SJtyR1makx.png)

### 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 → 先右再左
![Screenshot 2025-03-28 at 12.03.53 AM](https://hackmd.io/_uploads/SJUxvlQaJl.png)


:::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)
![Screenshot 2025-03-27 at 11.23.47 PM](https://hackmd.io/_uploads/SkecaJ7p1g.png)

```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 的排序性質，剛剛好符合左小右大。
![Screenshot 2025-03-28 at 1.23.46 AM](https://hackmd.io/_uploads/Hk0jtZQayg.png)
![Screenshot 2025-03-28 at 1.34.47 AM](https://hackmd.io/_uploads/Sk8L2bmp1x.png)
:::


#### RR：Left Rotation 左旋
---
新節點插在「**不平衡節點的右子節點的右邊**」
```
  10
    \
     20  ← 不平衡節點
        \
         30  ← 插入點（在右的右邊）
```
* 方向：「右」→「右」 → RR
* 解法：LeftRotate(10)
![Screenshot 2025-03-27 at 11.22.27 PM](https://hackmd.io/_uploads/ByMraJXp1x.png)

```c++
  Treenode* RotateLeft (Treenode* x) {
    Treenode* y = x->right;
    x->right = y->left;
    y->left = x;
    return y;
  }
```
![Screenshot 2025-03-28 at 1.36.06 AM](https://hackmd.io/_uploads/BJAi3Z7TJl.png)
:::info
單旋完的樹高只會 shorter or equal
:::


#### LR：先左旋再右旋
---
新節點插在「**不平衡節點的左子節點的右邊**」
```
     30 (x)  ← 不平衡節點
    /
  10 (y)     ← 左子節點
    \
     20  ← 插入點（在左的右邊）
```
![Screenshot 2025-03-27 at 11.46.36 PM](https://hackmd.io/_uploads/rJ3lQl7pJe.png)
* 方向：「左」→「右」 → LR
* 解法：**先讓這個樹變成 LL 的結構，再 RightRotate**。
    * LeftRotate(10)
    * RightRotate(30)

```c++
  Treenode* RotateLR(Treenode* x) {
    x->left = LeftRotate(x->left);  // 先變 LL
    return RightRotate(x);  // 再把 x 右旋
  }
```
![Screenshot 2025-03-28 at 1.54.24 AM](https://hackmd.io/_uploads/rysClMXpJl.png)
![Screenshot 2025-03-28 at 2.25.07 AM](https://hackmd.io/_uploads/Hk6mOfX61e.png)


#### RL：先右旋再左旋
---
新節點插在「**不平衡節點的右子節點的左邊**」
```
  10
    \
     30  ← 不平衡節點
    /
  20    ← 插入點（在右的左邊）
```
![Screenshot 2025-03-28 at 12.00.46 AM](https://hackmd.io/_uploads/B194Uem6ke.png)

* 方向：「右」→「左」 → RL
* 解法： **先讓這個樹變成 RR 的結構，再 LeftRotate**。
    * RightRotate(30)
    * LeftRotate(10)


```c++
  Treenode* RotateRL(Treenode* x) {
    x->right = RightRotate(x->right);  // 先變 RR
    return LeftRotate(x);  // 再把 x 左旋
  }
```
![Screenshot 2025-03-28 at 2.29.31 AM](https://hackmd.io/_uploads/rJpzYMQ6Jx.png)

:::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
---
![Screenshot 2025-04-10 at 12.41.01 AM](https://hackmd.io/_uploads/S1gEQX4Ckg.png)

**Case1**: 4 node 3 key
:::info
2 個 red pointer。
:::
![Screenshot 2025-04-10 at 12.08.44 AM](https://hackmd.io/_uploads/S1t5sMVRyl.png)
![Screenshot 2025-04-10 at 12.44.17 AM](https://hackmd.io/_uploads/ryRJV74Cyg.png)
:::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。
有兩種可能，看大的在上面還是小的在上面。
:::
![Screenshot 2025-04-10 at 12.30.41 AM](https://hackmd.io/_uploads/BJg6gQE0yx.png)
![Screenshot 2025-04-10 at 12.49.15 AM](https://hackmd.io/_uploads/SJ5GSX4C1x.png)
![Screenshot 2025-04-14 at 9.12.58 PM](https://hackmd.io/_uploads/ryhW9t5C1l.png)
Ans: 8 (2^3，每個 three node 的有兩個可能)
**Case2**: 2 node 1 key
:::info
2 個 black pointer。
:::

![Screenshot 2025-04-10 at 12.56.05 AM](https://hackmd.io/_uploads/HkgnI7VAyx.png =50%x)

### 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 
![IMG_479C2F5DAF4F-1](https://hackmd.io/_uploads/HkTCNFSAke.jpg)
![IMG_5572CCAE74A1-1](https://hackmd.io/_uploads/rkV1BFHCke.jpg)

### Red-Black Tree & AVL Tree 的比較
---
::: info
Red-Black Tree：插入刪除快，查找略慢但夠穩定
AVL Tree：查找快，刪除慢，適合查詢導向應用
:::

如果升序插入1-10到 Red-Black Tree & AVL Tree：
![期中考準備](https://hackmd.io/_uploads/S1ukiKrCye.jpg)
![IMG_CF543C57643F-1](https://hackmd.io/_uploads/ryzxjFHA1e.jpg)


#### 📊 表格比較

| 比較項目              | 🔴 Red-Black Tree                               | 🟢 AVL Tree                                      |
|-----------------------|--------------------------------------------------|--------------------------------------------------|
| 📐 平衡方式           | 顏色規則維持近似平衡（紅 / 黑）                 | 使用平衡因子（左右子樹高度差）嚴格平衡           |
| 📏 平衡程度           | 沒那麼平衡（最多比理想高度高兩倍）                    | ==更接近完全平衡，這也是為什麼在 Search （搜尋） 時 AVL 更吃香==  |
| 🔁 插入／刪除效率     | ==插入/刪除操作較快==，最多 O(log n) 次旋轉           | 插入最多旋轉 1 次，刪除複雜，可能多次旋轉         |
| 🚀 查找效率           | 較慢（因為樹高較高）                             | ==較快（因為更平衡）==                                |
| ⚙️ 旋轉次數（插入）   | 最多 2 次                                        | 最多 1 次                                        |
| ⚙️ 旋轉次數（刪除）   | 較少，操作簡單                                   | 較多，邏輯複雜 (在動態環境表現較不好)                 |
| 📦 結構儲存開銷       | 每個節點需記錄顏色（紅 / 黑）                    | 每個節點需記錄平衡因子或高度                      |
| 📚 適用場景           | 插入/刪除頻繁的資料結構（如 STL map/set）         | 查詢為主的資料結構（如資料庫索引）               |

---
✅ 優缺點整理
🔴 Red-Black Tree

- ✅ 插入與刪除成本低、效率穩定
- ✅ 實作不需記錄高度，只需記錄顏色
- ❌ 查找效率略低（因為樹高較大）
- ❌ 相對不那麼平衡

🟢 AVL Tree

- ✅ 保證更平衡 → 查找速度快
- ✅ 適合查詢密集的應用
- ❌ 刪除較複雜，需多次旋轉
- ❌ 實作需要追蹤平衡因子或高度

![Screenshot 2025-04-11 at 6.27.12 PM](https://hackmd.io/_uploads/B1gqAwI01x.png)

### Red-Black Tree Delete

---

分成兩階段：
1. 用 Binary Search Tree 的方式刪除節點
   * 兩個小孩：拿 inorder successor 去補。
   * 一個小孩：拿唯一的小孩補。
   * 沒小孩：直接刪。

2. 如果刪掉的是黑色節點 → 啟動 Fix-up（補黑）機制
➤ 目的：維持紅黑樹的「黑高度一致」規則

![一點點筆記-1](https://hackmd.io/_uploads/ryYhMO50yl.jpg)

![一點點筆記-2](https://hackmd.io/_uploads/SJxpMu5CJl.jpg)


## 單元五 Hash 雜湊

**基本概念**
Hash 是一種將資料的 key 經由 hash function 映射成陣列中的 index，讓我們可以在幾乎固定的時間內（O(1)）快速存取、插入或刪除資料的技術。

它就像一個自動分配置物櫃的系統，不需要一個個搜尋，只要知道 key，就能直接找到對應的位置。若兩個不同的 key 映射到同一個位置，就稱為 collision，這時就需要特別的處理方式（如 chaining 或 probing）來解決。
![Screenshot 2025-04-11 at 6.40.01 PM](https://hackmd.io/_uploads/SJ15W_80ye.png)
Perfect hash 是理論中的理想情況，現實中我們通常要處理 collision（碰撞）。

![Screenshot 2025-04-11 at 6.37.09 PM](https://hackmd.io/_uploads/SJQkWd8Cyx.png)

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

![Screenshot 2025-04-11 at 7.05.05 PM](https://hackmd.io/_uploads/B1ZdDOLAkl.png)
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。

---

![Screenshot 2025-04-11 at 7.34.36 PM](https://hackmd.io/_uploads/SJdICdLCke.png)
→ 用每三位做 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
---
![Screenshot 2025-04-11 at 7.59.21 PM](https://hackmd.io/_uploads/SyPXNYICke.png)
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`
![Screenshot 2025-04-11 at 8.00.10 PM](https://hackmd.io/_uploads/S1IU4F8Akg.png)

:::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 方法中，當多個元素碰撞後，被放到相鄰位置時，會形成一段連續的「鏈」狀區塊，新的元素如果也撞進來，就會往後塞，鏈越來越長，查找、插入效率會下降。
![Screenshot 2025-04-11 at 8.54.40 PM](https://hackmd.io/_uploads/r11QZqLCkx.png)

:::
| 名稱               | 意思                                                                 |
|--------------------|----------------------------------------------------------------------|
| **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 會依照==平方距離==繼續往後找：

![Screenshot 2025-04-11 at 10.43.50 PM](https://hackmd.io/_uploads/rJM2coI0yx.png)
（original）
![Screenshot 2025-04-11 at 10.44.21 PM](https://hackmd.io/_uploads/B1bRqs8Ryl.png)
(collision: 放在 5 + 1^2 的位子)
![Screenshot 2025-04-11 at 10.45.50 PM](https://hackmd.io/_uploads/HyqQjoIRJe.png)
(collision: 放在 5 + 2^2 的位子，但因為超過 hash table size 故 module 7 得到 2，放在 2 的位子)
![Screenshot 2025-04-11 at 10.48.03 PM](https://hackmd.io/_uploads/Sk1nijURkl.png)

| 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 **互質**，才能保證每一格都能訪問
![Screenshot 2025-04-12 at 12.06.03 PM](https://hackmd.io/_uploads/Bk_3UDP0yx.png)
:::info
Primary Hash Function：h1 = sum % 7
Secondary Hash Function（Step size）：h2(key) = 5 - (sum % 5)，5 是自訂的，整個 h2 都可以自訂。 
:::
![Screenshot 2025-04-12 at 12.08.50 PM](https://hackmd.io/_uploads/BJ1wPvvC1e.png)
sum = 15， h1(15) = 15 % 7 = 1 h2(1) = 5 - (15 % 5) = 5
index 1 發生 collision 用 h2 去計算 step size，結果是放在 1 + 5 的位置。
![Screenshot 2025-04-12 at 12.11.57 PM](https://hackmd.io/_uploads/BkjzdPPAke.png)
h1(36) = 36 % 7 = 1
h2(1) = 5 - (36 % 5) = 4
結果：放在 1 + 4 = 5 的位置。
![Screenshot 2025-04-12 at 12.13.34 PM](https://hackmd.io/_uploads/B1sddPwA1e.png)
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 會要求是質數。
:::
![IMG_A80EF517723E-1](https://hackmd.io/_uploads/S1YrCPPA1x.jpg)

### 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**
![Screenshot 2025-04-12 at 12.48.36 PM](https://hackmd.io/_uploads/HJb3x_wAJg.png)
- 缺點：
    - 需要做記憶體管理，可能像前一個節點的 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 有沒成功：
- 如果沒有成功就會花很多額外的時間![Screenshot 2025-04-12 at 1.11.18 PM](https://hackmd.io/_uploads/HyXWUdvAyx.png)

:::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 比較次數計算

![Screenshot 2025-04-12 at 1.58.53 PM](https://hackmd.io/_uploads/Bkj7btw0yx.png)

**為什麼會是 `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  |

訂正：
![Screenshot 2025-04-13 at 12.57.56 PM](https://hackmd.io/_uploads/HJ4hEauCJg.png)
| 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%**        |

![Screenshot 2025-04-13 at 1.13.19 PM](https://hackmd.io/_uploads/B1Cl_auA1g.png)
A: 2.9
11 * 19 + 1 *81

## 一些期中線上測驗的複習

![IMG_89B7C6960737-1](https://hackmd.io/_uploads/rkyIMR_Ckg.jpg)

![IMG_C727712D7FFA-1](https://hackmd.io/_uploads/H1OLXRO0Jx.jpg)

![IMG_736505C9A930-1 2](https://hackmd.io/_uploads/SkMZSROCyl.jpg)

Huffman tree 的 root 是由所有子節點合併出來的，不是原始某個 character。
Huffman tree 不是 balanced binary tree。可能是非常不平衡的，根據字元出現的頻率來決定深度。

![IMG_869D8D5F2FD7-1](https://hackmd.io/_uploads/rk4QHAOCkg.jpg)

![IMG_F99973917AEA-1](https://hackmd.io/_uploads/Hkgb_CuCJe.jpg)
| 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|

![IMG_C68E7ECFFB89-1](https://hackmd.io/_uploads/BJSTRA_0Jx.jpg)

![IMG_14BA32E9D374-1](https://hackmd.io/_uploads/BJzuz1KAyx.jpg)
![IMG_2CCBCFCF9261-1](https://hackmd.io/_uploads/rk4oE1Y0Jg.jpg)

![IMG_B92C9CA6185C-1](https://hackmd.io/_uploads/Byz2H1YCyx.jpg)

![IMG_8744B6C67A25-1](https://hackmd.io/_uploads/rkGfPJF0Jg.jpg)

![IMG_4730F741B3D9-1](https://hackmd.io/_uploads/BJKqukYRkl.jpg)

![IMG_88EC980BEA2A-1](https://hackmd.io/_uploads/H1WnhkF0yx.jpg)
![IMG_29CD5B4BF3DA-1](https://hackmd.io/_uploads/HyRV61tCJe.jpg)
