ĐẠI HỌC HUẾ
TRƯỜNG ĐẠI HỌC KHOA HỌC
KHOA CÔNG NGHỆ THÔNG TIN
o0o
TIỂU LUẬN
THIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁN
Đề tài:
CÂY ĐỎ ĐEN (Red-Black Trees)
Giảng viên hướng dẫn: TS. HOÀNG QUANG
Nhóm 3 – KHMT 2009:
1. Đinh Như Du
2. Trương Thị Mỹ Lê
3. Nguyễn Thị Liên
4. Lê Văn Trường
Huế, 11-2014
Chương 13. Cây đỏ đen
L Ờ I N Ó I ĐẦU
Trong môn Cấu trúc dữ liệu và giải thuật chúng ta đã biết một cây nhị phân
tìm kiếm có chiều cao h có thể thực thi bất kỳ trong số các thao tác trên cây có
độ phức tạp O(h) thời gian. Như vậy, các thao tác trên cây sẽ thực hiện nhanh
nếu cây cân bằng; nhưng nếu nó có chiều cao lớn (ví dụ cây lệch trái, lệch
phải,…) khả năng thực hiện của các phép toán có thể không tốt hơn so với một
danh sách liên kết. Nhóm 3-Lớp KHMT-Khóa 2009-2011 đã may mắn được
thầy TS Hoàng Quang giao cho đề tài: ”Cây đỏ đen” là một trong số nhiều
dạng cây tìm kiếm "cân bằng" để đảm bảo các thao trên cây giảm độ phức tạp
xuống là O(lgn). Muốn làm điều đó khi thực hiện các thao tác trên cây, phải
giữ được tính chất của cây đỏ đen.
Nhóm 3 xin chân thành cảm ơn các bạn học viên trong lớp đã góp ý cho đề
tài, đặc biệt là thầy TS. Hoàng Quang đã tận tình hướng dẫn, góp ý để nhóm 3
có thể hoàn thành tốt đề tài khá mới mẻ này.
Chương 12 đã chứng tỏ một cây nhị phân tìm kiếm có chiều cao h có thể

thực thi bất kỳ trong số các phép toán tập hợp động căn bản như: SEARCH (tìm
1 Nhóm 3- KHMT 2009
Chương 13. Cây đỏ đen
kiếm), PREDECESSOR (tìm nút kế trước), SUCCESOR (tìm nút kế sau),
MINIMUM (tìm nút có khóa nhỏ nhất), MAXIMUM (tìm nút có khóa lớn
nhất), INSERT (chèn nút) và DELETE (xóa nút) - trong O(h) thời gian. Như
vậy, các phép toán tập hợp chạy nhanh nếu cây tìm kiếm có chiều cao nhỏ;
nhưng nếu nó có chiều cao lớn (ví dụ cây lệch trái, lệch phải,…) khả năng thực
hiện của các phép toán có thể không tốt hơn so với một danh sách liên kết. Các
cây đỏ đen là một trong số nhiều lược đồ cây tìm kiếm "cân bằng" để đảm bảo
các phép toán tập hợp động căn bản chiếm O(lg n) thời gian trong trường hợp
xấu nhất.
13.1. Các tính ch
13.1. Các tính ch
ấ
ấ
t c
t c
ủ
ủ
a cây đ
a cây đ
ỏ
ỏ
đen
đen
Một cây đỏ đen là một cây nhị phân tìm kiếm cộng thêm một bit lưu trữ
cho mỗi nút gồm: màu của nó, có thể là đỏ hoặc đen. Nhờ ràng buộc cách thức
tô màu các nút trên một đường đi bất kỳ từ gốc đến một lá, các cây đỏ đen đảm
bảo không có đường đi nào dài hơn gấp đôi so với bất kỳ đường đi nào khác,

sao cho cây xấp xỉ cân bằng.
Mỗi nút của cây giờ đây chứa các trường: color (màu sắc), key (khóa),
left (con trái), right (con phải), và p (cha). Nếu một con hoặc cha của một nút
không tồn tại, trường biến trỏ tương ứng của nút chứa giá trị NIL. Ta sẽ xem
các NIL này như là các biến trỏ đến các nút ngoài (các lá) của cây nhị phân tìm
kiếm và cây thường, các nút mang khóa bình thường xem như là các nút trong
của cây.
Một cây nhị phân tìm kiếm là một cây đỏ đen nếu nó thỏa mãn các tính
chất đỏ đen dưới đây:
1. Mọi nút là đỏ hoặc đen.
2. Nút gốc là đen.
3. Mọi nút lá (NIL) là đen.
4. Nếu một nút là đỏ, thì cả hai con của nó là đen.
5. Đối với mỗi nút, tất cả các đường đi từ nút đó tới các lá hậu duệ chứa
cùng số lượng các nút đen.
Hình 13.1(a) đưa ra một ví dụ của một cây đỏ đen. Một cây đỏ đen có các nút
đen tô sẫm và các nút đỏ tô bóng. Mọi nút trong một cây đỏ đen là đỏ hoặc đen,
mọi lá (nil) là đen, các con của một nút đỏ đều đen, và mọi đường đi đơn giản
từ một nút đến một lá hậu duệ chứa cùng số lượng nút đen.
2 Nhóm 3- KHMT 2009
Chương 13. Cây đỏ đen
Hình 13.1 (a) Mỗi nút lá xem như một nil là đen. Mỗi nút không nil được đánh
dấu với chiều cao đen của nó; nút NIL có chiều cao đen bằng 0.
Hình 13.1 (b) Giống với cây đỏ đen nhưng mỗi nút NIL được thay bằng cờ
hiệu đơn giản nil[T], mà nó luôn luôn đen và chiều cao đen được bỏ qua.
Cha của nút gốc cũng là cờ hiệu.
Để tiện lợi trong việc giải quyết với các mệnh đề điều kiện ranh giới
trong mã giải của cây đỏ đen, chúng tôi sử dụng một cờ hiệu đơn giản để miêu
3 Nhóm 3- KHMT 2009
1

7
2
0
10
1
5
3
3
0
3
5
3
9
2
6
4
1
1
4
2
1
1
9
2
3
1
6
7
1
2

4
7
2
8
3
8
14
nil[T]
(b)
17
20
10
15
3
30
35
39
26
41
14
21
19 2316
7
12
47
28 38
NIL NIL
NIL NIL NIL NIL NIL
NIL
NIL NIL

