Trình bày: Đặng Thị Xuân TIên

Cây

đỏ đen

Định Nghĩa: Cây đỏ đen:

1. Mọi Node trong cây phải là đỏ hoặc đen.

2. Node gốc là Node đen.

3. Các Node ngoài phải (NULL Node) luôn luôn đen.

4. Nếu một Node là đỏ thì những Node con của nó phải là đen (quy tắc xung đột).

5. Mọi đường dẫn từ Node gốc đến Node ngoài phải có cùng số lượng Node đen.

Cây đỏ đen (Red-Black Tree) là một cây nhị phân tìm kiếm (BST) tuân thủ theo các quy tắc sau:

TÍNH CHẤT

Thời gian tìm kiếm O một Node:�O(log N)

Giả sử cây đỏ đen có N Node thì khi đó:

h <= 2 * log(N + 1)

Trong đó:

h là chiều cao của cây.

h_b là chiều cao đen.

TÍNH CHẤT

Tính chất 1:

h <= 2 * h_b

Tính chất 2:

Tính chất 3:

• Tìm kiếm và duyệt cây (giống BST).
• Thêm Node mới (insert Node).
• Xóa Node (delete Node).

Các thao tác trên cây đỏ đen

Phép chèn

Phép chèn bắt đầu bằng việc bổ sung một nút như trong cây tìm kiếm nhị phân bình thường và gán cho nó màu đỏ. Ta xem xét để bảo toàn tính chất đỏ đen từ các nút lân cận với nút mới bổ sung. Chú ý: Nhãn N sẽ dùng để chỉ nút đang chèn vào, P chỉ nút cha của N, G chỉ ông của N, và U chỉ chú bác của N. Nhớ rằng,giữa các trường hợp, vai trò và nhãn của các nút có thể thay đổi còn trong cùng một trường hợp thì không.

​

Trường hợp 1: 

N

Trường hợp 2

NIL

Trường hợp 3: 

P

U

G

G

Trường hợp 4: 

Trường hợp 5: 

Phép Xóa

Phép Xóa

Nếu cả N và gốc ban đầu của nó là đen thì sau khi xóa các đường qua "N" giảm bớt một nút đen. Do đó vi phạm Tính chất 5, cây cần phải cân bằng lại. Có các trường hợp sau:

Phép Xóa

Trường hợp 1: 

N là gốc mới. Trong trường hợp này chúng ta dừng lại. Ta đã giải phóng một nút đen khỏi mọi đường đi và gôc mới lại là đen. Không tính chất nào bị vi phạm.

Phép Xóa

Trường hợp 2:

Phép Xóa

Phép Xóa

Trường hợp 3:

Phép Xóa

Trường hợp 4:

S và các con của S là đen nhưng P là đỏ. Trong trường hợp này, chúng ta đổi ngược màu của S và P. Điều này không ảnh hưởng tới số nút đen trên các đường đi không qua N, nhưng thêm một nút đen trên các đường đi qua N, thay cho nút đen đã bị xóa trên các đường này.

Phép Xóa

Trường hợp 5:

Trong lúc đó, với một đường đi không đi qua N, có hai khả năng:

đi qua nút anh em của N. Khi đó cả trước và sau khi quay nó phải đi qua S và P, khi thay đổi màu sắc hai nút này đã tráo đổi màu cho nhau. Như vây đường đi này không bị thay đổi số nút đen.

đi qua nút bác của N', là con phải của S. Khi đó trước khi quay nó đi qua S, cha của S, và con phải của S, nhưng sau khi quay nó chỉ đi qua nút S và con phải của S, khi này S đã nhận màu cũ của cha P còn con phải của S's đã đổi màu từ đỏ thành đen. Kết quả là số các nút đen trên đường đi này không thay đổi.

Như vậy, số các nút đen trên các đường đi là không thay đổi. Do đó các tính chất 4 và 5 đã được khôi phục. Nút trắng trong hình vẽ có thể là đỏ hoặc đen, nhưng phải ghi lại trước và sau khi thay đổi.

Phép Xóa

Trường hợp 6:

Các ứng dụng từ cây đỏ đen

• Xây dựng các thuật toán rất có hiệu quả để định vị các phần từ trong một danh sách
• Xây dựng các mạng máy tính với chi phí rẻ nhất cho các đường điện thoại nối các máy phân tán
• Cây cũng được dùng để tạo ra các mã có hiệu quả để lưu trữ và truyền dữ liệu
• Cấu trúc cây được ứng dụng trong các giải thuật tìm kiếm, giải thuật sắp xếp và nhiều bài toán khác
• Cây dùng để biểu diễn bài toán quyết định (cây quyết định), biểu diễn quá trình tính toán các biểu thức đại số.

​

02

03

04

05