---
# System prepended metadata

title: 高等樹結構
tags: [資料結構, 高等樹結構]

---

[toc]
# 高等樹結構
## Min-Max Heap
### Min-Max Heap 定義
是一個 Complete Binary Tree，可用來製作 Doubled-Ended Priority Queue，且 Min-Max Heap 滿足 : 
- 此樹的 level 是以 min-level 與 max-level 交互出現
- root 位於 min-level
- 若 x 位於 min-level，則代表以 x 為 root 為子樹中，x 具有最小值
- 若 x 位於 max-level，則代表以 x 為 root 為子樹中，x 具有最大值

### Min-Max Heap 中插入某元素 x
步驟為 : 
1. x 先放置在 the last node 的下一個位置，令此位置值為 n
2. 令 x 的父點為 p，p 可能為 min-level 或 max-level
3. 分成下列 cases
    - case 1 : P 為 min-level
        ```cpp=
        if (x < ary[p]) {
            ary[n] = ary[p];
            verifyMin(ary, p, x);
        }else
            verifyMax(ary, n, x);
        ```

    - case 2 : P 為 max-level
        ```cpp=
        if (x > ary[p]) {
            ary[n] = ary[p];
            verifyMax(ary, p, x);
        }
        else 
            verifyMin(ary, n, x);
        ```

> $T(n) = O(logn)$

### Min-Max Heap 中刪除最小值
步驟為 : 
1. 移走 root 的 data
2. 將 the last node x 刪除
3. x 插入到一個 root 為空的 Min-Max Heap 中，依最小值所在位置分為三種 cases
    - case 1 : root 無子點，則將 x 置入 root 中
    - case 2 : root 的子孫當中的最小值為 root 左右子點其中之一，令其值為 k (root 左右子點的子點的子樹沒長滿)
        ```cpp=
        if (k < x)
            x 和 k 互換位置;
            goto 3.;
        else
            x 置入 root 中;
        ```
    - case 3 : root 子孫中最小值為 root 的孫子中其中一個，令其值為 k，其父點為 p
        ```cpp=
        if (k < x)
            k 置入 root;
            if (x > p)
                x 和 p 互換;
            goto 3.;
        else
            x 置入 root;
        ```

> $T(n) = O(logn)$

## Deap (Doubled-Ended Heap)
### Deap 定義
是一個 Complete Binary Tree，可用來製作 Doubled Ended Priority Queue，Deap 滿足 : 
- root 不存 Data
- root 的左子樹是 Min Heap
- root 的右子樹是 Max Heap
- 若 i 為 Min Heap 中之某個 node，令 j 為 i 在 Max Heap 之相對應 node，則 Deap[i] $\le$ Deap[j]

### Deap 中插入某元素 x
步驟為 : 
1. x 先暫存於 the last node 之下一個位置，令此位置為 n
2. 依照 x 所在位置分兩個 cases
    - case 1 : x 位於 Min Heap 中，假設與 x 對應的 Max Heap 位置為 j
        ```cpp=
        if (x > ary[j]) {
            ary[n] = ary[j];
            MaxHeapInsert(ary, j, x);
        }else
            MinHeapInsert(ary, n, x);
        ```
    - case 2 : x 位於 Max Heap 中，假設與 x 對應的 Min Heap 位置為 j
        ```cpp=
        if (x < ary[j]) {
            ary[n] = ary[j];
            MinHeapInsert(ary, j, x);
        }else
            MaxHeapInsert(ary, n, x);
        ```

> $T(n) = O(logn)$

### Deap 中刪除最小元素
步驟為 : 
1. Deap[2] 因為是最小值，所以 Data 移走，留下一個 Empty
2. 刪掉 the last node x
3. 左子樹之 root 之 Empty 由其 min(左子,右子) 替補，而新的 Empty 也如此遞補，直到 Empty 到 Min Heap 中的 leaf 為止
4. 執行 Deap 的插入 x 運作 at Empty

> $T(n) = O(logn)$

