資料結構-樹與二元樹

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

樹 (Tree)

• 由 >0 個節點 (Node) 所構成
• 森林 (Forest): 由 >=0 個樹所構成 (可以為空)

表示方式

• Link list
  | Data | child | sibling |

  • 假設 degree 為 k，並且有 n 個節點，會浪費 n*k-(n-1) 條 Link (Nil links)

• 轉為二元樹表示

• Child-sibling 方法
  | Data | child | sibling |

  • child: 指向 leftmost-child
  • sibling: 指向 次右兄弟

• 括號法
  以 父(子1,子2,...子n) 表示父點與子點之間的關係，並且可以巢狀方式表示

二元樹 (BT)

• 可以為空，若不為空則滿足:
  • 有 root 及左右子樹
  • 左右子樹也是二元樹
• 與樹比較:

樹	二元樹
不能為空	可以為空
degree >= 0	2 >= degree >= 0
子樹之間無次序/方向之分	子樹有左右之分

基本定理

• 二元樹 i level 的最多 Node 數為 $2^{i-1}$
• 高度為 k 的二元樹，最多 Node 樹為 $2^k-1$
  • 若二元樹有 n 個 Node，則其最小高度為 $⌈\log_2(n+1)⌉$
• 給予一個非空的二元樹，若 leaf 有 n₀ 個，Degree-2 的 Node 數有 n₂ 個，則 n₀ = n₂ + 1

分類

• skewed BT (斜曲)
  • left-skewed BT: 每個 Node 都只有左節點
  • right-skewed BT: 每個 Node 都只有右節點
• Full BT (完滿)
  • 高度為 k 的 Full BT 擁有最多的 Node 數 ($2^k-1$)
• Complete BT (完整)
  • 高度為 k 的 Complete BT 的 Node 數 $2^{k-1}-1<n<2^k-1$
  • Node 編號順序與高度為 k 的 Full BT 之前 n 個點編號一一對應 (由上而下，由左而右)
  • 若 Node 數為 n，某 Node 之編號為 i，則:
    • 左子點編號為 2i，若 2i > n 則無左子點
    • 左子點編號為 2i+1，若 2i+1 > n 則無左子點
    • 父點編號為 [i/2]，若 [i/2] < 1 則無父點
• Strict BT (嚴格)
  • 每個非 leaf 節點必有兩個子點 (n₁ = 0)

表示方式

• Array

  • 若樹高度為 k ，準備一個 array[1 … $2^k-1$]，將 Node 資料存入 Full BT 對應的編號
  • 若為 Complete/Full BT 有 n 個節點，只需要 array[1 … n]
  • 優點:
    • 易於存取左右節點及父點
    • 對於 Complete/Full BT 可以充分利用空間
  • 缺點:
    • 不易插入/刪除 Node (可能需要改變高度)
    • 對於 skewed BT 極為浪費空間 (浪費 $2^k-1-k$ 格)

• Link list
  | Lchild | Data | Rchild |

  • 優點:
    • 易於插入/刪除 Node
    • 對於 skewed BT 相較 Array 省空間
  • 缺點:
    • 不易存取父節點
    • 浪費約 50% 的 Link (n 個 Node 會有 n + 1 條 Nil link)

追蹤 (Traversal)

• 前序 (Preorder): DLR
• 中序 (Inorder): LDR
• 後序 (Postorder): LRD
• level-order (依照level由上而下，由左而右)

決定二元樹

• 中序 + 前序/後序/level-order: 可決定唯一的 BT
• 前序/後序/level-order 三選二: 無法決定唯一的 BT
  • ex: 給定 前序ABC + 後序CBA，能夠決定出四顆不同的 BT
• 如果是 Complete BT，前序/中序/後序 可決定唯一的 BT

產生 BT 個數

n 個 Nodes 可以形成的 BT 個數

• $\frac{1}{n+1}C_{n}^{2n}$ (卡塔蘭數)
• 遞迴定義: $B_{n} = \sum_{i=0}^{n-1}B_{i}B_{n-1-i}, B_0 = 1, B_1 = 1$
  • 假設左子樹有 $i$ 個節點: $B_i$ ($0<=i<=n-1$)
  • 右子樹會有 $n-1-i$ 個節點: $B_{n-1-i}$

二元搜尋樹 (BST)

• 是一個二元樹，若不為空則滿足:
  • 左子樹所有 Nodes 之值小於 Root
  • 右子樹所有 Nodes 之值大於 Root
  • 左右子樹也是 BST
• 對 BST 進行中序遍歷，可以得到由小到大的排序
• 插入&建立: 受到順序的影響
• 刪除:
  • 如果是葉節點: 直接刪除
  • 如果是 Degree-1 的節點: 將該節點的父點指向該點子節點
  • 如果是 Degree-2 的節點: 以該節點的左子樹最大值/右子樹最小值替代該節點，並且對要替代的節點進行處理
