ต้นไม้และต้นไม้ค้นหาแบบทวิภาค

ต้นไม้ (tree) ใช้จำลองความสัมพันธ์แบบลำดับชั้น และต้นไม้ค้นหาแบบทวิภาค (Binary Search Tree หรือ BST) ทำให้เราค้นหาข้อมูลได้เร็วระดับ O(log n) — แต่ต้องเป็นต้นไม้ที่ สมดุล เท่านั้น ไม่เช่นนั้นมันจะถดถอยลงเป็น O(n) และเหตุผลทั้งหมดที่เราเลือกใช้ต้นไม้แทนลิสต์ธรรมดาก็จะหายไป

แนวคิดหลัก

ต้นไม้คือโครงสร้างข้อมูลแบบลำดับชั้น (hierarchy) ที่ประกอบด้วย โหนด (node) เชื่อมต่อกันด้วยเส้นเชื่อม โดยไม่มีวงวน (cycle) คำศัพท์ที่ต้องรู้จัก:

• ราก (root) — โหนดบนสุด ไม่มีพ่อแม่
• โหนด (node) — หน่วยที่เก็บค่า และชี้ไปยังลูก
• เส้นเชื่อม (edge) — การเชื่อมต่อระหว่างโหนดกับลูกของมัน
• พ่อแม่ / ลูก (parent / child) — โหนดที่อยู่เหนือ/ใต้อีกโหนดหนึ่งโดยตรง
• พี่น้อง (sibling) — โหนดที่มีพ่อแม่เดียวกัน
• บรรพบุรุษ / ทายาท (ancestor / descendant) — โหนดใด ๆ ที่อยู่เหนือ/ใต้โหนดหนึ่งตามเส้นทางไปยังราก
• ใบ (leaf) — โหนดที่ไม่มีลูกเลย
• ซับทรี (subtree) — โหนดหนึ่งพร้อมทายาททั้งหมดของมัน มองเป็นต้นไม้ย่อยของตัวเอง
• ความลึก (depth) — จำนวนเส้นเชื่อมจากรากลงมาถึงโหนดหนึ่ง
• ความสูง (height) — จำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากโหนดหนึ่งลงไปถึงใบ (ความสูงของทั้งต้นไม้ = ความสูงของราก)
• ดีกรี (degree) — จำนวนลูกที่โหนดหนึ่งมี

ต้นไม้ทวิภาค (binary tree) คือต้นไม้ที่ทุกโหนดมีลูกได้ ไม่เกิน ๒ ตัว เรียกว่าลูกซ้ายและลูกขวา

        8          <- ราก (root)
       / \
      3   10
     / \    \
    1   6    14    <- 14 เป็นใบ (leaf)
       / \
      4   7        <- ความสูง = 3

โครงสร้างแบบลำดับชั้นนี้พบได้ทุกที่ ตั้งแต่ระบบไฟล์ในเครื่อง โครงสร้าง HTML ของหน้าเว็บ ไปจนถึงสายบังคับบัญชาในองค์กร

รูปทรงของต้นไม้ทวิภาค

ต้นไม้ทวิภาคไม่ได้มีหน้าตาแบบเดียว และรูปทรงส่งผลต่อประสิทธิภาพโดยตรง มีสามรูปทรงที่พบบ่อยทั้งในโจทย์สัมภาษณ์งานและในไลบรารีจริง:

รูปทรง	นิยาม	ทำไมถึงสำคัญ
Full	ทุกโหนดมีลูก ๐ หรือ ๒ ตัวเท่านั้น (ไม่มีลูกแค่ ๑)	เป็นข้อกำหนดปกติของ expression tree
Complete	ทุกชั้นเต็มหมดยกเว้นชั้นสุดท้ายที่อาจเติมจากซ้ายไปขวา	ทำให้เก็บต้นไม้ในอาเรย์แบนได้โดยไม่มีช่องว่างเสียเปล่า — นี่คือสิ่งที่ heap ใช้ประโยชน์โดยตรง
Perfect	ทุกชั้นเต็มสมบูรณ์	รับประกันความสูง = log2(n) พอดี ใช้เป็นรูปทรง “กรณีดีที่สุด” อ้างอิง

จำคำว่า “complete” ไว้ให้ดี — มันจะกลับมาอีกครั้งตอนพูดถึง heap ในหัวข้อถัดไป

คุณสมบัติของ BST

ต้นไม้ค้นหาแบบทวิภาคเพิ่มกฎหนึ่งข้อให้กับต้นไม้ทวิภาคธรรมดา:

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

กฎนี้สำคัญเพราะทำให้เราค้นหาได้แบบ “ตัดครึ่ง” เหมือน binary search: เริ่มที่ราก ถ้าค่าที่หาน้อยกว่าโหนด ก็ลงซ้าย ถ้ามากกว่าก็ลงขวา แต่ละก้าวตัดข้อมูลที่เหลือทิ้งไปครึ่งหนึ่ง ดังนั้นเมื่อต้นไม้สมดุล จำนวนก้าวจึงเป็น O(log n)

ผลพลอยได้ที่สวยงาม: การท่องแบบ in-order (ซ้าย → โหนด → ขวา) ของ BST จะให้ค่าออกมา เรียงจากน้อยไปมาก เสมอ

ตัวอย่างคลี่ทีละขั้น: การค้นหาค่า

ใช้ต้นไม้ด้านบน มาไล่การค้นหาสองแบบทีละขั้นตอนกัน

ค้นหาค่า 7 (พบ):

ขั้น	โหนดปัจจุบัน	การเปรียบเทียบ	ทิศทาง
1	8	7 < 8	ไปซ้าย
2	3	7 > 3	ไปขวา
3	6	7 > 6	ไปขวา
4	7	7 == 7	พบ ใช้ ๔ ก้าว

ค้นหาค่า 11 (ไม่พบ):

ขั้น	โหนดปัจจุบัน	การเปรียบเทียบ	ทิศทาง
1	8	11 > 8	ไปขวา
2	10	11 > 10	ไปขวา
3	14	11 < 14	ไปซ้าย
4	None	—	ไม่พบ เปรียบเทียบ ๓ ครั้งแล้วเจอช่องว่าง