NIL NIL NIL NIL
NIL NIL
NIL
NILNIL
NIL
1
1
1
2
2
2
1
2
1
1
1
1
1
1
1
1
3
2
2
1
Chương 13. Cây đỏ đen
tả NIL. Cho một cây đỏ đen T, cờ hiệu nil[T] là một đối tượng với các trường
giống như một nút bình thường trong cây. Trường color của nó là đen, và các
trường khác - p, left, right và key có thể được gán giá trị bất kỳ. Như trong hình
13.1 (b) chỉ ra, tất cả các con trỏ NIL được thay thế bằng cờ hiệu nil[T].

Ta dùng cờ hiệu để có thể xem một con NIL của một nút x như là một nút
bình thường có cha là nút x. Mặc dù ta có thể thêm vào một nút cờ hiệu riêng
đối với mỗi NIL trong cây, để cha của mỗi NIL được định nghĩa hợp lý, cách
này sẽ gây lãng phí không gian (bộ nhớ). Thay vì ta dùng một cờ hiệu nil[T] để
biểu thị cho tất cả các NIL của tất cả các lá và cha của gốc. Các giá trị của các
trường p, left, right, và key của cờ hiệu là không quan trọng, mặc dù ta có thể
thiết lập chúng trong suốt quá trình của một thủ tục cho sự thuận lợi của chúng
ta.
Thông thường ta giữ sự quan tâm của chúng ta đối với các nút trong của
một cây đỏ đen, vì chúng chứa các giá trị khóa. Trong phần còn lại của chương
này, ta bỏ qua các lá khi ta vẽ một cây đỏ đen, như trong hình 13.1(c).
Hình 13.1 (c ) Giống với cây đỏ đen nhưng toàn bộ các lá và cha của gốc
được bỏ qua. Chúng tôi sẽ dùng cách vẽ này trong phần còn lại của chương này.
Ta gọi số lượng các nút đen trên bất kỳ đường đi nào từ một nút x (nhưng
không bao gồm x) đến một lá là chiều cao đen của nút (black height) ký hiệu là
bh(x). Theo tính chất 5, khái niệm của chiều cao đen được định nghĩa hợp lý, vì
tất cả các đường đi xuống từ một nút đều có cùng số lượng các nút đen. Ta định
nghĩa chiều cao đen của một cây đỏ đen là chiều cao đen của nút gốc.
Bổ đề sau chỉ ra tại sao các cây đỏ đen tạo các cây tìm kiếm tốt.
Bổ đề 13.1:
Một cây đỏ đen với n nút trong có chiều cao tối đa 2lg(n+1).
4 Nhóm 3- KHMT 2009
17
20
10
15
3
30
35
39

26
41
14
21
19 2316
7
12
47
28 38
(c)
Chương 13. Cây đỏ đen
Chứng minh:
Trước tiên ta chỉ ra rằng cây con có gốc tại một nút x bất kỳ sẽ chứa ít
nhất 2
bh(x)
- 1 nút trong. Ta chứng minh sự khẳng định định này bằng phương
pháp quy nạp trên chiều cao của x.
+ Nếu chiều cao của x là 0, x phải là một lá (nil[T]) và như vậy cây con
có gốc tại x chứa ít nhất 2
bh(x)
- 1= 2
0
- 1=0 nút trong.
+ Với bước quy nạp, ta xét một nút x có chiều cao dương và là một nút
trong có 2 con, mỗi con có một chiều cao đen là bh(x) hoặc bh(x)-1, tùy thuộc
vào màu của nó là đỏ hoặc đen, theo thứ tự nêu trên. Bởi chiều cao của một con
của x nhỏ hơn chiều cao của chính x, nên ta có thể áp dụng giả thiết quy nạp để
kết luận rằng mỗi con có ít nhất 2
bh(x)-1
- 1 nút trong.

Như vậy cây con có gốc tại x chứa ít nhất (2
bh(x)-1
- 1) + ( 2
bh(x)-1
-1 ) + 1
=2
bh(x)
- 1 nút trong, điều phải chứng minh.
Để hoàn chỉnh chứng minh của bổ đề cho h là chiều cao của cây. Theo
tính chất 4 của các cây đỏ đen ít nhất phân nửa các nút trên đường đi đơn giản
bất kỳ từ gốc đến một lá, không kể gốc phải là đen. Do vậy, chiều cao đen của
gốc phải ít nhất là h/2; như vậy n >= 2
h/2
- 1.
Việc dời 1 sang bên phía trái và lấy loga trên cả 2 phía sẽ cho ra
lg(n+1)>=h/2 hoặc h <= 2lg(n+1)
Một kết quả trực tiếp của bổ đề này đó là các phép toán tập hợp động
SEARCH, PREDECESSOR, SUCCESOR, MINIMUM, MAXIMUM có thể
được thực thi trong O(lg(n)) thời gian trên các cây đỏ đen, bởi chúng có thể
được thực hiện để chạy trong O(h) thời gian trên một cây tìm kiếm có chiều cao
h (như đã nêu trong chương 12) và bất kỳ cây đỏ đen nào có n nút đều là một
cây tìm kiếm với chiều cao O(lg(n)). (tất nhiên những vấn đề liên quan đến NIL
trong các thuật toán trong chương 12 phải được thay bằng nil[T]).
Mặc dù các thuật toán TREE-INSERT và TREE-DELETE ở chương 12
chạy trong O(lg(n)) thời gian khi cho một cây đỏ đen là giá trị vào. Nhưng
chúng không trực tiếp hỗ trợ các phép toán tập hợp động INSERT và DELETE,
bởi chúng không đảm bảo cây nhị phân đã sửa đổi sẽ là một cây đỏ đen. Tuy
nhiên như các phần 13.3 và 13.4 sẽ cho thấy 2 phép toán này có thể được hỗ trợ
trong O(lg(n)) thời gian.
5 Nhóm 3- KHMT 2009

Chương 13. Cây đỏ đen
Ta có khai báo cấu trúc cây đỏ đen như sau:
TRBNode = record
key: byte;
left, right, p: TRBNodeP;
color: String[5]; {Red, Black}
end;
Trong đó:
P: Nút cha (cha của x thì ký hiệu p[x]).
Root: Nút gốc.
Color: Chứa giá trị màu của nút.
6 Nhóm 3- KHMT 2009
Chương 13. Cây đỏ đen
Một số thao tác cơ bản trên cây đỏ đen:
Tương tự như cây nhị phân tìm kiếm, phép toán phổ biến trên cây đỏ đen
là tìm kiếm theo khóa được lưu trữ trong cây. Ngoài phép toán SEARCH, cây
đỏ đen có thể được chứng minh rằng với các phép toán như tìm nút có giá trị
nhỏ nhất, lớn nhất, nút kế trước nút x và nút kế sau nút x đều được thực hiện
trong O(h) thời gian, với h là chiều cao của cây.