## Symmetric Min Max Heap (SMMH)
### Symmetric Min Max Heap 定義
是一個 Complete Binary Tree 且 root 不存 Data，可用來製作 Doubled Ended Priority Queue，SMMH 滿足 : 
- 左兄弟 $\le$ 右兄弟
- 若 node x 有祖父，則祖父的左子點必須 $\le$ x
- 若 node x 有祖父，則祖父的右子點必須 $\ge$ x

即衍生出 : 
- node i 的左子點是以 i 為 root 之子樹中 (不含 i) 之最小值
- node i 的右子點是以 i 為 root 之子樹中 (不含 i)之最大值

### Symmetric Min Max Heap 中插入某元素 x
步驟為 : 
1. x 先暫置 the last node 之下一個位置
2. verify 是否滿足左兄弟 $\le$ 右兄弟，若否，交換至正確位置
3. 以 bottom up 方式，驗證是否祖父的左子點小於 x，祖父的右子點大於 x，若未滿足，調整到正確位置 (要跟自己的爸爸和爸爸的兄弟比較，非跟祖父比較)

### Symmetric Min Max Heap 中刪除最小值
步驟為 : 
1. 移走左子樹 root 的 Data，形成一個 Empty
2. 將 the last node x 刪除
3. 調整直到符合 SMMH 定義
    ```cpp=
    repeat {
        
        若 左子點大於右子點
            兩值互換
        
        先比 Empty 的左子點及 Empty 右兄弟的左子點，找出最小值，設為 y
        
        再將 x 跟 y 比最小值
        if x < y
            x 置入 Empty
        else
            y 置入 Empty
            
    } 直到符合 SMMH 定義
    ```

## Extended Binary Tree
### Extended Binary Tree 定義
Binary Tree 若有 n 個 node，以 link list 表示，則有 n+1 條 Null links，在這些 Null links 上加上特殊節點稱為 External Node 或 Failure Node，其餘 node 稱為 Internal Node

### Extended Binary Tree 其他考題
- $外部\ node\ 數 = 內部\ node\ 數 + 1$
- 有些版本定義不同 : 
    - External Node 當 leaf
    - Internal Node 當 non-leaf
- 常考路徑長度 : 
    - $Internal\ path\ length = \sum(root\ 到內部\ node_i\ 之路徑長)$
    - $External\ path\ length = \sum(root\ 到外部\ node_j\ 之路徑長)$
- $External\ Node = Internal\ Node + 2*Node$

## Weight External Path Length (WEPL)
### Weight External Path Length 定義
給予 Extended Binary Tree n 個 external node 之加權值，令為 $q_i$，則 $WEPL = \sum(root\ 到\ external\ node\ 之路徑長 * q_i)$

### Weight External Path Length 最小值
給予 n 個 external nodes 加權值 $q_i$，則在 $\frac{1}{n}\binom{2n-2}{n-1}$ 棵不同的 Extended Binary Tree 中，找出 WEPL 之最小值 (有 n 個 external nodes 代表有 n-1 個 internal nodes)

使用 **Huffman Algorithm** 求 min WEPL 值
步驟為 : 
1. 令 $W = \{external\ nodes\ 加權值\}$ 之集合，令有 n 個加權值
2. 從 $W$ 中取出兩個 min weight，建立 Extended Binary Tree
3. 且此兩個加權值之和，視為新權值再加入 $W$ 中
4. 上述 2. ~ 3. 重複直到 $W$ 中只剩下一個權值，即共做 n-1 次

```cpp=
Huffman(W : 加權集合, n : node 個數) {

    for i = 1 to n-1 {
        t = new_Node();
        t -> Lchild = W.deleteMin();
        t -> Rchild = W.deleteMin();
        t -> weight = (t -> Lchild) -> weight + (t -> Rchild) -> weight;
        Insert(W, t);
    }
    
}
```

> $T(n) = O(nlogn)$

### Weight External Path Length 應用
- n 個 messages 要編碼傳輸，求最小的平均編碼位元長度或最小的平均解碼時間的編碼內容

