# [資演] 10- 二元搜尋樹

###### tags: `資演`


在生活中少不了要**比大小**的場景。所謂的比大小，其實是要對一群可以互相比較的量值（例如整數、浮點數）進行**排序**。

二元搜尋樹（binary search tree, BST）就是一種為了方便快速排序而誕生的資料結構。從名字也可以看出來，它和binary search脫不了關係。

## 什麼是二元搜尋樹？
簡單的說，二元搜尋樹是一種特別的二元樹，他滿足以下性質：
* 若任意節點的左子樹不為空，則左子樹上所有節點的值均小於它的根節點的值
* 若任意節點的右子樹不為空，則右子樹上所有節點的值均大於它的根節點的值
* 任意節點的左、右子樹也分別為二元搜尋樹
* 不存在鍵值相等的節點

簡單來說就是，對於任一個在二元搜尋樹：
* 左子樹都比父節點小
* 右子樹都比父節點大
* 每一個節點的值都不重複

所以當我們要查找資料的時候，就可以從根節點開始，比根節點小的就從左子樹開始找，比較大的就從右子樹開始找，如此不斷重複下去，直到找到目標節點、或者走到葉節點為止。

## 二元搜尋樹上的操作

### 搜尋
給定一個值`key`和一個BST（的根節點）`root`，我們想在這個BST中尋找這個值有沒有存在BST中，如果有則回傳`True`，沒有則回傳`False`。

按照前面提到的邏輯，我們從根節點開始，如果目標值比根節點小，就往左小孩走，搜尋左子樹；比根節點大，就往右小孩走，搜尋右子樹。如此不斷重複下去，直到找到目標節點、或者走到葉節點為止。這是一個遞迴的算法，因此可以寫出以下code：

def search(root, key):
    # Base Case 1: 根節點為空
    if not root:
        return False
        
    # Base Case 2: 根節點就是要找的值
    elif root.val == key:
        return True
 
    # 要找的值比根節點的值大 -> 往右子樹找
    elif root.val < key:
        return search(root.right,key)
        
    # 要找的值比根節點的值小 -> 往左子樹找
    else:
        return search(root.left,key)

### 排序
事實上，對一個BST進行inorder traversal，很自然地就會產生一個由小到大的順序，也就是對這些節點完成了排序。

其他種traversal方式也會生成不同的搜尋樹：


### 插入
給定一個值`key`和BST的根節點`root`，要將`key`插入該BST，我們應該怎麼做呢？

在這邊我們使用和搜尋類似的思路，先想像要插入的節點存在BST裡面，然後在BST裡面尋找這個節點。根據BST的規則，我們必須先找到這個要新增的節點**適合的位置**，再將這個節點接上BST。

要尋找對新節點而言的適當位置，需要召喚一位「哨兵」指針`succ`先行探路，而「將會成為新節點的父節點(準新手爸媽)」的那個指針`prev`，則跟著「哨兵」的腳步，往前推進。

假設我們要插入的值是100。一開始我們先把`succ`初始化為`root`，`prev`則是`None`，如下圖：
我們發現，100比10還要大，所以我們往`root`的右小孩前進，也就是說：

prev = succ
succ = succ.right

現在我們發現，100比1000還要小，所以往左小孩前進：
100和500比還是比較小，所以我們繼續往左小孩走；但是已經沒有左小孩了，所以這時候的`succ`變成`None`，`prev`則是500的節點。於是我們知道，100必須是500的左小孩，也就是說，走到不能再走的時候，哨兵`succ`的位置就是要插入的位置，準新手爸媽`prev`就是插入的新節點的父節點。最後完成插入的BST如下：

### 刪除
要從一個BST裡面刪除一個節點，有以下幾種可能：
1. 該節點不存在
這個情況不考慮，可以直接擲出例外或回傳`None`。
2. 該節點為葉節點，沒有左右子樹
這個狀況很簡單，直接刪去該節點即可。
3. 該節點有右子樹，無左子樹
這個也很簡單，只要刪掉該節點，然後把右子樹直接接到刪去的那個節點的父節點上就好了。
4. 該節點有左子樹，無右子樹
和狀況3類似，刪掉該節點，然後把左子樹直接接到刪去的那個節點的父節點上就好了。
6. 該節點有左右子樹
這時候就必須找到替代即將被刪除節點的中序接續子（Inorder Successor）節點，接著讓接續子節點取代被刪除的子節點，假如接續子節點本身也有子節點，那要同步找尋適合放置的位置。

## 例題
* 把BST變成circular doubly linked list
給定一個BST，我們希望把這個BST上的節點按照順序由小到大串成一個circular doubly linked list。注意在這邊我們希望可以**原地完成**這個操作(in-place)。

:::spoiler 解答
在這邊直覺就會想對這個BST進行inorder traversal，因為要排序。我們已經知道怎麼做inorder traversal了，接下來就是對節點進行適當的操作，把它們串成circular doubly linked list就好了。所以最直接的方式就是使用遞迴。這邊我們可以定義一個helper function，用這個函式來進行遞迴。這個helper function的概念是，把每個子樹都串成一個circular doubly linked list。

    """
    # 節點的定義
    class Node(object):
        def __init__(self, val, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
    """
    
    class Solution(object):
        def treeToDoublyList(self, root):
            """
            :type root: Node
            :rtype: Node
            """
            if root:
                head, tail = self.helper(root)
                return head
            return None


        def helper(self, root):
            """
            Idea: Construct a DLL for each subtree, then return the head and tail
            """
            
            head, tail = root, root
            
            if root.left:
                lh, lt = self.helper(root.left)
                lt.right = root
                root.left = lt
                head = lh
            if root.right:
                rh, rt = self.helper(root.right)
                rh.left = root
                root.right = rh
                tail = rt
            head.left = tail
            tail.right = head
            return (head, tail)

:::