🏝用Python來實現 Binary Search Tree 二元搜尋樹

Juliane Liebermann on Unsplash

定義

二元搜尋樹（Binary Search Tree，簡稱 BST）是一種特殊的二元樹結構，
具有以下特性：

1. 左子樹：左子樹上所有節點的值均小於該節點的值。
2. 右子樹：右子樹上所有節點的值均大於該節點的值。
3. 無重複值：每個節點的值都是唯一的。

這些特性使得二元搜尋樹在搜尋、插入和刪除操作上都具有較高的效率。

一開始，初始化時是一顆空樹，
隨著資料的增加而成為一顆擁有實體節點的二元搜尋樹。

優點

1.可以根據需求動態延伸或縮短，有效利用記憶體空間。

2.整顆樹的中序拜訪具有排序性質(左子樹 < 目前節點 < 右子樹)。

3.數據均勻分布時，有較優越的搜尋、插入和刪除效能。

缺點

1.不支援random acess，不支援BinarySearchTree[ index ] 這種操作。

2.如果要搜尋或者訪問某個元素，一定要從根節點開始拜訪(或搜尋)整顆樹。

run-time成本相當昂貴。

3.只能單向訪問，相當於單行道，只能從上到下(從根節點到葉子節點)訪問。

節點Node的Python實作

class Node:

  def __init__(self, data):
	  
	  		# 資料欄位
    self.data = data
    
     # 左子節點
    self.left = None
    
     # 右子節點
    self.right = None

Binary Search Tree的class定義 與 建構子

class BinarySearchTree:
  def __init__(self):

    # 初始化時是一顆空樹
    self.root = None

Binary Search Tree常見的操作

1.插入節點 insert(data)

如果當下節點為空，則放入當下的位置。

如果data比當下節點還小，則前往左子樹尋找空位。

如果data比當下節點還大，則前往右子樹尋找空位。

時間複雜度: 平均O(log n) 對數時間，最差O(n)線性時間。

  def insert(self, key):
    if self.root is None:
        self.root = Node(key)
    else:
        self._insert(self.root, key)
    return

  def _insert(self, root, key):
    if key < root.data:
      if root.left is None:
          root.left = Node(key)
      else:
          self._insert(root.left, key)
    else:
      if root.right is None:
          root.right = Node(key)
      else:
          self._insert(root.right, key)
    return

2.搜尋某個節點值 search(data)

從根節點開始往下搜尋，查看某個節點值是否存在。

如果當下節點值等於data，代表找到了。

如果data比當下節點還小，則前往左子樹尋找data。

如果data比當下節點還大，則前往右子樹尋找data。

如果找到了，返回該節點。

如果沒有，返回None。

時間複雜度: 平均O(log n) 對數時間，最差O(n)線性時間。

  def search(self, key):
    return self._search(self.root, key)

  def _search(self, root, key):
    if root is None or root.data == key:
      return root

    if key < root.data:
      return self._search(root.left, key)

    else:
      return self._search(root.right, key)

3.刪除指定的節點 delete( data )

從根節點開始往下搜尋，查看某個節點值是否存在。

如果當下節點值等於data，代表找到了。

如果data比當下節點還小，則前往左子樹尋找data。

如果data比當下節點還大，則前往右子樹尋找data。

如果有找到，刪除該節點，以右子樹的最小值填補空缺，返回被刪除的節點。

(補充: 有些課本會以左子樹的最大值填補空缺，也是可以的。)

如果沒有，返回None。

時間複雜度: 平均O(log n) 對數時間，最差O(n)線性時間。

  def delete(self, key):
    self.root = self._delete(self.root, key)

  def _delete(self, root, key):
  
    if root is None:
        return root
        
    if key < root.data:
        root.left = self._delete(root.left, key)
        
    elif key > root.data:
        root.right = self._delete(root.right, key)
        
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        temp = self._minValueNode(root.right)
        root.data = temp.data
        root.right = self._delete(root.right, temp.data)
        
    return Node(data)

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

4.取得樹的深度 depth()

從根節點開始往葉子節點拜訪，取得最長路徑上的節點數 = 樹的深度。

時間複雜度: O(log n) 對數時間

  def depth(self):
    return self._depth(self.root)

  def _depth(self, cur_node):
    if not cur_node:
      return 0
    
    return 1 + max( self._depth(cur_node.left), self._depth(cur_node.right) )

5.樹的中序拜訪 inorder traversal

先拜訪左子樹、接著拜訪當下節點、最後拜訪右子樹。

依此定義，遞迴拜訪整顆樹。

最後輸出的拜訪軌跡具有由小到大，已排序的性質。

