About Tree

Tree的完整整理：
Tree
定義：
1. 不允許Null Tree
2. 必存在Node Root
3. 其餘Nodes形成Subtree

Binary Tree
定義：
1. 允許Null Tree
2. 0<=degree<=2
3. Subtree有順序之分

Binary Tree Three Rules
1. i-level Tree：Nodes Max = 2^(i-1)
2. k-height Tree：Node Max = 2^k-1
3. N(Node numbers) = n0(leafs numbers) + n1(degree 1 numbers) + n2(degree 2 numbers) ; n0 = n2 + 1

Special Binary Tree
1. Skewed Binary Tree (left or right)
2. Full Binary Tree (every level is full)
3. Complete Binary Tree (every nodes degree=2)

Binary Search Tree
定義：
1. Binary Tree的一種
2. L.child < Root < R.child
3. L.child and R.child are Binary Search Tree

Extend Binary Tree
1. Binary Tree的一種
2. 在原有子葉n個節點上，加入n+1個空連結形成Complete Binary Tree，額外的節點稱為外部和失敗節點
3. E：外部節點；I：內部節點。用Level算內外部路徑，E.I.成正比，即Complete Binary Tree的E.I.有Min；加權後，則不一定。

M.W.E.P.L. Problem
使用Huffman Algorithm（霍夫曼演算法）解決之。
Tip：挑選兩個Min Number為Child建立子樹。

AVL Tree
1. 為BST的一種，左右子樹高度差不能超過1
2. Balance Factor Value is (-1,0,1)
3. L.child and R.child are AVL Tree
Node計算
要形成樹高h的AVL Tree：最少需要F(h+2)-1個Nodes

B-Tree
1. Balance m-way Search Tree
2. Root至少要有2個Child Node
3. 除了Root與Terminal Nodes外，其餘Nodes符合[m/2] <= degree <= m
Node計算
最多Node數；[m^n-1]/[m-1]
最多鍵值個數：m^n-1