Wiki › Cấu trúc dữ liệu › Cây › Cây nhị phân tìm kiếm (BST)

Cây nhị phân tìm kiếm (BST)

huunguyen Updated Tháng sáu 2, 2026

Cây nhị phân tìm kiếm (Binary Search Tree, BST) là một cây nhị phân lưu các khoá có thứ tự sao cho mọi thao tác thêm, xoá, tìm kiếm, tìm phần tử nhỏ nhất/lớn nhất, tìm phần tử kế cận (lowerbound/upperbound) đều chạy trong $O (h)$ với $h$ là chiều cao cây. Khi cây được giữ cân bằng (AVL, Red-Black Tree, Treap...) thì $h = O (\log N)$ , biến mọi truy vấn "tập hợp có thứ tự động" thành $O (\log N)$ thay vì $O (N)$ như khi quét mảng. Đây chính là cấu trúc đứng sau set/map của C++ và SortedList của Python — công cụ thiết yếu cho các bài cần duy trì một tập phần tử thay đổi liên tục mà vẫn truy vấn được theo thứ tự.

Ý tưởng / Trực giác

Tính chất bất biến (invariant) của BST: với mọi node $u$ , mọi khoá ở cây con trái đều nhỏ hơn $u$ , mọi khoá ở cây con phải đều lớn hơn $u$ (giả sử không trùng khoá).

Vì sao tính chất này hữu ích? Vì nó cho phép tìm kiếm theo kiểu chặt nhị phân ngay trên cấu trúc cây: khi đứng ở node $u$ và muốn tìm khoá $x$ , ta chỉ cần so $x$ với khoá tại $u$ . Nếu $x$ nhỏ hơn, đáp án (nếu có) chắc chắn nằm ở cây con trái — ta loại bỏ toàn bộ cây con phải; ngược lại loại bỏ cây con trái. Mỗi bước đi xuống một tầng, nên số bước bằng đúng chiều cao $h$ .

Hệ quả quan trọng: duyệt in-order (Trái → Gốc → Phải) cho ra dãy khoá tăng dần. Trực giác: khi đứng ở $u$ , in-order in toàn bộ cây con trái (đều nhỏ hơn $u$ ) trước, rồi đến $u$ , rồi cây con phải (đều lớn hơn $u$ ). Đệ quy xuống thì tính chất "trái < gốc < phải" áp dụng ở mọi tầng, nên dãy in ra hoàn toàn được sắp xếp. Nhờ vậy BST không chỉ trả lời "có/không tồn tại" mà còn trả lời được "phần tử nhỏ nhất $\geq x$ ", "phần tử lớn nhất $< x$ ", "phần tử kế trước/kế sau" — những truy vấn mà unordered_set (bảng băm) không làm được.

Điểm yếu: nếu chèn dữ liệu theo thứ tự đã sắp xếp (1, 2, 3, ...) vào một BST thường, cây thoái hoá thành một "danh sách xích" có $h = N$ , mọi thao tác trở về $O (N)$ . Đây là lý do trong thực chiến ta dùng BST tự cân bằng, nơi cây tự xoay để giữ $h = O (\log N)$ .

Ví dụ chạy tay

Chèn lần lượt dãy 5, 3, 7, 1, 4 vào BST rỗng. Mỗi khoá đi xuống từ gốc, rẽ trái nếu nhỏ hơn, rẽ phải nếu lớn hơn, đến khi gặp chỗ trống.

Chèn 5            Chèn 3 (3<5: trái)   Chèn 7 (7>5: phải)
   5                    5                    5
                       /                    / \
                      3                    3   7

Chèn 1                       Chèn 4
(1<5: trái; 1<3: trái)       (4<5: trái; 4>3: phải)
        5                            5
       / \                          / \
      3   7                        3   7
     /                           /  \
    1                           1    4   ← chỗ trống bên phải của 3

Cây cuối cùng:

Bây giờ tìm khoá $x = 4$ , đánh dấu node đang xét bằng [ ]:

Bước 1: ở [5], 4 < 5 → rẽ trái
Bước 2: ở [3], 4 > 3 → rẽ phải
Bước 3: ở [4], 4 == 4 → TÌM THẤY

Chỉ 3 phép so sánh cho cây 5 phần tử — đúng bằng chiều cao.

Duyệt in-order trên cây trên cho dãy đã sắp xếp:

