Largest Independent Set ใน Binary Tree

Independent Set ใน Binary Tree คือ subset ของโหนดที่ไม่มี edge ใดๆ เชื่อมระหว่างโหนดใน subset นั้น (คือ ไม่มีโหนดใดเป็น parent/child ของอีกโหนดหนึ่งในเซต)

เป้าหมาย: หาขนาดของ Largest Independent Set (LIS)

ตัวอย่าง Input และ Output

Binary Tree:
        20
       /  \
      8    22
     / \    \
    4  12    25
      / \
     10 14

Output: Size of the Largest Independent Set is: 5
(ตัวอย่างเซต: {20, 4, 10, 14, 25} หรือ {8, 22, 4, 10, 14} เป็นต้น)

อัลกอริทึม Dynamic Programming on Tree

ฟังก์ชัน longSetSize(root)

แนวคิด: 2 กรณีสำหรับแต่ละโหนด

1. รวมโหนด root (Include root): ไม่สามารถรวมลูกของ root ได้ → รวม root + LIS ของ grandchild ทั้งหมด
2. ไม่รวมโหนด root (Exclude root): สามารถรวมลูกของ root ได้ → LIS ของ left child + LIS ของ right child

เลือกกรณีที่ให้ค่ามากกว่า

ขั้นตอน (Memoization):

1. ถ้า root = NULL → คืน 0
2. ถ้า root->setSize != 0 (คำนวณแล้ว) → คืน root->setSize
3. ถ้าเป็น leaf (ไม่มีลูก) → setSize = 1
4. Exclude root: setSizeEx = longSetSize(left) + longSetSize(right)
5. Include root: setSizeIn = 1 + LIS ของ grandchild ทั้ง 4 ตัว (ถ้ามี)
6. root->setSize = max(setSizeIn, setSizeEx)
7. คืน root->setSize

ตัวอย่างโค้ด C++

#include <iostream>
#include <algorithm>
using namespace std;

struct node {
    int data;
    int setSize;
    node *left, *right;
};

int longSetSize(node *root) {
    if (root == NULL) return 0;
    if (root->setSize != 0) return root->setSize;
    if (root->left == NULL && root->right == NULL)
        return (root->setSize = 1);

    // ไม่รวม root
    int setSizeEx = longSetSize(root->left) + longSetSize(root->right);

    // รวม root
    int setSizeIn = 1;
    if (root->left)
        setSizeIn += longSetSize(root->left->left) + longSetSize(root->left->right);
    if (root->right)
        setSizeIn += longSetSize(root->right->left) + longSetSize(root->right->right);

    root->setSize = max(setSizeIn, setSizeEx);
    return root->setSize;
}

node* getNode(int data) {
    node* newNode = new node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    newNode->setSize = 0;
    return newNode;
}

int main() {
    node *root = getNode(20);
    root->left = getNode(8);
    root->left->left = getNode(4);
    root->left->right = getNode(12);
    root->left->right->left = getNode(10);
    root->left->right->right = getNode(14);
    root->right = getNode(22);
    root->right->right = getNode(25);

    cout << "Size of the Largest Independent Set is: " 
         << longSetSize(root);
    return 0;
}

Output

Size of the Largest Independent Set is: 5

ความซับซ้อน

• Time: O(n) - แต่ละโหนดคำนวณ 1 ครั้ง
• Space: O(n) - เรียกซ้อน (recursion stack) + memoization