Hướng giải của Tìm kiếm 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

Bài toán yêu cầu kiểm tra sự tồn tại của một giá trị trong BST. Ta xây dựng cây BST từ dãy đầu vào, sau đó với mỗi truy vấn, ta thực hiện thao tác tìm kiếm trên BST.

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

  1. Định nghĩa cấu trúc nút của BST gồm giá trị, con trái và con phải.
  2. Xây dựng BST bằng cách chèn lần lượt từng phần tử của dãy.
  3. Với mỗi truy vấn \(x\), duyệt cây: nếu \(x\) nhỏ hơn giá trị nút hiện tại, qua trái; nếu lớn hơn, qua phải; nếu bằng, trả về \(true\).
  4. In ra kết quả tương ứng.

Độ phức tạp: \(O((N + Q) \log N)\) với cây cân bằng, tuy nhiên với BST thông thường có thể là \(O(N^2)\) trong trường hợp xấu nhất.

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;
}

bool search(Node* root, int x) {
    if (!root) return false;
    if (root->val == x) return true;
    if (x < root->val) return search(root->left, x);
    return search(root->right, x);
}

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;
        cout << (search(root, x) ? "YES" : "NO") << "\n";
    }
    return 0;
}

Nhận xét

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