考研相關文章參考資料為 wjungle 大神提供的筆記

Doubled-ended priority Queue

兩端皆可插入元素，一端提供 deleteMax，一端提供 deleteMin
資料結構:
- Min-Max Heap
- Deap
- SMMH
提供操作:
- Insert x
- Delete-Max
- Delete-Min

Min-Max Heap

是一個 Complete BT，並且滿足:
- level 以 min-level 與 max-level 交替出現
  - x 位於 min-level: 以 x 為 root 之子樹中，x 為最小值
  - x 位於 max-level: 以 x 為 root 之子樹中，x 為最大值
- Root 位於 min-level
Insert x
- 把 x 放到最後一個節點的下一個位置
- 根據 x 的父節點 p 所在 level 進行挑戰
  - 如果挑戰父節點成功: 將父節點下移，並挑戰父節點原本位置的祖父節點
  - 挑戰失敗: 挑戰祖父節點
Delete-Min
- 刪除 root 的資料，並且刪除最後一個節點 x 的資料
- (迴圈)將 x 插入一個 root 為空的 Min-Max Heap 中，分為以下三種情況:
  - 若 root 沒有子點: 將 x 插入 root，結束
  - 若 root 的子孫中的最小值是 root 的左右子點之一，令其為 k:
    - 若 k < x: k, x 互換，結束
    - 否則將 x 插入 root，結束
  - 若 root 的子孫中的最小值是 root 的孫子之一，令其為 k，且 k 的父節點為 p:
    - 若 k < x: k 插入 root
      - 若 x > p: x, p 互換
        繼續迴圈
    - 否則將 x 插入 root，結束

Deap (Doubled-ended Heap)

是一個 Complete BT，並且滿足:
- Root 沒有 Data
- Root 的左子樹為 min-Heap
- Root 的右子樹為 max-Heap
- 若 i 為 min-Heap 中的一個點，j 為其在 max-Heap 中的對應位置
  - 則 Deap[i] <= Deap[j]
  - $j = i + 2^{⌈\log_2(i+1)⌉-2}$
  - 如果 j > n (對應位置沒有點) 則 j = j/2 (找父節點)
Insert x (要進行 Heap 插入操作的資料一定為 x)
- 把 x 放到最後一個節點的下一個位置，令其位置為 n
- 如果 x 與其對應節點 j 滿足 Deap 規定 (Deap[n] <= Deap[j] / Deap[n] >= Deap[j])
  - 則在 n 位置進行 Heap 的插入 (x)
  - 否則將 j 位置的資料移至 n，在 j 位置進行 Heap 的插入 (x)
Delete-Min
- 刪除 min-Heap 頂端的資料，產生空缺位置 E，並且刪除最後一個節點 x 的資料
- (迴圈)對於 E，不斷的從其左右子點中挑選較小值進行替代，直到 E 位於葉節點
- 在 E 的位置進行 Insert x

SMMH (symmetric Min-Max Heap)

是一個 Complete BT，並且滿足:
- Root 沒有 Data
- 左 Sibling <= 右 Sibling
- 若 x 有祖父，則
  - 祖父的左子點 <= x
  - 祖父的右子點 >= x
特點:
- Node i 的左子點為以 i 為 Root 的子樹中 (不含 i) 的最小值
- Node i 的右子點為以 i 為 Root 的子樹中 (不含 i) 的最大值
Insert x
- 把 x 放到最後一個節點的下一個位置
- 檢查是否滿足 左 Sibling <= 右 Sibling，如果不滿足則對調位置
- (迴圈)挑戰其祖父節點的左右子點，如果不滿足 SMMH 的規定則將其對調，直到滿足規定為止
Delete-Min
- 刪除 root 左子點的資料，產生空缺位置 E，並且刪除最後一個節點 x 的資料
- (迴圈)找出 Min(E 的左子點, E 的右兄弟的左子點)，並與 x 比較
  - 若 min < x: min 與 E 對調
  - 否則將 x 插入 E，結束
