Bài toán tập độc lập lớn nhất trên cây nhị phân

Tập độc lập (Independent Set) của cây nhị phân là tập các nút sao cho không có hai nút nào kề nhau (không có cạnh nối trực tiếp). Tìm kích thước tập độc lập lớn nhất.

Sử dụng quy hoạch động trên cây: với mỗi nút, xét hai trường hợp — chọn nút đó (thì không chọn con) hoặc không chọn (thì có thể chọn con).

Đầu vào và Đầu ra

Đầu vào: Cây nhị phân:
       20
      /  \
     8    22
    / \     \
   4  12     25
     / \
    10 14

Đầu ra: Size of Largest Independent Set = 5
(Tập: {20, 4, 10, 14, 25} hoặc {8, 22, 10, 14, 4}...)

Thuật toán

Hàm longSetSize(root) trả về kích thước LIS của cây con gốc root.

• Nếu root == NULL → 0.
• Nếu đã tính (memorization) → trả về root->setSize.
• Nếu lá → 1.
• setSizeEx (không chọn root) = longSetSize(left) + longSetSize(right).
• setSizeIn (chọn root) = 1 + longSetSize(left->left) + longSetSize(left->right) + longSetSize(right->left) + longSetSize(right->right).
• Lưu max(setSizeIn, setSizeEx) vào root->setSize và trả về.

Ví dụ C++

#include <iostream>
using namespace std;

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

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

    int setSizeEx = longSetSize(root->left) + longSetSize(root->right);
    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* n = new node;
    n->data = data; n->left = n->right = NULL; n->setSize = 0;
    return n;
}

int main() {
    node *root = getNode(20);
    root->left = getNode(8); root->right = getNode(22);
    root->left->left = getNode(4); root->left->right = getNode(12);
    root->left->right->left = getNode(10); root->left->right->right = getNode(14);
    root->right->right = getNode(25);
    cout << "Size of the Largest Independent Set is: " << longSetSize(root);
}

Kết quả

Size of the Largest Independent Set is: 5