Re: [分享] 2024.10.22 Tree & Binary Tree

[OriginalGod (原神)]

有錯請指教。
沒啥時間了，應該會專攻Tree、Search & Sort、Graph這三章，其他加減看了。
之前太混，想認真就是認真不起來。

Def:
- Tree
  - m-way search Tree
    degree 0 ~ m，if node degree m, number of keys in node m-1
    - Balanced m-way search Tree(B tree of order m)
      root degree 2 ~ m，others degree [m]/2 ~ m
      external nodes are the same level
      - B+ tree of order m
        分Index level(不放Data), Data blocks level(存Data，以Link list串連)
      - 2-3 tree(B tree of order 3)
      - 2-3-4 tree(B tree of order 4)
  - Binomial Tree with order h
    root之level為0，高度h(只有root一個點為高度0)
    - Binomial Heap
      - Fibonacci Heap
- Forest
- Binary Tree(BT)
  - skewed BT
  - Complete BT
    - Full BT
    - Binary Heap(Heap)
    - min-max Heap
    - Doubled-ended Heap(Deap)
    - symmetric min-max Heap(SMMH)
  - strict BT
  - Binary Search Tree(BST)
    - Balanced BST
      - AVL Tree
        Balance factor = 1 or -1 or 0
      - Red-Black Tree(RB Tree)
        same black height
    - optimal BST(OBST)
    - Splay Tree
  - Thread BT
  - Extended BT
    Weighted External path length(WEPL)
    - Leftist Heap(min Leftist Tree)
      shortest(x) = 0 (外部node) or
                    1 + min{shortest(x->lchild),shortest(x->rchild)} (內部node)
- BT Traversal(追蹤)
  - Preorder(DLR)
  - Inorder(LDR)
  - Postorder(LRD)
  - level-order

Def(Representation):
- Tree表示方式
  - Link list
  - 化成Binary Tree(leftmost-child-next-right-sibling 左兒子,右兄弟)
    - 給定 Tree，求 BT
      給定 BT，求 Tree
  - child-sibling(左兒子,右兄弟)
  - 括號法
- Forest表示方式
  - 化成Binary Tree
- BT表示方式
  - Array
    Complete BT
    容易存左右子點父點、不易增刪Node
  - Link list
    skewed BT
    Thread BT
      每個node多出LeftThread, RightThread，True為引線、False為子點
      多一Head node不存Data(空樹為左T右F，非空樹左右F指向Root)
    Extend BT
      node存weight(非Data)
    容易增刪Node、不易存父點、浪費links space
- Disjoint sets表示方式
  - Link list
    Data以及Parent(pointer指向父點，root指向Null)
  - Array
    root指向0(表示Null)或(-1)*(node數)

Thm:
- Tree之基本定理
  - if Tree's Degree = k
    node數 = leaf數 + Degree-1之node數 + ... + Degree-k之node數
           = Branch數 + 1
           = (1*Degree-1之node數 + ... + k*Degree-k之node數) + 1
- BT之基本定理
  - 給定 高度k，求 最多node數
    - 第i個level上，最多node數
  - 給定 node數，求 最小高度
  - leaf數 = Degree-2之node數 + 1
  - 給定 node數，求 可能的BT個數
    n個node可能的BT數 = sum(i個node可能的BT數 * n-1-i個node可能的BT數)
                      = 1/(n+1) * C(2n取n)
    where i=0~n-1
- Complete BT之基本定理
  - if n個node編號:1~n
    給定 編號為i的node，求 左子點、右子點、父點編號
- BT Traversal(追蹤)
  - 給定 BT，求 Traversal
  - 給定 Traversal，求 BT
    - 給定 Pre+Inorder或Post+Inorder或level+Inorder，求 BT
      對node總數或順序長度作induction
    - 給定 Pre或Post或level或Inorder，求 Complete BT
    - 給定 Pre或Post或level，求 BST
