Cây đỏ đen (Red-Black Tree) là một cây tìm kiếm nhị phân tự cân bằng, nhờ vậy chiều cao cây luôn bị giới hạn ở mức O(log n) bất kể dữ liệu được thêm vào theo thứ tự nào. Khác với AVL, cây đỏ đen dùng màu sắc của từng nút và một quy tắc về số nút đen trên mọi đường đi từ gốc xuống lá để giữ cân bằng, nhờ đó mã nguồn thực thi gọn hơn và chịu tải tốt hơn với chuỗi thao tác xen kẽ thêm, xoá.
Bài viết này giải thích bốn bất biến của cây đỏ đen, quy trình thêm và xoá nút, biến thể nghiêng trái của Robert Sedgewick, và lý do các thư viện lớn như C++ và Java lại chọn cấu trúc dữ liệu này cho bản đồ có khoá.
Ví dụ minh hoạ rõ nhất về cây đỏ đen là một cây hoàn chỉnh với các lá NIL tô đen ở đáy. Mọi lá đều nằm ở cùng một độ sâu tính theo số nút đen, và không nút đỏ nào có con đỏ.
Bốn bất biến của cây đỏ đen
Một cây đỏ đen hợp lệ phải thoả mãn đồng thời bốn điều kiện sau, theo định nghĩa chuẩn được dùng trong sách Introduction to Algorithms và trong bài viết về cây đỏ đen trên Wikipedia:
- Mỗi nút mang một màu, hoặc đỏ hoặc đen.
- Gốc của cây luôn có màu đen.
- Mọi lá NIL đều có màu đen.
- Nếu một nút có màu đỏ thì cả hai nút con của nó đều có màu đen.
Quy tắc quan trọng nhất về mặt hiệu năng là bất biến thứ năm, dù nó không nằm trong danh sách trên: trên mọi đường đi từ một nút bất kỳ xuống các lá NIL phía dưới, số lượng nút đen phải bằng nhau. Người ta gọi giá trị chung đó là chiều cao đen (black-height) của nút. Chính bất biến này ngăn câc bẹp một nhánh sâu hơn nhánh khác, và từ đó kéo theo giới hạn chiều cao tổng thể: đường đi dài nhất không bao giờ dài quá gấp đôi đường đi ngắn nhất, nên với n nút thì chiều cao luôn nhỏ hơn hoặc bằng 2 lần log2(n + 1).
Bất biến số nút đen bị phá vỡ tạm thời ngay sau mỗi lần thêm nút, và việc xoay về phải đặt lại nó. Ba trường hợp phổ biến được xử lý như sau: nút thêm là gốc thì sơn lại đen; cha và con đều đỏ thì sơn cha thành đen rồi xoay; hoặc nút, cha, chú đều đỏ thì đổi màu hai nhánh và xoay ở nơi khác.
Cách thêm và xoá một nút
Quy trình thêm nút trong cây đỏ đen gần giống cây tìm kiếm nhị phân thông thường: đi xuống từ gốc để tìm chỗ trống, chèn nút màu đỏ vào. Vì nút mới luôn đỏ, vi phạm dễ xảy ra nhất là phát sinh cặp đỏ-đỏ với nút cha. Hàm sửa chữa phải đi ngược lên từ nút vừa chèn, và chỉ cần xử lý tối đa ba trường hợp:
- Nút cha đen, hoặc nút thêm là gốc: sơn gốc thành đen là xong.
- Cha và con đều đỏ, chú thì đen: sơn cha và chú thành đen, sơn ông nội thành đỏ rồi lặp lại từ ông nội.
- Cha đỏ, chú đỏ: sơn cha và chú thành đen, sơn ông nội thành đỏ, rồi xoay quanh ông nội để đưa cặp đỏ ra khỏi nhánh.
Nếu cha và chú nằm ở hai phía khác nhau so với ông nội, cần hai lần xoay. Hàm rb_insert_color() trong mã nguồn [nhánh chính của Linux](https://raw.githubusercontent.com/torvalds/linux/master/lib/rbtree.c) thực hiện đúng thuật toán này, bên cạnh các hàm xoay trái và xoay phải.
Quy trình xoá phức tạp hơn vì cây đỏ đen cho phép nút xoá có một con. Cách chuẩn dùng trong CLRS thay nút xoá bằng nút kế tiếp theo thứ tự trung tố, rồi sửa chữa theo hai khái niệm “double black” và “sibling” để bù lại số nút đen bị mất. Khi em của nút đen bị thiếu cũng là nút đen, thuật toán dừng lại được ngay, đó là lý do cây đỏ đen dễ viết và dễ kiểm chứng hơn AVL. Hàm rb_erase() cùng __rb_erase_color() hiện thực hoá quy trình này, và rb_erase() còn tự động hoàn tất sửa chữa màu trước khi trả về, nên phía gọi không cần can thiệp thêm.
Biến thể cây đỏ đen nghiêng trái
Điểm khó chịu của cài đặt CLRS là các trường hợp xoay lặp lại và điều kiện đệ quy rối rắm. Robert Sedgewick đề xuất biến thể cây đỏ đen nghiêng trái với một bổ sung: nếu một nút chỉ có một con đỏ, con đỏ đó bắt buộc phải là con trái. Với quy tắc này, cây đỏ đen tương đương một-một với cây 2-3-4, và Robert Sedgewick cho biết mã nguồn chỉ còn khoảng một phần tư số dòng của bản gốc.
Trong bài báo Left-Leaning Red-Black Trees and their Application to Dictionary Implementation, ông cũng đo chiều cao trung bình khoảng 2 lần ln N cho cây sinh từ khoá ngẫu nhiên, tức gần bằng giá trị tối ưu lg N. Nhiều thư viện Java như Apache Commons Collections đã chuyển sang biến thể này để có mã ngắn và kiểm thử dễ hơn.
So sánh cây đỏ đen với các cấu trúc cân bằng khác
| Đặc tính | Cây đỏ đen | Cây AVL | B-tree | Heap nhị phân |
|---|---|---|---|---|
| Tìm kiếm | O(log n) | O(log n) | O(log n) | O(n) |
| Thêm nút | O(log n) | O(log n) | O(log n) | O(log n) |
| Xoá nút | O(log n) | O(log n) | O(log n) | O(log n) |
| Cân bằng | Đều đặn, chiều cao gần 2 log n | Chặt chẽ, chiều cao gần 1,44 log n | Đều đặn theo trang | Không cân bằng |
| Ứng dụng điển hình | Bản đồ, tập khoá có thứ tự | Bản đã cân bằng cao | Cơ sở dữ liệu, hệ thống tệp | Hàng đợi ưu tiên |
Cây đỏ đen và AVL đều cho chi phí tìm kiếm giống nhau, nhưng đánh đổi khác nhau. AVL cân bằng chặt hơn nên tìm kiếm nhanh hơn một chút, đổi lại thêm và xoá phải xoay nhiều hơn. Cây đỏ đen chấp nhận cây cao hơn khoảng 40% để đổi lấy số lần xoay ít hơn, phù hợp với mẫu sử dụng thêm nút và xoá xen kẽ. B-tree thì dành cho dữ liệu nằm trên đĩa vì mỗi nút chứa cả trăm khoá nên giảm số lần đọc trang.
Ứng dụng thực tế trong hệ điều hành và ngôn ngữ
Cây đỏ đen không chỉ là ví dụ trong sách giáo khoa. Trong tài liệu API rbtree của nhân Linux, hàm rb_insert_color() và rb_erase() được dùng để đặt tiến trình. Bộ lập lịch CFS trong [fair.c](https://raw.githubusercontent.com/torvalds/linux/master/kernel/sched/fair.c) giữ cây tasks_timeline.rb_root để sắp xếp tiến trình theo virtual runtime, và lớp epoll trong [eventpoll.c](https://raw.githubusercontent.com/torvalds/linux/master/fs/eventpoll.c) dùng một biến thể cây đỏ đen có lưu nút trái cực để duyệt danh sách sẵn sàng trong O(1) cho phần tử đầu tiên.
Ở tầng ứng dụng, std::map của C++ theo [đặc tả cppreference](https://en.cppreference.com/w/cpp/container/map) thường dùng cây đỏ đen, cam kết tìm kiếm, thêm, xoá O(log n) trong trường hợp xấu nhất và duyệt theo thứ tự tăng dần. Lớp [TreeMap của Java](https://raw.githubusercontent.com/openjdk/jdk/master/src/java.base/share/classes/java/util/TreeMap.java) cũng vậy, với các hàm fixAfterInsertion() và fixAfterDeletion() làm nhiệm vụ tương ứng. Lưu ý đây là các bản triển khai phổ biến chứ không phải yêu cầu bắt buộc của đặc tả, vì đặc tả chỉ yêu cầu hành vi và độ phức tạp.
Một số triển khai nâng cao của cây đỏ đen còn hỗ trợ phép ghép nhanh (concat) để nối hai cây con có khoá không lồng nhau, mà không cần duyệt qua từng nút. Các hàm như rbtree_join() trong các thư viện như Boost.Intrusive hoặc trong riêng GCC libstdc++ cho phép ghép hai cây trong thời gian O(log n) chỉ cần biết giá trị lớn nhất của cây trái và nhỏ nhất của cây phải. Thuật toán này thường dùng trong các hàng đợi ưu tiên có thể hợp nhất hoặc trong các cấu trúc phân đoạn.
Khi nào nên chọn cây đỏ đen
Cây đỏ đen hợp lý khi bạn cần một bản đồ có thứ tự với chi phí thao tác chắc chắn, đặc biệt khi dữ liệu đến từ nguồn không kiểm soát thứ tự chèn, như chỉ số cơ sở dữ liệu nhận ID từ nhiều node khác nhau. Nếu chỉ cần tra cứu theo khoá và không cần duyệt theo thứ tự, bảng băm vẫn nhanh hơn với hằng số O(1). Nếu dữ liệu lớn nằm trên ổ đĩa, hãy chọn B-tree hoặc LSM-tree thay vì cây nhị phân. Còn nếu chỉ cần lấy phần tử nhỏ nhất liên tục, heap nhị phân là lựa chọn đơn giản hơn nhiều.
Nguồn tham khảo: bài viết Red-black tree trên Wikipedia, bài viết Left-leaning red-black tree, bài viết Cây 2-3-4 trên Wikipedia, tài liệu Red-Black Trees của nhân Linux, và bài báo Left-Leaning Red-Black Trees của Robert Sedgewick.
