Giáo trình Cây đỏ đen

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN 
 KHOA CÔNG NGHỆ THÔNG TIN 
 BỘ MÔN CẤU TRÚC DỮ LIỆU 2 
Lời nói đầu: 
 Cây đỏ đen là một trong những cấu trức dữ liệu hay, cùng với cây nhị phân tìm 
kiếm là những cấu trúc dữ liệu có điểm mạnh trong việc lưu trữ và tìm kiếm dữ liệu. 
Song cây đỏ đen có những đặc tính riêng mà nhờ đó nó đã làm nổi bật những điểm 
mạnh của mình. 
 Trong phạm vi bài báo cáo này, chúng em xin trình bài về : khái quát cây đỏ đen, 
các thuật toán cơ bản, code cài đặt các thuật tóan cơ bản và có những nhận xét về cấu 
trúc cây đỏ đen này. 
Chúng em chân thành cam ơn cô Phạm Phạm Tuyết Trinh đã tạo điều kiện cho 
chúng em tìm hiểu đề tài lý thú này. Dù hết sức cố gắng song vẫn không tránh được 
những sai xót nhất định chúng em mong được sư mong nhận được những đóng góp 
chân tình để bài làm trở nên hòan chỉnh hơn. 
 Nhóm thực hiện 
Cây Đỏ Đen 
 2 
Mục lục: 
Lời nói đầu: ..................................................................................................................... 1 
Mục lục: ........................................................................................................................... 2 
I- Giới thiệu: ................................................................................................................ 3 
II- Định nghĩa: .......................................................................................................... 5 
III- Các thuật toán cơ bản của Black and Red Tree ............................................... 6 
1- Thêm một Node mới ........................................................................................... 6 
2- Xóa một node: .................................................................................................... 14 
IV- Thuật toán cài đặt: ............................................................................................ 14 
V- Nhận xét : ........................................................................................................... 31 
Cây Đỏ Đen 
 3 
I- Giới thiệu: 
Cây đỏ đen được ra giới thiệu bởi Rudolf Bayer trong quyển “Symmetric Binary 
B-Trees: Data Structure and maintenance Algorithms”, nhà xuất bản Acta 
Informatica, Tâp1, trang 290-306. Sau đó Leonidas J.Guibas và Robert Sedgewick 
đã thêm các đặc tính của cây đỏ đen và đặt tên cho nó ( Tham khảo: Guibas, L. and 
Sedgewick R. “ A dichromatic Framwork for Balanced Trees”, in Proc. 19th IEEE 
Symp. Foundations of Computer Science, trang 8-21, năm 1978). 
Ta đã biết cây tìm kiếm nhị phân thông thường có những thuận lợi lớn về mặt lưu 
trữ và truy xuất dữ liệu trong phép toán tìm kiếm thêm vào hay loại bỏ một phần tử. 
Do đó, cây tìm kiếm nhị phân xem ra là một cấu trúc lưu trữ dữ liệu tốt. 
Tuy nhiên trong một số trường hợp cây tìm kiếm nhị phân có một số hạn chế. Nó 
hoạt động tốt nếu dữ liệu được chèn vào cây theo thứ tự ngẫu nhiên. Tuy nhiên, nếu 
dữ liệu được chèn vào theo thứ tự đã đuợc sắp xếp sẽ không hiệu quả. Khi các trị số 
Cây Đỏ Đen 
 4 
