Cây Đỏ-Đen (Red-Black Tree) trong cấu trúc dữ liệu

Xem Red-Black Tree. Là cây tìm kiếm nhị phân tự cân bằng. Điều kiện cho mỗi nút:

• Mỗi nút có màu: Đỏ hoặc Đen.
• Gốc luôn đen.
• Không có hai nút Đỏ liền kề.
• Mọi đường từ nút (kể cả gốc) đến nút NULL con cháu có cùng số nút đen.

Ví dụ Red-Black Tree

Red-Black Tree với nút NULL ở lá

So sánh với AVL Tree

AVL cân bằng chặt chẽ hơn Red-Black. Nhưng nhược điểm: nhiều phép xoay (rotation) hơn khi chèn/xóa. Với nhiều chèn/xóa, Red-Black tốt hơn.