這章節要來探討Map和Set背後的實作到底怎麼做到的。

先前討論過LinkedList，其實就是一個可行的實作方法，但是有個致命的缺陷，就是add跟contains時，runtime將會是Θ(N)，因為我們必須要遍歷整個list才能確切知道要操作的位置在哪裡：

有沒有什麼辦法可以讓search的動作變得更有效率？有的，如果我們把初始的index放在中間而非開頭（或結尾），是不是search的範圍就減半了：

看起來很不錯，但不僅止於此，我們甚至可以把這個概念套到中間以外的元素群：

以上就是鼎鼎大名的BST(Binary Search Tree)。

BST只是tree的其中一種，要了解BST，首先先了解一下tree是什麼：

• 任意兩個節點只有一條路徑可互通。

所以以下圖案只有綠色符合定義，紅色就不能稱為Tree。

而Binary Tree得符合：

• 每個節點下一層都最多只有2個小孩

最後，BST還得符合一個定義：

• 每個節點左側的小孩需大於自己；右側小孩需小於自己
• 不會有重複的節點(key)

接著我們來看看BST的威力！

一開始我們討論到，假設用LinkedList來實作Set或Map的話，在add和contains方法將會是Θ(N)的效率；而BST呢？

由於BST的定義導致每一層都可以輕鬆判斷大小，並且就只有左邊或右邊的選擇，等於是說每一層的選擇都讓之後的搜尋範圍減半！最終我們的runtime就是取決於整棵BST的height，也就是

Θ($\log_{2} N$)，以asymptotics分析來說，我們就會把2為底忽略，也就是Θ(logN)。

要知道，logN是很可怕的效率，老師舉了一個例子，假設電腦要花1微秒（百萬分之一秒）執行一次binary判斷，則logN的效率要處理10^300000大小的Map，只要花一秒。

BST的search和insert方法的實作都滿直覺的：

public static BST search(BST T, Key k){
    if(T == null){
        return null;
    }
    if(T.key == k){
        return T;

    }else if(k < T.key){
        return find(T.left, k);

    }else if(k > T.key){
        return find(T.right, k);
    }
}

public static BST insert(BST T, Key ik) {
		if (T == null){
		  return new BST(ik);
		}
		if (ik ≺ T.key){
		  T.left = insert(T.left, ik);

		}else if (ik ≻ T.key){
		  T.right = insert(T.right, ik);

		}
		return T;
}

不過delete就比較難了，因為為了維持BST的定義，在把node拿掉後，會有重新排序Tree的議題。

首先我們會有三種可能的情形：

第一種最單純，假若要刪除的node沒有child，那就是從它的parent把連結移除即可：

第二種也不會太麻煩，有鑒於binary search的特性，要刪除的節點其小孩也一定會大於(或小於)parent，所以只要把連結挪到他小孩身上即可：

第三種乍看之下很頭大，因為感覺會大風吹！該如何去重新建立連結去把斷層的節點補起來呢？其實如果仔細思考之後會發現比想像中簡單：

關鍵在於新的節點只要能夠滿足讓左邊的節點都小於它以及右邊的節點都大於它即可，這樣思考下就可以發現，那就是找左邊Tree中最大的節點，抑或右邊Tree中最小的節點，都可以滿足這個條件，所以其實最終的改動比想像中還小～

這個實作概念被稱作Hibbard deletion。

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License