cần chèn đã đuợc sắp xếp thì cây nhị phân trở nên không cân bằng. Khi cây không 
cân bằng, nó mất đi khả năng tìm kiếm nhanh (hoặc chèn hoặc xóa) một phần tử đã 
cho. 
Chúng ta khảo sát một cách giải quyết vấn đề của cây không cân bằng: đó là cây đỏ 
đen, là cây tìm kiếm nhị phân có thêm một vài đặc điểm . 
Có nhiều cách tiếp cận khác để bảo đảm cho cây cân bằng: chẳng hạn cây 2-3-4. 
Tuy vậy, trong phần lớn trường hợp, cây đỏ đen là cây cân bằng hiệu quả nhất, ít ra 
thì khi dữ liệu được lưu trữ trong bộ nhớ chứ không phải trong những tập tin. 
Trước khi khảo sát cây đỏ đen, hãy xem lại cây không cân bằng được tạo ra như thế 
nào. 
Hình 3.1. Các node được chèn theo thứ tự tăng dần 
Những node này tự sắp xếp thành một đường không phân nhánh. Bởi vì mỗi node lớn 
hơn node đã được chèn vào trước đó, mỗi node là con phải. Khi ấy, cây bị mất cân 
bằng hoàn toàn. Nếu ta chèn những mục (item) theo thứ tự giảm dần, mỗi node sẽ là 
con trái của node cha của chúng - cây sẽ bị mất cân bằng về phía bên kia. 
* Độ phức tạp: 
Khi cây một nhánh, sẽ trở thành một danh sách liên kết, dữ liệu sẽ là một chiều thay vì 
hai chiều. Trong trường hợp này, thời gian truy xuất giảm về O(N), thay vì O(logN) 
đối với cây cân bằng. 
Để bảo đảm thời gian truy xuất nhanh O(logN) của cây, chúng ta cần phải bảo đảm cây 
luôn luôn cân bằng (ít ra cũng là cây gần cân bằng). Điều này có nghĩa là mỗi node trên 
cây phải có xấp xỉ số node con bên phải bằng số node con bên trái. 
Một cách tiếp cận giải quyết vấn đề cân bằng lại cây: đó là cây đỏ đen-là cây tìm kiếm 
nhị phân vì thế nó có các tính chất của cây tìm kiếm nhị phân ví dụ : node con trái nhỏ 
hơn node cha, node cha nhỏ hơn node con phải, bên cạnh đó cây đỏ đen còn được bổ 
sung một số đắc điểm. 
Cây
Tro
tử 
khô
cân
Cây
Kh
đen
 Đỏ Đen 
ng cây đỏ 
thì thủ tục
ng. Nếu c
 bằng. 
II- Đị
 đỏ đen là 
i chèn (hay
. Nếu được
M
đen, việc c
 chèn sẽ k
ó, sẽ xây d
nh ngh
một cây nh
Mọi node
Node gốc
Nếu một n
Mọi đườn
 xóa) một n
 tuân thủ, c
Số lượng n
cao đen (bl
là mọi đườn
Bổ đề: 
ột cây đỏ
ân bằng đư
iểm tra xem
ựng lại cấu
ĩa: 
ị phân tìm 
 phải là đỏ 
 và các nod
ode là đỏ, 
g dẫn từ gố
ode mới, c
ây sẽ được
H
ode đen trê
ack height)
g dẫn từ g
 đen n-nod
5
ợc thực thi 
 tính chấ
 trúc cây. 
kiếm( BST
hoặc đen. 
e lá phải lu
những nod
c đến một 
ần phải tuâ
 cân bằng. 
ình 3.2. Mộ
n một đườn
. Ta có thể 
ốc đến lá p
e 
trong khi c
t cân bằng
Bằng cách 
) tuân thủ c
ôn luôn đen
e con của n
lá phải có c
n thủ các q
t ví dụ về c
g dẫn từ gố
phát biểu q
hải có cùng
hèn, xóa. K
 của cây c
này, cây lu
ác quy tắc 
. 
ó phải đen
ùng số lượ
uy tắc trên 
ây đỏ đen 
c đến lá đư
uy tắc 4 th
 chiều cao 
hi thêm m
ó bị vi ph
ôn luôn đư
sau: (hình 
. 
ng node đe
-gọi là quy
ợc gọi là c
eo một cách
đen. 
ột phần 
ạm hay 
ợc giữ 
3.2) 
n. 
 tắc đỏ 
hiều 
 khác 
Cây Đỏ Đen 
 6 
Có: height <= 2 log(n+1) 
 height : Chiều cao cây 
