Tree & Binary Search Tree

Tree คือ abstract data type ที่เก็บข้อมูลแบบลำดับชั้น เป็นเซตของ node ที่มีความสัมพันธ์แบบ parent–child

นิยามและคำศัพท์

• node (หรือ vertex) เก็บ element
• node บนสุดเรียกว่า root
• ทุก node มี parent 1 ตัว ยกเว้น root
• ทุก node มีลูก 0 ตัวขึ้นไป
• node ที่ไม่มีลูกเรียกว่า leaf
• node ที่มี parent เดียวกันเรียกว่า sibling

Depth และ Height

การใช้งานจริง

• Family tree — ผังตระกูล
• Organization chart — ผังองค์กร
• Directory tree — โครงสร้างโฟลเดอร์ในระบบไฟล์
• HTML DOM — แท็กซ้อนแท็ก
• Game tactic — ต้นไม้เส้นทางการเดินของตัวละคร

Binary Tree และชนิดต่าง ๆ

Binary Tree = ต้นไม้ที่ทุก node มีลูกได้ไม่เกิน 2 ตัว (left, right)

height k  →  จำนวน node มากสุด = 2^(k+1) - 1

height 1 → 3 node
height 2 → 7 node
height 3 → 15 node

โครงสร้าง node ในโค้ด

public class BinaryTreeNode {
    int element;
    BinaryTreeNode left;
    BinaryTreeNode right;

    public BinaryTreeNode(int data){
        this.element = data;
        this.left = null;
        this.right = null;
    }
}

สร้างต้นไม้:

BinaryTreeNode root = new BinaryTreeNode(1);
root.left  = new BinaryTreeNode(2);
root.right = new BinaryTreeNode(3);
root.left.left  = new BinaryTreeNode(4);
root.left.right = new BinaryTreeNode(5);

DFS — Depth-First Search

ลงลึกสุดก่อน แล้วค่อยถอยกลับ (backtrack) ใช้ recursion (เบื้องหลังคือ stack)

public void printPreOrder(BinaryTreeNode x)
{
    if(x != null)
    {
        System.out.print(x.element + " ");
        printPreOrder(x.left);
        printPreOrder(x.right);
    }
}

BFS — Breadth-First Search

ไล่ทีละชั้น ซ้ายไปขวา (level order) ใช้ queue

ผลลัพธ์จากต้นไม้ข้างบน:  1, 8, 6, 3, 4, 2, 7, 9, 5, 0

1. ใส่ root ลง queue
2. dequeue มา 1 ตัว พิมพ์ค่า
3. enqueue ลูกซ้ายและลูกขวาของมัน
4. ทำซ้ำจนกว่า queue จะว่าง

Binary Search Tree (BST)

ปัญหาค่าซ้ำ

ถ้าใส่ค่าซ้ำเป็น node ใหม่ ค่าที่เท่ากันจะกระจายอยู่คนละชั้น ทำให้จัดการยาก ทางแก้ที่นิยมคือไม่สร้าง node ใหม่ แต่เก็บตัวนับจำนวนครั้งไว้ใน node เดิม

ทำไม BST เป็น O(h)

log₂ n  ≤  h  ≤  n

ต้นไม้เอียง 1-2-3-4-5-6 หา 6  →  ต้องไล่ทุก node = 6 ครั้ง

ต้นไม้ balanced หา 3:
   3 < 4 ไปซ้าย
   3 > 2 ไปขวา
   เจอ 3        → ใช้ 3 ครั้ง = height ของต้นไม้

ความสูงของ complete binary tree:

n = 1  → h = 0        log₂1 = 0
n = 3  → h = 1        log₂3 ≈ 1
n = 7  → h = 2        log₂7 ≈ 2
n = 15 → h = 3        log₂15 ≈ 3

BST: Search

public boolean search(int element) {
    BinaryTreeNode current = root;
    while (current != null) {
        if (current.element == element) {
            return true;
        } else if (current.element > element) {
            current = current.left;
        } else if (current.element < element) {
            current = current.right;
        }
    }
    return false;
}

แนวคิดเดียวกับ binary search: เริ่มที่ root → น้อยกว่าไปซ้าย มากกว่าไปขวา → ทำซ้ำจนเจอหรือชน null

BST: Insert

เดินเหมือน search ถ้าเจอค่าเดิมก็ไม่ทำอะไร ถ้าไม่เจอให้แทรกที่ตำแหน่งสุดท้ายที่เดินถึง

3 < 6 : ไปซ้าย
3 > 2 : ไปขวา
3 < 4 : ไปซ้าย
node 4 ไม่มีลูกซ้าย → แขวน 3 ไว้ตรงนั้น

public void insert(int element) {
    BinaryTreeNode current = root;
    while (current != null) {
        if (current.element == element) {
            break;
        } else if (current.element > element) {
            if (current.left != null) {
                current = current.left;
            } else {
                current.left = new BinaryTreeNode(element);
                break;
            }
        } else {
            if (current.right != null) {
                current = current.right;
            } else {
                current.right = new BinaryTreeNode(element);
                break;
            }
        }
    }
}

BST: Delete ทั้ง 3 กรณี

ต้นไม้:      7
          /     \
         4        8
       /   \     /
      2     5   ...
     / \     \
    1   3     6

ลบ 4:
  ค่าน้อยสุดของ subtree ขวาของ 4 = 5
  1. เอา 5 มาแทนค่าใน node 4
  2. ลบ node 5 เดิม (ซึ่งกลายเป็นกรณีมีลูก 1 ตัว → ดึง 6 ขึ้นมา)

BFS หาเส้นทางสั้นสุด

โจทย์: หาเส้นทางสั้นสุดจาก S ไป G เดินได้ทีละช่อง ทิศทางพิจารณาตามลำดับ ขวา ล่าง ซ้าย บน (ช่องสีเทาเดินไม่ได้)

1. ไล่ขยายทีละชั้นด้วย BFS ให้เลขกำกับลำดับที่เจอแต่ละช่อง
2. เมื่อถึง G ให้ย้อนกลับตาม parent เก็บลง stack — ได้ 7, 4, 2, 1
3. Pop stack ออกมาจะได้เส้นทางตามลำดับจริง: 1, 2, 4, 7