Cây đỏ đen (red black tree) là cây nhị phân tìm kiếm được ràng buộc thêm bởi 1 số điều kiện (constraint) để đảm bảo cây luôn ở trạng thái tương đối cân bằng (độ dài giữa các nhánh cây không chênh lệch nhau quá lớn), nhằm tối đa hóa hiệu quả các thao tác tìm kiếm và lưu trữ trên cây.
1 dạng khác của cây nhị phân tự cân bằng là cây AVL, tuy nhiên điều kiện cân bằng của cây đỏ đen được thiết kế lỏng hơn so với cây AVL. Ở cây AVL độ dài 2 nhánh cây chênh nhau không quá 1 đơn vị thì ở cây đỏ đen 1 nhánh cây có độ dài không quá 2 lần nhánh còn lại (với mọi nút). Do tính chất này trong trường hợp thực hiện nhiều lần các thao tác thêm và xóa với cây đỏ đen sẽ hiệu quả hơn so với cây AVL vì không phải tái cấu trúc cây quá nhiều lần.
Tính chất cây đỏ đen
- Mọi nút đều có thuộc tính là đỏ hoặc đen.
- Nút gốc là nút đen.
- Tất cả nút NULL là nút đen.
- Nếu 1 nút là đỏ thì tất cả nút con của nó phải là đen, hay nói cách khác không có 2 nút đỏ liên tiếp trên 1 đường đi từ gốc đến lá.
- Với mọi đường đi từ gốc đến NULL, số nút đen là bằng nhau.
Ở đây 2 tính chất logic chính để tạo nên tính cân bằng cho cây đỏ đen là tính chất 4 và 5. Ta sử dụng 2 tính chất này để chứng minh tính cân bằng của cây đỏ đen.
Tính cân bằng của cây đỏ đen
Theo tính chất 5, với mọi đường đi từ gốc đến NULL số nút đen là bằng nhau, gọi số nút đen này là bh
(black-height, không tính NULL).
Trong trường hợp không có nút đỏ nào ta có cây nhị phân hoàn hảo (Perfect Binary Tree) có tổng số nút n = 2^bh - 1
.
Trong trường hợp có thêm các nút đỏ và số nút đen giữ nguyên, ta có tổng số nút n >= 2^bh - 1.
Gọi độ cao cây là h, theo tính chất 4 do không có 2 nút đỏ liên tiếp trên đường đi từ gốc đến NULL nên ta có bh >= h/2, vì nếu bh < h/2 ta bắt buộc phải có 2 nút đỏ liên tiếp.
Tổng hợp 2 ý trên ta có n >= 2^bh -1 >= 2^(h/2) - 1
. Suy ra: n + 1 >= 2^(h/2)
=> log(n + 1) >= h/2
hay h <= 2log(n + 1)
.
Suy ra độ phức tạp tính toán của cây nhị phân là O(h) hay chính là O(logn)
.
Các thao tác tái cấu trúc cây
Ngoài các thao tác chính của cây nhị phân tìm kiếm (Thêm, xóa), chúng ta sử dụng các công cụ sau để tái cấu trúc cho cây khi cần thiết.
Xoay trái (Left-rotation) và xoay phải (Right-rotation)
Từ trạng thái 1 -> trạng thái 2 ta có thao tác xoay trái đối với x. Ngược lại từ 2 -> 1 ta có thao tác xoay phải đối với y. Ta kiểm tra tính chất của cây nhị phân tìm kiếm hoàn toàn đảm bảo trong cả 2 trường hợp (các nút trái < gốc < các nút phải).
Phần cây xoay có thể là con trái hoặc con phải của P
.