สังเกตว่าแม้การค้นหาที่ “ไม่พบ” ก็ยังใช้เวลาแค่ O(h) (h = ความสูง) เหมือนกัน — เพียงแต่จบลงที่ช่องว่างแทนที่จะเจอค่าที่ตรงกัน

การท่องต้นไม้ (Traversals)

การท่อง (traversal) คือการเยี่ยมทุกโหนดอย่างเป็นระบบ มี ๓ แบบหลักที่เป็น depth-first สำหรับต้นไม้ทวิภาค ต่างกันที่ “เยี่ยมโหนดตัวเองตอนไหน” เทียบกับลูกของมัน:

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

def preorder(node):    # โหนด -> ซ้าย -> ขวา
    if node is None:
        return
    print(node.val)
    preorder(node.left)
    preorder(node.right)

def inorder(node):     # ซ้าย -> โหนด -> ขวา  (ได้ค่าเรียงลำดับใน BST)
    if node is None:
        return
    inorder(node.left)
    print(node.val)
    inorder(node.right)

def postorder(node):   # ซ้าย -> ขวา -> โหนด
    if node is None:
        return
    postorder(node.left)
    postorder(node.right)
    print(node.val)

• pre-order — เหมาะกับการ “คัดลอก” หรือสร้างต้นไม้ขึ้นใหม่ และการบันทึกโครงสร้าง (เช่น serialize)
• in-order — ใน BST จะได้ค่าที่เรียงลำดับแล้ว เหมาะกับการแสดงผลแบบเรียง
• post-order — เยี่ยมลูกก่อนพ่อแม่ เหมาะกับการ “ลบ” ต้นไม้จากล่างขึ้นบน หรือคำนวณค่าของ expression tree (คำนวณค่าของลูกให้เสร็จก่อนค่อยรวมที่โหนดพ่อแม่)

ตัวอย่างคลี่ทีละขั้น: สามแบบการท่องของต้นไม้เดียวกัน

ใช้ต้นไม้เดิม (ราก 8) นี่คือลำดับที่แต่ละแบบเยี่ยม:

การท่อง	ลำดับผลลัพธ์
pre-order	8, 3, 1, 6, 4, 7, 10, 14
in-order	1, 3, 4, 6, 7, 8, 10, 14
post-order	1, 4, 7, 6, 3, 14, 10, 8

สังเกตว่า in-order ให้ลิสต์ที่เรียงลำดับสมบูรณ์ — นี่คือผลตอบแทนโดยตรงจากคุณสมบัติของ BST

วิดเจ็ตด้านบนแสดงแอนิเมชันของ call tree ของ fib(n) ไม่ใช่การท่องต้นไม้โดยตรง — แต่โมเดลทางความคิดถ่ายทอดกันได้เลย ทุกการเรียก traversal (inorder(node.left), inorder(node.right)) ก็คือ stack frame ใหม่ที่ต้อง return กลับมาให้ครบก่อนที่พ่อแม่ของมันจะทำงานต่อ ลองดูว่าการเรียก fib แตกกิ่งลงไป ไล่ลึกลงถึงก้นบึ้ง แล้วค่อย ๆ คลี่กลับขึ้นมาอย่างไร — จังหวะ “แตกลงแล้วคลี่กลับ” นั้นเหมือนกับที่ inorder(8) ทำเป๊ะ: มันจะดิ่งลงไปตามแนวซ้ายสุดก่อน แล้วค่อย print อะไรออกมา

การท่องแบบ Level-order (BFS)

การท่องสามแบบข้างต้นทั้งหมดเป็นแบบ depth-first — คือดิ่งลงไปตามกิ่งหนึ่งก่อนแล้วค่อยถอยกลับ บางครั้งเราต้องการเยี่ยมโหนด ทีละชั้น แทน (แถวบนสุดก่อน แล้วค่อยแถวถัดไป ไปเรื่อย ๆ) นี่คือ breadth-first search (BFS) ซึ่งทำด้วยคิว (queue) แทนการเรียกซ้ำ (recursion):

from collections import deque

