Learning Objectives
- 說明二元搜尋樹的性質：左子樹都比節點小、右子樹都比節點大
- 追蹤搜尋與插入從根往下走的路徑，說明比較次數等於走過的層數
- 說明中序走訪二元搜尋樹會得到由小到大的結果
- 分辨刪除節點的三種情況，用後繼者處理有兩個子節點的節點
- 說明依序插入已排序的資料會讓樹退化成一條線，以及平衡樹要解決的問題
- 使用 C++ set／map、Java TreeMap／TreeSet，以及 Python 的 bisect 替代做法
資料一直在變，還要能快速搜尋
第 04 課的二分搜尋很快：排好序的陣列裡找一個數，最多比 log₂n 次。可是如果資料會一直新增、刪除呢？ 例如選課系統的候補名單、線上遊戲依分數排好的玩家、圖書館依書號排好的館藏，隨時有東西進來、有東西離開。
| 做法 | 搜尋 | 插入一筆 | 刪除一筆 |
|---|---|---|---|
| 排好序的陣列 | O(log n)（二分搜尋） | O(n)（後面的元素要往後挪） | O(n) |
| 鏈結串列（第 11 課） | O(n)（只能一個一個走） | 找到位置後 O(1) | 找到位置後 O(1) |
| 二元搜尋樹（樹的形狀好的時候） | O(log n) | O(log n) | O(log n) |
二元搜尋樹（binary search tree，BST）是一種二元樹（第 13 課），每個節點都滿足：
- 左子樹裡所有的值都比這個節點小
- 右子樹裡所有的值都比這個節點大
這個性質讓它像一棵「做好的二分搜尋」：站在任何一個節點，和目標比一次，就知道該往左還是往右，另一邊整棵子樹都不用看。 這一課假設樹裡沒有重複的值，遇到相同的值就不再插入。
插入：走到空位就放下
依序插入 50、30、70、20、40、60、80、35。每次都從根出發：比節點小往左、比節點大往右，走到空的位置就建立新節點。insert 用遞迴寫：回傳「插入之後這棵子樹的根」，上一層把它接回 node.left 或 node.right。注意最後的 35：先比 50 往左、再比 30 往右、再比 40 往左，掛在 40 的左邊。
搜尋：每比一次往下一層
搜尋和插入走的是同一條路，只是走到空的位置時，代表目標不在樹裡：
cur = root
while cur is not None:
if target == cur.val:
return cur # 找到了
elif target < cur.val:
cur = cur.left # 往左
else:
cur = cur.right # 往右
return None # 走到空位：不在樹裡
每比一次就往下一層，所以比較次數最多等於樹高（從根到最深的節點經過幾個節點）。 樹的形狀越「矮胖」，搜尋越快；n 個節點的樹排得夠整齊時，樹高大約是 log₂n。
搜尋：cur 從根往下走
前面大約 160 步是用上一個範例的 insert 建出同一棵樹，可以直接把進度條拖到後面，從 search(root, 35) 開始看。找 35 比較 4 次（50、30、40、35）；找 65 比較 3 次（50、70、60），60 的右邊是空的，所以 65 不在樹裡。
中序走訪：由小到大
第 13 課學過中序走訪（inorder）：先走左子樹、再處理自己、最後走右子樹。 用在二元搜尋樹上，剛好會由小到大拜訪每個值：
- 左子樹的值全部比自己小，所以先把它們走完
- 接著是自己
- 右子樹的值全部比自己大，最後才走
所以「把一堆數插進 BST，再中序走訪」就是一種排序方法。n 個數各插入一次，樹的形狀好的時候總共 O(n log n)。
中序走訪得到排序結果
建好樹之後（前面約 150 步），看 inorder 怎麼先一路往左走到 20，才開始把值放進 out。out 一格一格長出來，永遠是由小到大。
想一想：插入、搜尋與中序
依序插入 40、20、60、10、30、50 建成一棵二元搜尋樹，再插入 25，25 會掛在哪裡？
用「搜尋」範例的樹（插入 50、30、70、20、40、60、80、35）找 45，會印出什麼？
依序插入 8、3、10、1、6、14，再做中序走訪，印出的順序是什麼？
刪除的三種情況
刪除比插入麻煩，因為拿掉一個節點之後，它的子節點要有地方接，而且整棵樹還要維持「左小右大」。先找到要刪的節點，再看它有幾個子節點：
| 情況 | 做法 |
|---|---|
| 葉節點（沒有子節點） | 直接拿掉，父節點那一邊變成空的 |
| 只有一個子節點 | 讓那個子節點頂替自己的位置 |
| 兩個子節點 | 找後繼者（右子樹裡最小的值），把它的值複製過來，再到右子樹刪掉後繼者 |
第三種情況為什麼用後繼者？要找一個值來頂替，它必須比左子樹全部大、比右子樹全部小。右子樹裡最小的那個剛好符合： 它比左子樹全部大（因為它在右子樹），又比右子樹其他值都小。後繼者的找法是從右子節點出發，一直往左走到底。
後繼者一定沒有左子節點（不然它就不是最小的），所以到右子樹刪掉它時，只會遇到前兩種簡單情況。 改用「前驅者」（左子樹裡最大的值）也可以，道理相同。
C++ 的 delete 是保留字，所以範例的 C++ 函式叫 remove，並在拿掉節點時用 delete 釋放記憶體；Python 和 Java 會自動回收沒有人指到的物件。
刪除：葉節點、一個子節點、兩個子節點
同一棵樹依序刪除 20（葉節點）、30（只有右子節點 40）、50（兩個子節點）。刪除 50 時，succ 從 70 出發往左走到 60，把 60 複製到根，再到右子樹把原本的 60 刪掉。建樹的部分約 160 步，可以拖到刪除開始的地方看。
樹的形狀取決於插入順序
同樣一組數，插入的順序不同，長出來的樹就不同。最糟的情況是資料已經排好序： 依序插入 1、2、3、4、5、6，每個新的數都比樹裡所有的數大，只能一直往右掛，樹變成一條線，和鏈結串列沒有兩樣。
| 樹的形狀 | 樹高 | 搜尋、插入、刪除 |
|---|---|---|
| 整齊（每一層盡量填滿） | 約 log₂n | O(log n) |
| 退化成一條線 | n | O(n) |
下面的範例用迴圈版的插入，回傳新節點在第幾層，順便算出兩棵樹的樹高。
依序插入讓樹退化成一條線
插入 6 到 chain 時，cur 要從 1 一路走過 2、3、4、5，比較 5 次才找到空位；good 同樣 6 個數，樹高只有 3。資料越多差距越大：1,000 個依序插入的數，樹高是 1,000；排得整齊的話只要 10 層。
平衡樹與內建的有序容器
避免退化的辦法，是在每次插入、刪除之後調整樹的形狀，讓樹高一直保持在 O(log n)，這類樹叫平衡二元搜尋樹（self-balancing BST）。 調整的基本動作叫旋轉（rotation）：把一個子節點轉上來當父節點，左小右大的性質不變，但某一邊的高度少了一層。常見的兩種：
- AVL 樹：1962 年由 Adelson-Velsky 與 Landis 提出，是第一種自我平衡的二元搜尋樹。每個節點左右子樹的高度最多差 1。
- 紅黑樹（red-black tree）：源自 Bayer 1972 年的對稱二元 B 樹，1978 年 Guibas 與 Sedgewick 用紅、黑兩種顏色描述它。 平衡的要求比 AVL 寬鬆，插入、刪除時需要的調整比較少。
旋轉的細節這一課不展開；實際寫程式時，通常直接用語言內建的有序容器：
| 語言 | 寫法 | 說明 |
|---|---|---|
| C++ | set<int>、map<int, string> |
依鍵排序，搜尋、插入、刪除 O(log n)；常見的實作是紅黑樹。lower_bound、upper_bound 可以找相鄰的值 |
| Java | TreeSet<Integer>、TreeMap<Integer, String> |
以紅黑樹實作；floor、ceiling、floorKey 找相鄰的值 |
| Python | 標準函式庫沒有 | 可以用排好序的串列配 bisect：搜尋 O(log n)，但 bisect.insort 插入時要挪動元素，O(n) |
import bisect
a = []
for x in [50, 30, 70, 20, 40]:
bisect.insort(a, x) # 插入並保持排序
print(a) # [20, 30, 40, 50, 70]
i = bisect.bisect_right(a, 45)
print(a[i - 1]) # 小於等於 45 的最大值：40
注意 C++ 的 unordered_set、Java 的 HashSet、Python 的 set 和 dict 是雜湊表（第 12 課），不依大小排序；需要「由小到大走訪」或「找比 x 小的最大值」時，要用上面的有序容器。
想一想：刪除、退化與有序容器
依序插入 50、30、70、60、80、65，再刪除 50（用後繼者取代）。刪除之後，70 的左子節點是什麼？
把 1、2、3、…、1000 依序插入一棵普通的二元搜尋樹（不做平衡），再搜尋 1000，要比較幾次？
想要「一直保持由小到大，而且能找出小於等於 x 的最大值」，下列哪一個不適合？
實作：小於等於 x 的最大值
完成 floor（C++／Java 叫 floorOf）：在二元搜尋樹裡找出小於等於 x 的最大值，找不到就回傳 -1。只能從根往下走一條路，不要把整棵樹走訪一遍。預期輸出在右邊。
重點整理
- 二元搜尋樹：每個節點的左子樹都比它小、右子樹都比它大
- 搜尋、插入都從根往下走，每比一次下一層；比較次數最多等於樹高
- 中序走訪二元搜尋樹得到由小到大的結果
- 刪除分三種：葉節點直接拿掉；一個子節點就讓子節點頂替；兩個子節點用後繼者（右子樹最小值）取代
- 樹高決定速度：整齊時約 log₂n，依序插入已排序的資料會退化成一條線，樹高 n
- 平衡樹（AVL、紅黑樹）用旋轉維持 O(log n)；實務上用 C++
set／map、JavaTreeSet／TreeMap，Python 可用bisect搭配串列
下一課：堆積與優先佇列。同樣是二元樹，堆積只要求「父節點比子節點小（或大）」，換來的是能用陣列存，而且永遠能在 O(1) 拿到最小值。