Bước	Thăm cây con trái	In gốc	Thăm cây con phải
node 3	in 1	in 3	in 4
node 5	(đã in 1,3,4)	in 5	in 7

Kết quả: 1, 3, 4, 5, 7 — tăng dần, đúng như tính chất.

Bảng các phép duyệt khác trên cùng cây:

Kiểu duyệt	Thứ tự thăm	Kết quả
In-order	Trái → Gốc → Phải	1, 3, 4, 5, 7 (tăng dần)
Pre-order	Gốc → Trái → Phải	5, 3, 1, 4, 7
Post-order	Trái → Phải → Gốc	1, 4, 3, 7, 5

Cài đặt

Trong thi đấu, gần như không bao giờ tự cài BST — hãy dùng cấu trúc chuẩn đã được cài bằng Red-Black Tree (cân bằng, $O (\log N)$ mọi thao tác). Tự cài chỉ cần khi bạn muốn thao tác đặc biệt (order statistics, merge...) — khi đó dùng Treap/Fenwick thay vì BST thường.

C++ — `set`, `multiset`, `map`

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

set<int> s;
s.insert(5); s.insert(3); s.insert(7);   // {3,5,7}
s.erase(3);                              // {5,7}

cout << *s.begin();   // 5  → phần tử nhỏ nhất
cout << *s.rbegin();  // 7  → phần tử lớn nhất
bool co = s.count(5); // 1 nếu tồn tại (set: 0 hoặc 1)

// lower_bound: iterator tới phần tử ĐẦU TIÊN >= x
// upper_bound: iterator tới phần tử ĐẦU TIÊN >  x
auto it = s.lower_bound(6);   // trỏ tới 7
if (it != s.end())  cout << *it;        // phần tử nhỏ nhất >= 6
if (it != s.begin()) cout << *prev(it); // phần tử lớn nhất <  6  (KỀ TRÁI)

// multiset: cho phép trùng khoá
multiset<int> ms;
ms.insert(3); ms.insert(3);
ms.erase(ms.find(3));   // CHỈ xoá MỘT bản; ms.erase(3) sẽ xoá HẾT mọi số 3!

// map: khoá -> giá trị, tự sắp theo khoá
map<string,int> mp;
mp["alice"] = 10;
for (auto& [key, val] : mp)            // duyệt theo thứ tự khoá tăng dần
    cout << key << ' ' << val << '\n';

Python — `SortedList`

from sortedcontainers import SortedList   # không có sẵn ở mọi judge, cần kiểm tra

sl = SortedList([5, 3, 7, 1])
sl.add(4)
sl.remove(3)

print(sl[0], sl[-1])        # nhỏ nhất, lớn nhất
i = sl.bisect_left(4)       # vị trí phần tử đầu tiên >= 4
j = sl.bisect_right(4)      # vị trí phần tử đầu tiên >  4

Độ phức tạp

Thao tác	BST mất cân bằng	BST cân bằng (`set`/`map`)
Tìm kiếm `find`/`count`	$O (N)$	$O (\log N)$
Chèn `insert`	$O (N)$	$O (\log N)$
Xoá `erase`	$O (N)$	$O (\log N)$
`lower_bound`/`upper_bound`	$O (N)$	$O (\log N)$
Nhỏ nhất/lớn nhất	$O (N)$	$O (\log N)$ *
Duyệt in-order toàn bộ	$O (N)$	$O (N)$

Lý giải thời gian: mỗi thao tác tìm/chèn/xoá chỉ đi theo một đường từ gốc xuống, số bước bằng chiều cao $h$ . Cây tự cân bằng đảm bảo $h = O (\log N)$ vì số node ít nhất ở một cây cao $h$ tăng theo hàm mũ của $h$ , nên $h$ chỉ tăng theo logarit của $N$ . (*Với set C++, *begin() là $O (1)$ vì con trỏ tới phần nhỏ nhất được lưu sẵn.)

Bộ nhớ: $O (N)$ . Mỗi khoá là một node lưu thêm 2–3 con trỏ (trái, phải, cha) và 1 bit/byte màu để cân bằng. Hằng số bộ nhớ của set/map lớn hơn nhiều so với mảng hay vector (mỗi node cấp phát động riêng), nên với $N$ lớn và chỉ cần truy vấn tĩnh, nên cân nhắc sắp xếp mảng + chặt nhị phân thay vì set.