- Extended BT之定理
  - External path length = Internal path length + 2n
    External node數 = Internal node數 + 1
    對Internal node數作induction(拆成左右子樹)
  - 給定 External node數及其加權值，求 min.WEPL
    use Huffman Algo，在可能的Extend BT找出min.WEPL
- AVL Tree之定理
  - 給定 高度h，求 所需最少node數、最多node數(Full)
    對高度作induction
  - 給定 node數，求 最小高度(Full)、最大高度
- m-way search Tree之定理
  - 給定 高度h，求 最多node數、最多key(Data)數
- B Tree之定理
  - 給定 高度h，求 最多、最少node數、最多、最少key(Data)數
- RB Tree之定理
  - 給定 node數，求 最大高度
    先證明以某一node x為root的子樹，至少包含2^(bh(x))-1 node
    where bh(x)為以x為root的子樹到leaf會有的黑色node數
    對bh(x)作induction
    n >= 2^(bh(x))-1 >= 2^(h/2)-1 (因為紅黑樹的特性)
    2*log(n+1) >= h
  - 給定 2-3-4 tree，求 RB Tree
    原本2-3-4 tree存在的link視為黑色，否則視為紅色
- OBST之定理
  - 給定 內外部node數及其加權值，求 最小搜尋總成本之BST(OBST)及其cost
    use DP
    O(n^3)
    - Cij = Wi,j + min{ Ci,r-1 + Cr,j }
      where i+1 <= r <= j
- Leftist Heap之定理
  - n >= 2^(shortest(x))-1 where x為root
    對shortest(x)作induction
- Binomial Tree之定理
  - 給定 高度h，求 第i個level上node數、總node數
    對高度h作induction 或 加總各個level上node數(C(h取0)+...C(h取h))
- Binomial Heap之定理
  - 給定 node數，求 最多Binomial Tree數
    O(log n)，node數寫成二進制

DS with Algo(要知道時間複雜度、怎麼寫，會寫就會操作):
- ☆BT recursive algo
  - BT Traversal
    - Preorder(T:BT), Postorder(T:BT), Inorder(T:BT)
      用Stack，O(n)
    - level-order
      用Queue，O(n)
  - Count(T:BT), CountDegree1(T:BT), CountDegree2(T:BT), Leaf(T:BT)
  - Height(T:BT)
  - Swap(T:BT)
  - Eval(T:expression BT)
    node結構多出Res欄(存運算結果或變數值)
    - 給定 expression，求 BT
  - Copy(orig:BT)
  - Equal(S,T:BT)

- ☆BST recursive algo
  Tree's sorting: Inorder可得小至大排序，RDL追蹤或stack可得大至小排序
  - Search(T:BST,x:Data)
    給定 BST及其Data range，求 平均比較次數 = 總比較次數/Data range
  - ☆☆Search ith smallest item
  - Find-max, Find-min
  - Insert
    - rotation (AVL, RB Tree)
      O(1)
    - Bottom up (RB Tree先插node再檢查)
    - Top Down (RB Tree先檢查再插node)
  - Delete
  上述皆是O(h) = O(n) ~ avg O(log n)
  高度最小化最佳(Full, Complete, AVL, RB Tree)
  splay tree會再作rotation

- Heap algo
  可製作Priority Queue
  - Search
    O(n)
  - Find-max or min
    Θ(1)
  - Insert
    O(h) = O(log n)
  - ☆☆Build
    - Top-Down(邊Insert邊排序)
      O(n*log n)，(log1 + ... + log n) = log(n!) ≒ n*log n
    - Bottom-up(全Insert再排序)
      O(n)
      最大成本 = sum(level i最多node數 * 以level i為root之子樹高)
               = sum( 2^(i-1) * (h-i) )
               = n-h+1
      where i = 1 ~ h = 1 ~ log n
      - Adjust(tree,i,n)
        O(log n)
      - CreateHeap(tree,n)
  - Delete-max or min
    O(h) = O(log n)
    - Adjust
  - Merge
    O(n)
  - Decrease key of a node
    O(log n)
  - Delete(先Decrease key變min，再Delete-min)
    O(log n)

