簡介

相信各位在準備面試的時候，Binary Search Tree 這個資料結構一定會被問到，他是 Tree 大本營中最先學到的一種演算法，在資料的搜尋、插入、刪除上都有很好的表現，在Balanace Tree的狀況下可以達到O(logn)，所謂的Balanace Tree就像是左邊跟右邊的枝葉數量差不多，不會出現左邊很多右邊很少的情況，這樣才能達到O(logn)的時間複雜度。

定義


那我們先來說說BST的四個特性：

  1. 根(root)的左邊節點(left node)其子樹(sub-tree)中所有的節點值都小於根(root)的值。
  2. 根(root)的右邊節點(right node)其子樹(sub-tree)中所有的節點值都大於根(root)的值。
  3. 任意節點的左右子樹都符合BST。
  4. 不存在任何key/value相等的節點。

小提醒：我把第四點畫起來是因為很多人會不記得第四點，但遇過面試有問，但想一下就會知道如果有相等值的節點就會違反第一點或第二點。

如果我還是想要塞入相同的值怎麼辦？ BST的變體

如果硬要塞相同的值，有一些變體可以處理重複的值，這些變體包括

  • 左傾或右傾策略 (Left-Leaning or Right-Leaning Strategy):當插入重複的值時，可以選擇將重複的值插入左子樹或右子樹。例如，所有重複的值都放在右子樹。
  • 計數器方法 (Counter Method): 在每個節點上添加一個計數器來記錄該值的出現次數。這樣，當插入重複的值時，只需要增加該節點的計數器，而不需要插入新的節點。

使用第一種策略（所有重複值都插入右子樹）時，樹的結構如下：

1
2
3
4
5
  10
 /  \
5    15
 \
  5

使用第二種策略（計數器方法）時，樹的結構如下，但節點 5 的計數器為 2：

1
2
3
  10
 /  \
5(2)  15

Balance 的重要性

Binary Search Tree (BST) 是基於 Binary Search Algorithm 的概念以 Tree 的資料結構所建立，也可以說他是為了搜尋而生的演算法，因為他的搜尋時間複雜度是O(logn)，當然這是在平衡樹的情況下，如果是一個不平衡的樹，那搜尋時間複雜度就會變成O(n)。關鍵就在平衡。那我們這邊就先來講 樹高。

以 3 個 node 的 BST 為例，會有三種排列的可能性分別是：

好，那今天如果我們要搜尋 10 這個鍵值：

  • 第一種排列：只需要一次比較（從 root 進入，10 < 20，往左走，找到了）
  • 第二種排列：需要兩次比較（從 root 進入，10 < 30，往左走，10 < 20，繼續往左走，找到了）

所以我們可以看到在一樣數量的 node 的情況之下，不一樣的樹高對搜尋產生的影響是很關鍵的，如果有平衡就可以讓樹高在最理想的情況，使搜尋可以達到 O(log n)。

如果平衡的話，假有共有 n 個節點，那麼樹高應該就是 ( log n ) + 1。

四種操作

接下來介紹搜尋、新增、改值、刪除四種操作

新增節點

假設我們今天要把值為 15 的節點新增進去，要做以下事情：

  1. 先建立 15 的節點
  2. 與 root 節點比大小，15 < 20，所以往左走
  3. 與節點10 比大小，15 > 10，所以往右走

搜尋節點

假設我們要搜尋 15 這個節點，其實跟新增的步驟差不多，先逐一比大小，差在要確認經過的節點的值是不是 15 即可。

  1. 把要找的值 15 與 root 節點比大小，15 < 20，所以往左走
  2. 把要找的值 15 與節點10 比大小，15 > 10，所以往右走
  3. 與節點15比較發現 15 == 15，找到了

修改節點的值

根搜尋也差不多，只是找到節點後，把該節點的值改掉即可。或是直接把舊的節點刪除，插入更新值的節點。

刪除節點

刪除節點比較複雜一點，大概會有以下刪除的狀況：

  1. 刪除的節點是葉子節點（沒有子節點）：該節點無子節點,直接刪除。
  2. 刪除的節點有一個子節點：該節點只有一個子節點,直接刪除,並把子節點接上去。
  3. 刪除的節點有兩個子節點：該節點有兩個子節點,找到左子樹中最大的節點或右子樹中最小的節點來替代被刪除的節點。

情況1 - 刪除孤兒：直接把該節點刪除即可

情況2 - 替代被刪除的節點

情況3 - 從左子樹(small nodes)找最大(max)去掌管左子樹，或是從右子樹(big smalls)找最小(min)去掌管右子樹

實作

先定義兩個class，把操作方法定義在 BST 裡面

1
2
3
4
5
6
7
8
9
10
class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.parent = None 

class BST(object):
    def __init__(self, root: Node):
        self.root = root

新增節點

以 root 為起點開始比大小，直到發現空位就可插入，這邊是用 loop 的方法來寫，也可以用遞迴的方式來寫。

