Binary Tree

Binary Tree

又稱為 Knuth Tree , Ordered Tree
有限集合，可以為空
若非空則由左子樹、右子樹構成
每個 Node 之 Degree：0~2
子樹有次序之分

次序

子樹 B,C 在 Tree 中視為相同
在 Binary Tree 中視為不同

Difference with Tree

	Tree	Binary Tree
可否為空	$N o$ , 至少一樹根	$Y e s$
$N o d e D e g r e e$ (存在 $R o o t$ 時)	$\geq 0$	$0, 1, 2$

Three Theories of Binary Tree

[定理一] 第 i Level 最多
$N o d e$ 數

Def : 高度起始點為 1
Formula：
$2^{i - 1} ， i \geq 1$

證明方式：數學歸納法

Def : 高度起始點為 0
Formula：
$2^{i} ， i \geq 0$

證明方式：數學歸納法

[定理二] Height 為 k 的最多 Node 數 (整棵樹)

Def : 高度起始點為
$1$
Formula：
$2^{k} - 1, k \geq 1$

根據定理一：2⁰ + 2¹ + … + 2^k-1 從 Level 1 依序累加至 Level k

根據等比級數 =
$\frac{2^{k} - 2^{0}}{2 - 1}$

=
$2^{k} - 1$

Def : 高度起始點為
$0$
Formula：
$2^{(k + 1)} - 1, k \geq 0$

根據定理一：
$2^{0} + 2^{1} + . . . + 2^{k}$ 從
$L e v e l 0$ 依序累加至
$L e v e l k$

根據等比級數
$= \frac{2^{(k + 1)} - 2^{0}}{2 - 1}$

=
$2^{(k + 1)} - 1$

藉由上述定理我們可以對 Node 數取 log 反推回高度

[定理三] Branch(Degree) 與 Node 關係

Leaf 數 = L (綠色node)
Branch 數 = B (藍、紅 Degree)
Nodes 數 = N
Degree 為 1 的 Nodes = d₁ (藍色node)
Degree 為 2 的 Nodes = d₂ (紅色node)

在上述圖例得知

$L + d_{1} + d_{2} = N o d e$ 總數
二元樹中 Degree 為 0~2 ( 之後的 m-way Tree 同理 )
Degree 為 1 的 Node 有 1 個 Branch
Degree 為 2 的 Node 有 2 個 Branch
而
$(B r a n c h$
$數)$
$+ 1 = N o d e$ 總數
所以
$(1 * d_{1} + 2 * d_{2}) + 1 = N o d e$ 總數
藉由上述兩公式我們可以整理出

$L + d_{1} + d_{2} = N o d e 總數 = d_{1} + 2 d_{2} + 1$

$L = d_{2} + 1$
$(樹葉 = D e g r e e 為 2 的 N o d e s + 1)$

整理一下目前有的公式

Def : 高度起始點為 1
1. 第 i Level 最多 Node 數：
  $2^{k - 1}$ –––––-( 2的高度-1次方 )
2. Height 為 k 的最多 Node 數：
  $2^{k} - 1$ ––( 2的高度次方-1 )
3. Node總數 =
  $L + d_{1} + d_{2}$ –––––––( 樹葉 + Deg1的Nodes + Deg2的Nodes )
4. Node總數 = (
  $1 * d_{1} + 2 * d_{2}) + 1$ ––( 1倍Deg1的Nodes + 2倍Deg2的Nodes +1 )
5. Node總數 =
  $B r a n c h + 1$ ––––––––( 分支+1 )
6. 樹葉 =
  $d_{2} + 1$ ––––––––––––––-( Deg2的Nodes+1 )
7. Branch = 所有 Degree 合

補充：針對 3. 4. 的設計題
某樹之
$D e g r e e o f t r e e = k$ ( 最大Degree 為k )

$D e g r e e 為 i$ 的
$N o d e s$ 有
$i$ 個，
$1 \leq i \leq k$ ，求
$L e a f$ 總數？

Sol：

根據 3.
$N o d e s = D e g - 0$ 個數
$(L e a f) + D e g - 1$ 個數
$+ . . . + D e g - i$ 個數

從題目
$1 \leq i \leq k$ 得
$N o d e s = L e a f + 1 + 2 + . . . + k$
根據等差級數
$N o d e s = L e a f +$

根據 4. Nodes = ( 1 * d₁ + 2 * d₂ ) + 1
從題目
$D e g r e e 為 i 的 N o d e s 有 i 個$ 得 ( 1 * 1 + 2 * 2 + … + k * k ) + 1
根據平方合 Nodes =

移項即可得 Leaf =

關鍵字 Degree-0 (Leaf) , Degree-1 , Degree-2 , Height , Nodes , Branch 互通到熟練吧

Type of Binary Tree

Skewed Tree - 斜曲樹

左斜曲：每個非樹葉節點只有左子點。
右斜曲：每個非樹葉節點只有右子點。

Complete Binary Tree

由上至下由左而右依序填入

Def：編號 (Index) 起始點 1 , 某Node編號 = n
Left Child 編號 = Parent 編號 * 2
Right Child 編號 = Parent 編號 * 2 + 1
n's Parent 編號 =
$⌈ \frac{(n - 1)}{2} ⌉$

Def：編號 (Index) 起始點 0 , 某Node編號 = n
Left Child 編號 = Parent 編號 * 2 + 1
Right Child 編號 = Parent 編號 * 2 + 2
n's Parent 編號 =
$⌊ \frac{(n - 1)}{2} ⌋$

