二元樹

閱讀本文之前，建議讀者對指標要先有一點基本認識。如果需要學習資源的話，可以看這裡。

在學過了 Stack、Queue 與 Deque 和 Linked List 後，雖然這些資料結構已經可以幫我們做到許多事情，但想必讀者也注意到了這種序列狀的資料結構勢必有其不足之處，像是要在中間插入資料時特別慢。要做出更複雜、更強大的資料結構，我們經常會轉而使用樹狀的資料結構。

什麼是樹呢？資訊領域中的「樹」是一個由「節點」和「邊」組成的圖。

像是上圖中，每個圓圈就是一個節點（node 或 vertex），標在節點裡的數字是節點的編號，而節點之間的連線就是邊（edge）。有的時候我們會指定一個節點當作根節點（root）並畫在最上面，像是上圖的根節點就是節點 $1$，跟現實中的樹相反，我們會把一棵樹從根開始由上往下畫。

• 每個節點頭上連著的那個節點是它的父節點（parent），而底下吊著的節點則是它的子節點（child），例如上圖中，節點 $2$ 的子節點有節點 $3,4,5$，而節點 $2$ 是節點 $3,4,5$ 的父節點。
• 一個節點的父節點、父節點的父節點、……、一路到根的這一連串節點，就是這個節點的祖先（ancestor），反過來說，一個節點的子節點、子節點的子節點、……，就是它的子孫（descendant）。
• 某一節點 $v$ 和它底下所有子孫的這整群節點，就稱為以 $v$ 為根的子樹（subtree）。
• 根節點的深度（depth）是 $0$、往下一層的節點，也就是根節點的子節點的深度是 $1$、再往下一層的深度是 $2$……依此類推。整棵樹的深度，或者說是它的高度（height），是樹中最大的深度。

有一種特別的樹叫作二元樹（binary tree），意思就是樹上的每一個點都至多有兩個子節點，更進一步的，在把二元樹變成資料結構的時候，我們喜歡讓二元樹的子節點有左右之分，左邊的子節點就叫左子節點、右邊的就叫右子節點，兩個子節點為根的子樹分別叫作左子樹和右子樹。就算某個節點的子節點只有一個，它也會被規定是左子節點或右子節點。

二元樹的好處，就是它既是樹狀的，又足夠簡單，很適合作為資料結構使用。接下來我們就介紹一種基於二元樹的資料結構：二元搜尋樹。

樹狀資料結構中，每一個節點通常會維護一筆資料，稱作它的 key，我們就假設這個 key 是一個整數，並且用節點內的數字表示。二元搜尋樹的目的是維護一組有順序的資料，例如維護數字從小到大的順序，不過樹又不是序列，我們要怎麼規定資料在樹上的順序？於是在使用二元搜尋樹的時候，我們就規定

• 把所有節點的 key「從左邊到右邊讀」所讀出來的順序，是我們想要維護的順序。

還記得我們剛剛說子節點有左右之分嗎？所謂的「從左邊到右邊讀」，就是指好好的把二元樹按照左右之分畫好，從位於最左邊的節點開始念出每個節點的 key，更正式地說，就是

• 先去讀根節點左子樹的 key。
• 再讀根節點的 key。
• 最後再讀右子樹的 key。

在讀子樹的時候，就是把它當作一棵小一點的二元搜尋樹，用一樣的方式讀完整個子樹。用這個順序去讀，或更正式地說是「遍歷（traverse）」一棵樹的方式，有一個正式的名字叫作「中序遍歷（inorder traversal）」。舉例來說，在下圖的兩棵樹中，「從左讀到右」的順序都是 $1,2,3,4,5,6,7$，如果我們要的順序就是 key 由小到大排序過的順序，那它們都是符合規定的二元搜尋樹！

更正式一點的說，一棵二元搜尋樹除了得是一個二元樹以外，還要滿足以下條件：

這跟「中序遍歷必須是將 key 由小到大排序後的順序」是一樣的意思，因為「先走左邊、讀根節點、再走右邊」的意思就是要左邊 $\leq$ 中邊 $\leq$ 右邊嘛。

剛才我們說到，二元樹既是樹狀的，又足夠簡單──當我們要儲存一個二元樹時，只需要儲存每個節點的左右子節點分別是誰，或是沒有左右子節點就好，實作方式其實與 Linked List 很類似，就只是把「儲存前後的節點」改成「儲存左右子節點」，有需要時頂多再多存父節點即可。有了樹狀結構的幫忙，我們可以做到很多事情，接下來我們會大致暸解一遍二元搜尋樹支援的基本操作，不過多數時候我們都不需要自己寫出一棵二元搜尋樹，例如之後的文章就會介紹 STL 提供的 Set 與 Map，它們都是現成的快速又好用的二元搜尋樹，因此我們會將重點放在暸解二元搜尋樹是如何辦到這些事情的，而非具體的實作細節。

• 給定一個 key $x$，要怎麼找到一個有著這個 key 的節點？

二元搜尋樹的核心精神，是當我們要做任何事情時，就想辦法從根節點走到我們要去的地方。有了二元搜尋樹性質的幫助，這件事情變得非常簡單，我們從根節點開始，然後：

• 如果目前節點的 key 剛好就是 $x$，那我們就找到了。
• 如果目前節點的 key $< x$，我們知道 $x$ 應該要出現在右子樹，所以我們往右子節點走。
• 如果目前節點的 key $> x$，我們知道 $x$ 應該要出現在左子樹，所以我們往左子節點走。
• 如果要走的那個子節點不存在，就代表不存在 key 是 $x$ 的節點。