⚠️ Lỗi thường gặp

multiset::erase(giá_trị) xoá SẠCH mọi bản trùng. Triệu chứng: bài "xoá đúng một con bò có thời gian $t$ " lại làm biến mất mọi con cùng $t$ , kết quả sai. Cách tránh: luôn dùng ms.erase(ms.find(t)) để chỉ xoá một bản; chỉ dùng ms.erase(t) khi thực sự muốn xoá hết.
Quên kiểm tra end() / begin() trước khi truy cập. lower_bound có thể trả về s.end() (không có phần tử nào $\geq x$ ) — dereference nó là hành vi không xác định (UB), thường gây sai/RE. Tương tự, muốn lấy "phần tử lớn nhất $< x$ " bằng prev(it) nhưng nếu it == s.begin() thì không có kề trái — phải kiểm tra trước, đừng gọi prev(s.begin()).
Nhầm lower_bound/upper_bound của thuật toán std:: với của set. Gọi lower_bound(s.begin(), s.end(), x) (phiên bản trong <algorithm>) trên set vẫn biên dịch được nhưng chạy $O (N)$ do iterator của set không truy cập ngẫu nhiên — biến lời giải " $O (N \log N)$ " thành $O (N^{2})$ và TLE. Luôn dùng hàm thành viên s.lower_bound(x).
Dùng set khi không cần thứ tự. Nếu chỉ cần kiểm tra tồn tại/đếm phân biệt, unordered_set trung bình $O (1)$ nhanh hơn set $O (\log N)$ . Ngược lại, đừng dùng unordered_set rồi gọi lower_bound — bảng băm không có thứ tự, không hỗ trợ truy vấn kế cận.
Tràn số khi cộng dồn giá trị từ map/multiset. Khoá có thể tới $10^{9}$ và có $2 \cdot 10^{5}$ phần tử; tổng vượt int. Triệu chứng: kết quả âm hoặc sai ở test lớn. Cách tránh: dùng long long cho biến tích luỹ.
Cây tự cài bị thoái hoá $O (N)$ . Nếu tự viết BST thường rồi chèn dữ liệu đã sắp xếp, cây thành đường thẳng, TLE dù lý thuyết "tưởng" $O (\log N)$ . Cách tránh: dùng set/map chuẩn, hoặc Treap/randomized BST.

Biến thể / Mở rộng

BST tự cân bằng: AVL, Red-Black Tree (nền tảng của set/map), Treap — giữ $h = O (\log N)$ .
Order-statistics tree (đếm số phần tử nhỏ hơn $x$ , tìm phần tử thứ $k$ ): dùng __gnu_pbds::tree của GCC hoặc Fenwick Tree trên giá trị đã nén.
Khi cần truy vấn đoạn (tổng/min trên một khoảng chỉ số) thay vì tập có thứ tự, dùng Segment Tree hoặc Fenwick Tree.

Bài tập luyện

Số Phân Biệt (distnum) — (Amateur) Đếm số giá trị phân biệt: chèn hết vào set rồi lấy size() — bài khởi động làm quen thao tác cơ bản của tập có thứ tự.
MEX/Mốt và giá trị nhỏ hơn gần nhất (nearsmall) — (Intermediate) Với mỗi vị trí tìm phần tử nhỏ hơn gần nhất bên trái — luyện dùng cấu trúc có thứ tự để truy vấn "giá trị/chỉ số kế cận".
Mốt Cửa Sổ Trượt (swmode) — (Intermediate) Duy trì tần suất bằng map và một set<pair<freq,val>> để lấy mốt khi cửa sổ thêm/bớt phần tử — luyện thêm/xoá động kèm truy vấn cực trị theo thứ tự.
Đèn Giao Thông (trafficlts) — (Intermediate) Lắp đèn từng cái, sau mỗi lần tìm đoạn trống dài nhất: lưu vị trí đèn trong set, dùng lower_bound để tìm hai đèn kề trái–phải — ứng dụng kinh điển của truy vấn kế cận trên BST.
Giúp Qua Đường (helpcross) — (Intermediate) Ghép cặp tham lam bằng multiset các thời điểm rảnh, mỗi lần lấy phần tử phù hợp gần nhất qua lower_bound rồi xoá đúng một bản — luyện cạm bẫy erase(find(...)).