本系列文章同步分享於個人Blog → InformisTry-HankLee

前言

第十二天我們介紹了Binary Search，而Binary Search在執行的過程中，每一次的迴圈都是將已經正序排列的陣列拆成兩半，且左半段的數值一定比右半段的數值小，而我們在第四天介紹抽象資料型別的時候有提到一個資料結構也是會分成左右兩邊的，那就是Rooted Tree，因此今天我們要介紹的Binary Search Tree（ＢＳＴ）就是結合了Binary Search和Tree的特性而產生出來的一個資料結構。

Binary Search Tree是怎樣的資料結構呢？

Tree這種抽象資料型別下面也是有多種不同實作方式的資料結構，而今天我們要講的這個Binary Search Tree只是其中的一種，再講Binary Search Tree之前，我們要先介紹Binary Tree（其結構示意圖如下）:

配合上方示意圖，可以說Binary Tree的架構很簡單，大概就是兩點：

1. 一個有『根』的樹狀結構
2. 每一個節點都包含不多於兩個子節點
3. 在每一個父節點都會記碌左子節點和右子節點的資訊。

在實作上，位於整個結構中最下方節點並不會有子節點，此時其左右子節點的紀錄方式則為null

而Binary Search Tree則是在更進一步地規範：所有位於父節點左邊的子節點，其值均比父節點之值小；反之，所有位於父節點右邊的子節點，其值均比父節點之值大；那如果有一個值跟父節點的值相同，則看是要放在父節點的左邊或是右邊都可以，但是實作上必須統一，不能在同一個實作中，有的放左邊，有的放右邊。下方圖中則是示範兩種不同結構的Binary Search Tree：

上圖左邊的是『平衡型』的Binary Search Tree，而右邊則是『未平衡』的Binary Search Tree，而Binary Search Tree的平衡與否，與其在進行資料結構轉換前的陣列內容有關，假設原先的陣列是正序或倒序排列，那轉換後的Binary Search Tree絕對會是像上圖右邊一樣，呈現一個『棒狀』結構，這樣的結構與線性結構大同小異，並不能展現Binary Search Tree的優勢。關於如何平衡Binary Search Tree，我們晚點再來說。

在進入到下一個項目前，還有一個很重要的事情要說，就是Binary Search Tree的高度(height)，在計算高度時，起始值跟Array的index相同，都是從0開始，也就是Root Node的Height是0，其子節點的Height是1，依此類推，因此上方圖中的兩個BST的Height都是3。

Binary Search Tree的演算法

既然BST是一種資料結構，那他當然也有Search, Insert, Delete這三種操作，下面我們來一一介紹：

1. BST Search

如同上面所說，在建構BST時，會依照值的大小排到左邊分支或是右邊分支，因此在做Search的時候，可以透過這個特性去找，其Pseudo-code如下：

// Input: A BST tree and a target to be found
// Output: A BST tree
function BSTSearch(BSTree, t){
    if (BSTree is empyt) or (BSTree.value == t) {
        return BSTree;
    }
    if BSTree.value > t {
        return BSTSearch(Left child node of BSTree, t);
    }else{
        return BSTSearch(Right child node of BSTree, t);
    }
}

BST Search也是透過遞迴的方式進行，假設還沒有找到目標所在的位置，就會依據當前節點的值和目標比較，進而再將sub-tree傳入BSTSearch中，再一次進行拆解與尋找；下方範例GIF檔應該可以更清楚的表達這個過程：

在做BST Search的時候，若這個BST的結構是Stick，那這個BST Search的Worst Case時間複雜度為?(n)；但是，如果這個BST是balanced，那Worst Case就變成了?(㏒2 n)。

2. BST Insert

BST在做Insertion的時候，也是很簡單的，也是依據值的比較，來決定要加在哪一個節點下面，我們透過GIF來了解過程吧：

3. BST Delete

Deletion在BST裡面則比較麻煩，他有三種情況是需要被考慮的：

(1) 要刪除的Node並沒有任何的child node:

這個情況下的處理很簡單，由於這個要刪除的node並沒有其他child node，因此，直接斷開這個node相關的連結即可。

(2) 要刪除的Node有一個child node:

因為在BST裡面存在著parent-child的關係，因此每個node都會記錄期parent node和children node的資訊，當現在要刪除的Node(A Node)是有一個child node(C Node)的時候，即表示對於這個要刪除的node的parent node(B Node)而言，B Node要將原先紀錄A Node的資訊更改成C Node，而C Node則是將其parent node由原先的A Node改成B Node，這樣與A Node有關的所有連結都消失了，等同於A Node從BST中刪除了。

(3) 要刪除的Node有兩個child node:

當這個要刪除的Node有兩個child node的時候，我們則是要從他所有的child node中尋找能夠換到這個位置的Node，通常會有兩種方式，一是用左邊分支中最右下的Node或是其右邊分支最左下的Node去取代，二是若其中一個child node也只有連接一個child node，那也可以用這個child node來取代，因為僅有這兩種狀況其Node被置換到該位置後，不破壞BST的規則，有點複雜，看看下面GIF吧：

小結

1. Binary Search Tree的三個重點：有根、兩個children node、左小右大。
2. Stick BST的時間複雜度比Balanced BST大。
3. BST的Deletion要考慮多種情況。

預告

明天我們將會繼續介紹BST。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin