HỌC PHẦN �PHÂN TÍCH VÀ THIẾT KẾ THUẬT TOÁN �NÂNG CAO
GIẢNG VIÊN: TS. PHAN ANH CANG
1
2
BÁO CÁO
THUẬT TOÁN RED BLACK TREE
(Cây tự cân bằng đỏ đen)
Học viên: Lý Phương Trang
Mã số học viên: 22904016
Mã lớp: 0CTT22A
1. Khái niệm về Red Black Tree
Cây đỏ đen hay Red-Black Tree là cây tìm kiếm nhị phân tự cân bằng, trong đó mỗi nút chứa thêm một bit để biểu thị màu của nút, đỏ hoặc đen.
Hay nói cách khác:
Cây đỏ đen (Red Black Tree) là cây nhị phân tìm kiếm tự cân bằng, đượ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, đảm bảo hiệu quả các thao tác trên cây.
3
1. Khái niệm về Red Black Tree
Một 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 lỏng hơn 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.
4
Minh họa
5
2. 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.
Lưu ý: Tính chất 4 và 5 là hai chính yếu để tạo nên tính chất cân bằng cho cây đỏ đen. Sử dụng hai tính chất này để chứng minh tính cân bằng của cây đỏ đen.
6
3. Tính cân bằng của cây đỏ đen
Tổng hợp 2 ý trên ta có n >= 2^bh -1 >= 2^(h/2) - 1. Suy ra:
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).
7
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), 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.
- Đổi màu (Flip-color): Từ đỏ thành đen hoặc ngược lại.
8
4. Các thao tác tái cấu trúc
9
Minh họa về xoay trái đối với x
Cây đỏ đen có các thao tác thêm, xóa, tìm kiếm, tìm phần tử trước, phần tử sau, duyệt... giống như ở cây nhị phân thông thường. Ở đây chỉ nói về phần cài đặt 2 thao tác chính mà đòi hỏi cây đỏ đen tự tái cấu trúc nó để đạt được sự cân bằng:
- Nút đỏ mang ý nghĩa là cây đang lệch về phía nhánh cây chứa nó.
- Nếu T là cây đỏ đen thì mọi cây con của T đều thỏa mãn tính chất 4 và 5.
10
5. Các thao tác
Ví dụ:
11
Ý tưởng: Trước hết thêm phần tử vào cây như ở cây nhị phân tìm kiếm thông thường và gán cho nút mới này màu đỏ. Sau đó kiểm tra xem liệu có 2 phần tử màu đỏ liên tiếp xảy ra không (2 nút đỏ liên tiếp mang ý nghĩa là việc thêm phần tử làm cây lệch nhiều hơn mức cho phép về phía đó). Nếu có bằng cách vận dụng các thao tác xoay cây và đổi màu.
12
5.1. Áp dụng thuật toán cây đỏ đen thêm phần tử (Insert)
Tóm tắt thuật toán Insert
- Thêm nút mới và gán màu của nút mới là đỏ.
- Sửa tình huống có 2 nút đỏ liên tiếp nếu nút cha cũng là đỏ bằng cách xem nhánh đối diện:
+ Nếu nút cần sửa là gốc (không có cha) thì chuyển màu đỏ sang đen.
+ Nếu nút chú là màu đen ta có thể sửa sự lệch của cây con đang xét bằng phép xoay cây sang phía nhánh của nút chú.
+ Nếu nút chú màu đỏ ta đổi màu nút cha và chú thành đen, nút ông thành đỏ rồi tiếp tục gọi đệ qui lên trên (đối với nút ông) để sửa nút đỏ này nếu cần.
13
Thuật toán thêm phần tử (Insert)
Sau khi thêm 1 phần tử vào cây (nút 20)
14
5.1. Áp dụng thuật toán cây đỏ đen thêm phần tử (Insert)
Ý tưởng: Kiểm tra cây đang lệch về phía nào bằng cách xem nút đỏ đang nằm ở đâu quanh chỗ nút muốn xóa và cố gắng chuyển chỗ lệch đó về phía nhánh của phần tử này. Thực hiện tìm cách chuyển màu của nút muốn xóa thành đỏ mà vẫn giữ tính chất cây đỏ đen bằng cách vận dụng các thao tác xoay cây và đổi màu, khi đó ta dễ dàng xóa phần tử mà vẫn giữ được tính cân bằng của cây.
15
5.2. Áp dụng thuật toán cây đỏ đen xóa (Delete)
Tóm tắt thuật toán xóa
- Thực hiện các bước xóa ban đầu giống với cây nhị phân tìm kiếm thông thường, đưa về trường hợp xóa x là nút lá hoặc chỉ có 1 con (ít nhất 1 nút con của x là NULL).
- Nếu nút cần xóa x là màu đỏ bỏ qua các bước sau để đến bước cuối cùng (xóa x khỏi cây).
- Nếu x là màu đen ta tìm cách chuyển màu x sang đỏ, hay nói cách khác là chuyển dịch sự lệch của cây sang nhánh muốn xóa (đỏ tượng trưng cho nhánh cây dài hơn). Ta tìm nút đỏ lần lượt ở các vị trí sau (đến khi tìm được thì dừng):
+ Con của x.
+ Nút anh em (sibling) của x.
+ Con của nút anh em.
+ Cha của x.
16
5.2. Áp dụng thuật toán cây đỏ đen xóa (Delete)
- Nếu không tìm thấy đỏ ở các vị trí trên, ta tìm cách chuyển màu nút cha của x sang màu đỏ (bằng cách gọi đệ quy bước 2 nhưng là đối với cha của x).
- Khi đã tìm được đỏ ở 1 trong các vị trí này có thể áp dụng các biện pháp xoay cây và đổi màu để chuyển x sang đỏ mà vẫn giữ được tính chất của cây.
- Xóa x khỏi cây như ở cây nhị phân tìm kiếm thông thường.
17
5.2. Áp dụng thuật toán cây đỏ đen xóa (Delete)
Xóa 1 phần tử trong cây (nút 48)
18
5.2. Áp dụng thuật toán cây đỏ đen xóa (Delete)
19
20
- Hầu hết các chức năng của thư viện cây BST tự cân bằng trong C++ (hoặc TreeSet và TreeMap trong Java) đều sử dụng cấu trúc cây đỏ đen.
- Lập lịch tiến trình CPU cho hệ điều hành Linux.
- Áp dụng vào trong thuật toán phân cụm K-mean nhằm giảm độ phức tạp về thời gian.
- Ngoài ra MySQL cũng sử dụng cây đỏ đen cho các chỉ mục trên bảng.
21
6. Ứng dụng của cây đỏ đen
CÁM ƠN THẦY �VÀ CÁC BẠN ĐÃ LẮNG NGHE !
22