Bài 30: Binary Search Tree (BST) - Cây Tìm Kiếm Nhị Phân¶

Tác giả: FPTOJ Team
Nội dung tham khảo từ: CP-Algorithms, GeeksforGeeks - BST

Bản chất vấn đề¶

Cho một tập hợp số, cần hỗ trợ các thao tác: thêm, tìm kiếm, xóa, tìm min/max, tìm cận dưới (lower_bound).

Cách 1: Mảng — thêm \(O(1)\), tìm \(O(N)\). Chậm khi tập lớn.

Cách 2: set / map (Red-Black Tree) — tất cả \(O(\log N)\). Tốt, nhưng là "hộp đen", không hiểu cấu trúc bên trong.

Cách 3: BST — tất cả \(O(\log N)\) trung bình, và bạn hiểu rõ tại sao.

Binary Search Tree là cây nhị phân mà tại mỗi nút, mọi giá trị ở cây con trái đều nhỏ hơn nút đó, mọi giá trị ở cây con phải đều lớn hơn. Tính chất này cho phép tìm kiếm theo kiểu "chia đôi" y hệt tìm kiếm nhị phân trên mảng.

graph TD
    A((8)) --> B((3))
    A --> C((10))
    B --> D((1))
    B --> E((6))
    C --> F[NULL]
    C --> G((14))
    E --> H((4))
    E --> I((7))
    G --> J((13))
    G --> K[NULL]

Với cây trên, tìm số 7 chỉ mất 4 bước: tại 8 (7 nhỏ hơn, đi trái) → tại 3 (7 lớn hơn, đi phải) → tại 6 (7 lớn hơn, đi phải) → tại 7 (tìm thấy). So với duyệt mảng mất 8 bước, BST khai thác triệt để tính chất thứ tự để loại bỏ một nửa ứng viên mỗi bước.

Tư duy cốt lõi¶

Thao tác 1: Tìm kiếm (Search)¶

Tại mỗi nút, so sánh giá trị cần tìm \(v\) với \(node \to val\):

\(v < node \to val\) → đi trái
\(v > node \to val\) → đi phải
\(v = node \to val\) → tìm thấy

Nếu đi đến NULL thì giá trị không tồn tại trong cây.

graph TD
    A(("8 → đi trái")) --> B(("3 → đi phải"))
    B --> C(("6 → đi phải"))
    C --> D(("7 → TÌM THẤY"))

Thao tác 2: Chèn (Insert)¶

Đi từ gốc, so sánh \(v\) với từng nút để tìm vị trí lá thích hợp. Khi đến NULL, tạo nút mới tại đó.

graph TD
    A((8)) --> B((3))
    A --> C((10))
    B --> D((1))
    B --> E((6))
    E --> F((4))
    E --> G((7))
    F --> H(("5 ← mới"))

Quy trình: tại 8 (5 nhỏ hơn, trái) → tại 3 (5 lớn hơn, phải) → tại 6 (5 nhỏ hơn, trái) → tại 4 (5 lớn hơn, phải) → tạo nút 5.

Thao tác 3: Xóa (Delete)¶

Xóa phức tạp hơn vì phải đảm bảo tính chất BST sau khi xóa. Có 3 trường hợp:

Trường hợp 1: Nút lá (0 con) — xóa trực tiếp, trả về NULL.

Trường hợp 2: Có 1 con — thay nút bằng con duy nhất.

Trường hợp 3: Có 2 con — tìm nút kế nhiệm (min bên phải) hoặc tiền nhiệm (max bên trái), sao chép giá trị vào nút cần xóa, rồi xóa nút kế nhiệm/tiền nhiệm ở vị trí cũ.

Minh họa xóa nút gốc 8 (có 2 con): tìm min bên phải là 10, thay 8 bằng 10, rồi xóa 10 ở cây con phải.

graph TD
    A(("10 ← thay thế")) --> B((3))
    A --> C((14))
    B --> D[NULL]
    B --> E((6))
    E --> F((4))
    E --> G((7))
    C --> H((13))
    C --> I[NULL]

Thao tác 4: Tìm Min / Max¶

Min: đi liên tục sang trái từ gốc
Max: đi liên tục sang phải từ gốc

Với cây ở trên: min là 1 (8→3→1), max là 14 (8→10→14).

Duyệt Inorder¶

Duyệt theo thứ tự Trái → Gốc → Phải trên BST luôn cho ra dãy tăng dần. Đây là tính chất quan trọng nhất của BST, xuất phát trực tiếp từ tính chất "trái < gốc < phải".

Phân tích tính đúng đắn¶

