On this page

Binary Search Tree — พื้นฐาน & แนวคิด

👋 อ่านฟรีทั้งหมดบน Aph's Blog — เนื้อหาภาษาไทย ทำตามทีละหน้าใน sidebar ได้เลย หากมีข้อเสนอแนะหรืออยากให้เพิ่มหัวข้อไหน บอกได้เสมอ

tree (ต้นไม้) ที่จัดค่าไว้เป็นระเบียบ ซ้ายเล็กกว่า ขวาใหญ่กว่า จึง search แทรก ลบ ได้เร็ว O(h)

หมวดนี้ว่าด้วย Binary Search Tree (BST) หรือต้นไม้ค้นหาแบบทวิภาค เป็น data structure (โครงสร้างข้อมูล) ที่ออกแบบมาเพื่อ search (ค้นหา) insert (แทรก) และ delete (ลบ) ค่าได้เร็ว เจอบ่อยเวลาต้องเก็บข้อมูลที่ต้องค้นหาซ้ำ ๆ และอยากได้ความเร็วดีกว่า array (ลิสต์) ธรรมดา ถ้าคุณรู้จัก binary search ใน array ที่ sort (เรียง) แล้วมาก่อน BST ก็คือไอเดียเดียวกันแต่ทำบน tree (ต้นไม้)

BST คืออะไร

BST เป็น tree ที่แต่ละ node (โหนด) มี child (ลูก) ได้มากสุด 2 ตัว (ซ้ายกับขวา) แต่จุดเด่นที่ทำให้มันพิเศษกว่า tree ทั่วไปคือ มันจัดเรียงค่าไว้เป็นระเบียบตามกฎ ทำให้เรา search ค่าได้เร็วเหมือนตอนเปิดพจนานุกรม คือเปิดกลาง ๆ แล้วตัดสินใจว่าจะไปซ้ายหรือขวา ไม่ต้องไล่ดูทุก node

BST มีกฎเดียวที่ต้องจำ สำหรับทุก node ค่าใน subtree (ต้นไม้ย่อย) ทางซ้ายทั้งหมดต้อง น้อยกว่า ค่าของ node นั้น และค่าใน subtree ทางขวาทั้งหมดต้อง มากกว่า ค่าของ node นั้น พูดสั้น ๆ คือ left < node < right และกฎนี้เป็นจริงทุก node ไม่ใช่แค่ root (ราก) ต้นเดียว

python

# BST หน้าตาแบบนี้ (root = 5)
        #         5
        #        / \
        #       3   8
        #      / \   \
        #     2   4   9
        #
        # ทางซ้ายของ 5 (คือ 3,2,4) น้อยกว่า 5 ทั้งหมด
        # ทางขวาของ 5 (คือ 8,9) มากกว่า 5 ทั้งหมด
        # และกฎนี้จริงกับทุก node เช่น 3 มีซ้าย 2 (< 3) ขวา 4 (> 3)

เพราะมีกฎนี้ เวลาจะ search ค่าสักตัว เราเริ่มที่ root แล้ว compare (เทียบ) ถ้าค่าที่หาน้อยกว่า node ปัจจุบัน แปลว่ามันต้องอยู่ทางซ้าย (ทางขวาใหญ่กว่าหมดอยู่แล้ว ไม่ต้องดู) ถ้ามากกว่าก็ไปทางขวา ทำแบบนี้ไปเรื่อย ๆ แต่ละก้าวเราตัดครึ่งที่ต้องดูทิ้งไปเลย จึงใช้เวลาเท่ากับ height (ความสูง) ของ tree ไม่ใช่จำนวน node ทั้งหมด

นิยาม node และ Big-O

python

# นิยาม node ของต้นไม้ (LeetCode ให้มาแบบนี้)
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

operation	เฉลี่ย (สมดุล)	แย่สุด (เอียง)
search (ค้นหา)	O(log n)	O(n)
insert (แทรก)	O(log n)	O(n)
delete (ลบ)	O(log n)	O(n)

python

# template ค้นหาค่า target ใน BST แบบวนลูป — จำโครงนี้ไว้ใช้ได้
def search(root, target):
    node = root
    while node:
        if target == node.val:
            return node          # เจอแล้ว
        elif target < node.val:
            node = node.left     # ค่าเล็กกว่า ไปซ้าย
        else:
            node = node.right    # ค่าใหญ่กว่า ไปขวา
    return None                  # หาไม่เจอ

ทำไม O(h) ไม่ใช่ O(n)

h คือ height ของ tree (จำนวนชั้น) แต่ละก้าวเราลงลึกไปหนึ่งชั้นเสมอ ไม่เคยย้อนกลับ ถ้า tree สมดุลดี h ประมาณ log n การ search จึงเร็วมาก แต่ถ้า tree เอียงเป็นเส้นตรง (เช่น insert ค่าเรียงจากน้อยไปมาก) h จะกลายเป็น n และช้าลงเท่ากับ array ธรรมดา

หมวดนี้มี 2 ข้อ search ใน BST และ delete node ใน BST พร้อมแล้วกดถัดไปเริ่มข้อแรกได้เลย