Function SEARCH ( TRBNodeP TRBNodeP;
Begin
if (T= nil[T]) or (k = T^.key) then
SEARCH:=T
else
if k < T^.key then
SEARCH:= SEARCH(T^.left, k)
else SEARCH:= SEARCH(T^.right, k)
End;
Ví dụ, tìm khóa k=13 trong cây, có đường tìm kiếm:

15 → 6 → 7 → 13
k=25àSearch= nil[T]
 
Function Min(T: TRBNodeP): TRBNodeP;
Begin
while (T^.left <> nil[T]) do
T := T^.left;
Min:=T;
End;
Function Max(T: TRBNodeP): TRBNodeP;
Begin
while (T^.right <> nil[T]) do
T := T^.right;
Max:=T;
End;
Ví dụ:
Với cây đỏ đen ở bên,
+ Nút nhỏ nhất có giá trị =2
+ Nút lớn nhất có giá trị =20
7 Nhóm 3- KHMT 2009
Chương 13. Cây đỏ đen
!"#$%%& 
Giải thuật: Predecessor (x)
1 if left[x] ≠ nil[T]
2 then return Max(left[x])
3 y ← p[x]
4 while (y ≠ nil[T]) and (x = left[y]) do
5 x ← y
y ← p[y]
6 return y

Hàm tương ứng:
Function Predecessor ( x: TRBNodeP): TRBNodeP;
var y: TRBNodeP;
Begin
if (x^.left<> nil[T]) then
Predecessor:=Max(x^.left)
else
begin
y := x^.parent;
while (y<>nil[T]) and (x = y^.left) do
begin
x := y; y := y^.parent;
end;
Predecessor:=y;
end;
End;
Ví dụ: với cây đỏ đen ở bên: + Nút kế trước của 2 là Nil[T]
+ Nút kế trước của 20 là 18
'!%()*++,)) & 
Giải thuật: SUCCESSOR(x)
1 if right[x] ≠ nil[T]
2 then return Min(right[x])
3 y ← p[x]
4 while (y ≠ nil[T]) and (x = right[y]) do
5 x ← y
y ← p[y]
6 return y
Hàm tương ứng:
8 Nhóm 3- KHMT 2009
Chương 13. Cây đỏ đen

Function Successor (x: TRBNodeP): TRBNodeP;
var y: TRBNodeP;
begin
if (x^.right<> nil[T]) then
Successor :=Min(x^.right)
else
begin
y := x^.parent;
while (y<>nil[T]) and (x = y^.right) do
begin
x := y; y := y^.parent;
end;
Successor :=y;
end;
end;
Ví dụ:
Với cây đỏ đen như hình bên:
+ Nút kế sau của 13 là 15
+ Nút kế sau của 20 là nil[T]
Bài tập:
13.1-1: Trong mẫu hình 13.1 (a), vẽ cây nhị phân tìm kiếm hoàn chỉnh có chiều
cao 3 trên các khóa {1,2, ,15}. Bổ sung các lá NIL và tô màu các nút theo 3
cách khác nhau sao cho các chiều cao đen của các cây đỏ đen kết quả là 2, 3 và 4.
/01
+ Trường hợp chiều cao đen của cây là 2.
9 Nhóm 3- KHMT 2009
4
1
10
8

12
2
6
5 73
14
9
11
13
15
NIL NIL
NIL NIL
NIL NIL
NIL NIL
NIL NIL
NIL NIL
NIL NIL
NIL NIL
2
2
1
1
1
1
2
11
1
1
1
11
1

1
Chương 13. Cây đỏ đen
Trường hợp chiều cao đen của cây là 3.
Trường hợp chiều cao đen của cây là 4.
13.1-2: Vẽ cây đỏ đen mà kết quả của nó là sau khi thủ tục TREE-INSERT
được gọi trên cây trong hình 13.1 đối với khóa 36. Nếu nút được chèn vào là
màu đỏ, cây kết quả có phải là một cây đỏ đen không? kết quả là gì nếu nút
chèn vào có màu đen?
10 Nhóm 3- KHMT 2009
4
1
10
8
12
2
6
5 73
14
9
11
13
15
NIL NIL
NIL NIL
NIL NIL
NIL NIL
NIL NIL
NIL NIL
NIL NIL
NIL NIL

17
20
10
15
3
30
35
39
26
41
14
21
19 2316
7
12
47
28 38
NIL NIL
NIL NIL NIL NIL NIL
NIL
NIL NIL
NIL NIL NIL NIL
NIL NIL
NIL
NILNIL
NIL
1
1
1
2

2
2
1
2
1
1
1
1
1
1
1
1
3
2
2
1
4
1
10
8
12
2
6
5 73
14
9
11
13
15
NIL NIL

NIL NIL
NIL NIL
NIL NILNIL NIL
NIL NIL
NIL NIL
NIL NIL
Chương 13. Cây đỏ đen
/01Với cây đỏ đen ở trên, nút với khóa 36 sẽ được chèn vào ở vị trí con phải
của nút có khóa 35.
+ Nếu nút được chèn vào là màu đỏ, cây sẽ bị vi phạm tính chất 4. Do đó
nó không còn là cây đỏ đen.
+ Nếu nút được chèn vào là màu đen, cây sẽ bị vi phạm tính chất 5. Do
đó nó không còn là cây đỏ đen.
Qua đây chúng ta có nhận xét: nếu cho một cây đỏ đen là giá trị vào của
thủ tục TREE-INSERT thì kết quả có thể không còn là cây đỏ đen.
13.1-3: Chúng ta hãy đưa ra định nghĩa một cây đỏ đen yếu như một cây nhị
phân tìm kiếm mà nó thỏa mãn các tính chất chất đỏ đen 1, 3, 4 và 5. Nói cách
khác, gốc có thể là đỏ hoặc đen. Xét một cây đỏ đen yếu T, gốc của T là đỏ.
Nếu chúng ta tô màu đen cho gốc T nhưng không làm thay đổi T, kết quả cây
có phải là cây đỏ đen không?
/01 Kết quả cây vẫn là cây đỏ đen.
13.1-4: Giả sử chúng ta quan tâm đến mọi nút đỏ trong một cây đỏ đen thành
nút cha đen của nó, với mục đích là các con của nút đỏ trở thành các con của
cha đen (bỏ qua điều xảy ra với các khóa). Cấp của một nút đen có thể là gì sau
khi tất cả các con đỏ của nó được chú ý. Có thể nói điều gì với độ sâu của các
nút lá của cây kết quả?
/01
Sau khi tất cả các con đỏ của nó được chú ý, mức độ của mỗi nút màu
đen nút là:
+ 2, nếu cả hai nút con là màu đen,

+ 3, nếu một con là màu đen và một là màu đỏ, hoặc
+ 4, nếu cả hai con là màu đỏ.
Tất cả các lá của cây kết quả có độ sâu như nhau.
13.1.5: Chứng tỏ rằng đường đi đơn giản dài nhất từ một nút x trong một cây đỏ
đen đến một lá hậu duệ có chiều dài tối đa gấp đôi so với đường đi đơn giản
ngắn nhất từ nút x đến một lá hậu duệ.
/01
Trong đường đi dài nhất, ít nhất mọi nút khác là màu đen. Trong đường
đi ngắn nhất, nhiều nhất mọi nút là màu đen. Từ đó hai đường đi chứa cùng số
lượng các nút đen, chiều dài của đường đi dài nhất gấp tối đa hai lần chiều dài
của đường đi ngắn nhất.
Chúng ta có thể nói chính xác hơn điều này như sau:
Vì mọi đường đi chứa cùng số lượng bh(x) nút đen, ngay cả đường đi ngắn nhất
từ nút x tới các lá hậu duệ có độ dài tối thiểu là bh(x). Theo định nghĩa, đường
đi dài nhất từ nút x tới lá hậu duệ có chiều dài là height(x). Vì đường đi dài nhất
11 Nhóm 3- KHMT 2009
Chương 13. Cây đỏ đen
chứa bh(x) nút đen và có ít nhất một nửa số nút trên đường đi dài nhất là nút
đen (theo tính chất 4), tức là bh(x) >= height(x)/2. Bởi vậy, độ dài đường đi dài
nhất = height(x) <=2*bh(x) <= 2 lần độ dài đường đi ngắn nhất.


13.2. Các phép quay
13.2. Các phép quay
Các phép toán của cây nhị phân tìm kiếm TREE-INSERT và TREE-
DELETE, khi thực hiện trên một cây đỏ đen có n khóa, mất O(lg(n)) thời gian.
Do chúng sửa đổi cây nên kết quả có thể vi phạm các tính chất đỏ đen được nêu
trong đoạn 13.1. Để phục hồi các tính chất này ta phải thay đổi các màu của vài
nút và cũng thay đổi cấu trúc biến trỏ.
Ta thay đổi cấu trúc biến trỏ thông qua phép quay, mà nó là phép quay

cục bộ trong một cây tìm kiếm để bảo vệ các tính chất của cây nhị phân tìm
kiếm. Hình 13.2 chỉ ra hai loại phép quay; phép quay trái và phép quay phải.
Khi chúng ta thực hiện phép quay trái trên một nút x, ta thừa nhận rằng con phải
y của nó không phải là nil[T]; x có thể là một nút bất kỳ trong cây mà con phải
của nó không phải là nil[T]. Phép quay trái quay quanh đường nối từ x tới y. Nó
làm y trở thành nút gốc của cây con mới, với x thành con trái của y, con trái của
y thành con phải của x. Mã giải cho LEFT-RORATE thừa nhận rằng right[x]
≠
nil[T] và cha của gốc là nil[T].
23456 Các phép toán quay trên một cây nhị phân tìm kiếm. Phép toán
LEFT-RORATE(T, x) biến đổi cấu hình của hai nút bên trái thành cấu hình bên
phải bằng cách thay đổi một số biến trỏ bất biến. Cấu hình bên phải có thể
được biến đổi thành cấu hình bên trái bằng phép toán nghịch đảo RIGHT-
RORATE(T, y). Các mẫu tự
α
,
β
, và
γ
biểu thị cho các cây con tùy ý. Một
phép quay bảo toàn các tính chất của cây nhị phân tìm kiếm: các khóa trong
α
đứng trước key(x), key(x) đứng trước các khóa trong
β
, các khóa trong
β
đứng
trước key(y), key(y) lại đứng trước các khóa trong
γ
.

12 Nhóm 3- KHMT 2009
y
x
γ
β
α
x
y
β
γ
α
RIGHT-RORATE(T, y)
LEFT-RORATE(T, x)
Chương 13. Cây đỏ đen
LEFT-ROTATE(T, x)
1 y ← right[x] (*Đặt y là cây con phải của x*)
2 right[x] ← left[y] (*Quay nút con trái của y thành nút con phải của x*)
3 p[left[y]] ← x
4 p[y] ← p[x] (*Liên kết cha của y tới cha của x*)
5 if p[x] = nil[T]
6 then root[T] ← y
7 else if x = left[p[x]]
8 then left[p[x]] ← y
9 else right[p[x]] ← y
10 left[y] ← x (*Đặt x vào vị trí con trái của y*)
11 p[x] ← y
Hình 13.3 chỉ cách hoạt động của LEFT-RORATE. Mã của RIGHT-
RORATE cũng tương tự. Cả LEFT-RORATE lẫn RIGHT-RORATE đều chạy
trong O(1) thời gian. Phép quay chỉ thay đổi các biến trỏ; tất cả các trường khác
trong một nút vẫn giữ nguyên.

Hình 13.3 Một ví dụ về cách thức mà thủ tục LEFT-RORATE(T, x) sửa một cây
nhị phân tìm kiếm. Cây xuất hiện ở giá trị vào và cây đã sửa đổi đem lại danh
sách giá trị khóa giống nhau.
13 Nhóm 3- KHMT 2009
4
7
1
1
3
9
2
1
8
1
9
1
4
6
1
2
1
7
2
2
2
0
4
7
1
8

3
1
1
2
9
1
9
1
4
6
1
2
1
7
2
2
2
0
LEFT-ROTATE(T,x)
Chương 13. Cây đỏ đen
Bài tập:
13.2-1: Viết mã giải cho RIGHT-RORATE.
RIGHT-ROTATE(T, x)
1 y ← left[x] (*Đặt y là cây con trái của x*)
2 left[x] ← right[y] (*Quay nút con phải của y thành nút con trái của x*)
3 p[right[y]] ← x
4 p[y] ← p[x] (*Liên kết cha của y tới cha của x*)
5 if p[x] = nil[T]
6 then root[T] ← y
7 else if x = left[p[x]]

8 then left[p[x]] ← y
9 else right[p[x]] ← y
10 right[y] ← x (*Đặt x vào vị trí con phải của y*)
11 p[x] ← y
13.2-2: Chứng tỏ rằng cây tìm kiếm nhị phân n nút, có thể có chính xác n-1
phép quay.
13.2-3: Trong hình 13.2. sau:

Cho a, b và c là các nút tùy ý trong các cây con
α
,
β
, và
γ
theo thứ tự nêu trên,
trong cây trái của hình 13.2 (hình trên). Chiều sâu của a, b và c thay đổi ra sao
khi thực hiện một phép quay trái trên nút x trong hình?
/01 Chúng ta chuyển chiều sâu của các nút a, b, c trong cây sang khái niệm
chiều cao đen của chúng (giả sử chiều cao đen của các nút a, b, c trước khi thực
hiện phép quay trái là k). Khi thực hiện một phép quay trái trên nút x, chiều cao
đen của chúng sẽ không bị thay đổi (được bảo toàn).
Vấn đề này sẽ được thể hiện rõ hơn trong các bài tập của nội dung phép chèn.
13.2-4: Chỉ ra rằng có thể dùng O(n) phép quay để biến đổi bất kỳ cây tìm kiếm
nhị phân n- nút tùy ý thành một cây tìm kiếm nhị phân n-nút tùy ý bất kỳ khác.
/01 Trước tiên chứng tỏ rằng tối đa n-1 phép quay phải là đủ để biến đổi một
cây bất kỳ thành một chuỗi xích tiến phải.
14 Nhóm 3- KHMT 2009
y
x
γ

β
α
x
y
β
γ
α
RIGHT-RORATE(T, y)
LEFT-RORATE(T, x)
Chương 13. Cây đỏ đen
13.2-5: Ta nói rằng một cây tìm kiếm nhị phân T
1
có thể được biến đổi phải
thành cây tìm kiếm nhị phân T
2
nếu nó có thể thu được T
2
từ T
1
thông qua một
chuỗi lời gọi RIGHT-RORATE. Đưa một ví dụ hai cây T
1
và T
2
sao cho T
1
không thể được biến đổi phải thành T
2
. Khi đó chỉ ra rằng nếu một cây T
1

có thể
được biến đổi phải thành T
2
, nó có thể biến đổi phải dùng O(n
2
) lời gọi RIGHT-
RORATE.
13.3. Phép chèn
13.3. Phép chèn
Có thể thực hiện phép chèn một nút vào một cây đỏ đen n-nút
trong O(lg n) thời gian. Ta dùng một thủ tục mà nó là một sự sửa đổi không
đáng kể của thủ tục TREE-INSERT (đoạn 12.3) để chèn nút z vào cây T như
thể nó là một cây nhị phân tìm kiếm bình thường, sau đó ta tô đỏ z. Để bảo toàn
các tính chất đỏ-đen, ta gọi thủ tục RB-INSERT-FIXUP để tô màu lại các nút
và thực hiện các phép quay. Gọi thủ tục RB-INSERT(T,z) chèn nút z vào cây
đỏ đen T, giá trị trường khóa của z được thừa nhận là đã được điền vào.
Trước khi trình bày cụ thể về phép chèn một nút z vào cây đỏ đen, chúng
tôi đưa ra một ví dụ sau:
Chèn nút z có khóa bằng 15 vào
cây. Kết quả là trong cây có nút z và p[z]
đều có màu đỏ.
⇒ vi phạm tính chất 4.
Gọi y là nút chú bác của z (y chỉ đến
nút có khóa là 8 trong cây)
Chúng ta tiến hành các phép lật màu và
quay để sửa các vi phạm đối với cây đỏ đen này như sau:
1. Đổi màu p[z], y đỏ thành đen,
p[p[z]] thành đỏ; di chuyển z lên vị
trí p[p[z]].
⇒ tính chất 4 còn bị vi phạm.

15 Nhóm 3- KHMT 2009
Chương 13. Cây đỏ đen
2. z ← p[z]; RIGHT-ROTATE(T, z)
⇒ tính chất 4 còn bị vi phạm.
3. Đổi màu P[z] thành đen,
P[P[z]] thành đỏ;
LEFT-ROTATE(T, P[P[z]]
⇒ Cây đỏ đen không còn vi phạm
tính chất nào nữa.
Ta có thủ tục chèn như sau:
RB-INSERT(, 7)
1 y ← nil[T]
2 x ← root[T]
3 while x ≠ nil[T]
4 do y ← x
5 if key[z] < key[x]
6 then x ← left[x]
7 else x ← right[x]
8 p[z] ← y
9 if y = nil[T]
10 then root[T] ← z
11 else if key[z] < key[y]
12 then left[y] ← z
13 else right[y] ← z
14 left[z] ← nil[T]
15 right[z] ← nil[T]
16 color[z] ← RED
17 RB-INSERT-FIXUP(T, z)
Có 4 sự khác nhau giữa thủ tục TREE-INSERT và RB-INSERT. Đầu
tiên, các trường hợp NIL trong TREE-INSERT được thay bằng nil[T], Thứ hai,

16 Nhóm 3- KHMT 2009
Chương 13. Cây đỏ đen
Trong RB-INSERT chúng ta đặt left[z] và right[z] bằng nil[T] trong dòng 14-15
để duy trì đúng cấu trúc cây. Thứ 3, chúng ta tô đỏ cho z ở dòng 16, Thứ 4 vì
màu của z là đỏ nên có thể gây nên sự vi phạm một trong những tính chất của
cây đỏ đen. Chúng ta gọi thủ tục RB-INSERT-FIXUP(T,z) trong dòng 17 của
thủ tục RB-INSERT để khôi phục các tính chất của cây đỏ đen.
RB-INSERT-FIXUP(, 7)
1 while color[p[z]] = RED
2 do if p[z] = left[p[p[z]]]
3 then y ← right[p[p[z]]]
4 if color[y] = RED
5 then color[p[z]] ← BLACK ▹ TH 1
6 color[y] ← BLACK ▹ TH 1
7 color[p[p[z]]] ← RED ▹ TH 1
8 z ← p[p[z]] ▹ TH 1
9 else if z = right[p[z]]
10 then z ← p[z] ▹ TH 2
11 LEFT-ROTATE(T, z) ▹ TH 2
12 color[p[z]] ← BLACK ▹ TH 3
13 color[p[p[z]]] ← RED ▹ TH 3
14 RIGHT-ROTATE(T, p[p[z]]) ▹ TH 3
15 else (giống mệnh đề Then với "right" và "left" được tráo đổi)
16 color[root[T]] ← BLACK
Để hiểu cách thủ tục RB-INSERT-FIXUP làm việc như thế nào, chúng ta
sẽ xem xét mã của nó theo 3 bước chính. Trước hết, ta sẽ xác định sự vi phạm
các tính chất cây đỏ đen trong thủ tục RB-INSERT khi nút z được chèn và được
tô đỏ. Thứ hai ta xem xét mục tiêu chung của vòng lặp While trong các dòng từ
1-15. Cuối cùng chúng ta khảo sát mỗi trong số 3 trường hợp mà vòng lặp
While dừng và xem cách chúng hoàn thành mục tiêu như thế nào, hình 13.4 nêu

cách hoạt động của RB-INSERT trên một cây đen đỏ mẫu.
8 Tính chất đỏ đen nào có thể bị vi phạm khi gọi đến RB-INSERT-FIXUP?
Tính chất 1, 3 hiển nhiên đúng, vì hai con của nút đỏ mới chèn vào đều
được gán là nil[T]. Tính chất 5 nói rằng số lượng các nút đen là giống nhau trên
mọi đường đi từ một nút đã cho và nó cũng được thỏa mãn, bởi vì nút z thay thế
cho một nil[T] (đen) và nút z là đỏ với hai con nil[T]. Như vậy tính chất đáng
xem xét nhất có thể bị vi phạm là tính chất 2 đó là nút gốc phải là đen và tính
chất 4 là một nút đỏ không thể có 1 con đỏ. Cả 2 tính chất này có thể bị vi phạm
là do z được tô màu đỏ. Tính chất 2 bị vi phạm nếu z là gốc, và tính chất 4 bị vi
phạm nếu cha của z là đỏ. Hình 13.4 (a) chỉ ra 1 sự vi phạm tính chất 4 sau khi
nút z được thêm vào.
17 Nhóm 3- KHMT 2009
Chương 13. Cây đỏ đen
Vi phạm tính chất 2:
Vi phạm tính chất 4:
86mục tiêu chung của vòng lặp While trong các dòng từ 1-15?
Vòng lặp While ở dòng 1-15 đảm bảo cho 3 phần sau không thay đổi: Tại lúc
bắt đầu của mỗi lần lặp của vòng lặp:
a) Nút z là đỏ.
b) Nếu p[z] là gốc thì p[z] là đen
c) Nếu có một vi phạm tính chất cây đen đỏ, đó chỉ có thể là tính chất 2
hoặc là tính chất 4. Tính chất 2 vi phạm khi z là gốc và đỏ, tính chất 4 vi
phạm khi z và p[z] là đỏ.
Nói cách khác, mục tiêu chung của vòng lặp While là dời vi phạm đối với
tính chất 4 lên phía trên cây trong khi đó duy trì tính chất 5 dưới dạng một
bất biến.
Để giải quyết những vi phạm tính chất của cây đỏ đen, ta tập trung nhiều
hơn đến việc chỉ ra rằng thủ tục RB-INSERT FIXUP phục hồi các tính chất của
cây đỏ đen. Chúng ta sẽ tập trung vào nút z và những nút kề nó trong cây. Vì
nút z là đỏ. Chúng ta chứng tỏ rằng nút p[p[z]] tồn tại khi chúng ta xem xét nó ở

