Binary Search Tree (BST)

โครงสร้างข้อมูลและอัลกอริทึมใน Python

Miriam Antona

Software engineer

นิยาม

ซับทรีซ้าย ของโหนด:
- ค่า น้อยกว่า โหนดนั้น
ซับทรีขวา ของโหนด:
- ค่า มากกว่า โหนดนั้น
ซับทรีซ้ายและขวาต้องเป็น binary search tree

ภาพแสดงโครงสร้าง binary search tree

การนำไปใช้งาน

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

การค้นหา

ค้นหา 72

ภาพแสดงโครงสร้าง binary search tree

การค้นหา

ค้นหา 72

ภาพแสดงโครงสร้าง binary search tree โดยโหนดรากถูกเน้นสีเหลือง

การค้นหา

ค้นหา 72

ภาพแสดงโครงสร้าง binary search tree โดยโหนดรากและซับทรีซ้ายถูกเน้นสีเทา โหนดแรกของซับทรีขวาถูกเน้นสีเหลือง

การค้นหา

ค้นหา 72

ภาพแสดงโครงสร้าง binary search tree โดยซับทรีซ้ายและโหนดรากก่อนหน้าถูกเน้นสีเทา โหนดรากใหม่ถูกเน้นสีเหลือง

การค้นหา

ค้นหา 72

ภาพแสดงโครงสร้าง binary search tree โดยโหนดรากใหม่ถูกเน้นสีเหลือง และโหนดที่เหลือถูกเน้นสีเทา

การค้นหา

ค้นหา 72

ภาพแสดงโครงสร้าง binary search tree โดยโหนดรากใหม่ถูกเน้นสีเหลือง โหนดที่เหลือถูกเน้นสีเทา โหนดที่มีค่า 72 ถูกไฮไลต์

การค้นหา

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

การแทรก

def insert(self, data):

  new_node = TreeNode(data)

  if self.root == None:

ภาพแสดงโหนดใหม่

การแทรก

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

ภาพแสดงโหนดใหม่ที่กลายเป็นโหนดราก

การแทรก

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

ภาพแสดงโหนดใหม่และโหนดรากที่มีลูกทางขวา

การแทรก

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

การแทรก

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 และโหนดใหม่คือลูกทางซ้าย

การแทรก

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:

ภาพแสดงโหนดใหม่และ binary search tree ที่มีสมาชิกบางส่วน โดยโหนดรากคือ current_node

การแทรก

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

ภาพแสดงโหนดใหม่และ binary search tree ที่มีสมาชิกบางส่วน โดย current_node คือลูกซ้ายของโหนดราก

การแทรก

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:

ภาพแสดงโหนดใหม่และ binary search tree ที่มีซับทรีซ้าย

การแทรก

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

ภาพแสดง binary search tree ที่มีซับทรีซ้าย โดยโหนดใหม่กลายเป็นลูกขวาของโหนดราก

การแทรก

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:

ภาพแสดงโหนดใหม่และ binary search tree ที่มีสมาชิกบางส่วน

การแทรก

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

ภาพแสดงโหนดใหม่และ binary search tree ที่มีสมาชิกบางส่วน โดย current_node คือลูกขวาของโหนดราก

การแทรก

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

ภาพแสดงโหนดใหม่และ binary search tree ที่มีสมาชิกบางส่วน โดย current_node คือลูกขวาของโหนดราก และโหนดใหม่คือลูกซ้ายของ current_node

การลบ

ไม่มีลูก

ภาพแสดง binary search tree ที่มีสมาชิกบางส่วน โหนดที่จะถูกลบถูกเน้นสีแดง โหนดนี้ไม่มีลูก

การลบ

ไม่มีลูก
- ลบโหนดนั้นออก

ภาพแสดง binary search tree ที่มีสมาชิกบางส่วน โหนดที่จะถูกลบหายไปจากต้นไม้แล้ว

การลบ

มีลูกหนึ่งโหนด

ภาพแสดง binary search tree ที่มีสมาชิกบางส่วน โหนดที่จะถูกลบถูกเน้นสีแดง และโหนดนี้มีลูกทางขวา

การลบ

มีลูกหนึ่งโหนด
- ลบโหนดนั้นออก
- เชื่อมต่อลูกเข้ากับพาเรนต์ของโหนดที่ลบ

ภาพแสดง binary search tree ที่มีสมาชิกบางส่วน โหนดที่ถูกลบหายไปแล้ว และโหนดรากชี้ไปยังลูกขวาของโหนดที่ถูกลบ

การลบ

มีลูกหนึ่งโหนด
- ลบโหนดนั้นออก
- เชื่อมต่อลูกเข้ากับพาเรนต์ของโหนดที่ลบ