Tại sao BST cho phép tìm kiếm nhị phân?¶

Mọi nút \(u\) trong BST đều thoả mãn: tất cả giá trị trong cây con trái của \(u\) nhỏ hơn \(u \to val\), tất cả giá trị trong cây con phải lớn hơn \(u \to val\). Khi so sánh \(v\) với \(u \to val\):

Nếu \(v < u \to val\), ta loại bỏ toàn bộ cây con phải (tất cả đều lớn hơn \(u \to val\), do đó lớn hơn \(v\)).
Nếu \(v > u \to val\), ta loại bỏ toàn bộ cây con trái.

Mỗi bước loại bỏ ít nhất một nửa số nút còn lại, nên số bước tối đa là chiều cao \(h\) của cây.

Tại sao xóa đúng khi dùng kế nhiệm?¶

Nút kế nhiệm (min bên phải) là nút nhỏ nhất trong cây con phải, thoả mãn:

Lớn hơn mọi nút ở cây con trái (đảm bảo tính chất BST khi thay thế)
Là nút lá hoặc chỉ có con phải (dễ xóa, thuộc trường hợp 1 hoặc 2)

Sao chép giá trị kế nhiệm vào nút cần xóa không vi phạm tính chất BST. Sau đó xoá nút kế nhiệm ở vị trí cũ — thao tác này quy về trường hợp 0 hoặc 1 con, luôn đúng đệ quy.

Tại sao inorder cho dãy tăng dần?¶

Chứng minh bằng quy nạp: giả sử cây con trái cho dãy tăng dần \(L\), cây con phải cho dãy tăng dần \(R\). Theo tính chất BST, mọi phần tử trong \(L\) nhỏ hơn gốc, mọi phần tử trong \(R\) lớn hơn gốc. Duyệt Trái → Gốc → Phải tạo dãy \(L\), gốc, \(R\) — đúng thứ tự tăng dần.

Đánh giá độ phức tạp¶

Độ phức tạp thời gian¶

Gọi \(h\) là chiều cao cây, \(N\) là số nút.

Thao tác	Trung bình	Worst case
Tìm kiếm	\(O(h) = O(\log N)\)	\(O(N)\)
Chèn	\(O(h) = O(\log N)\)	\(O(N)\)
Xóa	\(O(h) = O(\log N)\)	\(O(N)\)
Min/Max	\(O(h) = O(\log N)\)	\(O(N)\)
Duyệt inorder	\(O(N)\)	\(O(N)\)

Worst case xảy ra khi BST bị méo (chèn dãy tăng/giảm dần), cây trở thành linked list, \(h = N\).

graph TD
    A((1)) --> B[NULL]
    A --> C((2))
    C --> D[NULL]
    C --> E((3))
    E --> F[NULL]
    E --> G((4))
    G --> H[NULL]
    G --> I((5))

Chèn 1, 2, 3, 4, 5 vào BST rỗng tạo cây nghiêng hoàn toàn — chiều cao \(N = 5\), mọi thao tác đều \(O(N)\).

Độ phức tạp bộ nhớ¶

Cấu trúc: \(O(N)\) cho \(N\) nút
Đệ quy: \(O(h)\) stack frame (worst case \(O(N)\))

BST tự cân bằng¶

Các biến thể giữ \(h = O(\log N)\) luôn đúng:

Cây	Chiều cao đảm bảo	Cơ chế
AVL Tree	\(h \leq 1.44 \log_2 N\)	Chênh lệch chiều cao 2 con \(\leq 1\)
Red-Black Tree	\(h \leq 2 \log_2(N+1)\)	Tô màu đỏ-đen, đảm bảo cân bằng
B-Tree	\(O(\log N)\)	Mỗi nút nhiều khoá, dùng trong database

Code hoàn chỉnh¶

C++Python

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

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

struct BST {
    Node* root = nullptr; // Bước 0: cây rỗng, gốc = NULL

    Node* insert(Node* node, int val) {
        if (node == nullptr) return new Node(val); // Bước 1: tới chỗ trống -> tạo nút mới
        if (val < node->val) // Bước 2: nhỏ hơn -> rẽ trái
            node->left = insert(node->left, val);
        else if (val > node->val) // Bước 3: lớn hơn -> rẽ phải (trùng thì bỏ qua)
            node->right = insert(node->right, val);
        return node; // Bước 4: trả nút hiện tại để cha nối lại
    }

    void insert(int val) { root = insert(root, val); }

    bool search(Node* node, int val) {
        if (node == nullptr) return false; // Bước 1: rơi khỏi lá -> không có
        if (val == node->val) return true; // Bước 2: khớp -> tìm thấy
        if (val < node->val) return search(node->left, val); // Bước 3: nhỏ -> sang trái
        return search(node->right, val); // Bước 4: lớn -> sang phải
    }