dòng 2,3,7,8,13,14.
(a)
18 Nhóm 3- KHMT 2009
Chương 13. Cây đỏ đen
(b)
c)
(d)
19 Nhóm 3- KHMT 2009
2
1
5
5
4
1
1
8
1
4
1
7
y
z
2
1
5
5
4
1
1
8

1
4
1
7
Trường hợp 1
z
y
2
1
5
5
4
1
1
8
1
4
1
7
Trường hợp 2
z
y
2
1
5
5
4
1
1
8

1
4
1
7
Trường hợp 3
z
Chương 13. Cây đỏ đen
Hình 13.4: Hoạt động của RB-INSERT-FIXUP. (a) Một nút z sau khi chèn. Vì z
và cha của nó p[z] cả hai đều là đỏ, một sự vi phạm đối với tính chất 4 xảy ra.
Do bác y của x là đỏ, ta có thể áp dụng trường hợp một trong mã. Các nút
được tô màu lại và biến trỏ z được dời lên cây, kết quả là cây được chỉ ra ở (b).
Một lần nữa, z và cha của nó cả hai đều có màu đỏ, nhưng bác y của z là đen.
Do z là con phải của p[z] nên trường hợp 2 có thể được áp dụng. Một phép
quay trái được thực hiện và cây kết quả được nêu trong (c). Giờ đây z là con
trái của cha nó, và trường hợp 3 có thể được áp dụng. Một phép quay phải cho
ra cây trong (d), đúng là một cây đỏ đen.
+(9: khảo sát mỗi trong số 3 trường hợp mà vòng lặp While dừng và
xem cách chúng hoàn thành mục tiêu như thế nào?
Nhớ rằng chúng ta cần chỉ ra rằng một vòng lặp bất biến là đúng trước
khi lần lặp đầu tiên mà mỗi lần lặp duy trì vòng lặp bất biến và vòng lặp bất
biến đó đưa ra cho chúng ta một tính chất quan trọng khi kết thúc vòng lặp.
Đầu tiên chúng ta xem xét đầu và cuối vòng lặp sau đó chúng ta sẽ xem
xét một cách chi tiết cách thân vòng lặp làm việc, chúng ta sẽ thấy rằng vòng
lặp duy trì tính bất biến trong mỗi lần lặp. Bằng cách này chúng ta cũng sẽ
chứng tỏ rằng có hai kết quả trong mỗi vòng lặp: z di chuyển lên cây, hoặc là
một số phép quay được thực hiện và vòng lặp kết thúc.
Đầu vòng lặp: Ưu tiên đối với vòng lặp đầu tiên, chúng ta bắt đầu với một cây
đen đỏ không có vi phạm, và chúng ta đã thêm vào một nút z đỏ. Chúng ta
chứng tỏ rằng các tính bất biến được duy trì vào lúc RB-INSERT FIXUP được gọi.
a) Khi RB-INSERT FIXUP được gọi, z là nút đỏ mà đã được thêm vào.