[color=#] 計算完請判斷該樹是否存在此節點
Parent , Child 編號關係證明：數學歸納法（略）

Def：高度起始點 1

根據定理二得出 k Level 的最大 Node 總數 =
$2^{k} - 1$
根據 Complete Binary Tree 特性，若高度
$k$ ，則
$N o d e s$ 必介於

$k$ 層第
$1$ 個：
$(2^{k - 1} - 1) + 1$ (藍色 Nodes) 到

$k$ 層最後一個：
$2^{k} - 1$
$N o d e s$ 之間

因此我們得知，給定一 Complete Binary Tree

$2^{k - 1} \leq N o d e s \leq 2^{k} - 1$

Strictly binary tree

除了 Leaf 以外，每個 Node 都有兩個 Child。
$N o d e s = n_{0} + n_{2}$

Full Binary Tree

長滿整棵樹，Nodes 等同定理二

Binary Tree Representation in C

Array

Def：編號 (Index) 起始點 1 , 高度 = k

假設 k = 3

建立一個 int tree[] 陣列，空間為：2^k-1 = 8 = s
Index：0 ,1 ,2 ,3 ,4 ,5 ,6 ,7

若使用迴圈，終止條件為

i<2^k-1 = 8-1 = s-1

i<=2^k-2 = 8-2 = s-2

存在情況下，設某點為 n

Root = tree[1]

n's Parent = tree[n/2] * 請注意程式語言對浮點數處理特性

n's Left Child = tree[2*n]

n's Right Child = tree[2*n+1]

Def：編號 (Index) 起始點 0 , 高度 = k

假設 k = 3

建立一個 int tree[] 陣列，空間為：2^k+1-1 = 8 = s
Index：0 ,1 ,2 ,3 ,4 ,5 ,6 ,7

若使用迴圈，終止條件為

i<2^k+1-1 = 8-1 = s-1

i<=2^k+1-2 = 8-2 = s-2

存在情況下，設某點為 n

Root = tree[0]

n's Parent = tree[(n-1)/2] * 請注意程式語言對浮點數處理特性

n's Left Child = tree[2*n+1]

n's Right Child = tree[2*n+2]

優點：

容易存取左右 Child
若 Perfect Binary Tree 則完美利用空間 (Def：root start from index 0)

缺點：

插入、刪除不便
Height 改變則需重新宣告新陣列
對於 Skewed Binary Tree 極為浪費
( Def：root start from index 0 , Height = k = Nodes , 2^k-1-k 未使用)

Linked List

Def：Nodes = n

Linked List 中的 Link 相當於定理所提到的 Branch
而在程式當中每個 Node 結構都有兩條 Link，有別於定理中的觀念
我們會將指向 Null 的 Link 也一併算進去 (藍Link)
實際上公式還是可行的，只要我們將 Null 也視為 Node

不過我們想探討的是沒有使用到的 Link (藍Link)
以下將 Branch 視為 Link

Links = 所有 Degree 合
因為每一個 Node 皆有 2 個 Links
=> 所有的 Links = 2*n

根據定理
有使用到的 Links = n - 1

根據 3. 4.得出
=>所有的 Links - 有使用到的 Links = 未使用的 Links
=> (2 * n) - (n-1) = n+1

可以這樣記 n-1 (未使用的LINK) -> n (Nodes) -> n+1 (使用的LINK)

優點：

Node 插入、刪除方便
對於 Skewed Binary Tree 完美利用空間

缺點：

各 Node Parent 不好尋找
幾乎有
$50 % L i n k s$ 未使用到，即指向
$N U L L$ 的
$L i n k$
(因此延伸出了 Threaded Binary Tree - 引線二元樹)

Binary Tree Traversal

to be continued

Multiple Structures of One Binary Tree

回憶一下，以下兩種結構的樹，如果是 Tree 那麼兩顆是一樣的，如果是 Binary Tree 則是不同的
此節探討的就是當 Binary Tree 具有 N Nodes (N
$\geq$ 1)，那麼這棵樹有幾種表示的方法，也就是他有幾種不同的結構

Formula

$\frac{1}{n + 1}$
$(\begin{array}{ccc} 2 n \\ n \end{array})$
給 3 Nodes 畫出所有的可能的 Binary Tree

Solution：
$\frac{1}{3 + 1}$
$(\begin{array}{ccc} 2 * 3 \\ 3 \end{array}) = 5$

Proof

to be continued
p.194

Binary Tree

次序

Difference with Tree

Three Theories of Binary Tree

[定理一] 第 i Level 最多 Node 數

證明方式：數學歸納法

證明方式：數學歸納法

[定理二] Height 為 k 的最多 Node 數 (整棵樹)

根據定理一：20 + 21 + … + 2k-1 從 Level 1 依序累加至 Level k

根據等比級數 = 2k−202−1

= 2k−1

根據定理一：20+21+ ... +2k 從 Level 0 依序累加至 Level k

根據等比級數 =2(k+1)−202−1

= 2(k+1)−1

[定理三] Branch(Degree) 與 Node 關係

Type of Binary Tree

Skewed Tree - 斜曲樹

Complete Binary Tree

Strictly binary tree

Full Binary Tree

Binary Tree Representation in C

Array

Linked List

Binary Tree Traversal

Multiple Structures of One Binary Tree

Formula

Proof

tags: Data Structure

Read more

PaddleOCR

Data Structure Note

Heap

M-way Search Tree

[定理一] 第 i Level 最多
$N o d e$ 數

根據定理一：2⁰ + 2¹ + … + 2^k-1 從 Level 1 依序累加至 Level k

根據等比級數 =
$\frac{2^{k} - 2^{0}}{2 - 1}$

=
$2^{k} - 1$

根據定理一：
$2^{0} + 2^{1} + . . . + 2^{k}$ 從
$L e v e l 0$ 依序累加至
$L e v e l k$

根據等比級數
$= \frac{2^{(k + 1)} - 2^{0}}{2 - 1}$

=
$2^{(k + 1)} - 1$

tags: `Data Structure`