    bool search(int val) { return search(root, val); }

    Node* findMin(Node* node) {
        while (node->left != nullptr) // Bước 1: min = đi trái hết cỡ
            node = node->left;
        return node;
    }

    Node* erase(Node* node, int val) {
        if (node == nullptr) return nullptr; // Bước 1: không tìm thấy -> xong
        if (val < node->val) // Bước 2: nhỏ -> xóa bên trái
            node->left = erase(node->left, val);
        else if (val > node->val) // Bước 3: lớn -> xóa bên phải
            node->right = erase(node->right, val);
        else { // Bước 4: tìm thấy nút cần xóa
            if (node->left == nullptr) { // TH1: 0 hoặc 1 con phải -> thay bằng con phải
                Node* temp = node->right;
                delete node;
                return temp;
            }
            if (node->right == nullptr) { // TH2: chỉ có con trái -> thay bằng con trái
                Node* temp = node->left;
                delete node;
                return temp;
            }
            // TH3: 2 con -> copy kế nhiệm (min phải) rồi xóa kế nhiệm ở dưới
            Node* successor = findMin(node->right);
            node->val = successor->val;
            node->right = erase(node->right, successor->val);
        }
        return node;
    }

    void erase(int val) { root = erase(root, val); }

    void inorder(Node* node) {
        if (node == nullptr) return; // Bước 1: cây rỗng -> dừng
        inorder(node->left); // Bước 2: duyệt trái
        cout << node->val << " "; // Bước 3: in gốc
        inorder(node->right); // Bước 4: duyệt phải (ra dãy tăng dần)
    }

    void print() { inorder(root); cout << endl; }
};