時間複雜度: O(n) 線性時間

  def inorder(self):
    return self._inorder(self.root, [])

  def _inorder(self, root, result):
    if root:
        self._inorder(root.left, result)
        result.append(root.data)
        self._inorder(root.right, result)
    return result

6.樹的逐層拜訪 level-order traversal

從樹根開始，逐層由上往下拜訪每一層，每一層由左往右拜訪每個節點。

時間複雜度: O(n) 線性時間

  def levelorder(self):

    bfs_q = [self.root] if self.root else []

    while bfs_q:
      
      next_level = []

      for cur_node in bfs_q:

        print(str(cur_node.data) + "->", end='')

        if cur_node.left:
          next_level.append(cur_node.left)
        if cur_node.right:
          next_level.append(cur_node.right)

      bfs_q = next_level

    return

測試範例

完整的Binary Search Tree實作和程式碼

class Node:
  def __init__(self, key):
    self.left = None
    self.right = None
    self.data = key

class BinarySearchTree:
  def __init__(self):

    # 初始化時是一顆空樹
    self.root = None


  def insert(self, key):
    if self.root is None:
        self.root = Node(key)
    else:
        self._insert(self.root, key)
    return


  def _insert(self, root, key):
    if key < root.data:
      if root.left is None:
          root.left = Node(key)
      else:
          self._insert(root.left, key)
    else:
      if root.right is None:
          root.right = Node(key)
      else:
          self._insert(root.right, key)
    return


  def search(self, key):
    return self._search(self.root, key)


  def _search(self, root, key):
    if root is None or root.data == key:
      return root

    if key < root.data:
      return self._search(root.left, key)

    else:
      return self._search(root.right, key)


  def inorder(self):
    return self._inorder(self.root, [])


  def _inorder(self, root, result):
    if root:
        self._inorder(root.left, result)
        result.append(root.data)
        self._inorder(root.right, result)
    return result


  def levelorder(self):

    bfs_q = [self.root] if self.root else []

    while bfs_q:
      
      next_level = []

      for cur_node in bfs_q:

        print(str(cur_node.data) + "->", end='')

        if cur_node.left:
          next_level.append(cur_node.left)
        if cur_node.right:
          next_level.append(cur_node.right)

      bfs_q = next_level

    return


  def delete(self, key):
    self.root = self._delete(self.root, key)


  def _delete(self, root, key):
    if root is None:
        return root
    if key < root.data:
        root.left = self._delete(root.left, key)
    elif key > root.data:
        root.right = self._delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left
        temp = self._minValueNode(root.right)
        root.data = temp.data
        root.right = self._delete(root.right, temp.data)
    return root


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


  def depth(self):
    return self._depth(self.root)


  def _depth(self, cur_node):
    if not cur_node:
      return 0
    
    return 1 + max( self._depth(cur_node.left), self._depth(cur_node.right) )

def test():
  # Demo:
  bst = BinarySearchTree()
  bst.insert(50)
  bst.insert(30)
  bst.insert(20)
  bst.insert(40)
  bst.insert(70)
  bst.insert(60)
  bst.insert(80)

  print("\nLevel order traversal of the BST" )
  bst.levelorder()
  print()

  print("\nInorder traversal of the BST:", bst.inorder())

  node = bst.search(40)
  if node:
      print("\nNode found with data 40:", node.data)
  else:
      print("\nNode not found")

  bst.delete(20)
  print("\nInorder traversal after deleting 20:", bst.inorder())

  print(f"\nTree depth = {bst.depth()}"  )     

if __name__ == "__main__":
  test()

測試輸出

Level order traversal of the BST
50->30->70->20->40->60->80->

Inorder traversal of the BST: [20, 30, 40, 50, 60, 70, 80]

Node found with data 40: 40

Inorder traversal after deleting 20: [30, 40, 50, 60, 70, 80]

Tree depth = 3

結語

其實Tree就是Node的組合與推廣，每個節點最多可以有兩個子節點的樹狀資料結構。

而Binary Search Tree就是Binary Tree額外加上依據節點值大小產生方向性的規則。

讀者可以透過紙筆追蹤演算法和程式執行邏輯，測試幾個簡單的小範例，

會有更深刻的了解和體會！

Binary Search Tree相關的演算法練習題與詳解

DFS經典應用題 BST最靠近的公共祖先節點 Leetcode #235

經典圖論題 二元搜索樹的區間和 Range Sum of BST_Leetcode #938

📆行程安排 我的行事曆I_My Calendar I_Leetcode #729

資料結構經典 在二元搜尋樹BST中搜索目標值_Leetcode #700_Leetcode精選75題

圖論進階題: 在二元搜索樹BST中刪除節點_Leetcode #450_Leetcode 精選75題

合縱連橫: 從定義出發，理解 二元搜尋樹BST 背後的本質