[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 時
步驟為 :
> **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 版]**
### 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 作法
- 兩點 :
- 
- 
- 三點 :
- LL
- RR
- LR
- RL
## 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)$ |
Sign in with Wallet
Connect another wallet