loop 的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class BST(object):
    def __init__(self, root: Node):
        self.root = root
    
    def add_node(self, node: Node):
        # 從 root 開始走
        current_node = self.root
        # 會一直往下走current_node=current_node.right/left，直到發生break
        while True: 
            # 不允許重複的值
            if node.value == current_node.value:
                raise Exception("Node already exists")
            # node 比較小塞 cur.left 
            elif node.value < current_node.value: 
                # 如果cur沒有left sub-tree，直接塞進去
                if current_node.left is not None:
                    current_node = current_node.left
                # cur.left 是空的，且 node < cur 因此 node 變成 cur.left 
                else:
                    current_node.left = node
                    node.parent = current_node
                    break
            # node 比較大塞 cur.right
            elif node.value > current_node.value:
                # 如果cur沒有right sub-tree，直接塞進去
                if current_node.right is not None:
                    current_node = current_node.right
                # cur.right 是空的，且 node > cur 因此 node 變成 cur.right 
                else:
                    current_node.right = node
                    node.parent = current_node
                    break

使用 Recursion 的方法：簡單來說就是把 continue 的部分改成呼叫自己，這樣就可以一直往下走，直到找到空位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def add_node(self, node: Node):
       if not self.root:
           self.root = node
       else:
           self._add_node_recursive(self.root, node)
   
   def _add_node_recursive(self, current_node: Node, new_node: Node):
       if new_node.value == current_node.value:
           raise Exception("Node already exists")
       elif new_node.value < current_node.value:
           if current_node.left is None:
               current_node.left = new_node
               new_node.parent = current_node
           else:
               self._add_node_recursive(current_node.left, new_node)
       else:
           if current_node.right is None:
               current_node.right = new_node
               new_node.parent = current_node
           else:
               self._add_node_recursive(current_node.right, new_node)

搜尋節點

基本上跟新增一樣，也是去比大小，找到的話就回傳

loop 的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class BST(object):
    def __init__(self, root: Node):
        self.root = root
    
    def get_node_by_value(self, value: int):
        # 從 root 開始走
        current_node = self.root
        # 會一直往下走current_node=current_node.right/left，直到發生break
        while True: 
            # 找到了
            if value == current_node.value:
                return current_node
            # value 比較小在 cur.left 
            elif value < current_node.value: 
                # 如果cur有left sub-tree，繼續往下走
                if current_node.left is not None:
                    current_node = current_node.left
                # cur.left 是空的，但 value < cur 正常應該要出現，但是沒有，表示不存在
                else:
                    raise Exception('node not found')
            # value 比較大在 cur.right
            elif value > current_node.value:
                # 如果cur有right sub-tree，繼續往下走
                if current_node.right is not None:
                    current_node = current_node.right
                # cur.right 是空的，且 value > cur 正常應該要出現，但是沒有，表示不存在
                else:
                    raise Exception('node not found')

Recursion 的方法程式碼就少了很多，也比較清楚：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class BST(object):
    def __init__(self, root: Node):
        self.root = root

    def get_node_by_value(self, value: int):
        return self._get_node_by_value_recursive(self.root, value)
    
    def _get_node_by_value_recursive(self, current_node: Node, value: int):
        if current_node is None:
            raise Exception('node not found')
        
        if value == current_node.value:
            return current_node
        # valu 比 cur 小，繼續往 left (小)深入
        elif value < current_node.value:
            return self._get_node_by_value_recursive(current_node.left, value)
        # value 比 cur 大，繼續往 right (大)深入
        else:
            return self._get_node_by_value_recursive(current_node.right, value)

刪除節點

刪除就很麻煩了，直接使用遞迴會比較好寫：

  1. 如果值小於當前節點的值，則遞歸地在左子樹中刪除節點。
  2. 如果值大於當前節點的值，則遞歸地在右子樹中刪除節點。
  3. 如果找到節點，分三種情況處理：
    1. 該節點無子節點，直接刪除。
    2. 該節點有一個子節點，讓該子節點接替被刪除節點的位置。
    3. 該節點有兩個子節點:
      1. 找到欲刪除節點的右子樹中的最小值節點（或左子樹中的最大值節點）
      2. 將其值複製到當前節點
      3. 並遞歸地刪除最小值節點。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class BST(object):
    def __init__(self, root: Node):
        self.root = root

    def delete_node_by_value(self, value: int):
        self.root = self._delete_node_recursive(self.root, value)

    def _delete_node_recursive(self, current: Node, value: int):
        if current_node is None:
            raise Exception('node not found')
        
        # value 比 cur 小，繼續往 cur.left (小)深入
        if value < current_node.value:
            current_node.left = self._delete_node_recursive(current_node.left, value) # 有一個子節點或 None，讓該節點接替被刪除節點的位置
        # value 比 cur 大，繼續往 cur.right (大)深入
        elif value > current_node.value:
            current_node.right = self._delete_node_recursive(current_node.right, value) # 有一個子節點或 None，讓該節點接替被刪除節點的位置
        # 找到了！
        else:
            # 情境1, 2: 只有一個子節點 或是 無節點，回到呼叫的地方 子節點會接替 current 是 被刪除的父節點，cur.left/right 串到那一個節點或是None
            if current_node.left is None: 
                return current_node.right
            elif current_node.right is None:
                return current_node.left
            
            # 情境3: 有兩個子節點，該節點有兩個子節點 
            min_larger_node = self._get_min(current_node.right) # (1)找到右子樹中的最小值節點（或左子樹中的最大值節點）
            current_node.value = min_larger_node.value # (2)將其值複製到當前節點
            current_node.right = self._delete_node_recursive(current_node.right, min_larger_node.value) # (3)並遞歸地刪除最小值節點。點
        
        return current_node # 回傳要被刪除那個點的被替代的新節點


    def _get_min(self, node: Node):
        current = node 
        while current.left is not None:
            current = current.left
        return current

Ref