Chuyển tới nội dung chính

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

Bạn sẽ học được gì

Cây tìm kiếm nhị phân (BST) sắp xếp dữ liệu để tìm kiếm nhanh như tìm kiếm nhị phân — nhưng thêm/xóa cũng nhanh. Bạn sẽ hiểu tính chất cốt lõi của nó và vì sao có thể tụt xuống O(n).

1. Tính chất BST: trái < gốc < phải​

Một BST là cây nhị phân thỏa: với mọi nút, tất cả giá trị bên trái nhỏ hơn nó, tất cả bên phải lớn hơn nó.

            ┌───┐
            │ 8 │
            └─┬─┘
        ┌─────┴─────┐
      ┌─┴─┐       ┌──┴─┐
      │ 3 │       │ 10 │
      └─┬─┘       └──┬─┘
    ┌───┴───┐        └───┐
  ┌─┴─┐   ┌─┴─┐      ┌───┴┐
  │ 1 │   │ 6 │      │ 14 │
  └───┘   └───┘      └────┘

Mọi thứ trái 8 đều < 8; mọi thứ phải 8 đều > 8. Tính chất này cho phép bỏ một nửa ở mỗi bước khi tìm — y như tìm kiếm nhị phân trên mảng.

2. Chạy debug: tìm 6 trong BST​

Tìm trong BST: so với nút hiện tại, nhỏ hơn đi trái, lớn hơn đi phải. Mỗi bước bỏ một nửa cây:

🐞 Tìm 6 trong BSTBước 1/6
1def tim(nut, x):
2  if nut is None:
3      return False
4  if x == nut.val:
5      return True
6  if x < nut.val:
7      return tim(nut.trai, x)
8  else:
9      return tim(nut.phai, x)
Biến tại bước này
tại8
x6
👉 Bắt đầu ở gốc 8.
🎬 Trực quan hóa tương tác — VisuAlgo
Trực quan hóa chèn, tìm, xóa trong BST. Thử nhập dữ liệu đã sắp xếp (1→2→3→4...) để thấy cây suy biến thành đường thẳng.
Nguồn: visualgo.net — Steven Halim, NUS. Dùng cho lớp học; ảnh chụp/video cần ghi nguồn URL.

3. Ba thao tác & độ phức tạp​

Thao tácCân bằngSuy biến (lệch)
TìmO(log n)O(n)
ChènO(log n)O(n)
XóaO(log n)O(n)

Tất cả tỉ lệ với chiều cao cây. Cây cân bằng → cao ~log n → O(log n). Nhưng...

4. Vấn đề: BST có thể SUY BIẾN thành danh sách​

Nếu chèn dữ liệu đã sắp xếp (1, 2, 3, 4...) vào BST thường, mỗi nút chỉ có con phải → cây thành một đường thẳng cao n → tìm kiếm tụt về O(n)!

chèn 1,2,3,4 vào BST thường:
   1
    \\
     2
      \\
       3
        \\
         4      ← cao n, không khác gì linked list!
Đang tải trình chạy code…

Đây là lý do cần cây tự cân bằng (AVL, red-black) ở hai bài tiếp theo — chúng đảm bảo cây luôn cao ~log n, giữ O(log n) trong mọi trường hợp.

5. Mẫu nhận diện​

  • Cần tìm kiếm + thêm/xóa đều nhanh VÀ giữ thứ tự → BST (cân bằng).
  • Chỉ cần tra cứu nhanh, không cần thứ tự → bảng băm (O(1)) thường hơn.
  • Chèn dữ liệu đã sắp xếp vào BST thường → cảnh báo suy biến O(n), cần cây cân bằng.

6. 🎮 Trò chơi: Hiểu BST​

🎮 Hiểu BSTCâu 1/4· Điểm 0· 🔥 0

BST: trái < gốc < phải. Tìm = nhỏ đi trái, lớn đi phải. Cân bằng → O(log n).

Trong BST, so với một nút thì cây con TRÁI chứa giá trị?

7. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Tính chất cốt lõi của BST?
2. Vì sao BST có thể tụt xuống O(n)?
3. Giải pháp cho BST suy biến là?
📚 Đọc thêm & Luyện tập
🎬 Video
🏋️ Luyện tập

8. Hoàn thành​

…

☑️ Tiếp theo: 2.5.3 — Cây cân bằng & AVL.