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

樹 (Tree)

表示方式

Link list
- Node: | Data | child 1 | child 2 | … | child k
- 假設 degree 為 $k$ ，並且有 $n$ 個節點，會浪費 $n*k-(n-1)$ 條 Link (Nil links)
轉為二元樹表示
Child-sibling 方法
- Node: | Data | child | sibling |
- child: 指向 leftmost-child
- sibling: 指向 次右兄弟
括號法
- 以 父(子1,子2,...子n) 表示父點與子點之間的關係，並且可以巢狀方式表示

二元樹第 $i$ level 的最多 Node 數為 $2^{i-1}$
高度為 $k$ $k$ 的二元樹，最多 Node 數為 $2^k-1$ $2^{k} - 1$
- 若二元樹有 $n$ 個 Node，則其最小高度為 $\lceil\log_2(n+1)\rceil$
給予一個非空的二元樹，若 leaf 有 $n_0$ 個，Degree-2 的 Node 數有 $n_2$ 個，則 $n_0 = n_2 + 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$ $n$ ，某 Node 之編號為 $i$ $i$ ，則:
  - 左子點編號為 $2i$ ，若 $2i > n$ 則無左子點
  - 左子點編號為 $2i+1$ ，若 $2i+1 > n$ 則無左子點
  - 父點編號為 $\lfloor i/2\rfloor$ ，若 $\lfloor i/2\rfloor < 1$ 則無父點
Strict BT (嚴格)
- 每個非 leaf 節點必有兩個子點 ( $n_1 = 0$ )

拜訪 BT 中每個 Nodes 各一次

$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$ $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}$

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

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

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

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

將 nil links 作為 Thread pointer，指向其他 Nodes
- x->lchild 作為左引線，指向中序順序中的前一個 Node
- x->rchild 作為右引線，指向中序順序中的後一個 Node
Structure
- Node: | 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$ 的中序後繼者
- 若 x->Right Thread == True，則 x->Rchild 即是
- 若 x->Right Thread == False
  - 沿著 $x$ 的右子點之左子點往左下尋找，直到該 Node 之 Left Thread==True (右子樹的最左子點)