二元搜尋樹（BST）

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

定義

  • 節點的左子樹：
    • 值小於該節點本身
  • 節點的右子樹：
    • 值大於該節點本身
  • 左、右子樹都必須是二元搜尋樹

二元搜尋樹的示意圖。

Data Structures and Algorithms in Python

實作

class TreeNode:  
  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

class BinarySearchTree:
  def __init__(self):
    self.root = None
Data Structures and Algorithms in Python

搜尋

  • 搜尋 72

二元搜尋樹的示意圖。

Data Structures and Algorithms in Python

搜尋

  • 搜尋 72

二元搜尋樹示意：根節點標成黃色。

Data Structures and Algorithms in Python

搜尋

  • 搜尋 72

二元搜尋樹示意：根與左子樹為灰色，右子樹的第一個節點為黃色。

Data Structures and Algorithms in Python

搜尋

  • 搜尋 72

二元搜尋樹示意：上一層根與其左子樹為灰色，新根節點為黃色。

Data Structures and Algorithms in Python

搜尋

  • 搜尋 72

二元搜尋樹示意：新根節點為黃色，其餘節點為灰色。

Data Structures and Algorithms in Python

搜尋

  • 搜尋 72

二元搜尋樹示意：新根節點為黃色，其餘節點為灰色。標示的節點數值為 72。

Data Structures and Algorithms in Python

搜尋

def search(self, search_value):

    current_node = self.root

    while current_node:

      if search_value == current_node.data:

        return True

      elif search_value < current_node.data:

        current_node = current_node.left_child

      else:

        current_node = current_node.right_child

    return False
Data Structures and Algorithms in Python

插入

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

新節點的圖示。

Data Structures and Algorithms in Python

插入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return

成為根節點的新節點圖示。

Data Structures and Algorithms in Python

插入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:

含右子節點的根與新節點圖示。

Data Structures and Algorithms in Python

插入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root

    while True:

      if data < current_node.data:

        if current_node.left_child == None:

新節點與有右子節點之根的圖示。current_node 為根。

Data Structures and Algorithms in Python

插入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return

根節點同時有左右子節點的圖示；current_node 為根；新節點為左子節點。

Data Structures and Algorithms in Python

插入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:

新節點與部分元素之二元搜尋樹圖示；current_node 為根。

Data Structures and Algorithms in Python

插入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None: 
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child

新節點與部分元素之二元搜尋樹圖示；current_node 為根的左子節點。

Data Structures and Algorithms in Python

插入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:

        if current_node.right_child == None:

具有左子樹之二元搜尋樹與新節點圖示。

Data Structures and Algorithms in Python

插入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return

具有左子樹之二元搜尋樹圖示；新節點成為根的右子節點。

Data Structures and Algorithms in Python

插入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:

新節點與含部分元素之二元搜尋樹圖示。

Data Structures and Algorithms in Python

插入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

新節點與含部分元素之二元搜尋樹圖示；current_node 為根的右子節點。

Data Structures and Algorithms in Python

插入

def insert(self, data):
  new_node = TreeNode(data)
  if self.root == None:
    self.root = new_node
    return
  else:
    current_node = self.root
    while True:
      if data < current_node.data:
        if current_node.left_child == None:
          current_node.left_child = new_node
          return 
        else:
          current_node = current_node.left_child
      elif data > current_node.data:
        if current_node.right_child == None:

          current_node.right_child = new_node
          return
        else:
          current_node = current_node.right_child

新節點與含部分元素之二元搜尋樹圖示；current_node 為根的右子節點；新節點為其左子節點。

Data Structures and Algorithms in Python

刪除

  • 無子節點

含部分元素之二元搜尋樹圖示。有一個將被刪除的紅色節點，且無子節點。

Data Structures and Algorithms in Python

刪除

  • 無子節點
    • 直接刪除

含部分元素之二元搜尋樹圖示。待刪節點已從樹中移除。

Data Structures and Algorithms in Python

刪除

  • 單一子節點

含部分元素之二元搜尋樹圖示。有一個將被刪除的紅色節點，該節點有右子節點。

Data Structures and Algorithms in Python

刪除

  • 單一子節點
    • 刪除該節點
    • 將其子節點接到該節點的父節點

含部分元素之二元搜尋樹圖示。待刪節點已移除，根指向被刪節點的右子節點。

Data Structures and Algorithms in Python

刪除

  • 單一子節點
    • 刪除該節點
    • 將其子節點接到該節點的父節點

二元搜尋樹示意圖。

Data Structures and Algorithms in Python

刪除

  • 兩個子節點

二元搜尋樹示意：將刪除的紅色根節點。

Data Structures and Algorithms in Python

刪除

  • 兩個子節點
    • 以其後繼節點取代
      • 也就是比該節點值大的最小值節點
    • 尋找後繼：

二元搜尋樹示意：將刪除的紅色根節點。

Data Structures and Algorithms in Python

刪除

  • 兩個子節點
    • 以其後繼節點取代
      • 也就是比該節點值大的最小值節點
    • 尋找後繼：
      • 先到右子節點

二元搜尋樹示意：將刪除的紅色根節點；根的右子節點為黃色。

Data Structures and Algorithms in Python

刪除

  • 兩個子節點
    • 以其後繼節點取代
      • 也就是比該節點值大的最小值節點
    • 尋找後繼：
      • 先到右子節點
      • 持續往左直到盡頭

二元搜尋樹示意：根節點將被刪除為紅色；為找後繼的另一節點為黃色。

Data Structures and Algorithms in Python

刪除

  • 兩個子節點
    • 以其後繼節點取代
      • 也就是比該節點值大的最小值節點
    • 尋找後繼：
      • 先到右子節點
      • 持續往左直到盡頭

二元搜尋樹示意：根節點將被刪除為紅色；為找後繼的另一節點為黃色。

Data Structures and Algorithms in Python

刪除

  • 兩個子節點
    • 以其後繼節點取代
      • 也就是比該節點值大的最小值節點
    • 尋找後繼：
      • 先到右子節點
      • 持續往左直到盡頭

二元搜尋樹示意：根節點將被刪除為紅色；為找後繼的另一節點為黃色；後繼為數字 13。

Data Structures and Algorithms in Python

刪除

  • 兩個子節點
    • 以其後繼節點取代
      • 也就是比該節點值大的最小值節點
    • 尋找後繼：
      • 先到右子節點
      • 持續往左直到盡頭

二元搜尋樹示意：根節點已被後繼取代。

Data Structures and Algorithms in Python

刪除

  • 兩個子節點
    • 以其後繼節點取代
      • 也就是比該節點值大的最小值節點
    • 尋找後繼：
      • 先到右子節點
      • 持續往左直到盡頭
      • 若後繼有右子節點：

二元搜尋樹示意：後繼節點具有右子節點。

Data Structures and Algorithms in Python

刪除

  • 兩個子節點
    • 以其後繼節點取代
      • 也就是比該節點值大的最小值節點
    • 尋找後繼：
      • 先到右子節點
      • 持續往左直到盡頭
      • 若後繼有右子節點：
        • 該子節點成為後繼父節點的左子節點。

二元搜尋樹示意：後繼節點曾有右子節點。該子節點已成為後繼父節點的左子節點，根也被後繼取代。

Data Structures and Algorithms in Python

用途

  • 高效排序清單
  • 搜尋比陣列、連結串列快很多
  • 插入、刪除比陣列快很多
  • 可用來實作進階資料結構：
    • 動態集合
    • 對照表（lookup tables）
    • 優先佇列
Data Structures and Algorithms in Python

一起來練習吧！

Data Structures and Algorithms in Python

Preparing Video For Download...