b) Nếu p[z] là gốc thì p[z] là đen và không thay đổi trước khi gọi thủ tục
RB-INSERT - FIXUP.
c) Chúng ta cũng thấy rằng tính chất 1,3, 5 được duy trì khi RB-INSERT-
FIXUP được gọi.
Nếu có vi phạm tính chất 2 khi đó nút gốc đỏ cần được thêm vào mới bởi nút z,
mà z là nút trong duy nhất trong cây. Bởi vì cha và hai con của z đều là nil[T]
(đen), cũng không vi phạm tính chất 4. Như vậy trường hợp này chỉ vi phạm
tính chất 2.
Nếu có vi phạm tính chất 4 thì khi đó bởi vì con của z là nil[T] (đen) và cây
không bị vi phạm tính chất nào cả trước khi z được thêm vào, sự vi phạm này là
cần thiết bởi vì cả z và p[z] là đỏ. Hơn nữa không vi phạm tính chất đỏ đen nào khác.
Cuối vòng lặp: Khi vòng lặp kết thúc nó thực hiện như vậy bởi vì p[z] là đen.
(Nếu z là gốc thì p[z] là nil[T] (đen)). Vì thế tính chất 4 không vi phạm ở cuối
vòng lặp. Chỉ tính chất 2 có thể vi phạm. Dòng 16 phục hồi tính chất này để khi
thủ tục RB-INSERT-FIXUP kết thúc thì tất cả các tính chất đỏ đen được thõa mãn.
20 Nhóm 3- KHMT 2009
Chương 13. Cây đỏ đen
Duy trì vòng lặp: Thật ra có 6 trường hợp để xem xét trong vòng lặp While
nhưng 3 trong số chúng tương ứng với 3 cái còn lại phục thuộc vào việc liệu
cha của z là con trái hay con phải của ông của z được xác định ở dòng 2. Chúng
ta đã đưa ra mã giải chỉ cho tình huống p[z] là con trái. Nút p[p[z]] tồn tại vì
qua vòng lặp bất biến nếu p[z] là gốc thi khi đó p[z] là đen. Một lần lặp được
thực hiện khi p[z] là đỏ, chúng ta biết rằng p[z] không thể là gốc. Vì thế p[p[z]] tồn tại.
Trường hợp 1 được phân biệt với trường hợp 2, 3 bằng cách tô màu y (nút chú
bác). Dòng 3 thực hiện y trỏ đến chú bác của z (right[p[p[z]]]) và việc kiểm tra
được thực hiện ở dòng 4. Nếu y là đỏ thì trường hợp 1 được thực hiện. Ngược
lại, thực hiện trường hợp 2 và 3. Trong tất cả 3 trường hợp p[p[z]] là đen vì cha
của nó p[z] là đỏ và tính chất 4 bị vi phạm vì z và p[z] là đỏ.
Trường hợp 1: Chú bác của z là đỏ. Hình 13.5 chỉ ra tình huống cho trường
hợp 1 (dòng 5-8). Trường hợp 1 được thực hiện khi cả p[z] và y là đỏ. Khi