• 比較次數:
  • 成功: 內部節點的 level
  • 失敗: 外部節點的 level - 1
  • 平均比較次數 (n 個節點):
    • skewed BT: $O(n)$
    • Full BT: $O(\log n)$

堆積 (Heap)

• 是一個 Complete BT，並且滿足:
  • 所有父點都 >= (<=) 子點之值
  • Root 具有最大(小)值
• 適合使用 array 保存 (Complete BT)
• 插入:
  • 將插入的節點放置於最後一個節點的後面
  • 往上不斷挑戰父節點並交換位置，直到無父點或是挑戰失敗
• 刪除 Max(Min):
  • 移走根結點，並且用最後一個節點取代
  • 將取代的節點由上而下不斷調整，直到滿足 Heap 為止
• 建立:
  • Top-down ($O(n\log n)$):
    • 依序進行插入操作
  • Bottom-up ($O(n)$):
    • 將所有節點以 Complete BT 表示
    • 從最後一個父點開始倒推，依序調整每顆子樹成為 Heap，直到調整到 Root 為止

Tree/Forest 轉為 BT

Tree

Leftmost-Child-Next-Right-Sibling

• 正向 (Tree -> BT):
  • 建立 Sibling 之間的 Links
  • 刪除父節點與子節點之間的連結，只保留 Leftmost-Child 的 Link
  • 順時針旋轉 45 度 (Leftmost-Child -> 左子點，Next-Right-Sibling -> 右子點)
• 反向 (BT -> Tree):
  • 逆時針旋轉 45 度 (右子點拉上成為父點的 Next-Right-Sibling)
  • 補足父子節點之間的 Links
  • 刪除 Sibling 間的 Links

Forest

• 正向 (Forest -> BT)
  • 將 Forest 中的每棵樹都化為 BT
  • 將每個 BT 的 roots 視為 Sibling 建立 Links
  • 將串接的 roots 順時針旋轉 45 度
• 反向 (BT -> Forest)
  • 將 root 之右子點拉上成為 root 的 Sibling
  • 刪除 roots 之間的 Sibling Links 得到多顆 BT
  • 每個 BT 再化為 Tree

Disjoint Sets

• 由一組互斥之集合組成
• 每個 set 利用樹的結構表示 (從 set 中選一點作為 root，其餘為它的子點)
  • Link list
  • Array: 紀錄每個點的 Parent (root 的 Parent 為 0/-1)

Union & Find

• Union(i, j): 聯集 i 所在的集合與 j 所在的結合
  • 任意的 Union:
    • 取 i (j) 的集合的 root 為 new root，另一個 set 為它的子樹
    • 可能產生一個高度為 $O(n)$ 樹，使得 Find 需要 $O(n)$ 的時間
  • Union-by-Height (Weight):
    • 取樹高較高 (節點較多) 者作為 new root，另一個 set 為它的子樹
    • 如果樹高 (節點) 相同則作任意的 Union
    • 如果是高度相同的 set 作 Union，樹的高度會增加 1，否則高度不變 (與樹高較高者相同)
    • 產生的樹最高為 $O(\log n)$，Find 最多需要 $O(\log n)$ 的時間
• Find(x): 找出 x 所在的集合，傳回 root (or root->data)
  • Simple-Find:
    • 沿著 x 的 Parent link 往上尋找，直到找到 root 並傳回
    • 需要 $O(h)$ 的時間 (h 為樹高)
  • Find-with-Path-Compression
    • 尋找 root 時，將 Parent link 上面的所有 Nodes 的 Parent 改為 root
    • 平均成本為 $O(\alpha(m,n))$，約為 $O(\log^*n)$ (趨近 $O(1)$)

引線二元樹 (Thread BT)

為了充分利用 link list 中的 n + 1 條 nil links

• 將 nil links 作為 Thread pointer，指向其他 Nodes
  • x->lchild 作為左引線，指向中序順序中的前一個 Node
  • x->rchild 作為右引線，指向中序順序中的後一個 Node
• Structure
  | Left Thread | Lchild | Data | Rchild | Right Thread |
  • Left Thread:
    • True: Lchild 是左引線
    • False: Lchild 是左子點
  • Right Thread:
    • True: Rchild 是右引線
    • False: Rchild 是右子點
  • 增加一個 Head node (串列首)
    • 不存 Data
    • Rchild 指向自己 (Right Thread = False)
    • 空樹: Lchild 指向自己 (Left Thread = True)
    • 非空樹: Lchild 指向 root (Left Thread = False)
• Insuc(x): 找出 x 的中序後繼者
  • 若 x->Right Thread == True，則 x->Rchild 即是
  • 若 x->Right Thread == False
    • 沿著 x 的右子點之左子點往左下尋找，直到該 Node 之 Left Thread==True (右子樹的最左子點)