目錄
介紹
Binary tree
Binary search tree
關於Tree
樹是一種常見的資料結構，如生活中可用於表示父系族譜、電腦中可以表示檔案系統
除此之外也是加速搜尋的一種資料結構
樹的定義
樹是一種圖，所以具有點集合、邊集合
樹有兩個限制
- 樹是一個連通圖
- 樹不會有Cycle
這兩個定義可以導出一些性質
比如: 任何兩點間只會且只會有一條path、 樹是邊最少的連通圖…
可以用父系族譜來理解
任何一個被寫在族譜上的人，一定跟其他人有關係(條件1)
並且不可能有人同時是兩個父親的兒子(條件2)
舉例:
Binary Tree
比樹多加了一層限制 : 每個節點最多只會有兩個子節點
上面的例子中，右一就不是binary tree,右二、右三則符合binary tree
Traversal
任意一張圖都可以用BFS、DFS來遍歷，樹也不例外
但由於樹的特性，使我們可以用以下四種方式遍歷，並得到不同的順序
在此我們規定一律先探索左邊、再探索右邊
並以下圖為範例
一. PreOrder
先到先做事 (做事可以是讀取節點值、修改節點、刪除節點 ….等操作)
然後才依序拜訪子節點
做事順序為: A、B、C、D(C做完退回B、然後往右走)、E(B做完退回C、退回A…)
二. InOrder
第一(左)子節點做完事，才做事，然後再拜訪右節點
做事順序為: C (因為無左子節點==左子節點完事)、B、D、A、E
三. PostOrder
依序拜訪子節點 、節點都做完事、才做事
做事順序為: C、D、B、E、A
Note
這三種traversal都是固定順序拜訪節點的，只是做事時機不同
因此在遞迴時調整 traversal(左節點) traversal(右節點) DoSomething() 順序即可
Note2
因為固定都是下圖的順序
因此可以想像每個節點有個旗子，pre在節點右邊；in在節點下方;post在節點左邊
並依這個箭頭順序，碰到旗子，就是做事時機
四.level-order
就是BFS
Binary Search Tree
在binary tree的條件下，加上"比自己值大的節點在自己的右方、比自己值小的節點在自己左方”
下圖是個例子: 可以驗證看看
特化搜尋
這個資料結構如其名，就是為了搜尋效率而生，並且類似於binary search
以上圖為例
要搜尋9
首先問10，因為比10小，所以排除了比10大的右邊所有節點，如果這棵樹夠"平衡”(左右兩側所有節點數目相近)，則幾乎少搜尋一半的數量
而最糟情況下，BST只需要O(樹高)的時間完成搜尋
平衡的重要性
完美的平衡狀態是在任意節點的左子節點 == 右子節點
實務上可以差一個節點的高度 (考慮null)
此時樹高將會是logn
因此搜尋複雜度為O(樹高) == O(logn)
但是BST也可能依資料輸入順序導致形狀不同
比如 輸入 5 2 3 1 7 6 8
會是完美的平衡狀態
但 輸入 1 2 3 4 5 6 7 8
則會退化成1維的linked list，此時樹高==n，造成搜尋複雜度降為O(n)
因此以下的變體都是在追求樹的平衡
旋轉
以下變體都會用到的操作-旋轉
旋轉可以在改變形狀(就有機會改變樹高)的同時，不破壞BST的性質
舉例而言
可以看到直觀上y點往上旋轉
仔細看則是y與x父子角色對調 同時B過繼給x
- 不破壞其特性
原因大小順序沒有破壞
仍是 A中所有節點 < y < B中所有節點 < x < C中所有節點
直覺上，用一條線從左掃到右邊，只要相對位置沒有改變，怎麼旋轉都沒有關係
- 實作
實作上會用指標的調換
#維護父指標
y->parent = x->parent;
x->parent = y ;
B->parent = x ; # 過繼
#維護子指標
y->right = x ;
x->left = B;
左旋 右旋
上述例子是一個右旋，因為將節點往右上翻過去
而左旋則是相對右旋，基本上是對稱的操作
想像如果將linked list中間的點進行左旋，將會接近平衡狀態
就能改善樹高問題
操作的時間複雜度
插入: O(樹高) 最糟情況為插入點在leaf
搜尋: O(樹高)
刪除
依目標節點的子樹存在分為三種情況:
- 沒有子樹 - 直接改為Null即可
- 只有一邊有子樹 - 直接把child取代原節點即可
- 有兩棵子樹-
這種情況最麻煩，不能單純選一邊節點取代自己
因為不保證兩個子樹一定是中點
舉例如下
因此需要找 子樹中的極端值做中點
例如左子樹的最大值、右子樹的最小值
因為左子樹的最大值一定比右子樹都小
並且左子樹也不需要更動
右子樹最小值同理
刪除時間複雜度因此為O(2*樹高)
AVL tree
為BST加上條件: 左右子樹最高差不能超過1
這樣可以保證搜尋最佳化 (O(logn) n是節點數)
平衡因子 (Balance Factor)
用來記錄此節點左右子樹高差
我們這邊定義為 左樹高 - 右樹高
因此若範圍在 -1,0,+1 都是符合條件的
常見對樹的操作為插入、讀取、刪除、搜尋
很顯然唯讀型的讀取、搜尋 不可能破壞AVL tree性質
而插入或刪除則有可能造成左右兩側差距變大，因此我們先討論插入的情況
插入新節點
可以遞迴的定義插入AVL tree的情況:
Base Case :
樹符合AVL tree 條件
Recursive Case:
已知原本樹符合AVL tree條件
插入新節點後，會有下列三種情況
- 原本BF=0 ,插入新節點會變成 -1 or +1
- 原本BF=+1 or -1 ,插入新節點會變成 0
- 原本BF=+1 or -1 ,插入新節點會變成 +2 or -2
很明顯地，我們只需要解決第三種情況，就可以依數學歸納法保證插入一定
不會破壞AVL tree 性質
Case 3的四種情況
探討BF違反的最低處節點，可以分為四種情況
- LL (不平衡的節點被插入在)在左子節點的左邊
- RR 右子節點的右邊
這兩種情況很單純，只要把問題子節點透過旋轉拉上來即可
以下為LL例子
Note
為甚麼在意問題的子節點?旋轉的標的也是?
想想一根桿子，要拉成一半ㄑ型，必須從中點，子節點就是那個中點
- LR 左子節點的右邊
- RL 右子節點的左邊
這兩種情況就需要對子節點的子節點做兩次旋轉
以LR為例，就要先與子節點做右璇
然後再與問題最低點做左旋
原因:先把LR問題或RL問題歸化成LL問題或RR問題，再依法I解決即可
刪除節點基本上就是
結合BST的刪除法，加上AVL的調整
時間複雜度
由此可見，搜尋一定可以維持在O(logn)的良好狀態
但犧牲的成本是每次插入、刪除要花常數時間 旋轉
O(logn+k)
k是rotation時間