Giao diện
Cấu trúc dữ liệu nâng cao
Mảng và danh sách liên kết giải quyết phần lớn bài toán hằng ngày. Nhưng khi hệ thống cần trả lời hàng triệu range query mỗi giây, khi database phải index hàng tỷ bản ghi trên ổ cứng, khi cluster phân tán cần thêm-bớt node mà không làm sập cache — bạn cần những cấu trúc dữ liệu được thiết kế riêng cho từng lớp bài toán đó.
Module này tập trung vào năm cấu trúc then chốt. Hiểu rõ đặc trưng và giới hạn của từng cấu trúc giúp bạn đưa ra quyết định thiết kế chính xác ngay từ đầu, thay vì thử-sai rồi refactor.
Bảng so sánh tổng quan
| Cấu trúc | Bài toán chính | Query | Update | Điểm mạnh | Điểm yếu |
|---|---|---|---|---|---|
| Segment Tree | Range query tổng quát (sum, min, max, gcd) | O(log n) | O(log n) | Linh hoạt, hỗ trợ lazy propagation | Code dài, bộ nhớ 4n |
| Fenwick Tree | Prefix sum + point update | O(log n) | O(log n) | Code ngắn gọn, hằng số nhỏ, bộ nhớ n | Chỉ hỗ trợ phép toán có nghịch đảo |
| Heap / Priority Queue | Truy xuất phần tử ưu tiên cao nhất | O(1) peek | O(log n) insert/extract | Đơn giản, nền tảng cho nhiều thuật toán | Không hỗ trợ search hay delete tùy ý |
| B-Tree / B+ Tree | Index dữ liệu trên disk | O(log_B n) | O(log_B n) | Tối ưu disk I/O, nền tảng database | Cài đặt từ đầu phức tạp |
| Consistent Hashing | Phân tán dữ liệu qua nhiều node | O(log n) lookup | O(log n) add/remove node | Tối thiểu key di chuyển khi scale | Cần virtual node để cân bằng tải |
Khi nào dùng cấu trúc nào?
Ứng dụng thực tế
| Lĩnh vực | Cấu trúc | Tình huống cụ thể |
|---|---|---|
| Database | B+ Tree | Index cho PostgreSQL, MySQL InnoDB |
| Distributed Cache | Consistent Hashing | Redis Cluster, Memcached phân tán |
| Finance | Segment Tree | Min/Max giá cổ phiếu trong khoảng thời gian |
| OS Scheduler | Heap | CPU scheduling, I/O priority queue |
| Competitive Programming | Fenwick Tree | Đếm nghịch thế, prefix frequency |
| CDN | Consistent Hashing | Định tuyến request đến edge server gần nhất |
| Game Engine | Segment Tree | 2D range query cho collision detection |
Lộ trình học
Thứ tự đề xuất dựa trên mức độ phụ thuộc kiến thức:
- Heap & Priority Queue — Nền tảng, xuất hiện trong Dijkstra, scheduling, top-K. Bắt đầu từ đây nếu chưa vững.
- Segment Tree — Vua range query, thiết yếu cho competitive programming và database aggregate.
- Fenwick Tree (BIT) — Phiên bản gọn nhẹ của Segment Tree cho bài toán prefix sum.
- B-Tree & B+ Tree — Kiến trúc lõi của storage engine, cần hiểu disk I/O.
- Consistent Hashing — Kỹ thuật system design, cầu nối sang distributed systems.
Quy tắc chọn nhanh
Prefix sum + point update → Fenwick Tree. Min/Max hoặc lazy range update → Segment Tree. Phần tử ưu tiên cao nhất → Heap. Dữ liệu trên disk → B-Tree. Phân tán nhiều node → Consistent Hashing.
🧠 Quiz
Câu 1: Fenwick Tree (BIT) và Segment Tree khác nhau cơ bản ở điểm nào?
- [ ] A) Fenwick Tree nhanh hơn Segment Tree trong mọi trường hợp
- [x] B) Fenwick Tree code ngắn hơn, ít bộ nhớ hơn, nhưng Segment Tree linh hoạt hơn (hỗ trợ lazy propagation, range update)
- [ ] C) Segment Tree chỉ dùng cho sum query, Fenwick Tree dùng cho mọi loại
- [ ] D) Không có sự khác biệt, chỉ là hai cách implement cùng ý tưởng
💡 Giải thích: Fenwick Tree: ~15 dòng code, 1×N bộ nhớ, O(log n) cho point update + prefix query. Segment Tree: ~50+ dòng, 4×N bộ nhớ, nhưng hỗ trợ range update (lazy propagation), merge query phức tạp. Chọn Fenwick khi đủ, Segment Tree khi cần linh hoạt.
Câu 2: Heap (Priority Queue) đảm bảo thao tác nào nhanh nhất?
- [ ] A) Tìm kiếm phần tử bất kỳ — O(1)
- [x] B) Lấy phần tử min/max — O(1), insert/delete — O(log n)
- [ ] C) Sắp xếp toàn bộ — O(n)
- [ ] D) Truy cập phần tử theo index — O(1)
💡 Giải thích: Heap property đảm bảo root luôn là min (min-heap) hoặc max (max-heap) → peek O(1). Insert và extract đều O(log n) nhờ heapify up/down. Không hỗ trợ tìm kiếm hay truy cập theo index hiệu quả.