Nhấn vào đây để đọc bằng ngôn ngữ khác: English
Cây đỏ-đen là một loại cây tìm kiếm nhị phân cân bằng tự động trong khoa học máy tính. Mỗi nút của cây nhị phân có một bit bổ sung, và bit n��y thường được hiểu là màu (đỏ hoặc đen) của nút. Các bit màu này được sử dụng để đảm bảo rằng cây vẫn cân bằng một cách xấp xỉ trong quá trình chèn và xóa.
Sự cân bằng được bảo tồn bằng cách sơn mỗi nút của cây bằng một trong hai màu một cách thỏa mãn các thuộc tính nhất định, những thuộc tính này hạn chế tỉ lệ mất cân bằng của cây trong trường hợp xấu nhất. Khi cây bị thay đổi, cây mới sau đó được sắp xếp lại và sơn lại để khôi phục các thuộc tính về màu sắc. Các thuộc tính được thiết kế sao cho việc sắp xếp lại và sơn lại này có thể được thực hiện một cách hiệu quả.
Việc cân bằng của cây không hoàn hảo, nhưng đủ tốt để cho phép nó đảm bảo tìm kiếm trong thời gian O(log n), trong đó n là tổng số phần tử trong cây. Các thao tác chèn và xóa, cùng với việc sắp xếp lại và sơn lại cây, cũng được thực hiện trong thời gian O(log n).
Một ví dụ về cây đỏ-đen:
Ngoài các yêu cầu được đặt ra cho một cây tìm kiếm nhị phân, các yêu cầu sau phải được đáp ứng bởi một cây đỏ-đen:
- Mỗi nút có màu đỏ hoặc đen.
- Gốc của cây là màu đen. Quy tắc này đôi khi được bỏ qua. Vì gốc luôn có thể được thay đổi từ màu đỏ thành màu đen, nhưng không nhất thiết phải ngược lại, quy tắc này không ảnh hưởng nhiều đến phân tích.
- Tất cả các lá (NIL) đều là màu đen.
- Nếu một nút có màu đỏ, thì cả hai con của nó đều là màu đen.
- Mọi đường từ một nút cụ thể đến bất kỳ nút lá con NIL nào của nó đều chứa cùng số lượng nút đen.
Một số định nghĩa: số lượng nút đen từ gốc đến một nút là độ sâu đen của nút đó; số lượng đều nhau của các nút đen trên tất cả các đường từ gốc đến các lá được gọi là chiều cao đen của cây đỏ-đen.
Những ràng buộc này áp dụng một tính chất quan trọng của cây đỏ-đen: đường từ gốc đến lá xa nhất không dài hơn gấp đôi đường từ gốc đến lá gần nhất. Kết quả là cây xấp xỉ cân bằng chiều cao. Vì các thao tác như chèn, xóa và tìm kiếm giá trị đều yêu cầu thời gian tối đa tỉ lệ thuận với chiều cao của cây, giới hạn trên lý thuyết này về chiều cao cho phép cây đỏ-đen là hiệu quả trong trường hợp xấu nhất, khác với cây tìm kiếm nhị phân thông thường.
- Trường hợp Trái Trái (
plà con trái củagvàxlà con trái củap) - Trường hợp Trái Phải (
plà con trái củagvàxlà con phải củap) - Trường hợp Phải Phải (
plà con phải củagvàxlà con phải củap) - Trường hợp Phải Trái (
plà con phải củagvàxlà con trái củap)