- Disjoint sets
  Kurskal's algo中判斷邊(u,v)加入spanning Tree中是否形成cycle
  Find Equiv Sets根據等位配對資訊，求出等位集合
  Find connected components of undirected graph 找出無向圖之連通子圖
  - Make-Set(x)
  - Union(x,y)
    O(1)
    - Arbitrary Union
    - Union by Height
      Binomial Tree
    - Union by Weighting rule(多node為爸)
    - Union by rank
  - Find(x) 找root
    O(h) = O(log n)
    - with Collapsing rule(path Compression) 經過之node改指向root
      O(α(m,n))
---> 我感覺不常考。

- Thread BT
  每個node多出LeftThread, RightThread，True為引線、False為子點
  多加一個Head node不存Data(空樹為左T右F，非空樹左右F)
  - Inorder(T:thread BT)
    - Insuc(x) 找出x的Inorder後繼者
  - Insert T as a Right child of S
    - Insuc(x)
  - Insert T as a Left child of S
    - Inpre(x)
---> 我感覺不常考。

- min-max Heap, Deap, SMMH
  可製作Double-ended Priority Queue
  - Insert
    O(log n)
  - Delete-max or min
    O(log n)
  - Find-min or max
    O(1)

- Extended BT
  - Huffman algo
    一種Greedy algo
    O(n*log n)
    每一個回合對Heap作Del-min、Insert weight花O(log n)，執行n-1回合
    - n個runs之最佳合併方式
    - 給定 n個message編碼傳輸(weight是頻率，WEPL是平均編碼位元長度)，
      求 Huffman coding tree編碼/解碼樹
      求 各message之編碼內容
      求 最小平均編碼位元長度(最小平均解碼時間的編碼內容)
      where 平均編碼位元長度 = message所需編碼位元長度 / message數

- m-way search Tree
  External Sort
  External Search
    資料量太大，無法一次全部存於memory中進行搜尋
    必須使用外部儲存體保存再分批載入search
  用來組織Data Blocks，加大m可有效降低Tree高度，可降低I/O次數，可增加效能
  - Search
  - Insert
  - Delete
    O(h)

- B tree, B+ tree
  - Insert
  - Delete

- Leftist Heap
  - Merge
    - Insert
    - Delete
  上述皆為O(log n)

- Binomial Heap, Fib Heap
  - Find Min
    O(1) 或 O(log n) (Weiss無min pointer)
  - Union(Merge)
    - Lazy Merge (相同高度無須合併，合併即root間用link串聯)
      O(1)
    - 勤勞 Merge (相同高度才要合併，root小當new root，另一當子樹，從root小到大)
      O(log n)，合併兩顆Binomial Tree只花O(1)，最多log(n+1)棵Binomial Tree
      - Delete Min
        O(log n)
    - Insert
      amortized O(1) 少部分當n=2^k-1 O(log n)
  - ☆☆Decrease-key
    O(1) (Fib Heap) 或 O(log n) (DS、Weiss版本)
  - Delete(先Decrease-key變min再Delete-min)
    O(log n)

--------------------------------------------------------------------------
以下還未弄懂:

What is amortized cost?

Disjoints Sets的應用

Huffman algo

有些DS的insert如何作rotation

RB Tree Top Down和Bottom up差別? 是否會有同樣input不同output的可能?
https://www.pttweb.cc/bbs/Grad-ProbAsk/M.1506650404.A.588
看不太懂FRAXIS大大這篇寫的...

OBST的Table Result

...等

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.171.161.147 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/talk/M.1729608098.A.875.html
→ TKB5566: 看來松鼠找到同類了
cuteSquirrel大大，人蠻不錯的
→ TKB5566: 我忝為本科系出身 竟完全看不懂任何一行 有夠慘
XD
※ 編輯: OriginalGod (1.171.161.147 臺灣), 10/23/2024 01:07:00