這樣一來，我們就會往 key 是 $x$ 的節點直線前進，如果它的深度是 $d$，這個動作的時間複雜度就是 $O(d)$。

讀者可能有注意到，這個過程和基礎演算法 / 搜尋中提到的二分搜尋法非常相似，事實上，在二元搜尋樹上搜尋的過程，是完全可以解釋成二分搜尋法的：每一個子樹在中序遍歷中，都會是連續的一個區間，目前所在的節點為根的子樹，就是二分搜尋法中我們已知答案所在的區間，而根節點就是接下來我們把區間分成兩半的分界點，唯一的不同之處只有在二分搜尋法中，我們總是會選擇區間的正中央作為分界點，而在二元搜尋樹中，每次的分界點是被樹的結構（誰是子樹的根節點）所決定的。

既然搜尋的過程其實就是二分搜尋法，那我們還要一個樹狀結構幹嘛呢？二元搜尋樹厲害的地方就在於，我們還可以插入節點！

當要新增一個 key 是 $x$ 的節點時，我們就是要找到它應該所在的位置，方法與搜尋大同小異，我們一樣從根節點開始走：

• 如果目前節點的 key $< x$，我們知道 $x$ 應該要出現在右子樹，所以我們往右子節點走。
• 如果目前節點的 key $> x$，我們知道 $x$ 應該要出現在左子樹，所以我們往左子節點走。
• 如果目前節點的 key $= x$……那新的這個節點我們要放左邊還是右邊都可以，隨便往其中一邊走都行。
• 當要走的那邊已經沒有子節點了，那新加的這個節點就是那個子節點啦。

和搜尋差不多，我們筆直地朝著要插入的位置前進，因此若插入後的節點深度是 $d$，時間複雜度就是 $O(d)$。這裡就顯現出了二元搜尋樹相較於一般在序列上的二分搜的優勢：要在一個序列中插入新的元素很麻煩，但在二元搜尋樹上輕而易舉。

二元搜尋樹不只可以新增節點，刪除節點也是可以的，但是為了好好維持二元樹的結構與搜尋樹的性質，要做的事情就比較複雜了點，一種作法是：假設我們要刪除的節點叫作 $v$，然後

1. 如果 $v$ 是葉節點，直接刪掉就可以了。
2. 如果 $v$ 只有一個子節點，那把 $v$ 丟掉、把它的子節點接上它的父節點就可以了。
3. 如果 $v$ 有兩個子節點，找到左子樹裡最右邊的節點 $u$，把這兩個節點交換位置，然後重複這整個流程，直到進入前兩個 case 的其中一種為止。
   • 找到這個 $u$ 的方式，就是先往左子節點走，再不斷往右子節點走。
   • $u,v$ 在中序遍歷上是相鄰的，因為最後 $v$ 會消失，所以不用擔心最後會違反樹性質！

想像一下過程，我們走過的路線其實就是從根節點一路走向 $v$ 最終消失的位置，同樣的，如果那個位置的深度是 $d$，這個動作的時間複雜度就是 $O(d)$。

以上三種操作就是二元搜尋樹可以支援的最基本操作，Set 與 Map 都支援這些操作。綜上所述，如果我們最後操作到的節點位置深度是 $d$，要花費的時間就是 $O(d)$，因此我們可以說每次操作的時間複雜度就是 $O(\text{樹的高度})$，要是我們的二元搜尋樹總是不太深，那就很好，但是天底下沒有那麼好的事情，如果用我們上述的插入方法，用 $1,2,\dots,n$ 的順序插入節點的話，我們的樹就會長成：

從最上面到最下面足足有 $n$ 個節點！而且光是這個插入過程，就會花上 $O(1+2+\dots+n)=O(n^2)$ 的時間，真是太可怕了。

還記得我們剛剛說二元搜尋樹的搜尋其實就是二分搜尋法嗎？既然一般的序列上的二分搜只要花 $O(\log n)$ 的時間，我們可不可以想辦法保證二元搜尋樹的高度永遠都是 $O(\log n)$，然後每次操作就只需要花 $O(\log n)$ 的時間？答案是可以。我們的問題出在於，每次我們修改樹的結構，都只在乎要維持搜尋樹的性質，也就是 key 的大小關係而已，有很多種不同的二元搜尋樹演算法可以在這個過程中，同時控制樹的高度，這種二元搜尋樹也叫作平衡二元搜尋樹（balanced binary search tree 或 self-balancing binary search tree）。

像是 STL 中的二元搜尋樹 Set 與 Map，使用的都是一種叫作紅黑樹（red-black tree）的平衡二元搜尋樹，紅黑樹可以保持整棵樹的高度都在 $O(\log n)$ 之內，所以我們就可以快樂地在 $O(\log n)$ 的時間內做到以上那些操作，然而紅黑樹寫起來相當地複雜，在未來我們也會有需要自己寫平衡二元搜尋樹的時候，通常會改用一些比較好寫的平衡二元搜尋樹，不過寫起來還是有一些麻煩，幸運的是大多數時候 set 或 map 的功能就很夠用了，等到未來真的不夠用時，我們會再介紹怎麼自己寫平衡二元搜尋樹，本文章只是作為基本知識的介紹。

以下是一個實作一棵二元搜尋樹的練習題，測資是隨機生成的，你可以假設你按照上述方法寫出的二元搜尋樹可以通過這題。