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

Cây đỏ-đen (red-black tree)

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

Cây đỏ-đen (red-black tree) là một BST tự cân bằng khác, dùng cách tô màu nút thay vì đo chiều cao. Nó cân bằng "đủ tốt" với ít xoay hơn AVL khi cập nhật — nên là cây được dùng nhiều nhất trong thực tế. (Bài giới thiệu — hiểu ý tưởng và khi nào dùng.)

1. Ý tưởng: cân bằng bằng màu, không bằng chiều cao​

Thay vì đo chiều cao như AVL, cây đỏ-đen gắn mỗi nút một màu đỏ hoặc đen và tuân theo vài quy tắc màu. Các quy tắc này gián tiếp đảm bảo cây không lệch quá → chiều cao vẫn ~log n.

         ┌────┐
         │ 8  │ (đen)
         └─┬──┘
       ┌───┴────┐
     ┌─┴─┐    ┌─┴──┐
     │ 3 │    │ 10 │  (đỏ)
     └───┘    └────┘

2. Năm quy tắc (đọc hiểu, không cần thuộc)​

  1. Mỗi nút đỏ hoặc đen.
  2. Gốc luôn đen.
  3. Nút đỏ không có con đỏ (không hai đỏ liền nhau).
  4. Mọi đường từ một nút xuống các lá có cùng số nút đen.
  5. Lá (None) coi là đen.

Hệ quả của các quy tắc: đường dài nhất từ gốc xuống lá không quá gấp đôi đường ngắn nhất → cây "đủ cân bằng" → các thao tác vẫn O(log n).

3. Red-black vs AVL: chọn cái nào?​

AVLRed-black
Mức cân bằngrất chặtlỏng hơn (đủ tốt)
Tìm kiếmnhanh hơn chút (cây thấp hơn)hơi chậm hơn chút
Chèn/xóanhiều xoay hơnít xoay hơn → cập nhật nhanh
Dùng khitra cứu nhiều, ít cập nhậtcập nhật nhiều (thực tế phổ biến)

Cả hai đều O(log n). Red-black thắng khi cập nhật thường xuyên; AVL thắng khi tra cứu là chủ yếu. Vì đa số hệ thống cập nhật nhiều, red-black được dùng rộng hơn.

🎬 Trực quan hóa tương tác — VisuAlgo
VisuAlgo gộp các BST tự cân bằng chung một trang. Chèn dữ liệu sắp xếp để thấy cây tự xoay — AVL và red-black xử lý khác nhau thế nào.
Nguồn: visualgo.net — Steven Halim, NUS. Dùng cho lớp học; ảnh chụp/video cần ghi nguồn URL.

4. Bạn đã dùng red-black mà không biết​

Rất nhiều thư viện chuẩn cài map/set có thứ tự bằng cây đỏ-đen:

  • Java: TreeMap, TreeSet.
  • C++: std::map, std::set.
  • Linux kernel: lập lịch tiến trình, quản lý vùng nhớ.

Khi cần map/set giữ thứ tự với hiệu năng O(log n) đảm bảo, bên dưới thường là red-black.

5. Cây cân bằng vs bảng băm — tổng kết​

Bảng băm (dict/set)Cây cân bằng (red-black)
Tra cứuO(1) trung bìnhO(log n) đảm bảo
Giữ thứ tự❌ không✅ có (duyệt ra dãy sắp xếp)
Tìm khoảng / min / max / kế cậnkém✅ tốt
Dùng khitra cứu thuần, không cần thứ tựcần thứ tự, truy vấn khoảng

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

  • Cần map/set giữ thứ tự hoặc truy vấn khoảng (min/max, các phần tử trong [a,b]) → cây cân bằng.
  • Chỉ cần tra cứu nhanh, không cần thứ tự → bảng băm.
  • Trong thực tế: ít khi tự cài, dùng TreeMap/std::map/SortedDict... (bên dưới là red-black).

7. 🎮 Trò chơi: Hiểu red-black​

🎮 Hiểu red-blackCâu 1/4· Điểm 0· 🔥 0

Red-black: BST tự cân bằng bằng quy tắc màu; ít xoay hơn AVL → cập nhật nhanh, dùng rộng rãi.

Java TreeMap và C++ std::map thường cài bằng?

8. Quiz kiểm tra nhanh​

📝 Quiz kiểm tra nhanh
1. Cây đỏ-đen đảm bảo độ phức tạp?
2. Vì sao red-black được dùng rộng hơn AVL trong thực tế?
3. Ưu thế của cây cân bằng so với bảng băm?
📚 Đọc thêm & Luyện tập
🎬 Video
🏋️ Luyện tập

9. Hoàn thành​

…

☑️ Tiếp theo: 2.5.5 — Heap & hàng đợi ưu tiên.