int main() {
    BST tree;
    tree.insert(8);
    tree.insert(3);
    tree.insert(10);
    tree.insert(1);
    tree.insert(6);
    tree.insert(14);
    tree.insert(4);
    tree.insert(7);
    tree.insert(13);

    tree.print();             // 1 3 4 6 7 8 10 13 14
    cout << tree.search(6);   // 1
    cout << tree.search(5);   // 0

    tree.erase(8);
    tree.print();             // 1 3 4 6 7 10 13 14
}

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if node is None:
            return Node(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if node is None:
            return False
        if val == node.val:
            return True
        if val < node.val:
            return self._search(node.left, val)
        return self._search(node.right, val)

    def find_min(self, node):
        while node.left:
            node = node.left
        return node

    def erase(self, val):
        self.root = self._erase(self.root, val)

    def _erase(self, node, val):
        if node is None:
            return None
        if val < node.val:
            node.left = self._erase(node.left, val)
        elif val > node.val:
            node.right = self._erase(node.right, val)
        else:
            if node.left is None:
                return node.right
            if node.right is None:
                return node.left
            successor = self.find_min(node.right)
            node.val = successor.val
            node.right = self._erase(node.right, successor.val)
        return node

    def inorder(self, node=None, result=None):
        if result is None:
            result = []
        if node is None:
            return result
        self.inorder(node.left, result)
        result.append(node.val)
        self.inorder(node.right, result)
        return result

tree = BST()
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    tree.insert(v)

print(tree.inorder())    # [1, 3, 4, 6, 7, 8, 10, 13, 14]
print(tree.search(6))    # True
print(tree.search(5))    # False

tree.erase(8)
print(tree.inorder())    # [1, 3, 4, 6, 7, 10, 13, 14]

Trace chèn 5 số: 8, 3, 10, 1, 6¶

Bước	Chèn	Đường so sánh	Cây sau khi chèn
1	8	Gốc rỗng → 8 làm gốc	`8`
2	3	3 < 8 → trái của 8	`8 trái 3`
3	10	10 > 8 → phải của 8	`8 trái 3, phải 10`
4	1	1 < 8 → trái; 1 < 3 → trái của 3	`3 trái 1`
5	6	6 < 8 → trái; 6 > 3 → phải của 3	`3 phải 6`

Inorder sau 5 lần chèn: 1 3 6 8 10 (tăng dần).

Ứng dụng¶

Duyệt khoảng (Range Query)¶

Tìm tất cả phần tử trong khoảng \([L, R]\) trên BST, khai thác tính chất thứ tự để bỏ qua nhánh không cần thiết.

void rangeQuery(Node* node, int L, int R) {
    if (node == nullptr) return;
    if (L < node->val) rangeQuery(node->left, L, R);
    if (L <= node->val && node->val <= R)
        cout << node->val << " ";
    if (R > node->val) rangeQuery(node->right, L, R);
}

Độ phức tạp: \(O(k + h)\) với \(k\) là số phần tử trong khoảng, \(h\) là chiều cao cây.

Kiểm tra cây có phải BST¶

Dùng kỹ thuật truyền khoảng hợp lệ \([minVal, maxVal]\) khi duyệt đệ quy.

bool isBST(Node* node, long long minVal, long long maxVal) {
    if (node == nullptr) return true;
    if (node->val <= minVal || node->val >= maxVal) return false;
    return isBST(node->left, minVal, node->val) &&
           isBST(node->right, node->val, maxVal);
}

// Gọi: isBST(root, LLONG_MIN, LLONG_MAX)

BST so với Heap¶

Tiêu chí	BST	Heap
Tính chất	trái < gốc < phải	gốc \(\geq\) con (max-heap)
Tìm kiếm	\(O(\log N)\)	\(O(N)\)
Duyệt inorder	Tăng dần	Không có ý nghĩa
Ứng dụng	`set`, `map`	Priority Queue

Lưu ý và cạm bẫy¶

1. BST bị méo → thoái hoá O(N)¶

Chèn dãy tăng/giảm dần → cây nghiêng, thoái hoá thành linked list \(O(N)\). Trong thi đấu, dùng set / map (C++) đã cài Red-Black Tree sẵn thay vì tự cài BST thường.

2. Đệ quy quá sâu gây tràn stack¶

SAI: dùng đệ quy insert/search/erase trên cây méo \(N = 10^5\) → sâu \(10^5\) khung stack → crash.

// SAI: cây méo 1->2->3...->100000, gọi insert đệ quy sâu 100000
tree.insert(100001); // Stack overflow!

ĐÚNG: viết vòng lặp while cho insert/search, hoặc dùng cây tự cân bằng (std::set).

// ĐÚNG: chèn bằng vòng lặp, tốn O(1) bộ nhớ phụ
Node* cur = root, *par = nullptr;
while (cur) { par = cur; cur = (val < cur->val) ? cur->left : cur->right; }

3. Xử lý khóa trùng¶

SAI: để nhánh else chèn trùng sang phải → cây phình, search/erase sai ngữ nghĩa đếm.

// SAI: trùng vẫn tạo nút mới
if (val < node->val) node->left = insert(node->left, val);
else node->right = insert(node->right, val); // val == node->val cũng rẽ phải!

ĐÚNG: bỏ qua trùng, hoặc thêm trường cnt nếu cần đếm tần suất.

// ĐÚNG: trùng thì tăng bộ đếm, không tạo nút
if (val == node->val) { node->cnt++; return node; }

4. Kiểm tra BST: dùng `<=` vs `<` sai¶

SAI: chỉ kiểm tra con trực tiếp, hoặc dùng sai biên khi cho phép/không cho phép trùng.

// SAI: chỉ so với cha trực tiếp -> bỏ lọt cháu vi phạm ở xa
if (node->left && node->left->val > node->val) return false;

ĐÚNG: truyền khoảng (minVal, maxVal), cây không trùng dùng <=/>= để loại biên.

// ĐÚNG: mọi nút trái phải nằm gọn trong (minVal, maxVal)
if (node->val <= minVal || node->val >= maxVal) return false;
return isBST(node->left, minVal, node->val) &&
       isBST(node->right, node->val, maxVal);

Bài tập luyện tập (FPTOJ)¶

Bài	Nền tảng	Độ khó	Kiểu bài tập (Bản chất)
`bst-search`	Tìm kiếm trong BST	⭐	BST - tìm kiếm
`bst-insert`	Chèn vào BST	⭐	BST - chèn
`bst-delete`	Xoá nút khỏi BST	⭐⭐⭐	BST - xóa
`bst-validate`	Kiểm tra BST hợp lệ	⭐⭐	BST - kiểm tra
`bst-kth-min`	Phần tử nhỏ thứ K trong BST	⭐⭐	BST - inorder
`bst-lca`	Tổ tiên chung gần nhất trong BST	⭐⭐	BST - LCA
`bst-range`	Đếm số nút trong khoảng	⭐⭐	BST - range query
`bst-inorder`	Duyệt inorder của BST	⭐	BST - duyệt
`bst-pred-succ`	Predecessor và Successor trong BST	⭐⭐	BST - cận
`bst-balance`	Kiểm tra BST cân bằng	⭐⭐⭐	BST - cân bằng

Tài liệu tham khảo¶

Bài trước: Sparse Table ← | Bài tiếp theo: Bao lồi →