### Weight External Path Length 其他考題
- 在有加權值影響下，不見得樹高越小，WEPL 值越小
- Huffman Algorithm 採取 Greedy strategy (Greedy 不保證可以求出最佳解)
- 可以利用 Greedy 求出的 optimal solution 有 : 
    - Huffman Algorithm 求 minimal weight 印 string
    - 求 Minimum Spanning Tree
        - Kruskal's Algorithm
        - Prim's Algorithm
    - Dijkstra's Algorithm
    - Fractional Knapsack Problem

## AVL Tree
### AVL Tree 緣由
在面對 Dynamic Data 情況下，Binary Search Tree 中有可能形成 Skewed Binary Search Tree，使得搜尋、插入、刪除等等操作會得出 $O(n)$ 之最糟情況

因為希望有一種 Binary Seatch Tree 可以動態地維持高度之最小化(平衡化)，即 $O(logn)$ 之高度，如此，搜尋、插入、刪除等等操作就可以得到 $O(logn)$ 之最佳情況

### AVL Tree 定義
是一個 Height Balanced Binary Search Tree， 若不為空，則滿足 : 
- $|H_L-H_R|\le1$，$H_L\ 及\ H_R$ 為左右子樹高度
- 左右子樹也是 AVL Tree

### AVL Tree 插入刪除
插入刪除操作前處理與 Binary Search Tree 一樣，但若有不平衡，則 bottom up 調整不平衡的點

### AVL Tree 的平衡係數 (Balance Factor)
為該 node 的 $H_L-H_R$，在 AVL Tree 中，任何 node 的平衡係數值只有 3 種可能 : +1、0、-1

AVL Tree 之不平衡 : 
若新插入之 node，會導致某個離他最近的 node 變成不平衡，看此新點在這個不平衡的什麼子樹方向(只看兩層子樹)，分成四種狀況 : 
- case 1 : LL 不平衡
- case 2 : LR 不平衡
- case 3 : RL 不平衡
- case 4 : RR 不平衡

<br>

調整之兩大原則 : 
- 中間鍵值往上拉，小的放左，大的放右
- 孤兒之子樹依 Binary Search Tree 性質及可置入正確位置

<br>

旋轉 : 
- LL、RR $\rightarrow$ single rotation
- LR、RL $\rightarrow$ double rotation

### AVL Tree 其他考題
- 操作時發生 rotation 的次數
    - 插入某元素 x 頂多發生一種 rotation
        > $O(1)$
    - 刪除某元素 x 可能發生多種 rotation
         > $O(logn)$
- 要形成高度為 h 的 AVL Tree，所需的最少 node 數為 $F_{n+2}-1$，最多 node 數為 $2^n-1$
- AVL Tree 又叫 Fibonacci Binary Tree
- 比較表 
    | operation | Array | Link List | AVL Tree |
    | -------- | -------- | -------- | --- |
    | search for x | $O(logn)$ | $O(n)$ | $O(logn)$ |
    | search for kth item | $O(1)$ | $O(k)$ | $O(logn)$ |
    | delete x | $O(n)$ | $O(1)$ | $O(logn)$ |
    | delete kth item | $O(n-k)$ | $O(k)$ | $O(logn)$ |
    | insert x | $O(n)$ | $O(1)$ | $O(logn)$ |
    | inorder traversal | $O(n)$ | $O(n)$ | $O(n)$ |
- Rotation 時間為 $O(1)$

## M-way Serch Tree
### M-way Search Tree 定義
用在 external search 或 external sort 中，由於資料量太大，無法一次全部置於 memory 中進行搜尋，必須使用外部儲存體保存，再分批載入 search

因此，在 disk 中，通常用 M-way Search Tree 組織 Data Block (加大 M，可有效降低 Tree 高度，降低 I/O 次數，效能上升)

此外，規定 2 $\le$ M-way Search Tree 的 degree $\le$ m

> external search : 例如 M-way Search Tree
> internal search : 例如 AVL tree, Binary Search Tree 等等
### M-way Search Tree 其他考題
- M-way Search 有 n 個 nodes，求最小高度
    - h = $\lceil log_m(n+1)\rceil$
