Cây đỏ-đen trong cấu trúc dữ liệu

Trong phần này chúng ta sẽ xem Cây Đỏ-Đen là gì. Cây Đỏ-Đen là cây tìm kiếm nhị phân tự cân bằng. Có một số điều kiện cho mỗi nút. Những thứ này giống như bên dưới -

• Mỗi nút có màu sắc. Màu nào là Đỏ hoặc Đen

• Gốc sẽ luôn có màu đen

• Sẽ không có hai nút Đỏ liền kề

• Mọi đường dẫn từ một nút (bao gồm cả gốc) đến bất kỳ nút NULL nào con của nó đều có cùng số lượng nút đen.

Ví dụ về cây Đỏ-đen

Cây đỏ-đen với các nốt sần ở lá

So sánh với Cây AVL

Cây AVL cân bằng hơn so với cây Đỏ-Đen. Nhưng nhược điểm lớn là sẽ có nhiều thao tác xoay hơn trong quá trình chèn và xóa. Đối với việc chèn và xóa nhiều lần, cây Đỏ-Đen sẽ rất hữu ích.