Chương trình C++ triển khai cây khoảng (Interval Tree)

Cây khoảng (Interval Tree) là một cấu trúc dữ liệu cây có thứ tự dùng để lưu trữ các khoảng. Nó cho phép tìm kiếm hiệu quả tất cả các khoảng chồng lấp với một khoảng hoặc điểm cho trước. Dưới đây là chương trình C++ triển khai cây khoảng.

Thuật toán

Bắt đầu
  Hàm insert() dùng để chèn nút mới vào cây:
    Nếu cây rỗng, nút mới trở thành gốc.
    Lấy giá trị low của khoảng tại gốc.
    Nếu low của gốc nhỏ hơn, khoảng mới đi vào cây con trái.
    Ngược lại, nút mới đi vào cây con phải.
    Nếu cần, cập nhật giá trị max của tổ tiên này.
Kết thúc

Bắt đầu
  Hàm intervalFind() tìm kiếm khoảng i cho trước trong cây khoảng:
    Nếu cây rỗng trả về null.
    Nếu khoảng cho trước chồng lấp với gốc
      Trả về gốc->i
    Nếu con trái của gốc tồn tại và max của con trái
      lớn hơn hoặc bằng khoảng cho trước, thì i có thể
      chồng lấp với khoảng trong cây con trái
    Ngược lại
      khoảng chỉ có thể chồng lấp với cây con phải.
Kết thúc

Mã ví dụ

#include <iostream>
using namespace std;

struct Interval {
    int l, h;
};

struct ITNod {
    Interval *i;
    int max;
    ITNod *l, *r;
};

ITNod * newNode(Interval i) {
    ITNod *t = new ITNod;
    t->i = new Interval(i);
    t->max = i.h;
    t->l = t->r = NULL;
    return t;
}

ITNod *insert(ITNod *r, Interval i) {
    if (r == NULL)
        return newNode(i);
    int l = r->i->l;
    if (i.l < l)
        r->l = insert(r->l, i);
    else
        r->r = insert(r->r, i);
    if (r->max < i.h)
        r->max = i.h;
    return r;
}

bool Overlap(Interval i1, Interval i2) {
    if (i1.l <= i2.h && i2.l <= i1.h)
        return true;
    return false;
}

Interval *intervalFind(ITNod *root, Interval i) {
    if (root == NULL)
        return NULL;
    if (Overlap(*(root->i), i))
        return root->i;
    if (root->l != NULL && root->l->max >= i.l)
        return intervalFind(root->l, i);
    return intervalFind(root->r, i);
}

void inorder(ITNod *root) {
    if (root == NULL)
        return;
    inorder(root->l);
    cout << "[" << root->i->l << ", " << root->i->h << "]" << " max = " << root->max << endl;
    inorder(root->r);
}

int main(int argc, char **argv) {
    Interval ints[] = { { 5, 20 }, { 6, 7 }, { 3, 4 }, { 67, 26 }, { 3, 4 } };
    int n = sizeof(ints) / sizeof(ints[0]);
    ITNod *root = NULL;
    for (int i = 0; i < n; i++)
        root = insert(root, ints[i]);
    cout << "Duyệt in-order của cây khoảng đã xây dựng:\n";
    inorder(root);
    Interval x = { 7, 6 };
    cout << "\nTìm kiếm khoảng [" << x.l << "," << x.h << "]";
    Interval *res = intervalFind(root, x);
    if (res == NULL)
        cout << "\nKhông có khoảng chồng lấp";
    else
        cout << "\nChồng lấp với [" << res->l << ", " << res->h << "]";
    return 0;
}

Kết quả đầu ra

Duyệt in-order của cây khoảng đã xây dựng:
[3, 4] max = 4
[3, 4] max = 4
[5, 20] max = 26
[6, 7] max = 26
[67, 26] max = 26
Tìm kiếm khoảng [7,6]
Chồng lấp với [5, 20]