Algorithms & Applications
Trang chủ / Module 3
🌳 Module 3 / 14 · 1-2 tuần

Cấu trúc dữ liệu Cây: Binary Tree, BST, Balanced Tree, B-Tree

Binary Search Tree, vì sao cây cần tự cân bằng (AVL/Red-Black), và B-Tree — cấu trúc dữ liệu đứng sau mọi database index bạn đã dùng.

BSTB-TreeDatabase Index
📌 Vì sao module này quan trọng

Đây là module có ứng dụng trực tiếp nhất vào công việc backend hàng ngày: mọi lần bạn tạo INDEX trên 1 cột database, bạn đang dùng B-Tree. Hiểu cách cây hoạt động bên dưới giải thích được rất nhiều hành vi "kỳ lạ" của database mà trước đây chỉ biết dùng theo kinh nghiệm.

🎯 Mục tiêu học tập

  • Triển khai và duyệt Binary Search Tree (BST), hiểu các thao tác insert/search/delete
  • Giải thích vì sao BST không cân bằng có thể suy biến thành O(n), và cách AVL/Red-Black Tree giải quyết
  • Hiểu cấu trúc B-Tree và vì sao nó là lựa chọn tối ưu cho database index (không phải Binary Tree thường)
  • Đọc hiểu được EXPLAIN ANALYZE của database dưới góc nhìn cấu trúc cây

Binary Search Tree (BST)

BST duy trì bất biến (invariant): với mỗi node, toàn bộ node ở cây con trái nhỏ hơn nó, toàn bộ node ở cây con phải lớn hơn nó — bất biến này cho phép tìm kiếm, thêm, xoá đều O(log n) (nếu cây cân bằng) bằng cách loại bỏ một nửa không gian tìm kiếm ở mỗi bước, giống hệt tìm kiếm nhị phân trên mảng đã sắp xếp nhưng hỗ trợ insert/delete hiệu quả mà mảng không làm được.

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

def insert(root, val):
    if root is None:
        return Node(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def search(root, val):
    if root is None or root.val == val:
        return root
    return search(root.left, val) if val < root.val else search(root.right, val)

Vấn đề mất cân bằng — vì sao cần AVL/Red-Black Tree

Nếu dữ liệu được insert theo thứ tự đã sắp xếp sẵn (1, 2, 3, 4, 5...), BST "ngây thơ" suy biến thành 1 danh sách liên kết — mọi thao tác trở thành O(n) thay vì O(log n), mất hoàn toàn lợi ích của cấu trúc cây. Self-balancing tree (AVL Tree, Red-Black Tree) tự động thực hiện các phép "xoay" (rotation) sau mỗi insert/delete để đảm bảo cây luôn giữ chiều cao ~O(log n) bất kể thứ tự dữ liệu vào — đây là lý do các cấu trúc dữ liệu có sẵn trong hầu hết ngôn ngữ (TreeMap của Java, std::map của C++) đều dùng Red-Black Tree bên dưới thay vì BST thường.

💡 Không cần tự cài đặt

Hầu như không ai tự viết lại AVL/Red-Black Tree trong công việc thực tế — điều quan trọng là hiểu vì sao chúng cần thiết, để nhận ra khi nào 1 thư viện/database đang dùng cấu trúc cây cân bằng bên dưới và tại sao điều đó quan trọng cho hiệu năng ổn định.

B-Tree — cấu trúc đứng sau mọi Database Index

Binary Tree (mỗi node tối đa 2 con) không tối ưu cho dữ liệu lưu trên đĩa (khác RAM) — đọc đĩa theo block (thường 4KB-16KB) có chi phí cố định lớn bất kể đọc ít hay nhiều trong 1 block, nên muốn giảm thiểu số lần đọc đĩa, không phải giảm số phép so sánh. B-Tree giải quyết đúng vấn đề này: mỗi node chứa nhiều khoá (thường hàng trăm, vừa khít 1 block đĩa), giảm chiều cao cây xuống rất thấp (thường chỉ 3-4 tầng dù có hàng triệu bản ghi) — nghĩa là tìm 1 bản ghi chỉ cần 3-4 lần đọc đĩa, thay vì hàng chục lần nếu dùng Binary Tree thường.

Đây chính xác là cấu trúc bên dưới CREATE INDEX trong PostgreSQL/MySQL (B-Tree index — loại index mặc định) mà bạn đã dùng ở khoá AI Engineer (Module 2) và Databricks (liên hệ Liquid Clustering, Module 3). Hiểu B-Tree giải thích trực tiếp: vì sao WHERE indexed_col = x nhanh nhưng WHERE indexed_col LIKE '%x%' (tìm ở giữa chuỗi) không tận dụng được index — B-Tree được sắp xếp theo thứ tự, chỉ hỗ trợ tra cứu hiệu quả theo prefix/khoảng giá trị, không hỗ trợ tìm kiếm chuỗi con tuỳ ý.

Đọc EXPLAIN ANALYZE dưới góc nhìn cấu trúc Cây

EXPLAIN ANALYZE SELECT * FROM orders WHERE customer_id = 12345;
-- Index Scan using idx_customer_id on orders
--   (cost=0.42..8.44 rows=1 width=120)
--   -> đang duyệt B-Tree index: đi từ root xuống leaf, ~3-4 lần đọc block
--      thay vì Sequential Scan phải đọc TOÀN BỘ bảng (O(n) block đọc)

Khi thấy Index Scan trong execution plan, đó chính là B-Tree đang hoạt động — hiểu cấu trúc bên dưới giúp bạn dự đoán được hiệu năng truy vấn sẽ thay đổi thế nào khi dữ liệu tăng trưởng (số lần đọc đĩa tăng theo O(log n), không phải O(n)), thay vì chỉ "tin tưởng" index mà không hiểu vì sao nó nhanh.

🏋️ Bài tập thực hành

Triển khai BST và đo tác động của mất cân bằng

Triển khai đầy đủ BST (insert/search/delete) bằng ngôn ngữ quen thuộc. Thử nghiệm 2 kịch bản: (1) insert 10.000 số ngẫu nhiên, đo chiều cao cây và thời gian tìm kiếm trung bình; (2) insert 10.000 số theo thứ tự đã sắp xếp, đo lại 2 chỉ số đó — so sánh và giải thích sự khác biệt bằng chính khái niệm mất cân bằng đã học. Sau đó chạy EXPLAIN ANALYZE trên 1 bảng có index ở database quen thuộc, xác định chỗ nào trong output thể hiện việc dùng B-Tree.

📚 Tài nguyên học tập

✅ Tự đánh giá hoàn thành

  • Triển khai đúng insert/search trên BST
  • Giải thích được vì sao BST không cân bằng có thể suy biến thành O(n)
  • Giải thích được vì sao B-Tree (không phải Binary Tree) là lựa chọn tối ưu cho database index
  • Đọc hiểu được phần Index Scan trong EXPLAIN ANALYZE của 1 database thật