[分享] 2024.10.07 Tree & Binary Tree

[OriginalGod (原神)]

有錯請指教。

Def:
- Tree
  - m-way search Tree
    - B tree
- Forest
- Binary Tree(BT)
  - skewed BT
  - Complete BT
    - Full BT
    - Heap
  - strict BT
  - Binary Search Tree(BST)
    - AVL Tree
    - Red-Black Tree
  - Thread BT
- 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
    Ex:Heap
  - Link list

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數)
    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
    - 給定 Pre或Post或level或Inorder，求 Complete BT
    - 給定 Pre或Post或level，求 BST

DS with Algo(要知道怎麼寫、時間複雜度):
- BT recursive algo
  - BT Traversal
    - Preorder(T:BT),Postorder(T:BT),Inorder(T:BT)
      用Stack，O(N)
  - Copy(orig:BT)
  - Equal(S,T:BT)
  - Count(T:BT),CountDegree1(T:BT),CountDegree2(T:BT),Leaf(T:BT)
  - Height(T:BT)
  - Swap(T:BT)
  - Eval(T:expression BT)
    - 給定 expression，求 BT

- Tree's sorting
  - Heap sort
  - Search Tree

- BST
  Inorder可得小至大排序，RDL追蹤或stack可得大至小排序
  - Insert
  - Delete
  - Search(T:BST,x:Data)
    給定 BST及其Data range，求 平均比較次數

- Heap
  可製作Priority Queue
  - Insert
  - Delete-max or min
  - Search-max or min
  - Search
  - Build
    - Top-Down(邊Insert邊排序)
    - Bottom-up(全Insert再排序)
      - Adjust(tree,i,n)
      - CreateHeap(tree,n)
  - Merge???
  - Decrease key???
--------------------------------------------------------------------------
以下還未弄懂:

- Disjoint sets
  - Union by Weighting rule
  - Union by Height
  - Union by rank and path compression
  - Find(x) with Collapsing rule

- Find Equiv Sets
- Find connected components of undirected graph 找出無向圖之連通子圖

- Thread BT
  - Insuc(x)
  - Inorder Traversal
  - Insert T
......未完待續。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.171.169.22 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/talk/M.1728302183.A.159.html
推 cuteSquirrel: 該不會課本封面是一座橋吧 全部回憶都上來惹
其實我是補大碩的非本科生XD
推 cuteSquirrel: 如果是紙筆測驗的話 二元樹 二元搜尋樹 都很愛考
→ cuteSquirrel: Binary Tree, Binary Search Tree + 相關各種操作
→ cuteSquirrel: 進階的有可能考到平衡二元搜尋樹, AVL 樹, 紅黑樹
→ cuteSquirrel: 但是因為比較難，所以可能也就一兩題。
感謝！
※ 編輯: OriginalGod (1.171.169.22 臺灣), 10/07/2024 21:07:38
推 cuteSquirrel: 剛好路過 看到 希望對你有幫助 不客氣