複習我們都曾學過的 binary search tree
簡介
為了後面的 treap 和 skip list 所以決定先來寫一篇 binary search tree 作為複習，相信大家沒學過也聽過 binary search tree，是本科大學資結在學 tree 的時候最先學到的幾種之一，今天就來好好的重溫天真美好的大學時光吧。以下簡稱 binary search tree 為 BST。
先給大家最關心的時間與空間複雜度：
定義
我們先來說說 BST 的四條定義：
- 以左邊節點 ( left node ) 作為根的子樹 ( sub-tree ) 的所有值都小於根節點 ( root )
- 以右邊節點 ( right node ) 作為根的子樹 ( sub-tree ) 的所有值都大於根節點 ( root )
- 任意節點 ( node ) 的左、右子樹也分別符合 BST 的定義
- 不存在任何鍵值 ( key/value ) 相等的節點。
（謎之音）：很多人會不記得第四點，但遇過面試有問，但想一下就會知道如果有相等值的節點就會違反第一點或第二點。
Binary Search
既然稱為 binary search tree，那想必跟 binary search 脫不了關係，沒錯 BST 便是基於 binary search 而建立的資料結構，BST 也可以說是為搜尋而生的，所以搜尋的時間複雜度當然也要能達成 O(log n)，但不是說使用了 BST 做搜尋就一定可以穩定 O(log n)，如同上圖所示，搜尋的最差情況是在 O(n) ，關鍵就在平衡，在講平衡之前，我們先來講樹高。
以 3 個 node 的 BST 為例，有三種排列可能（就不列 10 -> 20 -> 30 了，跟第二種差不多，只是左右反過來）
好，那今天如果我們要搜尋 10 這個鍵值：
- 第一種排列：只需要一次比較（從 root 進入，10 < 20，往左走，找到了）
- 第二種排列：需要兩次比較（從 root 進入，10 < 30，往左走，10 < 20，繼續往左走，找到了）
所以我們可以看到在一樣數量的 node 的情況之下，不一樣的樹高對搜尋產生的影響是很關鍵的，如果有平衡就可以讓樹高在最理想的情況，使搜尋可以達到 O(log n)。
如果平衡的話，假有共有 n 個節點，那麼樹高應該就是 ( log n ) + 1。
四種操作
接下來介紹搜尋、新增、改值、刪除四種操作
新增節點
假設我們今天要把值為 15 和 40 的節點新增進去
先做 15 的節點：
- 與 root 節點 ( 20 ) 比較，15 < 20，左子樹不為空，往左子樹走
- 與節點 ( 10 ) 比較，10 < 15，右子樹為空，就把 15 填進去
相信聰明的你已經知道怎麼新增節點了，試試看把 40 新增進去吧。
沒錯就是這樣，按照上面的邏輯 40 就應該放在 30 的右邊（右子樹）。
搜尋結點
假設我們要搜尋 15 這個節點，其實跟新增的步驟差不多，先逐一比大小，差在要確認經過的節點的值是不是 15 即可。
- 與 root 節點 ( 20 ) 比較，15 < 20，往左子樹走
- 與節點 ( 10 ) 比較，10 < 15，往右子樹走
- 與節點 ( 15 ) 比較，15 == 15，找到了！
修改節點的值
我上網查發現沒有什麼人講到如果要改值的話怎麼操作最有效率，但最簡單的方法應該是就把該舊值的節點刪除，然後插入更新值的節點。
刪除節點
我們先來列出刪除節點的四種可能：
- 該節點沒有左右子樹
- 該節點只有右子樹
- 該節點只有左子樹
- 該節點有左右子樹
第 1 種情況是最簡單的，只要直接刪掉就可以了。
再來是第 2 種，也是很簡單，只要刪掉節點，然後把父節點 ( 20 ) 連到右子樹的 root ( 15 ) 即可。
第 3 & 4 種其實做法是一樣的，就是要找被刪除的節點的左子樹中最大值的節點，然後取代被刪除節點的位置。
實作
又來到實作的時間啦
先來定義兩個 class，把操作方法定義在 BST 裡面
新增節點：
以 root 為起點開始比大小，直到發現空位就可插入，這邊是用 loop 的方法來寫，也可以用遞迴的方式來寫。
搜尋節點
基本上跟新增一樣，也是去比大小，找到的話就回傳。
刪除節點：
刪除就很麻煩了，記得我們上面說的四種可能：
- 該節點沒有左右子樹
- 該節點只有右子樹
- 該節點只有左子樹
- 該節點有左右子樹
我們需要分開處理：
第一和第二點跟上面說的差不多，只要記得檢查是不是 BST 的 root 即可，是的話要 update BST 中的 self.root。
第三和第四點就有一點複雜了，分成幾種情況：
被刪除的 node 的 left sub-tree 的 root 是否為該 sub-tree 最大值的 node
if true：
就把 left sub-tree 的 root 接上被刪除的 node 的位置，結束。
if false：
被刪除的 node 的 left sub-tree 的最大值的 node 是否有 left sub-tree，有的話要先接回 left sub-tree 的最大值的 node 的 parent node，才能把最大值的 node 取代原本刪除的 node
檢查被刪除的 node 是不是 BST 的 root，是的話要 update BST。
寫完覺得看起來還是很複雜，說不定直接看 code 最好懂。
後記
上一篇已經不知道隔了多久，養成一個好習慣果然是很困難的事啊。總之寫了兩篇基本的資料結構，下篇決定要來寫有趣一點的，請大家敬請期待啦。
感謝你/妳花時間讀這篇文章，如果你覺得這篇文章寫得不錯、有幫助到你，希望你能給我一點「拍手鼓勵」，也可以留言讓我知道你的想法，我會多加點油寫出更多內容的！
1. 拍「10下」：表示你喜歡這篇文章，謝謝你！
2. 拍「20下」：表示你覺得這篇文章很棒、願意分享給朋友！
3. 拍「30–40下」：希望未來我能寫更多這類主題的文章！
4. 拍好拍滿「50下」：給我最大的鼓勵，這將會支持我繼續寫作，並持續分享我的經驗！拍手小秘訣： 只要將滑鼠(或手指)持續按著不放手掌的icon，就能夠連續拍手囉，試試看吧！