ภาพแสดงโครงสร้าง binary search tree

การลบ

มีลูกสองโหนด

ภาพแสดง binary search tree โดยโหนดรากที่จะถูกลบถูกเน้นสีแดง

การลบ

มีลูกสองโหนด
- แทนที่ด้วยโหนดผู้สืบทอด (successor)
  - โหนดที่มีค่าน้อยที่สุดซึ่งมากกว่าค่าของโหนดนั้น
- วิธีหา successor:

ภาพแสดง binary search tree โดยโหนดรากที่จะถูกลบถูกเน้นสีแดง

การลบ

มีลูกสองโหนด
- แทนที่ด้วยโหนดผู้สืบทอด
  - โหนดที่มีค่าน้อยที่สุดซึ่งมากกว่าค่าของโหนดนั้น
- วิธีหา successor:
  - ไปที่ลูกขวา

ภาพแสดง binary search tree โดยโหนดรากที่จะถูกลบถูกเน้นสีแดง และลูกขวาของโหนดรากถูกเน้นสีเหลือง

การลบ

มีลูกสองโหนด
- แทนที่ด้วยโหนดผู้สืบทอด
  - โหนดที่มีค่าน้อยที่สุดซึ่งมากกว่าค่าของโหนดนั้น
- วิธีหา successor:
  - ไปที่ลูกขวา
  - วนเข้าหาโหนดซ้ายจนสุด

ภาพแสดง binary search tree โดยโหนดรากที่จะถูกลบถูกเน้นสีแดง และอีกโหนดหนึ่งถูกเน้นสีเหลืองเพื่อหา successor

การลบ

มีลูกสองโหนด
- แทนที่ด้วยโหนดผู้สืบทอด
  - โหนดที่มีค่าน้อยที่สุดซึ่งมากกว่าค่าของโหนดนั้น
- วิธีหา successor:
  - ไปที่ลูกขวา
  - วนเข้าหาโหนดซ้ายจนสุด

การลบ

มีลูกสองโหนด
- แทนที่ด้วยโหนดผู้สืบทอด
  - โหนดที่มีค่าน้อยที่สุดซึ่งมากกว่าค่าของโหนดนั้น
- วิธีหา successor:
  - ไปที่ลูกขวา
  - วนเข้าหาโหนดซ้ายจนสุด

ภาพแสดง binary search tree โดยโหนดรากที่จะถูกลบถูกเน้นสีแดง อีกโหนดถูกเน้นสีเหลืองเพื่อหา successor และพบว่า successor คือเลข 13

การลบ

มีลูกสองโหนด
- แทนที่ด้วยโหนดผู้สืบทอด
  - โหนดที่มีค่าน้อยที่สุดซึ่งมากกว่าค่าของโหนดนั้น
- วิธีหา successor:
  - ไปที่ลูกขวา
  - วนเข้าหาโหนดซ้ายจนสุด

ภาพแสดง binary search tree โดยโหนดรากถูกแทนที่ด้วย successor แล้ว

การลบ

มีลูกสองโหนด
- แทนที่ด้วยโหนดผู้สืบทอด
  - โหนดที่มีค่าน้อยที่สุดซึ่งมากกว่าค่าของโหนดนั้น
- วิธีหา successor:
  - ไปที่ลูกขวา
  - วนเข้าหาโหนดซ้ายจนสุด
  - ถ้า successor มีลูกทางขวา:

ภาพแสดง binary search tree โดยโหนด successor มีลูกทางขวา

การลบ

มีลูกสองโหนด
- แทนที่ด้วยโหนดผู้สืบทอด
  - โหนดที่มีค่าน้อยที่สุดซึ่งมากกว่าค่าของโหนดนั้น
- วิธีหา successor:
  - ไปที่ลูกขวา
  - วนเข้าหาโหนดซ้ายจนสุด
  - ถ้า successor มีลูกทางขวา:
    - ลูกนั้นจะกลายเป็นลูกซ้ายของพาเรนต์ของ successor

ภาพแสดง binary search tree โดยลูกของ successor กลายเป็นลูกซ้ายของพาเรนต์ของ successor และโหนดรากถูกแทนที่ด้วยโหนด successor แล้ว

การนำไปใช้

จัดเรียงลิสต์ได้อย่างมีประสิทธิภาพ
ค้นหาเร็วกว่า array และ linked list มาก
แทรกและลบเร็วกว่า array มาก
ใช้สร้างโครงสร้างข้อมูลขั้นสูง:
- dynamic set
- lookup table
- priority queue

มาฝึกกันเถอะ!

โครงสร้างข้อมูลและอัลกอริทึมใน Python