- 檢查是否滿足 左 Sibling <= 右 Sibling

統整

相同之處
- Insert x, Delete-Max 與 Delete-Min 操作之時間複雜度為 $O(\log n)$
- Complete BT
- 插入操作都會先將 x 置於最後一個節點的下一個位置，並且向上挑戰
- 刪除操作都會先將最後一個節點 x 的資料刪除
相異之處

	Min-Max Heap	Deap	SMMH
結構	交替不同 level	左右分為 min/max Heap	左右對稱結構
Root Data	O	X	X
Min 位置	Root	Root 的左子點	Root 的左子點
Max 位置	Max(Root 的左右子點)	Root 的右子點	Root 的右子點

延伸二元樹 (Extended BT)

若以 link list 表示有 n 個節點的 BT，則會有 n + 1 個 nil links，將其加上特殊節點 (External Node/Failure Node)，其餘的 n 個節點稱為 Internal Node
路徑長:
- I (Internal path length): Root 到各個內部節點的路徑長總和
- E (External path length): Root 到各個外部節點的路徑長總和
- 定理: E = I + 2N (N 為內部節點個數)
  - 可用數學歸納法證明

WEPL (Weighted External path length)

給予每個外部節點加權值，計算總和之前要先個別將路徑長乘上該點加權值
不一定樹高越小 WEPL 越小
求不同的樹狀結構之最小 WEPL - Huffman Algo
- 令 W 為 n 個外部節點加權值的集合
- (迴圈 n - 1 次)從 W 中取出 2 個最小值，建立 Extended BT，並且將兩個權值之和視為新的權值加入 W 中，直到 W 中只剩下一個權值
- 記得重新計算 WEPL 值 (不是直接用剩下的權值)
- 利用 Heap 維護 W 集合，每次操作花費 $O(\log n)$ 時間，共 n - 1 次，故時間複雜度為 $O(n\log n)$
- 應用:
  - 編碼 (Extended BT 左分支為 0/右分支為 1)
    - 平均解碼時間
    - 平均編碼位元長度
  - 求 WEPL

平衡樹

AVL Tree

是一個 Height Balanced BST，若不為空，則滿足:
- |H_L - H_R| <= 1 (H_L, H_R 為左右子樹高度)
- 左右子樹也是 AVL Tree
平衡係數 (Balance Factor): H_L - H_R
- AVL tree 中每個點的平衡係數為 -1 / 0 / 1
不平衡的情況:
- 考慮新插入的點造成的最近之不平衡點，從該點向新插入的點的方向，只看兩層子樹，則會有 LL, LR, RL, RR 四種情況
處理不平衡
- 只考慮三個節點 (四種情況表示法之兩條線所連接的三個 Node)，將中間鍵值往上拉，鍵值小的放左，大的放右
- 孤兒子樹 (原本中間鍵值 Node 的其他左右子樹) 依照 BST 的性質重新放入
旋轉次數 (若題目沒有標註則要自己清楚說明):
- 對於 Algo:
  - Single Rotation (1): LL, RR
  - Double Rotation (2): LR, RL
- 對於 DS: 皆為 1 次 Rotation
定理: 形成高度為 h 的 AVL Tree
- 最少需要 F_h+2 - 1 個 Nodes (F: 費氏數列)
  - 可用數學歸納法證明
  - 每個非葉節點之左右子樹高度差 1 (Fibonacci BT)
  - 遞迴定義: $N_H = N_{H-2} + N_{H-1} + 1, N_0 = 0, N_1 = 1$
- 最多 Node 數: $2^n-1$ (Full)

B tree of order m

m-way search Tree

每個點有最多 m 個子節點 (m - 1 個 key)
主要用於 external search/sort (加大 m 可以減少樹高，降低 I/O 次數)
高度 h 的 m-way search Tree:
- 最多有 $\frac{m^h-1}{m-1}$ 個 Nodes
- 最多有 $m^h-1$ 個 keys