- 高度為 h 的 M-way Search tree，求
    - 最多 node 數為 $\frac{m^h-1}{m-1}$
    - 最多 key 數為 $m^h-1$

## B tree
### B tree 定義
是一個 Balanced M-way Search Tree，主要用於 external search/sort 中，滿足

- root 至少有兩個子點，最多 m 個 (即 2 $\le$ root degree $\le$ m)
- 除了 root 及 failure nodes 之外，其餘 node 的 degree 為 $\lceil \frac{m}{2}\rceil\ \le$ node degree $\le m$ (或 $\lceil\frac{m}{2}\rceil-1\ \le$ key 數 $\le m-1$)
- 所有 failure nodes 均位於同一層 level 上

> **2-3 Tree**
> 也就是 B Tree of Degree 3
> 因為整棵樹只有兩類 nodes (2-node 或 3-node)
> 即 $2 \le$ degree $\le 3$

> **2-3-4 Tree**
> 也就是 B Tree of Degree 4
> 因為整棵樹只有三類 nodes (2-node 或 3-node 或 4-node)
> 即 $2 \le$ degree $\le 4$

### B Tree 插入某元素 x 在 order 為 m 時
步驟為 : 
1. 先 search for x，找出適當的置入 node 且在該 node 內置入 x
2. 檢查該 node 是否 overflow
    - case 1 : 沒有 overflow
      即 key 數 $\le$ m-1
      則 exit
    - case 2 : overflow 了
      即 key 數 $\gt$ m-1
      則須執行 split 處理，且處理完後，需針對父點對2.步驟重複
      
> **Split 處理**
> 拉第 $\lceil \frac{m}{2}\rceil$ 個 key 到父點，其餘左右分裂成兩個子點