Tính chất: height <= 2 * bh(x) 
Thời gian tìm kiếm: O( log n ) 
Chứng Minh: 
III- Các thuật toán cơ bản của Black and Red Tree 
1- Thêm một Node mới 
Chúng ta sẽ xem xét việc mô tả qui trình chèn. Gọi X, P, và G để chỉ định nhãn những 
node liên quan. X là node vi phạm quy tắc ( X có thể là một node mới được chèn, hoặc 
node con khi node cha và node con xung đột đỏ-đỏ, nghĩa là có cùng màu đỏ). 
· X là một node cho trước. 
· P là node cha của X. 
· G là node ông bà của X (node cha của P). 
Trong quá trình thêm vào node mới có thể vi phạm các quy tắc của cây đỏ đen, chúng 
ta sẽ thực hiện các thao tác sau đây: 
· Các phép lật màu trên đường đi xuống. 
Cây
· C
· C
1.1
Phé
đi t
trị 
Tuy
qua
Để
cần
có 
nod
Mộ
tam
nod
Hìn
 Đỏ Đen 
ác phép qu
ác phép qu
 Các p
p thêm vào
heo một đư
của khóa no
 nhiên, tro
y. 
 bảo đảm k
. Theo quy
hai node co
e cha là no
t phép lật m
 giác, node
e con trái v
h 3.4. Lật 
ay khi node
ay trên đườ
hép lật m
 trong cây 
ờng dẫn từ
de và khóa
ng cây đỏ đ
hông vi phạ
 tắc như sa
n đỏ, chún
de gốc, nó 
àu ảnh hư
 có màu đỏ
à phải của
màu 
 đã được c
ng đi xuốn
àu trên đư
đỏ đen bắt
 node gốc đ
 tìm kiếm.
en, đến đư
m các quy
u: nếu phép
g ta đổi các
vẫn vẫn gi
ởng đến cá
 trước phép
 P là X1 và
7
hèn. 
g. 
ờng đi xu
 đầu như trê
ến vị trí cầ
ợc điểm ch
 tắc màu, c
 thêm vào 
 node con t
ữ màu là đe
c quy tắc đ
 lật là P (P
 X2. Xem h
ống 
n cây tìm k
n chèn, đi 
èn là phức 
ần phải tiến
làm xuất hi
hành đen v
n). 
ỏ-đen ra sa
 thay cho n
ình 3.4a. 
iếm nhị ph
qua phải ha
tạp bởi các
 hành các p
ện tình trạn
à node cha
o? chúng ta
ode cha). C
ân thông th
y trái tùy v
 phép lật m
hép lật mà
g một nod
 thành đỏ (
 gọi node ở
húng ta gọ
ường: 
ào giá 
àu và 
u khi 
e đen 
trừ khi 
 đỉnh 
i hai 
Cây Đỏ Đen 
 8 
Hình 3.4a. trước khi lật màu, Hình 3.4b sau khi lật màu. 
Chúng ta nhận thấy sau khi lật màu chiếu con đen của cây không đổi. Như vậy phép lật 
màu không vi phạm quy tắc 4. 
Mặc dù quy tắc 4 không bị vi phạm qua phép lật, nhưng quy tắc 3 (một node con và 
node cha không thể đồng màu đỏ) lại có khả năng bị vi phạm. Nếu node cha của P là 
đen, không có vấn đề vi phạm khi P chuyển từ đen sang đỏ, nhưng nếu node cha của P 
là đỏ, thì sau khi đổi màu, ta sẽ có hai node đỏ trên một hàng. 
Điều này cần phải được chuẩn bị truớc khi đi xuống theo cây để chèn node mới. Chúng 
ta có thể giải quyết trường hợp này bằng một phép quay. 
Đối với node gốc thì phép lật màu node gốc và hai node con của nó vẫn làm cho node 
gốc cũng như hai node con có màu đen. Điều này tránh sự vi phạm quy tắc 2 và quy tắc 
3 (xung đột đỏ-đỏ). Trong trường hợp này, chiều cao đen trên mỗi đường đi từ node 
gốc tăng lên 1, do đó quy tắc 4 cũng không bị vi phạm. 
1.2 Các phép quay khi chèn node 
Thao tác chèn node mới có thể làm cho quy tắc đỏ-đen bị vi phạm. Do vậy sau khi 
chèn, cần phải kiểm tra xem có phạm quy tắc không và thực hiện những thao tác hợp 
lý. 
Như đã xét ở trên, node mới được chèn mà ta gọi là node X, luôn luôn đỏ. Node X có 
thể nằm ở những vị trí khác nhau đối với P và G, như trong hình 3.5. 
Cây
Hìn
X l
Điề
nod
Ng
Nế
nod
chá
Tha
và 
 Đỏ Đen 
h 3.5. Các 
à một node
u này có n
e con trái c
ược lại, X l
u X là node
e P ở bên t
u nội. Bốn
o tác phục
những bà c
biến dạng 
 cháu ngoạ
ghĩa là, X l
ủa G, hoặc
à một node
 cháu ngoạ
rái hay bên
 trường hợp
 hồi quy tắc
on của nó. 
của node đư
i nếu nó nằ
à node cháu
 nó là node
 cháu nội. 
i, nó có thể
 phải node 
 này được 
 đỏ-đen đư
Có 3 khả n
9
ợc chèn 
m cùng bên
 ngoại nếu
 con phải c
 hoặc bên t
G. Có hai k
trình bày tr
ợc xác địn
ăng xảy ra 
 node cha 
 hoặc nó là
ủa P và no
rái hoặc bê
hả năng tư
ong hình 3
h bởi các m
được xem x
P và P cùng
 node con t
de P là nod
n phải của 
ơng tự nếu
.5. 
àu và cấu h
ét như sau
 bên node 
rái của P v
e con phải 
P, tùy vào 
 X là một n
ình của no
:(hình 3.6)
cha G. 
à P là 
của G. 
việc 
ode 
de X 
Cây
Hìn
i) K
ii) K
iii)
Ch
i) K
P đ
xun
Do
ii) K
Nế
tha
cần
 Đỏ Đen 