p[p[z]] là đen thì chúng ta có thể tô màu cả p[z] và y là đen. Bằng cách sửa màu
thành đen của z và p[z] khi cả hai đều đang đỏ và màu của p[p[z]] từ đen thành
đỏ vì vậy thỏa mãn tính chất 5. Khi đó chúng ta lặp lại vòng lặp While với
p[p[z]] như là một nút z mới. Con trỏ z di chuyển lên hai mức trong cây.
Bây giờ chúng ta chứng tỏ rằng trường hợp 1 duy trì vòng lặp bất biến khi bắt
đầu lần lặp kế tiếp. Chúng ta sử dụng z để biểu thị nút z trong lần lặp hiện thời
và z'=p[p[z]] để biểu thị nút z tại bước kiểm tra ở dòng 1 trên lần lặp tiếp theo.
a) Bởi vì lần lặp này tô màu p[p[z]] đỏ, nút z' đỏ vào lúc bắt đầu lần lặp kế tiếp.
b) Nút p[z'] là p[p[p[z]]] trong lần lặp này và màu của nút này không thay
đổi. Nếu nút này là gốc thì nó là đen đối với lần lặp này và nó vẫn đen tại
lúc bắt đầu của lần lặp kế tiếp.
c) Chúng ta cũng đã chứng tỏ rằng trường hợp 1 thõa mãn tính chất 1,3,5.
Nếu nút z' là gốc khi bắt đầu lần lặp kế tiếp thì khi đó trường hợp 1 làm thỏa
mãn tính chất 4. Khi z' là đỏ và là gốc thì tính chất 2 là tính chất duy nhất bị vi
phạm và vi phạm này liên quan đến z'
(a)
21 Nhóm 3- KHMT 2009
z
A
B
D
C
α
δ
ε
γ
β
y
A
B