是一個 Balanced m-way search Tree，主要用於 external search/sort，滿足:
- 2 <= Root Degree <= m
- ⌈m/2⌉ <= 其餘 Nodes Degree <= m
- 所有 Failure Nodes 位於同一 level (平衡)
特例:
- order 3:
  - 2 <= Degree <= 3
  - 又稱為 2-3 Tree
- order 4:
  - 2 <= Degree <= 4
  - 又稱為 2-3-4 Tree
Insert x
- search x，將 x 置於適當位置
- (迴圈)檢查 x 所在節點是否發生 overflow (key 數 = m)
  - 如果發生 overflow，將執行 spilt，把 k_⌈m/2⌉ 移置父點，剩餘的點分為兩個 Node，並且對父點進行檢查
  - 如果沒有 overflow，結束
Delete x
- search x，尋找 x 所在位置
- 考慮兩種情況:
  - x 在葉節點:
    - (迴圈)刪除 x，並檢查是否發生 underflow (key 數 < ⌈m/2⌉ - 1)
      - 如果發生 underflow，先執行 Rotation，如果能夠 Rotation，結束。否則執行 Combine，並對父點進行檢查
      - 如果沒有 underflow，結束
  - x 不在葉節點:
    - 以 x 所在 Node 之左子樹最大值/右子樹最小值取代 x
    - 相當於某葉節點少一個 key，對其進行處理

Rotation
- 檢查左右兄弟是否有多餘的 key
- 如果有多餘的 key，將其給父點，並將父點的 key 給 x 所在的 Node
Combine
- 把父點的 key 往下拉，並將其與 x 所在 Node 以及其左/右兄弟合併
- 之後需要檢查父點是否 underflow

高度 h 的 B tree of order m:
- 最多有 $\frac{m^h-1}{m-1}$ 個 Nodes (同 m-way search Tree)
- 最多有 $m^h-1$ 個 keys (同 m-way search Tree)
- 最少有 $1 + 2*\frac{⌈\frac{m}{2}⌉^{h-1}-1}{⌈\frac{m}{2}⌉-1}$ $1 + 2 * \frac{⌈ \frac{m}{2} ⌉ ^{h - 1} - 1}{⌈ \frac{m}{2} ⌉ - 1}$
  - Root + 2 * ⌈m/2⌉-way search Tree (樹高 h - 1)
- 最少有 $2*⌈\frac{m}{2}⌉^{h-1}-1$ $2 * ⌈ \frac{m}{2} ⌉^{h - 1} - 1$
  - 除了 Root 外，每個 Node 有 ⌈m/2⌉ - 1 個 key

Red-Black Tree

Algo 版本

是一個 BST，滿足:
- Node 的顏色非黑即紅
- Root 必定為黑色
- Nil 視為黑色
- 紅色 Node 的兩個子點必定為黑色 (不能有連續兩個紅 Node)
- Root 到不同葉節點的路徑上都具有相同數量的黑色 Node
Insert x
- 先 search x，尋找插入 x 的位置
- 在 search 過程中，如果遇到某個 Node 有兩個紅色子點，則進行 Color change: 改為紅色 Node 接兩個黑色子點
- 檢查是否有連續兩個紅色的 Node，如果有則進行 Rotation 調整
- 插入 x 在適當位置，之後檢查
- 檢查是否有連續兩個紅色的 Node，如果有則進行 Rotation 調整
- 將 Root 改為黑色

Rotation
- 分為 LL, LR, RL, RR
- 同 AVL Tree 的操作 + 顏色設定: 黑色 Node 接兩個紅色子點

DS 版本

是一個 2-3-4 Tree 對應的 BST，滿足:
- Link 的顏色非黑即紅
- 若此 link 在 2-3-4 Tree 中已經存在，則視為黑色，否則為紅色
- 任何 path 上不會有連續的紅色 links
- Root 到不同葉節點的路徑上都具有相同數量的黑色 Link