h 3.6. Ba k
hả năng 1
hả năng 2
 Khả năng 
úng ta lần l
hả năng 1
en là trườn
g khắc đỏ-
 vậy, không
hả năng 2
u node P đỏ
y đổi về mà
 phải làm m
hả năng sa
: P đen 
: P đỏ và X
3: P đỏ và X
ượt xét các
: P đen 
g hợp đơn 
đỏ (quy tắc
 bị vi phạm
: P đỏ và X
 và X là no
u. Bắt đầu
ột phép lậ
u khi chèn 
 là cháu ng
 là cháu n
 khả năng c
giản. Node 
 3), và khô
 quy tắc v
 là cháu ng
de cháu ng
 với giá trị 
t màu trước
10
nút 
oại của G
ội của G 
ụ thể như s
thêm vào l
ng có việc 
ề màu. Tha
oại của G
oại, ta cần 
50 tại node
 khi chèn n
au: 
uôn đỏ. Nế
cộng thêm 
o tác chèn 
một phép q
 gốc, và ch
ode 12. 
u node cha
vào số nod
đã hoàn tất
uay đơn gi
èn các node
 đen, không
e đen (quy 
. 
ản và một v
 25, 75 và 
 có 
tắc 4). 
ài 
12. Ta 
Cây
Bây
phả
Tro
cân
Đ
Đ
Q
phé
Kh
Tro
đối
này
bằn
cây
 Đỏ Đen 
 giờ, chèn 
i có các th
ng trường 
 bằng cây. 
ổi màu nod
ổi màu nod
uay với no
p quay phả
i ta hoàn tấ
ng thí dụ n
 xứng khi n
 bằng cách
g cách đổi 
 lại được c
node mới X
ao tác như 
hợp này, ta
Sau đây là 
e G - node
e P - node 
de G (25) ở
i. 
t ba buớc tr
ày, node X
ode X là n
 tạo nên câ
màu node 
ân bằng. 
 là 6. (hìn
sau: (hình 3
 có thể áp d
các bước ấ
 ông bà của
cha của no
 vị trí đỉnh
ên sẽ bảo t
 là node ch
ode cháu ng
y 50, 25, 75
75 và 87, v
11
h 3.7a. )xuấ
.7) 
ụng ba bướ
y: 
 node X (tr
de X (node
, theo huớn
oàn cây đỏ
áu ngoại củ
oài nhưng
, 87, 93 (v
à quay trái 
t hiện lỗi: 
c để phục 
ong thí dụ 
 12) 
g làm nâng
 đen. Xem 
a một node
 của một no
ới phép lật 
với node 7
cha và con 
hồi tính đỏ
này là node
 node X lên
hình 3.7b. 
 con trái. C
de con phả
màu khi cầ
5 là node đ
đều đỏ, vì v
-đen và làm
 25). 
 (6). Đây l
ó một trườ
i. Thử làm
n). Chỉnh s
ỉnh. Một lầ
ậy cần 
 cho 
