先備知識與注意事項
先前的文章介紹過廣義的Tree(樹)、Binary Tree(二元樹)，這篇文章將繼續增加限制條件，使Binary Tree晉升成Binary Search Tree(BST，二元搜尋樹)。
這裡要處理的資料是日本漫畫的曠世鉅作《七龍珠》中各角色的戰鬥力。
七龍珠的劇情(正篇有七龍珠、七龍珠Z、七龍珠改、七龍珠GT、七龍珠超，劇場版還有七龍珠劇場版(太多了請參閱維基百科))時而前後連貫，時而交錯，為了維持每個系列之間的角色設定，就需要對角色設定進行管理，避免劇情不合邏輯，在此，筆者推薦鳥山明老師可以使用先進如BST的資料結構來整理角色的資料(當然，也是可以用excel或是國小生字簿，Whatever Works)。
熱血沸騰了。
目錄
引入Dictionary
搜尋與排序都需要「比大小」，欲執行「比大小」，就要使用「能夠比大小」的資料形態，亦即，兩個比較之物只能唯一滿足於「大於」、「小於」或「等於」之關係，最直觀的便是使用整數(integer)。
在先前的文章中，class TreeNode包含了指向child的pointer、指向parent的pointer，以及一個char data來儲存字母。那麼要使用char data進行「比大小」就必須而外自行定義規則，例如：「照字母順序排序，字母越前面值越大；若第一個字相同，則依序往下比較；若姓名中所有字母之順序皆相同則...」等等，已經有點麻煩，更別說是node所攜帶的資料項目比char data更複雜的情況，也許是一個姓名、一組帳戶資料、一本照片集、一組科學數據等等。
有鑒於制定規則的不方便，因此變通的方法就是直接在資料上加上「編號」，也可以想成，把資料對應(mapping)到特定編號或者賦予權重(weighting)，以編號/權重做為資料處理的依據，如排序、比大小、搜尋。
這樣的概念便是Dictionary，稱上述的「編號」為「Key(鍵值)」，稱「資料項目」為「Element(元素)」，並視一組「Key-Element pairs」的集合為Dictionary。
如圖一所示，若將先前的字母視為「Element」並加上「Key」，則(Key, Element)可以表示成(編號, A)，若處理學生資料，將編號視為學號，資料視為姓名，則能夠將(Key, Element)可以表示成(學號, 姓名)。
圖一：。
在接下來的篇幅，將使用七龍珠的角色姓名(悟空)作為Element，角色的戰鬥力視為Key：
圖二：。
修正後的class TreeNode可能長這樣：
// C++ code
class TreeNode{
private:
TreeNode *leftchild;
TreeNode *rightchild;
TreeNode *parent;
std::string data; // Element
int Key; // Key, used for comparison
...
};
備註：
- Dictionary的概念也出現在Hash Table、C/C++標準函式庫(Standard Library)中的container：
map等等，有非常多應用。 - 以下角色戰鬥力的絕對值是捏造的，不過相對值盡力維持正確(除了撒旦)，若有疑問，歡迎龍珠粉來信討論。
- 由於故事的角色眾多，以下將挑選較具有代表性的角色用來說明BST。
Binary Search Tree的特徵
有了加裝Dictionary後的TreeNode，便能夠說明BST的特徵。
- 任何CurrnetNode之Key若與其left child、right child之Key有以下關係(若pointer指向
NULL則忽略)：Key(L)<Key(Current)<Key(R)，則可稱這棵樹為Binary Search Tree(BST)。
以圖三為例，樹中有三個node，悟空的戰鬥力為\(1000\)，龜仙人的戰鬥力為\(8\)，克林的戰鬥力為\(2\)，若將龜仙人設為root，則克林的戰鬥力較小，因此成為龜仙人的left child，悟空的戰鬥力較大，便成為龜仙人的right child，如此便滿足Key(L)<Key(Current)<Key(R)，即可稱圖三為一棵BST。
圖三：。
有了BST後，便能夠替鳥山明老師處理角色之間的戰鬥力關係了。
在Binary Search Tree中管理資料
故事一開始的主要角色有悟空(\(1000\))、龜仙人(\(8\))和克林(\(2\))，以龜仙人為root能夠建立出一棵BST如圖四：
圖四：。
insert(新增資料)
隨著故事劇情推進，角色也會跟著增加，因此，要在BST中新增node(新增資料)。
「頭條！比克大魔王現身地球危害人間」，其戰鬥力為\(513\)，若要將其放進BST，根據BST的規則判斷出：
- 比克的戰鬥力比龜仙人高，因此要將比克放在龜仙人的right subtree(右子樹)；
- 接著再和悟空比較，比克的戰鬥力比悟空低，因此將比克建立在悟空的left child上，如圖五(a)所示：
圖五(a)：。
接著，賽亞人王子達爾登場，其戰鬥力為\(524\)，根據BST的規則，判斷出其應在「龜仙人的right subtree」、「悟空的left subtree」與比克的「right child」，如圖五(b)所示。
到目前為止，應該可以看出來，新增node需要先在BST中進行traversal，而且traversal的時間複雜度與height(樹高)成正比。
圖五(b)：。
search(搜尋資料)
在處理資料時，時常需要尋找某特定資料，是否存在資料結構中。以BST處理資料，最簡單的方式便是用Key尋找。
以圖六為例，故事推進到納美克星弗力札大王篇，若想要確認基紐隊長的資料是否已經建立完成，只要記住隊長的戰鬥力為「\(627\)」，進入BST中，便能夠找到隊長，必且回傳(return)隊長的node之資料、記憶體位置等等。
有時會出現欲搜尋的資料尚未被建立進BST中、或者已經從BST中移除的情況，例如，若要在悟空變成超級賽亞人之後找克林，以克林的戰鬥力「\(2\)」來搜尋，但是發現找不到，便回傳NULL。
因為克林被弗力札大王給殺死了啊啊阿啊(變身超級賽亞人)。
圖六：。
（界王神的聲音：為什麼root從龜仙人變成比克？不會違反BST規則嗎？詳見Red Black Tree系列之Rotation(旋轉)。）
sort(排序)
故事來到了魔人普烏篇，因為角色有點多，有點混亂，此時，若想要知道各角色戰鬥力的大小排序，只要按照Inorder Traversal即可按照戰鬥力(Key)高低列出所有資料：
圖七：藍色數字為戰鬥力(key)，紅色數字表示「戰鬥力由小到大」之順序。
delete(刪除資料)
最後，當角色死掉去領便當，就需要從BST刪除資料，而根據欲刪除資料之「child個數」可以分成三種情況：
- 刪除撒旦：撒旦在這棵BST中沒有child，因此，直接把撒旦的parent(普烏)之left child指向
NULL即可。 - 刪除弗力札：弗力札有一個child(left child)，因此刪除弗力札之前，需要先把弗力札的left child(基紐)接到弗力札的parent(龜仙人)上，又因為弗力札原本是龜仙人的right child，因此基紐將遞補弗力札，成為龜仙人的right child。
- 刪除西魯：西魯有兩個child，稍微麻煩一點，需要「多一個步驟」，將留待之後的文章做詳細說明。
圖八：。
根據以上的簡介，可以看出，新增資料(insert)、刪除資料(delete)本身都必須先執行一次搜尋(search)，而搜尋(search)的時間複雜度取決於BST的height(樹高)，因此，上面這三項操作的時間複雜度皆為\(O(height)\)。
特別注意，這裡的height什麼也無法保證，有可能運氣很好，BST很平衡(平衡的意思可以想成是Complete Binary Tree)，那麼height為\(\log{N}\)，如果運氣不好，BST退化成Linked list，那麼height為\(N\)。
運算成本當然是越低越好，所以才需要平衡的BST，例如Red Black Tree(紅黑樹)。後面的文章會再提到。
接下來，將以兩篇文章的篇幅，說明上述四種資料處理操作的演算法。
參考資料：
BST系列文章
Binary Search Tree: Intro(簡介)
Binary Search Tree: Search(搜尋資料)、Insert(新增資料)
Binary Search Tree: Sort(排序)、Delete(刪除資料)
回到目錄：