OBST (optimal BST)

給予 n 個內部節點加權值 p_i (1 <= i <= n)，(n + 1) 個外部節點加權值 q_i (0 <= i <= n)，則在 $\frac{1}{n+1}C_{n}^{2n}$ 棵不同 BST 中，具有最小搜尋總成本之 BST，稱為 OBST
搜尋總成本: 成功 cost + 失敗 cost
- 成功 cost: $\sum_{i=1}^{n}(Node_i~level *p_i)$ (Node_i 為內部節點)
- 失敗 cost: $\sum_{j=0}^{n}[(Node_j~level - 1)*q_i]$ (Node_j 為內部節點)
在有加權值的情況下，高度越小不一定 search cost 越小
求 OBST: Dynamic Programming
- 假設 $a_{i+1}, a_{i+2}, ...,a_{j}$ $a_{i + 1}, a_{i + 2}, . . ., a_{j}$ 是內部節點，且 $a_{i+1}<a_{i+2}<...<a_j$ $a_{i + 1} < a_{i + 2} < . . . < a_{j}$
  - 令 $p_{i+1}, p_{i+2}, ...,p_j$ 為內部 Nodes 加權值
  - 令 $q_{i+1}, q_{i+2}, ...,q_j$ 為外部 Nodes 加權值
- 定義 $T_{i,j}$ $T_{i, j}$ 代表由 $a_{i+1}, a_{i+2}, ...,a_j$ $a_{i + 1}, a_{i + 2}, . . ., a_{j}$ 組成之 OBST
  - $c_{i,j}$ 為其 cost
  - $r_{i,j}$ 為其 root
  - $w_{i,j}$ 為其內外部 Nodes 加權值總和
  - 令 i = j 時為空樹，且 $c_{i,j}=0,r_{i,j}=0,w_{i,j}=q_i$
  - 當 i > j 時未定義
- 求最小 $c_{i,j}$ $c_{i, j}$ :
  - 假設隨機取 $a_{K}$ 作為 root， $c_{i,j} = w_{i,j} + c_{i,k-1} + c_{k,j}$
  - 因此要取 $c_{i,j} = w_{i,j}+min[c_{i,r-1} + c_{r,j}]$ $c_{i, j} = w_{i, j} + m i n [c_{i, r - 1} + c_{r, j}]$
    - (i + 1 <= r <=j)
- 由上而下，求最小 $c_{i,j}$
- 樹的構造由下而上反推

Algo 版本

定義不同:
- 失敗 cost: $\sum_{j=0}^{n}[(Node_j~level)*q_i]$ (Node_j 為內部節點)
[Algo 版本] 之 cost = [DS 版本] 之 cost + $\sum_{j=0}^{n}q_i$ (外部 Nodes 之加權值總和)

其他

Splay Tree (外張樹)

	AVL Tree, B Tree	Splay Tree
實際成本	$O(\log n)$	$O(n)$
分攤成本	$O(\log n)$	$O(\log n)$

是一個 BST，操作與 BST 相同，每次操作之後必須針對 splay 起點進行 splay 運算，直到把它變為 root
- splay 起點:
  - Insert x: x
  - Search x: x
  - Delete x: x 的父節點
- splay 運算: 一連串 Rotation
  - Rotation: 針對由 splay 起點開始往上的三個點
    - 分為 LL, LR, RL, RR
    - 與 AVL Tree 操作不同
    - 目的是把 splay 起點移動到三個點的最上面 (剩餘兩點根據 BST 調整)

Leftist Heap (min-leftist Tree)

	Heap	Leftist Heap
Insert x	$O(\log n)$	$O(\log n)$
Delete min	$O(\log n)$	$O(\log n)$
Merge 2 Heap	$O(n)$	$O(\log n)$

Leftist Tree