à một 
ng hợp 
 điều 
ửa cây 
n nữa 
Cây
Hìn
iii)
Nế
phé
lật 
Lưu
 Đỏ Đen 
h 3.7. Nod
 Khả năng 
u node P đỏ
p đổi màu.
màu trước 
 ý là node
e P đỏ và X
3: P đỏ và X
 và X là no
 Cây đỏ đe
khi chèn no
 18 là node
 là node ch
 là cháu n
de cháu nộ
n được tạo 
de 12). Xe
 cháu nội. N
12
áu ngoại 
ội của G 
i, chúng ta
thành từ cá
m hình 3.8
ode này v
 cần thực h
c node 50, 
a. 
à node cha 
iện hai phé
25, 75, 12 
đều đỏ (cha
p quay và m
và 18. (cần
 và con đề
ột vài 
 phải 
u đỏ). 
Cây
Hìn
Ch
ở đ
như
nod
 Đỏ Đen 
h 3.8. Khả
ỉnh lại sự sắ
ỉnh, như ta
 thế cây sẽ
e 12 ở đỉnh
 năng 3: P 
p xếp này 
 đã làm tron
 không còn
, để phục h
đỏ và X là n
cũng khá rắ
g khả năng
 cân bằng n
ồi cây nhu
13
hình 3.8.c
ode cháu n
c rối hơn. 
 2, node ch
hư trước. (
 cũ). Phải c
ội 
Nếu ta cố q
áu trong X
Thử làm đ
ần một giả
uay phải n
 (18) đi ng
iều này, rồi
i pháp khác
ode ông bà
ang hơn là 
 quay trở lạ
. 
 G (25) 
đi lên, 
i, với 
Cây
Thủ
Phé
3.8
phé
Ch
nào
nod
Đ
Đ
Q
đây
Q
typ
ST
ST
ST
ST
} S
 Đỏ Đen 
 thuật cần 
p quay đầu
b. Bây giờ,
p quay, vớ
úng ta cũng
 (thứ tự kh
e thì khó m
ổi màu nod
ổi màu nod
uay với no
 là 12). 
uay lần nữa
2- 
Chú
thì k
cũn
bảo
IV- Th
edef enum 
ATUS_OK
ATUS_ME
ATUS_DU
ATUS_KE
tatusEnum
dùng khi X
 biến X từ 
 trường hợp
i node ông 
 cần tô mà
