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
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
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. 19
th
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.


y Đỏ Đen
ong cây đỏ
thì thủ tụ
c
ông. Nếu c
n bằng.
II- Đị

y đỏ đen là
hi chèn (hay
n. Nếu được
M
đen, việc 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
y xóa) một n
c tuân thủ, c
Số lượng n
cao đen (b
l
là mọi đườn
Bổ đề:
Một cây đỏ

Hình 3.2. Mộ
n một đườn
). Ta có thể
gốc đến lá p
de
trong khi c
ất cân bằng
Bằng cách
T) tuân thủ c
uôn luôn đen
de con của n
lá phải có c
ân thủ các q

ột ví dụ về c
ng dẫn từ gố
phát biểu q
hải có cùng
chèn, xóa. K
g của cây c
này, cây lu
các quy tắc
n.
nó phải đen
cùng số lượ
quy tắc trên
ây đỏ đen
ốc đến lá đư
quy tắc 4 th
g chiều cao

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
· C1.
1

Ph
é
đi t
trị
Tu
y
qua
Để
cầ
n

ode và khóa
ong cây đỏ đ
không vi phạ
y tắc như sa
on đỏ, chún
ode gốc, nó
màu ảnh hư
e có màu đỏ
và phải của
màu
e đã được c
ờng đi xuốn
àu trên đư
đỏ đen bắt
ừ node gốc đ
a tìm kiếm.
đen, đến đư
ạm các quy
au: nếu phép
ng ta đổi các
vẫn vẫn gi
ưởng đến cá
ỏ trước phép
a P là X1 và
7
chèn.
ng.
ường đi xu
t đầu như trê
đến vị trí cầ

hân thông th
ay trái tùy v
c phép lật m
phép lật mà
ng một nod
a thành đỏ (
a gọi node ở
Chúng ta gọhường:
vào giá
màu và
àu khi
de đ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.

gược lại, X l
u X là node
de P ở bên t
áu nội. Bốn
ao tác phục
những bà c
biến dạng
e cháu ngoạ
nghĩa là, X l
của G, hoặc
là một node
e cháu ngoạ
trái hay bên
n trường hợp
c hồi quy tắc
con của nó.
của node đư
ại nếu nó nằ
là node cháu
c nó là node
e cháu nội.
ại, nó có thể
n phải node
p này được
c đỏ-đen đư
Có 3 khả n
9
ược chèn
ằm cùng bên
u ngoại nếu

hình của no
u:(hình 3.6)cha G.
và P là
của G.
việc
node
ode X
Cây

Hì
n
i) K
ii) K
iii)
C
h
i) K
P đ
xun
Do
ii) K
Nế
th
a
cần
y Đỏ Đen
nh 3.6. Ba k

c 3), và khô
m quy tắc v
X là cháu ng
ode cháu ng
u với giá trị
ật màu trước
10

nú
t
goại của G
nội của G
cụ thể như s
thêm vào l
ông có việc
ề màu. Th
a
goại của G
goại, ta cần
50 tại nod
e
c khi chèn n
sau:
luôn đỏ. Nế
cộng thêm
ao tác chèn
một phép
q
e gốc, và ch
node 12.

này
bằn
cây
y Đỏ Đen
y giờ, chèn
ải có các th
ong trường
n bằng cây.
Đổi màu nod
Đổi màu nod
Quay với no
ép quay phả
hi ta hoàn tấ
ong thí dụ n
i xứng khi n
y bằng cách
ng cách đổi
y lại được c
node mới X
ao tác như
hợp này, t
a
Sau đây là
de G - node
de P - node
de G (25)
ở
ải.
ất ba buớc tr
này, node X

ớc để phục
rong thí dụ
e 12)
ng làm nâng
đen. Xem
ủa một node
g của một no
với phép lật
với node 7
cha và con
hồi tính đ
ỏ
này là node
g node X lên
hình 3.7b.
e con trái. C
ode con phả
màu khi cầ
5 là node đ
đều đỏ, vì
v
ỏ-đen và làm
e 25).
n (6). Đây l
Có một trườ
ải. Thử làm
ần). Chỉnh s
ỉnh. Một lầ
khi chèn no
18 là node
X là node ch
X là cháu n
ode cháu nộ
en được tạo
ode 12). Xe
cháu nội. N
12
háu ngoại
nội của G
ội, chúng ta
thành từ cá
em hình 3.8
Node này v
a cần thực h
ác node 50,
a.
à node cha
hiện hai phé
25, 75, 12
đều đỏ (ch
a
ép quay và m
và 18. (cần
a và con đềmột vài
n phải