Cây nhị phân tìm kiếm (BST) là cây nhị phân với tính chất: với mọi node , tất cả node ở cây con trái có giá trị nhỏ hơn , tất cả node ở cây con phải có giá trị lớn hơn .
Tính chất
- Duyệt in-order cho dãy tăng dần
- Tìm kiếm, chèn, xóa: với là chiều cao cây
- BST không cân bằng có thể đạt → cần BST tự cân bằng (AVL, Red-Black Tree)
Các phép duyệt
5
/ \
3 7
/ \
1 4
| 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 |
Dùng BST có sẵn trong lập trình thi đấu
Trong thực tế không cần tự cài BST. Dùng cấu trúc chuẩn (cài bằng Red-Black Tree, cho mọi thao tác):
C++ — set và map
#include <set>
#include <map>
// set: tập không trùng, có thứ tự
set<int> s;
s.insert(5); s.insert(3); s.insert(7);
s.erase(3);
cout << *s.begin(); // 3 → nhỏ nhất
cout << *s.rbegin(); // 7 → lớn nhất
auto it = s.lower_bound(4); // iterator đến phần tử >= 4
auto it = s.upper_bound(4); // iterator đến phần tử > 4
bool found = s.count(5); // 1 nếu tồn tại
// multiset: cho phép trùng
multiset<int> ms;
ms.insert(3); ms.insert(3);
ms.erase(ms.find(3)); // chỉ xóa 1 phần tử (không phải erase(3))
// map: key → value, sắp xếp theo key
map<string, int> mp;
mp["alice"] = 10;
mp["bob"] = 20;
for (auto& [key, val] : mp)
cout << key << " " << val << "\n";
Python — SortedList
from sortedcontainers import SortedList
sl = SortedList([5, 3, 7, 1])
sl.add(4)
sl.remove(3)
print(sl[0]) # 1 — nhỏ nhất
print(sl[-1]) # 7 — lớn nhất
idx = sl.bisect_left(4) # index của phần tử >= 4
idx = sl.bisect_right(4) # index của phần tử > 4
Tóm tắt độ phức tạp
| Thao tác | BST mất cân bằng | BST cân bằng |
|---|---|---|
| Tìm kiếm | ||
| Chèn | ||
| Xóa |
Bình luận