CTDL2

TRƯỜNG ĐH CÔNG NGHỆ THÔNG TIN
NỘI DUNG
Cây đỏ đen
Các phép toán trên cây Đỏ-đen
Khái niệm cây đỏ đen
Cây đỏ đen là cây nhị phân tìm kiếm có các thuộc tính sau
1. Một nút hoặc là đỏ hoặc đen.
2. Tất cả các lá (nút NULL) là đen.
3. Nút gốc có màu đen
4. Cả hai con của mọi nút đỏ là đen. (và suy ra mọi nút đỏ có nút cha là đen.)
5. Không có 2 nút đỏ kề nhau (vậy nếu nút cha là đỏ thì các nút con phải là đen)
Ưu điểm của cây đỏ-đen
Tính chất 5 còn được gọi là tính chất "cân bằng đen".
Ưu điểm của cây đỏ đen nằm ở tính chất này
Do đó đường đi dài nhất từ gốc đến nút lá không quá 2 lần với đường đi ngắn nhất (cây nhị phân tìm kiếm có thể chênh lệch nhau N lần, trong trường hợp ta thêm vào 1 dãy khoá có thứ tự)
Khi tìm kiếm vị trí để thêm hay xoá 1 nút trên cây củng nhanh hơn cây nhị phân tìm kiếm.
Ví dụ về cây đỏ đen
Các phép toán trên cây đỏ-đen
Thêm 1 nút có khoá x vào cây
Loại bỏ 1 nút có khoá bằng x trong cây
Tìm kiếm 1 nút có khoá bằng x trong cây
Thêm 1 nút vào cây đỏ-đen
Nút muốn thêm vào luôn có màu đỏ
Khi thêm vào ta thêm như cây nhị phân tìm kiếm
Sau khi thêm ta phải điều chỉnh để phù hợp với các tính chất đỏ-đen.
Khi thêm 1 nút có khoá x vào cây có các trường hợp sau. Gọi X là nút mới thêm vào.
TH1: X có chú (bác) là nút đỏ
TH2: Chú của X có màu đen, X là nút con phải
TH3: Chú của X có màu đen, X là cây con trái

Trường hợp 1_1
C
D
A
B
1
2
3
4
5
C
D
A
B
1
2
3
4
5
X
X
X có chú (bác) là nút đỏ
P
U
Nếu C là nút gốc của cây
Trường hợp 1_2
5
X có chú (bác) là nút đỏ
5
C
D
A
B
1
2
3
4
X
Nếu C không là nút gốc của cây
Trường hợp 2
C
D
A
B
1
2
3
4
5
C
D
B
A
1
2
4
5
3
X
X
Chú của X có màu đen, X là nút con phải
P
U
Trường hợp 3
5
C
D
B
A
1
2
4
3
X
5
B
C
A
1
2
4
3
X
D
Chú của X có màu đen, X là cây con trái
P
U
Ví dụ minh họa
15
19
5
2
20
10
12
8
6
x
P
U
15
19
5
2
20
10
12
8
6
x
P
U
TH 2_1
Ví dụ minh họa
15
19
5
2
20
10
12
8
6
x
U
TH 2
15
19
10
2
20
5
12
8
6
P
U
P
x
Ví dụ minh họa
15
19
10
2
20
5
12
8
6
P
U
x
15
19
10
2
20
5
12
8
6
TH 3
Bài tập
10, 85, 15, 70, 20, 60, 30, 50, 65, 80, 90, 40, 5,55,16
Bài tập (tt)
Thêm 45 vào cậy trên
45
Thêm 45 (tt)
30
70
50
65
85
15
20
10
60
80
90
40
55
5
16
45
X
Thêm 45 (tt)
Xoá 1 nút trên cây
Tìm nút có khoá cần xoá
Xoá nút đó như xoá nút trong cây nhị phân tìm kiếm
Nút đã xoá có nhiều nhất 1 cây con
Nếu ta xoá nút có màu đỏ thì cây vẫn là cây đỏ-đen
Giả sử nút xoá là nút đen
Gọi x là con của nút đã xoá
Nếu x có màu đỏ, thì ta đổi lại màu đen -> stop
Nếu x là nút có màu đen thì sẽ rơi vào các trường hợp được xét như sau
Trường hợp 1
5
B
D
A
C
1
3
4
2
X
E
6
5
D
E
B
C
3
4
X
A
W
1
2
6
W
Anh em X là nút đỏ
Trường hợp 2-1
5
B
D
A
C
1
3
4
2
X
E
W
5
B
D
A
C
1
3
4
2
X
E
6
6
Anh em X là nút đen, cha của x là đen
Trường hợp 2-2
5
B
D
A
C
1
3
4
2
X
E
W
5
B
D
A
C
1
3
4
2
X
E
6
6
Anh em X là nút đen, cha của x là đỏ
Trường hợp 3
5
B
D
A
C
1
3
4
2
X
E
W
6
5
B
C
A
E
1
3
4
2
X
D
W
6
Anh em X là nút đen, cha của x tùy ý, con trái của nút anh em có màu đỏ, con phải của nút anh em có màu đen
Trường hợp 4
5
B
D
A
C
1
3
4
2
X
E
W
6
1
5
D
E
B
C
1
3
4
2
X
W
A
6
Anh em X là nút đen, cha của x tùy ý, con trái của nút anh em tùy ý , con phải của nút anh em có màu đỏ
Ví dụ xóa 1 nút trên cây
Xóa (tt)
20
70
60
65
85
15
16
10
60
80
90
40
55
5
Xóa nút
18
21
1
19
24
7
14
5
8
15
11
Xóa 11
Xóa nút (tt)
Xóa 14
18
21
1
19
24
7
5
8
13
X
Xóa nút (tt)
Xóa 14
18
21
1
19
24
7
5
8
13
X
Tìm 1 nút có khoá bằng x trong cây
Khi tìm 1 nút có khoá trong cây thì cũng tương tự như cây nhị phân tìm kiếm đã học.
Hết