Shortest(x): 令 x 是 extended BT 之 Node，則 Shortest(x)=
- 0 if x 為外部 Node
- 1 + min(Shortest(x->Lchild), Shortest(x->Rchild)) if x 為內部 Node
Shortest(x) 是一個 Node 到達外部節點的最短距離
Leftist Tree:
- 對於任何 Node x 滿足 Shortest(x->Lchild) >= Shortest(x->Rchild)

是一個 Leftist Tree，且也是 min-Tree (所有父點 <= 子點)
Merge 2 Leftist Heap: H₁, H₂
- 比較兩樹之 root，找出最小 root (不失一般性，令 H₁ 之 root 最小)
- H₁ 之 root 作為新 root，並保留其左子樹
- (迴圈) Merge(H₁ 右子樹, H₂) 作為新 root 之右子樹，重複直到只剩下一棵 min-Tree
- 檢查是否滿足 Leftist Tree，如果不滿足進行 Swap 調整 (左右子樹互換)
Delete min
- 刪除 root，形成兩棵子樹 H₁, H₂
- Merge(H₁, H₂)
Insert x in Leftist Heap H₁:
- 將 x 當作一棵 Leftist Heap H₂
- Merge(H₁, H₂)

Binomial Heap

Binomial Tree

令 root 之 level 為 0
B₀ 代表高度 0 的 Binomial Tree，只有 root 一個點
B_k 代表高度 k 的 Binomial Tree，由兩個 B_k-1 組成，任一個 B_k-1 之 root 為新 root，另一個 B_k 為其子樹
相關公式:
- B_k 第 i level 的 Node 數為 $C_{k}^{i}$
- B_k 之 Node 總數為 $2^k$ $2^{k}$
  - 若 Node 數為 n，則 $k = \log n$

為 Binomial Tree 組成的集合 (Forest)，且每一棵樹必須是 min-Tree
Merge 2 Binomial Heap
- (迴圈) 合併相同高度之 Binomial Tree，root 較小者作為新 root，另一個為其子樹，直到沒有相同高度之 Binomial Tree
  - 通常是由小而大進行合併
- 合併的時間複雜度為 $O(\log n)$ (n 為 data 數)
Delete min
- 從所有的樹中找到最小的 root，令此樹為 T，剩餘樹的集合為 H₁
- 將 T 的 root 刪除，令其剩餘子樹的集合為 H₂
- Merge(H₁, H₂)
- 時間複雜度為 $O(\log n)$
Insert x in Binomial Heap H₁:
- 將 x 當作一個 Binomial Heap H₂
- Merge(H₁, H₂)
- 時間複雜度:
  - 大部分 case 為 $O(1)$
  - 少部分 case 為 $O(\log n)$
  - 分攤時間: $O(1)$

DS 版本

採取 Lazy merge:
- Merge 時不合併相同高度的 Binomial Tree
- 在 Delete min 時才進行相同高度的合併
增加一個 a 指標: 指向 min(roots)

	Algo 版本	DS 版本
Insert x	$O(1)$	$O(1)$
Delete min	$O(\log n)$	$O(\log n)$
Merge	$O(\log n)$	$O(1)$
Search min	$O(\log n)$	$O(1)$

Fibonacci Tree [DS 版本]

視為 Binomial Heap 的 superset，又稱為 Extended Binomial Heap，除了基礎的三個操作 (Insert, Delete min, Merge) 之外，另外增加兩個動作:
- Delete Node: 刪除特定節點
  - 時間複雜度 $O(\log n)$ (分攤時間)
- Decrease key of a Node: 減少鍵值
  - 時間複雜度 $O(1)$ (分攤時間)
Delete Node
- 如果該 Node 是 root，則執行 Delete min
- 否則將刪除的 Node 的子樹分離出來 (相同高度部核定)
Decrease key of a Node
- 如果是針對 root 的操作，需要檢查是否要移動 a 指標，指向最小 root
- 如果是針對其他 Node 的操作，需要檢查是否小於其父節點，如果 Decrease key 之後小於父節點，則將其獨立出來成為新的 Binomial Tree