def level_order(root):
    if root is None:
        return []
    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        result.append(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    return result

Level-order เหมาะกับ: การพิมพ์ต้นไม้ทีละแถว การหาความกว้างของแต่ละชั้น หรือการบันทึกโครงสร้างต้นไม้ในแบบที่ประกอบกลับได้ง่ายทีละชั้น

ตัวอย่างคลี่ทีละขั้น — ไล่สถานะคิวของต้นไม้เดิม:

ขั้น	ดึงออกจากคิว	ลำดับที่เยี่ยมแล้ว	เพิ่มเข้าคิว
1	8	8	3, 10
2	3	8, 3	1, 6
3	10	8, 3, 10	14
4	1	8, 3, 10, 1	—
5	6	8, 3, 10, 1, 6	4, 7
6	14	8, 3, 10, 1, 6, 14	—
7	4	8, 3, 10, 1, 6, 14, 4	—
8	7	8, 3, 10, 1, 6, 14, 4, 7	—

ผลลัพธ์สุดท้าย: 8, 3, 10, 1, 6, 14, 4, 7 — ชั้นบนสุดก่อน แล้วไล่จากซ้ายไปขวาในแต่ละแถว

การแทรกและการค้นหา

def insert(node, val):
    if node is None:
        return Node(val)
    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    return node

def search(node, val):
    if node is None or node.val == val:
        return node
    if val < node.val:
        return search(node.left, val)
    return search(node.right, val)

ทั้งสองฟังก์ชันเดินตามหลัก “เปรียบเทียบแล้วไปซ้ายหรือขวา” แบบเดียวกับตัวอย่างการค้นหาข้างบนเป๊ะ — การแทรกก็คือ “ค้นหาตำแหน่งที่ค่านี้ ควรจะอยู่แล้ววางมันตรงนั้น”

ตัวอย่างคลี่ทีละขั้น: สร้าง BST ขึ้นมาใหม่ทั้งหมด

แทรกค่า 50, 30, 70, 20, 40, 60, 80 ลงในต้นไม้ว่าง ทีละตัว:

แทรก	เส้นทางที่เดิน	ไปอยู่ที่
50	(ว่างเปล่า)	กลายเป็นราก
30	30 < 50 ไปซ้าย	ลูกซ้ายของ 50
70	70 > 50 ไปขวา	ลูกขวาของ 50
20	20 < 50 → 20 < 30 ไปซ้าย ไปซ้าย	ลูกซ้ายของ 30
40	40 < 50 → 40 > 30 ไปซ้าย ไปขวา	ลูกขวาของ 30
60	60 > 50 → 60 < 70 ไปขวา ไปซ้าย	ลูกซ้ายของ 70
80	80 > 50 → 80 > 70 ไปขวา ไปขวา	ลูกขวาของ 70

ผลลัพธ์ — ต้นไม้ที่สมดุลสมบูรณ์แบบ ความสูง 2 สำหรับ 7 โหนด:

        50
       /  \
      30    70
     / \   / \
    20 40 60 80

นี่คือหน้าตาของ BST เมื่อลำดับการแทรก “เป็นมิตร” (สุ่มหรือสมดุลพอประมาณ) หัวข้อถัดไปเราจะดูว่าถ้าลำดับไม่เป็นมิตรจะเกิดอะไรขึ้น

การลบ (Delete)

การลบเป็นการดำเนินการที่ยุ่งยากที่สุดของ BST เพราะการเอาโหนดออกต้องไม่ทำลายกฎ left < node < right มีสามกรณี:

1. โหนดเป็นใบ — ลบทิ้งได้เลย พอยน์เตอร์ของพ่อแม่ก็กลายเป็น None
2. โหนดมีลูกเดียว — เชื่อมข้าม: ให้พ่อแม่ชี้ตรงไปยังลูกตัวเดียวของโหนดนั้นแทน
3. โหนดมีลูกสองตัว — จะลบทิ้งเฉย ๆ ไม่ได้เพราะจะเกิดช่องว่าง ต้องหา in-order successor ก่อน (ค่าน้อยที่สุดในซับทรีฝั่งขวา — เดินไปทาง right แล้วเดิน left, left, left... ต่อ) แล้วคัดลอกค่านั้นมาใส่แทนที่โหนดที่กำลังจะ “ลบ” จากนั้นค่อยลบ successor ตัวเดิมออกจากซับทรีฝั่งขวา (ซึ่งรับประกันว่ามีลูกได้มากสุดตัวเดียว จึงลดรูปกลับไปเป็นกรณี ๑ หรือ ๒)

def delete(node, key):
    if node is None:
        return None
    if key < node.val:
        node.left = delete(node.left, key)
    elif key > node.val:
        node.right = delete(node.right, key)
    else:
        # เจอโหนดที่จะลบแล้ว
        if node.left is None:
            return node.right          # กรณี 1 หรือ 2
        if node.right is None:
            return node.left           # กรณี 2
        # กรณี 3: มีลูกสองตัว — แทนที่ด้วย in-order successor
        successor = node.right
        while successor.left is not None:
            successor = successor.left
        node.val = successor.val
        node.right = delete(node.right, successor.val)
    return node

ตัวอย่างคลี่ทีละขั้น: ลบโหนดที่มีลูกสองตัว

ใช้ต้นไม้เดิม (ราก 8) ลบค่า 3 ออก โหนด 3 มีลูกสองตัว (1 และ 6) จึงเข้ากรณี ๓:

1. หา in-order successor ของ 3: ไปยังซับทรีฝั่งขวา (รากคือ 6) แล้วเดินไปทางซ้ายต่อ 6 มีลูกซ้ายคือ 4 และ 4 ไม่มีลูกซ้ายอีก ดังนั้น successor คือ 4
2. คัดลอก 4 มาใส่แทนที่โหนดที่กำลังเก็บค่า 3 อยู่
3. ลบโหนด 4 ตัวเดิมออกจากซับทรีฝั่งขวาแบบ recursive — 4 เป็นใบ จึงลบทิ้งได้ตรง ๆ

ก่อน:                หลังลบ 3:
        8                    8
       / \                  / \
      3   10                4   10
     / \    \      ->      / \    \
    1   6    14           1   6    14
       / \                     \
      4   7                     7

ตอนนี้โหนด 4 อยู่ในตำแหน่งที่ 3 เคยอยู่ และตำแหน่งเดิมของมันใต้ 6 ก็หายไป คุณสมบัติของ BST ยังคงเป็นจริงทุกที่

เรื่องของความสมดุล

ความเร็ว O(log n) ของ BST ไม่ได้รับประกันเสมอไป ลองดูสิ่งที่เกิดขึ้นเมื่อเราใส่ข้อมูลที่เรียงมาแล้ว เช่น 1, 2, 3, 4, 5 (เทียบกับลำดับที่ “เป็นมิตร” อย่าง 50, 30, 70, ... ในตัวอย่างการแทรกก่อนหน้านี้):

    1
     \
      2
       \
        3
         \
          4
           \
            5    <- ความสูง = n

ทุกค่าใหม่มากกว่าค่าเดิมเสมอ จึงไปอยู่ฝั่งขวาเรื่อย ๆ ต้นไม้กลายสภาพเป็น “ลิงก์ลิสต์” ที่มีความสูงเท่ากับ n การค้นหาจึงต้องไล่ทีละโหนด กลายเป็น O(n) — เสียข้อได้เปรียบของต้นไม้ไปจนหมด

นี่คือกับดักสำคัญ: BST ธรรมดาเร็วแค่ “โดยเฉลี่ย” กับข้อมูลที่กระจายแบบสุ่ม แต่กรณีเลวร้ายสุดคือ O(n)

ทางแก้ — ต้นไม้ที่ปรับสมดุลตัวเอง (self-balancing trees) โครงสร้างอย่าง AVL tree และ red-black tree เก็บข้อมูลเสริม (ความสูงที่บันทึกไว้ หรือ “สี” ของโหนด) และหลังจากทุกการแทรกหรือลบ จะตรวจสอบว่าต้นไม้เอียงไปหรือไม่ ถ้าเอียง มันจะทำ การหมุน (rotation) — การจัดเรียงพอยน์เตอร์เพียงไม่กี่ตัวใหม่ในระดับท้องถิ่น ที่สลับโหนดกับลูกตัวหนึ่งของมัน โดยยังคงรักษาลำดับของ BST ไว้ — เพื่อคืนความสมดุลกลับมา AVL tree จะปรับสมดุลอย่างเข้มงวด (ผลต่างความสูงระหว่างซับทรีไม่เกิน ๑ เสมอ ทำให้ค้นหาเร็วมากแต่หมุนบ่อยเวลาเขียน) ส่วน red-black tree จะหลวมกว่า (กฎความสมดุลที่อ่อนกว่า บังคับผ่านการให้สีโหนด) แต่ต้องหมุนน้อยกว่าโดยเฉลี่ย นี่คือเหตุผลที่มันอยู่เบื้องหลังไลบรารีมาตรฐานของภาษาส่วนใหญ่ (เช่น std::map ของ C++, TreeMap ของ Java) ไม่ว่าจะแบบไหน การรับประกันเหมือนกัน: ความสูงจะอยู่ที่ O(log n) เสมอ ไม่ว่าจะแทรกข้อมูลในลำดับใดก็ตาม (กลไกการหมุนโดยละเอียดเป็นหัวข้อขั้นสูง — ตอนนี้ขอแค่รู้ว่า ทำไม มันถึงมีอยู่: เพื่อเอาชนะการถดถอยแบบที่แสดงไว้ข้างต้นนั่นเอง)

heap เข้ามาเกี่ยวข้องตรงไหน heap เป็นโครงสร้างต้นไม้อีกแบบที่มักสับสนกับ BST เพราะมักถูกวาดเป็นต้นไม้ทวิภาคเหมือนกัน — แต่มันบังคับกฎที่อ่อนกว่ามาก คือ heap property (พ่อแม่ ≤ ลูกเสมอสำหรับ min-heap หรือ ≥ สำหรับ max-heap) ซึ่ง ไม่ใช่ การเรียงลำดับซ้าย/ขวาแบบเต็มรูปแบบของ BST เพราะ heap สนใจแค่ลำดับระหว่างพ่อแม่กับลูก และถูกรักษาให้เป็นต้นไม้ทวิภาคแบบ complete เสมอ (แนวคิด “รูปทรง” จากหัวข้อก่อนหน้า) มันจึงถูกอัดลงในอาเรย์แบนได้โดยไม่ต้องมีพอยน์เตอร์เลย และความสามารถพิเศษหนึ่งเดียวของมัน — หาค่าน้อยสุดหรือมากสุดได้ทันที และลบออกได้ใน O(log n) — ทำให้มันเป็นเครื่องยนต์ตามธรรมชาติเบื้องหลัง priority queue, heapq ของ Python, อัลกอริทึมของ Dijkstra และตัวจัดตารางงานของระบบปฏิบัติการ ข้อแลกเปลี่ยนคือ heap ทำไม่ได้ สำหรับการค้นหาค่าใด ๆ แบบ O(log n) ทั่วไป (ต้องอาศัยการเรียงลำดับแบบเต็มของ BST) — มันเป็นผู้เชี่ยวชาญเฉพาะทางสำหรับ “หาค่าน้อย/มากสุดให้ที” ในขณะที่ BST เป็นผู้เล่นรอบด้านสำหรับ “รักษาทุกอย่างให้เรียงลำดับและค้นหาได้”

การวิเคราะห์ความซับซ้อน

การดำเนินการ	BST สมดุล	BST ไม่สมดุล (กรณีเลวร้าย)
ค้นหา (search)	O(log n)	O(n)
แทรก (insert)	O(log n)	O(n)
ลบ (delete)	O(log n)	O(n)
ท่องทั้งต้นไม้ (แบบใดก็ได้)	O(n)	O(n)
พื้นที่ (ความลึกของ recursion stack)	O(log n)	O(n)

ความแตกต่างของค้นหา/แทรก/ลบ มาจาก “ความสูง” ของต้นไม้ล้วน ๆ: ทุกการดำเนินการนี้ใช้เวลาตามความสูง — O(log n) สำหรับต้นไม้สมดุล ไปจนถึง O(n) สำหรับต้นไม้เอียง ส่วนการท่องทั้งต้นไม้จะเยี่ยมทุกโหนดครั้งเดียวเสมอ จึงเป็น O(n) ไม่ว่าจะสมดุลหรือไม่ — แต่ต้นไม้ที่ เอียง ยังกินพื้นที่ recursion stack ถึง O(n) ด้วย เทียบกับ O(log n) ของต้นไม้สมดุล

โจทย์จากโลกจริง: ดัชนีเรียงลำดับและการค้นหาแบบช่วง

ลองนึกถึงระบบ autocomplete หรือ ดัชนีฐานข้อมูลที่เรียงลำดับ เมื่อผู้ใช้พิมพ์ “ad” เราต้องการคืนคำทั้งหมดที่อยู่ในช่วง ["ad", "ae") อย่างรวดเร็ว

ถ้าเก็บข้อมูลในลิสต์แบบแบน (flat list) ที่ไม่เรียง การหาช่วงต้องสแกนทุกตัว = O(n) ทุกครั้ง แต่ถ้าใช้ BST แบบสมดุล (หรือญาติของมันอย่าง balanced tree ที่ฐานข้อมูลจริงใช้):

• หาจุดเริ่มต้นของช่วงได้ใน O(log n)
• แล้วท่องแบบ in-order ต่อไปเพื่อดึงค่าที่อยู่ในช่วงตามลำดับ

นี่คือเหตุผลที่ดัชนีของฐานข้อมูล (เช่น B-tree ซึ่งเป็นการขยายแนวคิดของ BST) ทำ range query ได้เร็วกว่าการสแกนทั้งตารางมหาศาล ต้นไม้รักษาลำดับไว้ตลอดเวลา จึงตอบคำถามแบบ “มากกว่า/น้อยกว่า/อยู่ระหว่าง” ได้อย่างมีประสิทธิภาพ (เทียบกับกรณีการใช้งาน heap ข้างต้น: ดัชนีฐานข้อมูลต้องการ การเข้าถึงช่วงแบบเรียงลำดับ จึงต้องเลือก BST แบบสมดุล ไม่ใช่ heap — heap จะบอกได้แค่แถวที่น้อยที่สุดแถวเดียว แต่บอก “ทุกแถวระหว่าง ‘ad’ ถึง ‘ae’” ไม่ได้)

แบบฝึกหัด

๑. ทำนายเส้นทางการค้นหา จากต้นไม้ในหัวข้อแนวคิดหลัก (ราก = 8) ให้เขียนลำดับโหนดที่ถูกเยี่ยมเมื่อค้นหาค่า 7

เฉลย

8 → 3 → 6 → 7 เริ่มที่ 8 (7 < 8 ไปซ้าย) → 3 (7 > 3 ไปขวา) → 6 (7 > 6 ไปขวา) → 7 พบ ใช้ ๔ ก้าว

๒. แทรกตามลำดับแล้ววาดต้นไม้ แทรกค่า 5, 2, 8, 1, 3 ลงใน BST ว่าง ตามลำดับนี้ แล้ววาดต้นไม้ที่ได้

เฉลย

      5
     / \
    2   8
   / \
  1   3

5 เป็นรากก่อน, 2 < 5 ไปซ้าย, 8 > 5 ไปขวา, 1 < 5 < 2 ไปซ้ายของ 2, 3 < 5 แต่ > 2 ไปขวาของ 2

๓. ตรวจสอบว่าเป็น BST หรือไม่ ต้นไม้ต่อไปนี้เป็น BST ที่ถูกต้องหรือไม่ เพราะอะไร?

      10
     /  \
    5    15
        /  \
       6    20

เฉลย

ไม่เป็น BST ที่ถูกต้อง โหนด 6 อยู่ในซับทรีฝั่งขวาของ 10 ดังนั้นทุกค่าในนั้นต้องมากกว่า 10 แต่ 6 < 10 จึงผิดกฎ ข้อควรระวัง: การตรวจสอบต้องดู “ช่วงค่าที่อนุญาต” ของทั้งซับทรี ไม่ใช่แค่เทียบกับพ่อแม่โดยตรง

๔. หาค่าน้อยสุดและมากสุด ใน BST ใด ๆ ค่าน้อยสุดและมากสุดอยู่ที่ตำแหน่งใด และต้องเดินอย่างไรไปถึง?

เฉลย

• น้อยสุด: เดินไปทางซ้ายสุดเรื่อย ๆ จนไม่มีลูกซ้าย
• มากสุด: เดินไปทางขวาสุดเรื่อย ๆ จนไม่มีลูกขวา

ทั้งสองใช้เวลา O(h) โดย h คือความสูง (ดังนั้น O(log n) เมื่อสมดุล) นี่คือเส้นทางเดียวกับที่ฟังก์ชัน delete ใช้หา in-order successor เป๊ะ

๕. in-order ให้อะไร ถ้าท่องต้นไม้จากข้อ ๒ แบบ in-order จะได้ลำดับใด?

เฉลย

1, 2, 3, 5, 8 — เรียงจากน้อยไปมาก ตามคุณสมบัติของ BST

๖. level-order ให้อะไร ใช้ต้นไม้เดียวกับข้อ ๒ (ราก 5) การท่องแบบ level-order (BFS) จะให้ลำดับใด?

เฉลย

5, 2, 8, 1, 3 — รากก่อน แล้วไล่จากซ้ายไปขวาในชั้นถัดไป แล้วชั้นถัดไปอีก เทียบกับผลลัพธ์ in-order (1, 2, 3, 5, 8) — ต้นไม้เดียวกันแต่ลำดับต่างกันโดยสิ้นเชิง เพราะ BFS เยี่ยมตาม ความลึก ในขณะที่ in-order เยี่ยมตาม ตำแหน่งค่า

๗. ลบโหนดที่มีลูกสองตัว ใช้ต้นไม้จากหัวข้อแนวคิดหลัก (ราก 8) หลังจากลบ ราก (8) ซึ่งมีลูกสองตัว (3 และ 10) ออก ต้นไม้จะมีหน้าตาอย่างไร?

เฉลย

in-order successor ของ 8 คือค่าน้อยที่สุดในซับทรีฝั่งขวา (รากคือ 10) เนื่องจาก 10 ไม่มีลูกซ้าย 10 จึง เป็น successor เอง คัดลอก 10 มาใส่ที่ราก แล้วลบโหนด 10 ตัวเดิมออกจากซับทรีฝั่งขวา — มันมีแค่ลูกขวา (14) จึงถูกเชื่อมข้ามและแทนที่ด้วย 14

        10
       /  \
      3    14
     / \
    1   6
       / \
      4   7

๘. จับผิดบั๊ก AI เขียนฟังก์ชัน search นี้ให้ มันคอมไพล์ผ่านและดูเหมือนจะทำงานถูกต้องเวลาทดสอบผิวเผิน ผิดตรงไหน และผิดกับอินพุตแบบใดบ้าง?

def search(node, val):
    if node is None:
        return None
    if val < node.val:
        return search(node.left, val)
    else:
        return search(node.right, val)

เฉลย

บั๊กคือ: ไม่มีการตรวจสอบ val == node.val เลย เมื่อค่าที่หาเท่ากับค่าของโหนดปัจจุบัน โค้ดจะตกไปใน branch else แล้วเรียกซ้ำเข้าไปในซับทรีฝั่งขวา — แต่ตามคุณสมบัติของ BST ซับทรีฝั่งขวามีแต่ค่าที่ มากกว่า node.val เท่านั้น ดังนั้นค่าที่หาจะไม่มีวันเจอที่นั่น ฟังก์ชันจะคืนค่า None (ไม่พบ) แม้ว่าค่านั้นจะมีอยู่ในต้นไม้จริง ๆ ตรงโหนดที่มันเพิ่งเดินผ่านไปนั่นเอง

วิธีแก้: เพิ่มการตรวจสอบความเท่ากันอย่างชัดเจนก่อนเปรียบเทียบ:

def search(node, val):
    if node is None or node.val == val:
        return node
    if val < node.val:
        return search(node.left, val)
    return search(node.right, val)

วิพากษ์โค้ดจากปัญญาประดิษฐ์

พรอมป์ที่ให้ AI: “เขียนคลาส BST ใน Python ให้หน่อย พร้อมบอกความซับซ้อนด้านเวลาของการค้นหา”

คำตอบของ AI: คลาส BST ธรรมดา (insert/search ตามที่แสดงไว้ก่อนหน้า) พร้อมคำกล่าวอ้าง:

“การค้นหาในต้นไม้ของผมเป็น O(log n) เสมอ เพราะ BST ตัดข้อมูลครึ่งหนึ่งในทุกก้าว”

ตัดสิน — คำกล่าวนี้ผิดตรงไหน?

คำกล่าว ผิด เพราะ BST ธรรมดา (ที่ไม่ปรับสมดุล) ไม่รับประกันความสูง O(log n)

ตัวอย่างค้าน: แทรกข้อมูลที่เรียงมาแล้ว เช่น 1, 2, 3, 4, 5 ต้นไม้จะเอียงไปทางขวาทั้งหมดจนกลายเป็นลิงก์ลิสต์ความสูง n การค้นหาค่า 5 ต้องเดินผ่านทุกโหนด = O(n)

ที่ถูกต้องคือ: BST ธรรมดาเป็น O(log n) โดยเฉลี่ย กับข้อมูลสุ่ม แต่กรณีเลวร้ายเป็น O(n) หากต้องการ O(log n) ที่รับประกัน ต้องใช้ต้นไม้ปรับสมดุลตัวเอง เช่น AVL หรือ red-black tree

ปรับปรุง — อย่าสมมติว่าสมดุล ให้ตรวจสอบจริง:

def height(node):
    if node is None:
        return -1
    return 1 + max(height(node.left), height(node.right))

def is_balanced(node):
    if node is None:
        return True
    left_h, right_h = height(node.left), height(node.right)
    return (
        abs(left_h - right_h) <= 1
        and is_balanced(node.left)
        and is_balanced(node.right)
    )

คำตอบฉบับปรับปรุงเลิกยืนยัน O(log n) แบบไม่มีเงื่อนไข เพิ่มวิธี ตรวจสอบ จริงว่าต้นไม้ที่ได้มาสมดุลหรือไม่ และชี้ทางแก้หากไม่แน่ใจ: ถ้าข้อมูลที่เข้ามาอาจมาแบบเรียงแล้ว (หรือเกือบเรียง) ให้สับ (shuffle) ก่อนแทรก หรือเปลี่ยนไปใช้โครงสร้างที่ปรับสมดุลตัวเอง (AVL/red-black tree หรือไลบรารีสำเร็จรูปอย่าง sortedcontainers ของ Python) เพื่อให้การรับประกัน O(log n) เป็นจริงเสมอ ไม่ใช่แค่ “ส่วนใหญ่”

🎮 เกมเดฟ: ต้นไม้ฉาก (scene tree) และควอดทรี (quadtree)

ต้นไม้ฉาก (scene tree) ของเกมเอนจินคือต้นไม้ในความหมายตรงตัวของบทเรียนนี้เป๊ะ ๆ นั่นคือ โหนดที่เชื่อมกันด้วยเส้นเชื่อมพ่อแม่-ลูก ไม่มีวงวน และมีกฎเพิ่มอีกหนึ่งข้อทับซ้อนลงไป: transform ของพ่อแม่ (ตำแหน่ง การหมุน สเกล) จะไหลลงไปประกอบกับทายาททุกตัว การท่องต้นไม้แบบ depth-first คือวิธีที่เอนจินอย่าง Godot ใช้ตอบคำถามว่า “ทุกอย่างในโลกอยู่ที่ไหน” ในทุกเฟรม และเมื่อโลกใหญ่ขึ้น เราจะเปลี่ยนจากกลเม็ด “เรียงตามค่า” ของ BST ไปเป็นกลเม็ด “เรียงตามพื้นที่” แทน นั่นคือ ควอดทรี (quadtree) — ต้นไม้ที่แบ่งกิ่งตามเรขาคณิต ไม่ใช่ตาม </>

ตัวอย่างคลี่ทีละขั้น: กระจาย transform ลงไปในต้นไม้ฉาก

แนวทางไร้เดียงสาคือเก็บตำแหน่ง สัมบูรณ์ (absolute) ในโลกของแต่ละเอนทิตี้ตรง ๆ พอพ่อแม่ขยับ เราต้องจำไว้ให้ได้ว่าต้องอัปเดตลูก หลาน เหลนทุกตัวด้วยมือ — พลาดตัวเดียว อาวุธก็จะลอยหลุดออกจากมือที่ถืออยู่ ทางแก้ที่ต้นไม้มอบให้คือ: แต่ละโหนดเก็บแค่ ออฟเซ็ตท้องถิ่น (local offset) เทียบกับพ่อแม่ของมันเท่านั้น แล้วใช้การท่องแบบ preorder เพียงรอบเดียวคำนวณตำแหน่งในโลกใหม่ทั้งหมดจากรากลงไป — ขยับโหนดเดียว การท่องก็จะกระจายผลลัพธ์ลงไปถึงทุกอย่างที่อยู่ข้างใต้โดยอัตโนมัติ

class Node:
    def __init__(self, name, local_x, local_y, local_scale=1.0):
        self.name = name
        self.local_x = local_x
        self.local_y = local_y
        self.local_scale = local_scale
        self.children = []
        self.world_x = 0.0
        self.world_y = 0.0
        self.world_scale = 1.0

    def add_child(self, child):
        self.children.append(child)

def propagate_transform(node, parent_x=0.0, parent_y=0.0, parent_scale=1.0):
    # พ่อแม่ -> ลูก: สเกลออฟเซ็ตท้องถิ่นก่อน แล้วค่อยบวกด้วยตำแหน่งในโลกของพ่อแม่
    node.world_scale = parent_scale * node.local_scale
    node.world_x = parent_x + node.local_x * parent_scale
    node.world_y = parent_y + node.local_y * parent_scale
    for child in node.children:              # preorder: เยี่ยมโหนดก่อน แล้วค่อยลงไปหาลูก
        propagate_transform(child, node.world_x, node.world_y, node.world_scale)

# สร้างลำดับชั้น: Player -> Sprite, Camera, Weapon -> Muzzle
player = Node("Player", 100, 100)
sprite = Node("Sprite", 0, 0)
camera = Node("Camera", -200, 0)
weapon = Node("Weapon", 20, -10)
muzzle = Node("Muzzle", 15, 0)
weapon.add_child(muzzle)
for child in (sprite, camera, weapon):
    player.add_child(child)

propagate_transform(player)
print(muzzle.world_x, muzzle.world_y)        # 135.0 90.0

player.local_x, player.local_y = 300, 150    # ขยับตัว player...
propagate_transform(player)                  # ...ท่องรอบเดียว อัปเดตทายาททุกตัว
print(muzzle.world_x, muzzle.world_y)        # 335.0 140.0

propagate_transform คือ การท่องแบบ preorder — เยี่ยมโหนดก่อน แล้วค่อยเรียกซ้ำเข้าไปในลูกของมัน — รูปแบบเดียวกับ preorder() ที่เจอไปก่อนหน้านี้ในบทเรียน เพียงแต่สะสม transform แทนที่จะ print ค่าออกมา

วิดเจ็ตด้านบนแสดงแอนิเมชันรูปทรงของ call tree แบบ depth-first ใด ๆ: ดิ่งลงไปตามกิ่งซ้ายสุดก่อน แล้วคลี่กลับ แล้วค่อยไปกิ่งถัดไป นั่นคือรูปทรงการเรียกของ propagate_transform เป๊ะตอนที่มันไล่ตาม Player → Weapon → Muzzle — ตำแหน่งในโลกของ Muzzle จะยังไม่เสร็จสมบูรณ์จนกว่าการเรียกซ้ำที่ลงไปถึงมันจะ return กลับมา

รูป: ต้นไม้ฉาก (scene tree) — transform ของ Player ไหลลงไปสู่ Sprite, Camera และ Weapon แล้ว Weapon ก็ส่งต่อลงไปอีกชั้นหนึ่งถึง Muzzle

ควอดทรีเข้ามาเกี่ยวข้องตรงไหน ต้นไม้ฉากจัดลำดับ ความสัมพันธ์ พ่อแม่/ลูก ส่วนควอดทรีจัดลำดับ พื้นที่ สำหรับ broad-phase collision ในโลกเปิดขนาดใหญ่ การเช็กทุกคู่ในบรรดา n เอนทิตี้คือ O(n²) — และคู่ส่วนใหญ่ก็ไม่ได้อยู่ใกล้กันเลยด้วยซ้ำ ควอดทรีแก้ปัญหานี้ด้วยการแบ่งพื้นที่สี่เหลี่ยมจัตุรัสออกเป็นสี่ควอแดรนต์แบบ recursive ทุกครั้งที่ควอแดรนต์หนึ่งมีเอนทิตี้เกินเกณฑ์ที่กำหนด (เช่น ๔ ตัว) ทำให้การตรวจชนต้องลงไปเช็กแค่ควอแดรนต์ที่ทับซ้อนกับ bounding box ของเอนทิตี้เท่านั้น เทียบกับเอนทิตี้หยิบมือเดียวที่อยู่ในนั้นจริง ๆ แล้วข้ามส่วนที่เหลือของโลกไปทั้งหมดโดยไม่ต้องตรวจดูเลย — เปลี่ยนการกวาดทั่วโลกแบบ O(n²) ให้กลายเป็นอะไรที่ใกล้เคียง O(n log n) แทน

แบบฝึกหัดเกมเดฟ

๑. ลำดับการท่อง propagate_transform(player) เยี่ยมห้าโหนดข้างบนตามลำดับใด?

เฉลย

Player, Sprite, Camera, Weapon, Muzzle — เป็นการท่องแบบ preorder: เยี่ยมโหนดก่อน แล้วไล่ลูปเข้าไปในลูกของมันตามลำดับ Weapon จะถูกเยี่ยมก่อนที่จะเรียกซ้ำเข้าไปในลูกของมันเองคือ Muzzle

๒. คำถามเรื่องความลึกและดีกรี Muzzle มี ความลึก (depth) เท่าไรในลำดับชั้นนี้? Weapon มี ดีกรี (degree) เท่าไร (จำนวนลูก)? Muzzle เป็นใบ (leaf) หรือไม่?

เฉลย

ความลึกของ Muzzle = ๒ (Player → Weapon เป็นเส้นเชื่อมหนึ่งเส้น, Weapon → Muzzle เป็นเส้นเชื่อมที่สอง) ดีกรีของ Weapon = ๑ (มีแค่ Muzzle) ใช่ Muzzle เป็นใบ — ดีกรี ๐

๓. ทำไม propagation ถึง “ทำงานถูกต้องเอง” หลังจาก player.local_x, player.local_y = 300, 150 แล้วเรียก propagate_transform(player) เพียงครั้งเดียว ตำแหน่งในโลกของ Muzzle ก็อัปเดตถูกต้อง — ทั้งที่ไม่มีโค้ดตรงไหนแตะ muzzle.local_x หรือ muzzle.local_y เลย ทำไม?

เฉลย

เพราะการท่องรับประกันว่าจะเยี่ยมพ่อแม่ — และอัปเดต world_x/world_y ของมันเสร็จ — ก่อนที่จะเรียกซ้ำเข้าไปในลูกของพ่อแม่นั้นเสมอ ดังนั้นตำแหน่งในโลกของ Weapon จะถูกคำนวณใหม่จากตำแหน่งในโลก ใหม่ ของ Player แล้วตำแหน่งในโลกของ Muzzle ก็จะถูกคำนวณใหม่จากตำแหน่งในโลก ใหม่ ของ Weapon ต่อ มีแค่ออฟเซ็ตท้องถิ่นเท่านั้นที่คงที่ ส่วนค่าที่สะสมในโลกจะไหลลงไปตามเส้นทางเดียวกับที่การท่องเดินผ่าน

๔. ควอดทรี เทียบกับ ลิสต์แบบแบน โลกเปิดขนาดใหญ่มีเอนทิตี้ ๑๐,๐๐๐ ตัว ทำไมการหา “ทุกเอนทิตี้ที่อยู่ในระยะ ๕๐ หน่วยจากผู้เล่น” ด้วยควอดทรีถึงเร็วกว่าการวนลูปผ่านลิสต์แบบแบนทั้ง ๑๐,๐๐๐ ตัว?

เฉลย

ลิสต์แบบแบนต้องเช็กระยะทางแบบ O(n) — ทุกเอนทิตี้ ทุกที่ในโลก ไม่ว่าจะอยู่ไกลแค่ไหน ควอดทรีให้เราลงไปเช็กเฉพาะควอแดรนต์ที่ทับซ้อนกับพื้นที่ค้นหารัศมี ๕๐ หน่วยเท่านั้น ควอแดรนต์ไหนที่ไม่ทับซ้อนก็ข้ามไปได้เลย โดยไม่ต้องตรวจดูเอนทิตี้แม้แต่ตัวเดียวข้างในนั้น ต้นทุนจึงแปรผันตามจำนวนเอนทิตี้ที่อยู่ใกล้จุดนั้นในพื้นที่จริง ไม่ใช่ตามจำนวนเอนทิตี้ทั้งหมดในโลก

โจทย์ท้าทาย

ท้าทาย ๑: อย่าคำนวณใหม่สิ่งที่ไม่ได้ขยับ การเรียก propagate_transform กับทั้งต้นไม้ทุกเฟรมคือการเสียแรงเปล่าถ้า ๙๙% ของโหนดไม่ได้ขยับเลยตั้งแต่เฟรมก่อน ลองร่างแนวทางที่ข้ามการคำนวณซับทรีใหม่ เว้นแต่มีอะไรข้างในนั้นเปลี่ยนแปลงจริง ๆ

แนวทาง

ให้ทุกโหนดมีแฟล็ก dirty: bool เมื่อ local transform ของโหนดหนึ่งเปลี่ยน ให้ทำเครื่องหมาย dirty ทั้งโหนดนั้น และทายาททุกตัวของมัน (เพราะตำแหน่งในโลกของทายาทตอนนี้ขึ้นอยู่กับค่าเก่าที่อยู่สูงขึ้นไปในสาย) ในแต่ละเฟรม ให้ท่องต้นไม้แต่คำนวณ world transform ใหม่เฉพาะโหนดที่ dirty เท่านั้น ส่วนการเดินลงไปหาลูกยังทำเหมือนเดิมเสมอ เพราะบรรพบุรุษที่ dirty บังคับให้ซับทรีทั้งหมด dirty ไปด้วย พอคำนวณโหนดใหม่เสร็จก็ล้างแฟล็กทิ้ง นี่คือแนวคิดเดียวกับที่ Node2D/Node3D ของ Godot เองใช้ภายใน (บิต “transform dirty”) เพื่อเลี่ยงการคำนวณเมทริกซ์ซ้ำสำหรับส่วนของต้นไม้ที่ไม่ได้ขยับ

ท้าทาย ๒: การแทรกลงควอดทรี (quadtree insert) ลองร่างวิธีสร้าง insert(entity) สำหรับโหนดควอดทรีที่มีขอบเขต (x, y, w, h) และความจุ (เช่น ๔ เอนทิตี้ต่อโหนด ก่อนที่จะต้องแบ่งย่อย)

แนวทาง

class QuadNode:
    def __init__(self, x, y, w, h, capacity=4):
        self.bounds = (x, y, w, h)
        self.capacity = capacity
        self.entities = []
        self.children = None   # กลายเป็นลิสต์ของ QuadNode สี่ตัวหลังแบ่งย่อย

    def insert(self, entity):
        if not self._overlaps(entity, self.bounds):
            return False
        if self.children is None and len(self.entities) < self.capacity:
            self.entities.append(entity)
            return True
        if self.children is None:
            self._subdivide()
        return any(child.insert(entity) for child in self.children)

_subdivide() แบ่ง self.bounds ออกเป็นสี่ควอแดรนต์เท่า ๆ กัน แล้วสร้าง QuadNode ให้แต่ละอัน เอนทิตี้ที่มีอยู่เดิมสามารถแทรกใหม่ลงในลูกใหม่เหล่านี้ได้ การสืบค้น (เช่น “ทุกอย่างในรัศมี r จากจุด P”) จะเดินในต้นไม้เดียวกันนี้ โดยลงไปเฉพาะลูกที่ขอบเขตทับซ้อนกับวงกลมของการค้นหาเท่านั้น — เป็นกลเม็ด “ข้ามสิ่งที่ไม่ทับซ้อน” แบบเดียวกับที่ใช้อธิบายเรื่องการชนกันในย่อหน้าก่อนหน้านี้

เจาะลึกเพิ่มเติม

• MIT 6.006 Introduction to Algorithms — Binary Search Trees / AVL — เลกเชอร์เรื่อง BST และต้นไม้สมดุล
• Stanford CS161 — Design and Analysis of Algorithms — เนื้อหาต้นไม้ค้นหาและการวิเคราะห์
• CLRS (Cormen et al.), Introduction to Algorithms, บทที่ ๑๒ — Binary Search Trees และบทที่ ๑๓ — Red-Black Trees: การอธิบายเชิงลึกและรัดกุมที่สุด รวมพิสูจน์การหมุนแบบเต็มรูปแบบ
• Sedgewick & Wayne, Algorithms (ฉบับที่ ๔), บทที่ ๓.๒–๓.๓ — โค้ด Java ที่สะอาดสำหรับ insert/delete/traversal ของ BST ซึ่งต่อยอดตรงไปสู่ red-black BST ในบทเดียวกัน
• Weiss, Data Structures and Algorithm Analysis — การวิเคราะห์ความสูงของต้นไม้และกรณีการหมุนของ AVL อย่างรัดกุมด้วยสูตรคณิตศาสตร์
• Goodrich, Tamassia & Goldwasser, Data Structures and Algorithms in Python — โค้ด BST, AVL, และ splay tree แบบ Python ล้วน ที่อ่านคู่กับโค้ดในบทเรียนนี้ได้เลย
• VisuAlgo — Binary Search Tree — เครื่องมือแสดงภาพการทำงานของ BST แบบโต้ตอบ