Cây K-D là một cấu trúc dữ liệu có khả năng xử lý các vấn đề trong không gian đa chiều. Nó được tổ chức dưới dạng một cây nhị phân tìm kiếm, chia nhỏ không gian nhiều chiều thành các phần và đảm bảo rằng tọa độ của nút nào đó trên một trục nhất định sẽ lớn hơn tất cả các nút bên trái và nhỏ hơn tất cả các nút bên phải.

Xây dựng Cây K-D

Để xây dựng cây K-D với số chiều k, tại mỗi tầng i, chúng ta chọn chiều thứ (i % k) để sắp xếp các điểm. Sử dụng ý tưởng của thuật toán quickselect, chúng ta có thể tìm ra phần tử ở giữa (median) trong khoảng thời gian logarit. Phần tử này sẽ trở thành gốc của cây tại phân đoạn hiện tại, sau đó phân đoạn sẽ được chia làm hai và tiếp tục xây dựng đệ quy cho từng nhánh con.

Dưới đây là một ví dụ về cách xây dựng cây K-D:

// Cấu trúc cho cây K-D hai chiều
struct Node {
    int min[2], max[2], coord[2];
    int leftChild, rightChild;
    Node() : leftChild(0), rightChild(0) {
        min[0] = min[1] = INT_MAX;
        max[0] = max[1] = INT_MIN;
    }
};

Node nodes[MAX_NODES];

bool compareByDimension(int idx, const Node &a, const Node &b) {
    return a.coord[idx] < b.coord[idx];
}

void buildTree(int L, int R, int depth, int &rootIndex) {
    if (L > R) return;
    int mid = (L + R) / 2;
    rootIndex = mid;
    int dim = depth % 2; // Chọn chiều dựa trên độ sâu
    std::nth_element(nodes + L, nodes + mid, nodes + R + 1,
                     [dim](const Node &a, const Node &b) {
                         return a.coord[dim] < b.coord[dim];
                     });
    if (mid - 1 >= L) buildTree(L, mid - 1, depth + 1, nodes[mid].leftChild);
    if (mid + 1 <= R) buildTree(mid + 1, R, depth + 1, nodes[mid].rightChild);
    updateBounds(mid); // Cập nhật ranh giới tối thiểu và tối đa
}

Độ phức tạp của Cây K-D

Cây K-D thực chất là một phương pháp tối ưu hóa thô, thường kết hợp với kỹ thuật cắt cành. Mặc dù vậy, độ phức tạp trung bình của nó khi xử lý dữ liệu ngẫu nhiên là O(n^(1 + (1 - 1/k))), với k là số chiều.

Ví dụ ứng dụng Cây K-D

Bài toán P4475: Vương quốc Sô-cô-la

Trong bài toán này, cần xây dựng một hệ trục tọa độ với x và y là trục hoành và tung tương ứng. Đối với mỗi truy vấn, phạm vi thỏa mãn yêu cầu là liên tục, cụ thể là một nửa mặt phẳng nằm bên trái của một đường thẳng. Chúng ta sử dụng cây K-D để kiểm tra từng nút từ gốc, nếu toàn bộ hoặc không có điểm nào trong phạm vi đáp ứng điều kiện, chúng ta sẽ cắt bỏ nhánh đó.

Một phần mã nguồn:

void updateNode(int index) {
    int l = nodes[index].leftChild, r = nodes[index].rightChild;
    nodes[index].sum = nodes[l].sum + nodes[r].sum + nodes[index].value;
    for (int d = 0; d < 2; ++d) {
        nodes[index].min[d] = nodes[index].max[d] = nodes[index].coord[d];
        if (l) {
            nodes[index].min[d] = std::min(nodes[l].min[d], nodes[index].min[d]);
            nodes[index].max[d] = std::max(nodes[l].max[d], nodes[index].max[d]);
        }
        if (r) {
            nodes[index].min[d] = std::min(nodes[r].min[d], nodes[index].min[d]);
            nodes[index].max[d] = std::max(nodes[r].max[d], nodes[index].max[d]);
        }
    }
}

bool checkCondition(int x, int y) {
    return A * x + B * y < C;
}

int queryTree(int nodeIndex) {
    if (!nodeIndex) return 0;
    int count = 0;
    count += checkCondition(nodes[nodeIndex].min[0], nodes[nodeIndex].min[1]);
    count += checkCondition(nodes[nodeIndex].min[0], nodes[nodeIndex].max[1]);
    count += checkCondition(nodes[nodeIndex].max[0], nodes[nodeIndex].min[1]);
    count += checkCondition(nodes[nodeIndex].max[0], nodes[nodeIndex].max[1]);
    if (count == 4) return nodes[nodeIndex].sum;
    if (!count) return 0;
    int result = 0;
    if (checkCondition(nodes[nodeIndex].coord[0], nodes[nodeIndex].coord[1])) 
        result += nodes[nodeIndex].value;
    result += queryTree(nodes[nodeIndex].leftChild);
    result += queryTree(nodes[nodeIndex].rightChild);
    return result;
}

Kết luận

Cây K-D là một công cụ mạnh mẽ trong việc xử lý các vấn đề không gian đa chiều, đặc biệt hữu ích khi kết hợp với các kỹ thuật cắt cành để giảm thiểu số lượng phép so sánh.