ông quan tr
à biết phải
e ông bà củ
e X (không
de P - node
 với node 
Xóa m
ng ta đã bi
hó khăn ph
g vậy, thậm
 qui tắc của
uật toá
{ 
, 
M_EXHAU
PLICATE_
Y_NOT_F
; 
 là node ch
một node c
 là tương t
bà ở đỉnh, 
u lại các nú
ọng, nhưng
 gọi chúng
a node X (
 phải màu 
 cha của X 
ông bà của 
ột node:
ết trong cậy
ức tạp hơn
 chí còn ph
 cây đỏ đen
n cài đ
STED, 
KEY, 
OUND 
14
áu nội là ti
háu nội thà
ự như khả n
như đã làm
t. Ta làm đ
 nếu ta đợi
 như thế nà
 node 25).
của node c
- ở đỉnh (k
X (25) ở đỉ
 nhị phân t
 việc inser
ức tạp hơn
. 
ặt: 
ến hành ha
nh node ch
ăng 1, và t
 trước đây.
iều này trư
 đến khi sa
o). Các bướ
ha; node X
hông phải v
nh, về hướ
ìm kiếm vi
t 1 phần tử 
 vì trong qu
i phép quay
áu ngoại, n
a có thể áp
 Kết quả nh
ớc khi làm 
u khi quay 
c là: 
 đây là nod
ới node ôn
ng nâng X 
ệc xóa 1 ph
vào cậy, và
á trình thê
 hơn là mộ
hư trong h
 dụng cùng
ư trong hìn
bất cứ phép
mới tô màu
e 18). 
g bà; node 
lên (quay p
ần tử ra kh
 ở cây đỏ đ
m vào phải
t phép. 
ình 
 một 
h 3.8c. 
 quay 
 lại 
cha 
hải). 
ỏi cây 
en 
 đảm 
Cây Đỏ Đen 
 15 
typedef int KeyType; /* Kiểu dữ liệu khoá */ 
/* Dữ liệu lưu trữ */ 
typedef struct { 
int stuff 
} RecType; 
#define compLT(a,b) (a < b) 
#define compEQ(a,b) (a == b) 
/* Khai báo cấu trúc dữ liêu */ 
typedef enum { BLACK, RED } nodeColor; 
typedef struct NodeTag { 
struct NodeTag *left; /* Con trái */ 
struct NodeTag *right; /* Con phải */ 
struct NodeTag *parent; /* Cha */ 
nodeColor color; /* Màu node (BLACK, RED) */ 
KeyType key; /* Khoá sử dụng tìm kiếm */ 
RecType rec; /* Dữ liệu node */ 
} NodeType; 
typedef NodeType *iterator; 
#define NIL &sentinel /* Node cầm canh */ 
static NodeType sentinel = { &sentinel, &sentinel, 0, BLACK, 0}; 
static NodeType *root = NIL; /* Node gốc */ 
Cây Đỏ Đen 
 16 
/************************** 
* Xoay tráI node x * 
**************************/ 
static void rotateLeft(NodeType *x) { 
NodeType *y = x->right; 
/* Thiết lập liên kết x->right */ 
x->right = y->left; 
if (y->left != NIL) y->left->parent = x; 
/* Thiết lập liên kết y->parent */ 
if (y != NIL) y->parent = x->parent; 
if (x->parent) { 
if (x == x->parent->left) 
x->parent->left = y; 
else 
x->parent->right = y; 
} else { 
root = y; 
} 
/* link x and y */ 
y->left = x; 
if (x != NIL) x->parent = y; 
Cây Đỏ Đen 
 17 
} 
static void rotateRight(NodeType *x) { 
/**************************** 
* Xoay node x bên phải * 
****************************/ 
NodeType *y = x->left; 
/* Thiết lập liên kết x->left */ 
x->left = y->right; 
if (y->right != NIL) y->right->parent = x; 
/* Thiết lập liên kết y->parent */ 
if (y != NIL) y->parent = x->parent; 
if (x->parent) { 
if (x == x->parent->right) 
x->parent->right = y; 
else 
x->parent->left = y; 
} else { 
root = y; 
} 
/* liên kết x và y */ 
y->right = x; 
Cây Đỏ Đen 
 18 
if (x != NIL) x->parent = y; 
} 
/************************************* 
* Chương trình chính thêm node x vào cây đỏ đen* 
*************************************/ 
static void insertFixup(NodeType *x) { 
/* Kiểm tra thuộc tính đỏ đen */ 
while (x != root && x->parent->color == RED) { 
/* we have a violation */ 
if (x->parent == x->parent->parent->left) { 
NodeType *y = x->parent->parent->right; 
if (y->color == RED) { 
/* chú bác là RED */ 
x->parent->color = BLACK; 
y->color = BLACK; 
x->parent->parent->color = RED; 
x = x->parent->parent; 
} else { 
/* chú bác là BLACK */ 
if (x == x->parent->right) { 
/* tạo ra x là con trái*/ 
Cây Đỏ Đen 
 19 
x = x->parent; 
rotateLeft(x); 
} 
/* đổi màu và xoay */ 
x->parent->color = BLACK; 
x->parent->parent->color = RED; 
rotateRight(x->parent->parent); 
} 
} else { 
/* Tương tự như trên */ 
NodeType *y = x->parent->parent->left; 
if (y->color == RED) { 
/* chú bác là is RED */ 
x->parent->color = BLACK; 
y->color = BLACK; 
x->parent->parent->color = RED; 
x = x->parent->parent; 
} else { 
/* chú bác là BLACK */ 
if (x == x->parent->left) { 
x = x->parent; 
Cây Đỏ Đen 
 20 
rotateRight(x); 
} 
} 
x->parent->color = BLACK; 
x->parent->parent->color = RED; 
rotateLeft(x->parent->parent); 
} 
} 
root->color = BLACK; 
} 
/*********************************************** 
* Cấp phát và thêm vào trên cây * 
***********************************************/ 
StatusEnum insert(KeyType key, RecType *rec) { 
NodeType *current, *parent, *x; 
/Tìm cha mới*/ 
current = root; 
parent = 0; 
while (current != NIL) { 
if (compEQ(key, current->key)) 
return STATUS_DUPLICATE_KEY; 
Cây Đỏ Đen 
 21 
parent = current; 
current = compLT(key, current->key) ? 
current->left : current->right; 
} 
/* Thiết lập node mới */ 
if ((x = malloc (sizeof(*x))) == 0) 
return STATUS_MEM_EXHAUSTED; 
x->parent = parent; 
x->left = NIL; 
x->right = NIL; 
x->color = RED; 
x->key = key; 
x->rec = *rec; 
/* Thêm node */ 
if(parent) { 
if(compLT(key, parent->key)) 
parent->left = x; 
else 
parent->right = x; 
} else { 
root = x; 
Cây Đỏ Đen 
 22 
} 
insertFixup(x); 
return STATUS_OK; 
} 
/************************************* 
* Chương trình chính loại bỏ node x * 
*************************************/ 
void deleteFixup(NodeType *x) { 
while (x != root && x->color == BLACK) { 
if (x == x->parent->left) { 
NodeType *w = x->parent->right; 
if (w->color == RED) { 
w->color = BLACK; 
x->parent->color = RED; 
rotateLeft (x->parent); 
w = x->parent->right; 
} 
if (w->left->color == BLACK && w->right->color == BLACK) { 
w->color = RED; 
x = x->parent; 
} else { 
Cây Đỏ Đen 
 23 
if (w->right->color == BLACK) { 
w->left->color = BLACK; 
w->color = RED; 
rotateRight (w); 
w = x->parent->right; 
} 
w->color = x->parent->color; 
x->parent->color = BLACK; 
w->right->color = BLACK; 
rotateLeft (x->parent); 
x = root; 
} 
} else { 
NodeType *w = x->parent->left; 
if (w->color == RED) { 
w->color = BLACK; 
x->parent->color = RED; 
rotateRight (x->parent); 
w = x->parent->left; 
} 
if (w->right->color == BLACK && w->left->color == BLACK) { 
Cây Đỏ Đen 
 24 
w->color = RED; 
x = x->parent; 
} else { 
if (w->left->color == BLACK) { 
w->right->color = BLACK; 
w->color = RED; 
rotateLeft (w); 
w = x->parent->left; 
} 
w->color = x->parent->color; 
x->parent->color = BLACK; 
w->left->color = BLACK; 
rotateRight (x->parent); 
x = root; 
} 
} 
} 
x->color = BLACK; 
} 
StatusEnum erase(iterator z) { 
NodeType *x, *y; 
Cây Đỏ Đen 
 25 
if (z->left == NIL || z->right == NIL) { 
/* y có một node con là NIL */ 
y = z; 
} else { 
/* Tìm cây thay thế với node con NIL */ 
y = z->right; 
while (y->left != NIL) y = y->left; 
} 
/* y chỉ có một con */ 
if (y->left != NIL) 
x = y->left; 
else 
x = y->right; 
/* Xoá y */ 
x->parent = y->parent; 
if (y->parent) 
if (y == y->parent->left) 
y->parent->left = x; 
else 
y->parent->right = x; 
else 
Cây Đỏ Đen 
 26 
root = x; 
if (y != z) { 
z->key = y->key; 
z->rec = y->rec; 
} 
if (y->color == BLACK) 
deleteFixup (x); 
free (y); 
return STATUS_OK; 
} 
StatusEnum eraseKey(KeyType key) { 
NodeType *z; 
/* Tìm node */ 
z = root; 
while(z != NIL) { 
if(compEQ(key, z->key)) 
break; 
else 
z = compLT(key, z->key) ? z->left : z->right; 
} 
if (z == NIL) return STATUS_KEY_NOT_FOUND; 
Cây Đỏ Đen 
 27 
return erase(z); 
} 
iterator next(iterator i) { 
if (i->right != NIL) { 
for (i = i->right; i->left != NIL; i = i->left); 
} else { 
iterator p = i->parent; 
while (p && i == p->right) { 
i = p; 
p = p->parent; 
} 
/* trả về node "inorder" */ 
i = p; 
} 
return i; 
} 
iterator begin() { 
/* Trả về con trỏ đến giá trị đầu tiên */ 
iterator i; 
for (i = root; i->left != NIL; i = i->left); 
Cây Đỏ Đen 
 28 
return i; 
} 
iterator end() { 
/* Trả về con trỏ đến giá trị cuối cùng */ 
return NULL; 
} 
RecType value(iterator i) { 
return i->rec; 
} 
StatusEnum find(KeyType key, iterator *iter) { 
NodeType *current; 
current = root; 
while(current != NIL) { 
if(compEQ(key, current->key)) { 
*iter = current; 
return STATUS_OK; 
} else { 
current = compLT (key, current->key) ? 
current->left : current->right; 
} 
} 
Cây Đỏ Đen 
 29 
return STATUS_KEY_NOT_FOUND; 
} 
int main(int argc, char **argv) { 
int maxnum, ct, n; 
RecType rec; 
KeyType key; 
StatusEnum status; 
/* Chạy bằng dòng lệnh: 
* 
* rbt maxnum 
* 
* rbt 2000 
* Xữ lý 2000 records 
* 
*/ 
iterator iter; 
maxnum = atoi(argv[1]); 
printf("maxnum = %d\n", maxnum); 
for (ct = maxnum; ct; ct--) { 
key = rand() % 90 + 1; 
if ((status = find(key, &iter)) == STATUS_OK) { 
Cây Đỏ Đen 
 30 
rec = value(iter); 
if (rec.stuff != key) printf("fail rec\n"); 
status = erase(iter); 
if (status) printf("fail: status = %d\n", status); 
} else { 
rec.stuff = key; 
status = insert(key, &rec); 
if (status) printf("fail: status = %d\n", status); 
} 
/* Hiễn thị các node */ 
{ 
iterator i; 
for (i = begin(); i != end(); i = next(i)) { 
RecType rec; 
rec = value(i); 
printf("%d\n", rec.stuff); 
} 
} 
return 0; 
Cây Đỏ Đen 
 31 
V- Nhận xét : 
Giống như cây tìm kiếm nhị phân thông thường, cây đỏ đen có thể cho phép việc tìm 
kiếm, chèn và xóa trong thời gian O(log2N). Thời gian tìm kiếm là gần như bằng nhau 
đối với hai loại cây, vì những đặc điểm của cây đỏ đen không sử dụng trong quá trình 
tìm kiếm. Điều bất lợi là việc lưu trữ cần cho mỗi node tăng chút ít để điều tiết màu đỏ-
đen (một biến boolean). 
Đặc thù hơn, theo Sedgewick, trong thực tế tìm kiếm trên cây đỏ đen mất khoảng 
log2N phép so sánh, và có thể chứng minh rằng nó không cần hơn 2*log2N phép so 
sánh. 
Thời gian chèn và xóa tăng dần bởi một hằng số vì việc phải thực thi phép lật màu và 
quay trên đường đi xuống và tại những điểm chèn. Trung bình một phép chèn cần 
khoảng chừng một phép quay. Do đó, chèn hày còn chiếm O(log2N) thời gian, nhưng 
lại chậm hơn phép chèn trong cây nhị phân thường. 
Bởi vì trong hầu hết các ứng dụng, có nhiều thao tác tìm kiếm hơn là chèn và xóa, có lẽ 
không có nhiều bất lợi về thời gian khi dùng cây đỏ đen thay vì cây nhị phân thuờng. 
Dĩ nhiên, điều thuận lợi là trong cây đỏ đen, dữ liệu đã sắp xếp không làm giảm hiệu 
suất O(N).