D
C
α
δ
ε
γ
β
new z
Chương 13. Cây đỏ đen
(b)
Hình 13.5 Trường hợp 1 của thủ tục RB-INSERT. Tính chất 4 bị vi phạm vì z và
cha của z đều là đỏ. Cùng một hành động được thực hiện ở (a) z là con phải,
hoặc ở (b) z là con trái. Mỗi cây con
δγβα
,,,
và
ε
đều có một gốc là đen và
mỗi cây con đều có cùng chiều cao đen. Mã của trường hợp 1 sẽ thay đổi các
màu của vài nút, bảo toàn được tính chất 5: tất cả các lộ trình đi xuống từ một
nút đến một lá đều có cùng số lượng nút đen. Vòng lặp While tiếp tục với ông
nội p[p[z]] của nút z làm z mới. Mọi vi phạm đối với tính chất 4 giờ đây chỉ có
thể xảy ra giữa z mới là đỏ và cha của nó nếu nó cùng màu đỏ.
Nếu nút z' không phải là nút gốc vào lúc bắt đầu của vòng lặp kế tiếp khi đó
trường hợp 1 không tạo nên sự vi phạm tính chất 2. Trường hợp 1 khi đó là đúng và
nó chỉ vi phạm tính chất 4 và nó thoát khỏi lúc bắt đầu vòng lặp này. Khi đó nó làm
z' đỏ và con trái của p[z']. Nếu p[z'] là đen thì tính chất 4 không bị vi phạm. Nếu
p[z'] là đỏ, màu z' đỏ tạo nên một sự vi phạm tính chất 4 giữa z' và p[z'].
Trường hợp 2: Chú bác y của z là đen và z là con phải.
Trường hợp 3: Chú bác y của z là đen và z là con trái.

Trong trường hợp 2 và 3 màu của chú bác y của z là đen. Hai trường hợp
được phân biệt bởi z hoặc là con trái hoặc là con phải của p[z]. Dòng 10-11 tạo
nên trường hợp 2, mà nó được chỉ ra trong hình 13.6 cùng với trường hợp 3.
Trong trường hợp 2 nút z là con phải của cha của nó. Chúng ta dùng ngay phép
quay trái để chuyển sang trường hợp 3 (dòng 12-14), lúc đó z là con trái. Bởi vì
cả z và p[z] là đỏ, phép quay không ảnh hưởng đến chiều cao đen của nút cũng
như tính chất 5.
Chúng ta xem xét trường hợp 3 trực tiếp hay thông qua trường hợp 2, nút
chú bác y của z là đen, thì khi đó mặt khác chúng ta cũng phải thực hiện trường
hợp 1.Thêm vào đó nút p[p[z]] tồn tại, khi đó chúng ta đã chứng tỏ rằng nút đã
tồn tại lúc này ở dòng 2 và 3 được thực hiện, và sau khi di chuyển z lên một
mức ở dòng 10 và xuống một mức ở dòng 11, sự đồng nhất của p[p[z]] vẫn
không thay đổi. Trong trường hợp 3 chúng ta thực hiện một vài phép đổi màu
và một phép quay phải mà nó vẫn bảo toàn tính chất 5 và khi ấy chúng ta không
22 Nhóm 3- KHMT 2009
z
ε
B
A
D
C
α
δ
γ
β
y
ε
B
A
D

C
α
δ
γ
β
new z
Chương 13. Cây đỏ đen
còn có hai nút đỏ trong một hàng. Thân của vòng lặp While không thực hiện
thêm lần nữa vì p[z] bây giờ là đen.
Hình 13.6: Các trường hợp 2 và 3 của thủ tục RB-INSERT. Như trong trường
hợp 1, tính chất 4 bị vi phạm trong trường hợp 2 hoặc trường hợp 3 bởi z và
cha p[z] của nó là đỏ. Mỗi cây con
δγβα
,,,
và
ε
đều có một gốc là đen và mỗi
cây con đều có cùng chiều cao đen. Trường hợp 2 được biến đổi thành trường
hợp 3 bằng một phép quay trái để bảo toàn tính chất 5: tất cả các lộ trình đi
xuống từ một nút đến một lá đều có cùng sô lượng nút đen. Trường hợp 3 tạo
nên vài thay đổi màu và một phép quay phải, cũng bảo toàn tính chất 5. Sau đó, vòng
lặp While kết thúc, bởi tính chất 4 được thỏa: không còn hai nút đỏ trong một hàng.
Bây giờ chúng ta chỉ ra rằng thân của vòng lặp While duy trì một vòng lặp
bất biến trong trường hợp 2 và 3.(Vì chúng ta đã chứng tỏ rằng p[z] sẽ là đen
vào lúc kiểm tra tiếp theo ở dòng 1 và thân vòng lặp không được thực hiện lại).
a. Trong trường hợp 2 con trỏ z trở thành p[z], nó là đỏ. Không có sự thay
đổi nào nữa đối với z và màu của nó xảy ra trong trường hợp 2 và 3.
b. Trường hợp 3 làm cho p[z] trở thành đen sao cho nếu nó là nút gốc vào
lúc bắt đầu vòng lặp kế tiếp nó là đen.
c. Như trong trường hợp 1, tính chất 1,3 và 5 được bảo toàn trong trường hợp 2 và 3.

Khi nút z không phải là nút gốc trong trường hợp 2 và 3, ta biết rằng không
có sự vi phạm tính chất 2. Trong trường hợp 2 và 3 không giới thiệu một sự vi
phạm tính chất 2. Khi đó chỉ một nút được tạo thành đỏ trở thành con của một
nút đen bằng cách thực hiện phép quay trong trường hợp 3.
Trường hợp 2 và 3 xác đinh chỉ một sự vi phạm tính chất 4 và không giới
thiệu một sự vi phạm khác.
Mỗi lần lặp của vòng lặp duy trì tính bất biến, ta đã chỉ ra rằng thủ tục RB-
INSERT-FIXUP phục hồi đúng các tính chất của cây đỏ đen.
Phân tích: RB-INSERT chạy trong thời gian gì? Khi chiều cao của một cây đỏ
đen trên n nút là O(lg n), dòng 1-16 của RB-INSERT mất O(lg n) thời gian.
Trong RB-INSERT-FIXUP, vòng lặp While lặp lại nếu trường hợp 1 được thực
hiện và khi đó con trỏ z di chuyển lên hai mức của cây. Tổng số lượng thời gian
của vòng lặp While có thể được thực hiện do đó là O(lg n). Vì thế, RB-INSERT
23 Nhóm 3- KHMT 2009
A
B
C
α
δ
γ
β
B
A
C
α
δ
γ
β
A
C

B
α
δ
γ
β
Chương 13. Cây đỏ đen
mất tổng thời gian O(lg n). Điều thú vị là ở chỗ, nó không bao giờ thực hiện hơn hai
phép quay, khi đó vòng lặp while kết thúc nếu trường hợp 2 và 3 được thực hiện.
Bài tập:
13.3.1: Trong dòng 16 của thủ tục R-INSERT, chúng ta đặt màu của nút mới
chèn vào là đỏ. Chú ý rằng nếu ta đã chọn để ấn định màu của z là đen, thì tính
chất 4 của một cây đỏ đen sẽ không bị vi phạm. Tại sao ta không chọn màu của
z là đen.
/01 Bởi vì lúc này việc chèn một nút mới vào cây không vi phạm tính
chất 1, 2, 3, 4 của cây đỏ đen. Tuy vậy, tính chất 5 lại bị vi phạm và việc sửa
tính chất 5 là phức tạp. Do vậy, ta ta không chọn màu của z là đen.
13.3.2: Nêu kết quả của cây đỏ đen sau khi chèn thành công các khóa
41,38,31,12,19,8 vào một cây đỏ đen trống từ đầu.
/01
+ Sau khi chèn nút z = 41, sự vi phạm đối với tính chất 2 đã xẩy ra đối với cây,
vì cây chỉ có một nút duy nhất nên màu của nút 41 được đổi thành đen.
+ Sau khi chèn nút z =31, sự vi phạm đối với tính chất 4 đã xẩy ra đối với cây,
cây được phục hồi và được kết quả như hình sau.
+ Sau khi chèn nút z =12, sự vi phạm đối với tính chất 4 đã xẩy ra đối với cây,
cây được phục hồi và được kết quả như hình sau.
24 Nhóm 3- KHMT 2009