Hướng giải của Predecessor và Successor trong BST

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Để tìm predecessor và successor của một giá trị \(x\) trong BST, ta duyệt từ gốc xuống và cập nhật kết quả.

Các bước thực hiện:

  1. Xây dựng BST từ dãy đầu vào.
  2. Với mỗi truy vấn \(x\):
    • Khởi tạo \(pred = -1\), \(succ = -1\).
    • Duyệt từ gốc:
      • Nếu giá trị nút bằng \(x\): nếu có con trái, predecessor là giá trị lớn nhất ở con trái; nếu có con phải, successor là giá trị nhỏ nhất ở con phải.
      • Nếu giá trị nút lớn hơn \(x\): cập nhật \(succ\) và sang trái.
      • Nếu giá trị nút nhỏ hơn \(x\): cập nhật \(pred\) và sang phải.
  3. In kết quả, thay \(-1\) bằng \(NONE\).

Độ phức tạp: \(O((N + Q) \log N)\) trung bình.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int val) {
    if (!root) return new Node(val);
    if (val < root->val) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

int findMax(Node* root) {
    while (root->right) root = root->right;
    return root->val;
}

int findMin(Node* root) {
    while (root->left) root = root->left;
    return root->val;
}

void findPredSucc(Node* root, int x, int& pred, int& succ) {
    while (root) {
        if (root->val == x) {
            if (root->left) pred = findMax(root->left);
            if (root->right) succ = findMin(root->right);
            return;
        }
        if (root->val > x) {
            succ = root->val;
            root = root->left;
        } else {
            pred = root->val;
            root = root->right;
        }
    }
}

void printAns(int val) {
    if (val == -1) cout << "NONE";
    else cout << val;
}

int main() {
    int N, Q;
    cin >> N >> Q;
    Node* root = nullptr;
    for (int i = 0; i < N; ++i) {
        int a; cin >> a;
        root = insert(root, a);
    }
    while (Q--) {
        int x; cin >> x;
        int pred = -1, succ = -1;
        findPredSucc(root, x, pred, succ);
        printAns(pred); cout << " "; printAns(succ); cout << "\n";
    }
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.