### B Tree 刪除某元素 x 在 order 為 m 時
步驟為 : 
![image](https://hackmd.io/_uploads/rJieo9loA.png)

> **Rotation 處理**
> 跟有最多 keys 的兄弟借 (兄弟必須 keys 數 $\gt\lceil\frac{m}{2}\rceil-1$)
> 兄弟不夠才跟父點借 key

> **Combine 處理**
> 跟父點借 key
> 再跟剛剛不夠 key 的兄弟合併

### B Tree 其他考題

- 高度為 h 的 B tree，求
    - 最多 node 數為 $\frac{m^h-1}{m-1}$
    - 最多 key 數為 $m^h-1$
    - 最少 node 數為 $1+2*\frac{\lceil\frac{m}{2}\rceil^{h-1}-1}{\lceil\frac{m}{2}\rceil-1}$
    - 最少 key 數為 $2*\lceil\frac{m}{2}\rceil^{h-1}-1$

> AVL Tree 解決 Skewed Binary Search Tree
> B Tree 解決 Skewed M-way Search Tree

## B+ Tree
### B+ Tree 定義
B Tree 的變種，主要用於支持 Index Sequential Access Method (ISAM) 方法，常用於資料庫管理系統之內層製作

主要分為兩大 layers : 
- Index Layer : 採 B Tree 結構
- Data Blocks Layer : 以 link list 串聯，所有 data 均放於 data blocks

## Red-Black Tree
### Red-Black Tree 定義

**[Algo 版]**

是一個 Balanced Binary Search Tree，滿足 : 
- node 的顏色非黑即紅
- root 一律為黑色
- Null 一律為黑色
- 紅色 node 的兩個子點必定要是黑色 (相當於任何 path 不可以出現連續的紅色節點)
- root 到不同的 leaf 路徑上，皆有相同數的黑色 node 數

<br>

**[DS 版]**

是 2-3-4 Tree 對應的 Binary Search Tree，此 Binary Search Tree 滿足 : 
- link 的顏色非黑即紅
- 若此 link 原本在 2-3-4 Tree 中已存在，則視為黑色 link，否則視為紅色 link
- 任何 path 上不可出現連續的紅色 link
- root 到不同 leaf 的 path，皆具相同數的黑色 link

### Red-Black Tree 插入某元素 x

**[Algo 版]**

步驟為 : 
1. 先 Search for x
2. 在搜尋 x 時，所經過的 nodes 中，若有遇到某個 node 的兩個子點為紅色的話，需先做 color change，做完後，檢查有無連續的紅色 nodes，若有，則須做 rotation 處理
3. 此時，才置入 x 於正確位置，且新點一定標為紅色
4. 檢查有無連續的紅色 nodes，若有，則須做 rotation 調整
5. root 一律改為黑色

> **Rotation 調整**
> 分為 LL、LR、RL、RR四種 rotation
> 類似 AVL Tree，但要加上顏色設定
> 中間鍵值往上拉，標為黑色
> 小放左，大放右，這兩個子點標為紅色

### Red-Black Tree 轉換規則

**[DS 版]**

![image](https://hackmd.io/_uploads/SknCwyfi0.png =70%x)


### Red-Black Tree 其他考題
- 紅黑樹的插入、搜尋、刪除都是 $O(logn)$
- Rotation 的時間為 $O(1)$

## Optimal Binary Search Tree
### Optimal Binary Search Tree 定義
給予 n 個內部 nodes 加權值，令為 $p_i$，$1\le i\le n$ 及 n+1 個外部 nodes 加權值，令為 $q_j$，$0\le j\le n$

則在 $\frac{1}{n+1}\binom{2n}{n}$ 棵不同 Binary Search Tree 中，具有最小搜尋總成本的 Binary Search Tree，稱為 Optimal Binary Search Tree

而搜尋總成本 $=$ 成功搜尋 cost $+$ 失敗搜尋 cost，其中，
成功搜尋 cost $=$ $\sum (內部\ node_i\ 之\ level\ 值\ *\ p_i)$
失敗搜尋 cost $=$ $\sum [(外部\ node_j\ 之\ level\ 值-1)\ *\ p_j]$

### Optimal Binary Search Tree 用 DP 求

**假設** :
$a_{i+1}\ , a_{i+2}\ ,...,\ a_{j}$ 是內部節點且 $a_{i+1} < a_{i+2} < ... < a_{j}$
令 $p_{i+1}\ ,p_{i+2}\ , ... ,\ p_{j}$ 是內部節點的加權值， $q_i\ , q_{i+1}\ , ...,\ q_{j}$ 是外部節點的加權值

**定義** :
$T_{ij}$ 是由 $a_{i+1}\ , a_{i+2}\ , ...,\ a_{j}$ 構成的 OBST，令 
$c_{ij}$ 代表 $T_{ij}$ 的 cost
$r_{ij}$ 代表 $T_{ij}$ 的 root
$w_{ij}$ 代表 $T_{ij}$ 的內外部節點加權值和

因為 $T_{i,i}$ 是空樹，所以 $c_{i,i} = 0$，$r_{i,i} = NULL (或\ 0)$，$w_{i,i} = q_i$

**推算 $c_{i,j}$ 公式 :**
先在點 $a_{i+1}\ 到 a_j$ 中隨便選一個點當作 root，假設為 $a_k$，則以 $a_k$ 為 root 的最佳左子樹為 $T_{i, k-1}$，最佳右子樹為 $T_{k, j}$，此時
$c_{i,j} = 1*p_k + w_{i, k-1} + w_{k, j} + c_{i, k-1} + c_{k, j}$ 
$\quad \ = w_{i, j} + c_{i, k-1} + c_{k, j}$

故最優 root $a_k$ 要符合
$c_{i,j} = w_{i,j} + \displaystyle\min_{\ i+1\ \le k\ \le\ j} \{c_{i, k-1} + c_{k, j}\}$

> 乘 1 是因為 root 只比一次
> 而多加 $w_{i, k-1}$ 和 $w_{k, j}$ 是因為他們從原本自己為樹，變成別人的子樹，level 降一，要再多比較一次
> $p_k + w_{i, k-1} + w_{k, j} = w_{i, j}$


> $T(n) = O(|V|^3)$

:::warning
若是規定到 level 為 i 的外部節點的比較次數為 i+1 ( 比到此外部節點的父點後需要再比一次) 的話，則 $c_{i, j}$ 要比上述算的 $c_{i, j}$ 再多加 $\displaystyle\sum_{k=i}^{j}q_k$
即為 $c_{i,j} = w_{i,j} + \displaystyle\min_{\ i+1\ \le k\ \le\ j} \{c_{i, k-1} + c_{k, j}\} + \displaystyle\sum_{k=i}^{j}q_k$
:::

### Optimal Binary Search Tree 其他考題
- 在有加權值影響下，高度越小不一定 search cost 越小

## Splay Tree
### Splay Tree 緣由

|  | AVL Tree、B Tree | Splay Tree |
| -------- | -------- | -------- |
| **調整過程** | 複雜 | 簡單 |
| **實際成本** | $O(logn)$ | $O(n)$ |
| **分攤成本** | $O(logn)$ | $O(logn)$ |

### Splay Tree 定義
是一個 BST，操作與 BST 相同，差別是每一次運算之後，必須針對 splay 起點，進行 splay 運算，目的是把 splay 起點變成 root，且根據不同運算更改不同 splay 起點

|  | splay 起點定為 |
| -------- | -------- |
| Insert x | x 定為新 splay 起點 |
| Search x | x 定為新 splay 起點 |
| Delete x | x 的父點定為新 splay 起點 |

### Splay Tree Rotations 作法
- 兩點 : 
    - ![image](https://hackmd.io/_uploads/SkjOC92jA.png =60%x)
    - ![image](https://hackmd.io/_uploads/BkGcAq3sC.png =60%x)

- 三點 : 
    - LL
        ![image](https://hackmd.io/_uploads/B1Zp0q3s0.png =80%x)
    - RR
        ![image](https://hackmd.io/_uploads/BJS1Jinj0.png =80%x)
    - LR
        ![image](https://hackmd.io/_uploads/SJkZyo3iR.png =80%x)
    - RL
        ![image](https://hackmd.io/_uploads/HJofJoniA.png =80%x)

## Leftist Heap (= Min/Max Leftist Tree)
### Leftist Heap 緣由

|  | Heap | Leftist Heap |
| -------- | -------- | -------- |
| Insert x | $O(logn)$ | $O(logn)$ |
| Delete x | $O(logn)$ | $O(logn)$ |
| Merge 兩個 Heap | $O(n)$ | $O(logn)$ |

### Leftist Heap 定義
先定義 shortest(x) 值，令 x 為 extended Binary Tree 之 node，則 
$shortest(x) = \left\{ 
\begin{array}{l}
  0 \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad if\ x\ 是外部節點\\
  1 + min\left\{ 
\begin{array}{l}
  shortest(x \rightarrow Lchild)\\
  shortest(x \rightarrow Rchild) \qquad\ \ if\ x\ 是內部節點
\end{array}
\right.
\end{array}
\right.$

再定義 Leftist Tree，即對任何 node x 皆滿足 $shortest(x \rightarrow Lchild) \le shortest(x \rightarrow Rchild)$

最後才定義 Leftist Heap (Min Leftist Tree)，是一個 Leftist Tree，且也是 Min-Tree，即父點 $\le$ 子點

### Leftist Heap 合併
步驟為 : 
1. 比較兩個 Tree 的 root，找出最小 root，不失一般性，假設 H1 的 root 最小
2. H1 的 root 作為 new root，且 H1 的左子樹保留成 new root 的左子樹
3. Merge H1 的右子樹及 H2，成為 new root 的右子樹
4. 重複步驟 1.~3. 直到成為一顆 Min-Tree
5. 檢查是否符合 Leftist Tree，若不符合，則 swap 調整

### Leftist Heap 刪除最小
步驟為 : 
1. 刪除 root，得到兩個子樹 H1、H2
2. 合併 H1、H2

### Leftist Heap 插入某元素 x
步驟為 : 
1. x 自己成為 1 個 Leftist Heap H1
2. 合併 H1、H2


## Binomial Heap
### Binomial Heap 定義
先定義 Binomial Tree，令 root 的 level 為 0，並定義
$B_0$ : 代表高度為 0 的 Binomial Tree，只有 root 一個點
$B_k$ : 代表高度為 k 的 Binomial Tree，是由 2 個高度為 k-1 的 $B_{k-1}$ 組成，任一個 $B_{k-1}$ 之 root 為 new root，另一個 $B_{k-1}$ 為他的子樹

再定義 Binomial Heap，是由一組 Binomial Tree 組成的集合 (或 forest)，且每顆 Tree 必須是 Min Tree

> 另有定義 Binomial Heap 具以下特性
> 1. **Parent Pointer** : 由子點指向父點的單向鏈結串列，root 之 Parent Pointer 為 NULL
> 2. **Leftmost Child Pointer** : 由父點指向最左子點的單向鏈結串列
> 3. **Sibiling Pointer** : 由 sibling 指向 sibling 的雙向鏈結串列，且 root 之間也視為 sibling
> 4. **Minimum Pointer** : 一個指向最小 root 之 pointer

### Binomial Heap 合併
- 懶惰合併 : 
    步驟為 : 
    1. root 間之雙向鏈結串接即可，minimum pointer 重設
    
    > $T(n) = O(1)$
- 勤勞合併 : 
    步驟為 : 
    1. 具有相同高度的 Binomial Trees 需合併成一顆 Tree，合併時，較小的 root 為 new root，另一個為其子樹 (習慣先合併高度小的)
    2. 重複直到無高度相同之 Binomial Tree

    > $T(n) = O(logn)$
    > 因為最多有 $O(log(n+1))$ 棵樹要合併，又合併一棵樹需要 $O(1)$

### Binomail Heap 插入某元素 x
步驟為 : 
1. 讓 x 自己成為一個 Binomial Heap H1
2. 合併 H1、H2

> $T(n) = O(1) \ 或\ O(logn)$

### Binomial Heap 刪除最小元素
步驟為 : 
1. 找出 root 最小值，令此樹為 T，其他樹之集合為一個 Binomail Heap H1
2. 刪除 T 之 root，得到 T 子樹之集合，令為 H2
3. 合併 H1、H2

> $T(n) = O(logn)$

### Binomial Heap 其他考題
- Binomial Tree $B_k$ 之第 i level 的 node 數為 $\binom{k}{i}$
- Binomial Tree $B_k$ 之 node 總數為 $2^k$
- 若 node 數為 n，則 Binomial Tree $B_k$ 的 k 為 $logn$



## Fibonacci Heap (Extended Binomial Heap)
### Fibonacci Heap 定義
是 Binomial Heap 的 superset，又叫做 Extended Binomial Heap，除了 Binomial Heap 原本的插入元素、刪除最小值、合併這三個運算以外，還多了另外兩個動作，分別是刪除節點及減少鍵值

### Fibonacci Heap 刪除節點 x
步驟為 : 
1. 若 x 為 minimum pointer 指向的值，則執行刪除最小值的運算
2. 否則，從所屬雙向 pointer list 中刪除 x，將 x 之各子樹之雙向鏈結串列與 root 間雙向鏈結串接，具有相同高度之 Binomial Tree 合併

> $T(n) = O(logn)$

### Fibonacci Heap 減少鍵值
若是減少鍵值後會影響 Min Heap 的性質，則將減少鍵值的子樹獨立出來，若是減少鍵值後會成為 minimum，則將 minimum pointer 指向減少鍵值的 node

> $T(n) = O(1)$

### Fibonacci Heap 其他考題
- | 運算 | 時間 |
    | -------- | -------- |
    | 合併兩個 Heap | $O(logn)$ |
    | 刪除最小值 | $O(logn)$ |
    | 尋找元素 x | $O(1)$ (有 minimum pointer 時) |
    |  | $O(logn)$ (沒有 minimum pointer 時) |
    | 插入元素 x | $O(1)$ |
    | 減少鍵值 | $O(logn) |
    | 刪除元素 x | $O(logn)$ |
    
