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
NGUYỄN HOÀI PHƯƠNG -0212234
NGUYỄN HỒNG PHÚ -0212226

BÀI BÁO CÁO MÔN CẤU TRÙC DỮ LIỆU 2
GVHD : Ths . Phạm Phạm Tuyết Trinh
TP HCM , 2005
Cây Đỏ Đen Tháng 6 năm 2005
Nguyễn Hoài Phương 2 Nguyễn Hồng Phú
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ủ


Cây Đỏ Đen Tháng 6 năm 2005
Nguyễn Hoài Phương 3 Nguyễn Hồng Phú
Mục lục:
Lời nói đầu: ..................................................................................................................... 2

Mục lục: ........................................................................................................................... 3

I-

Giới thiệu: ................................................................................................................ 4

II-

Định nghĩa: .......................................................................................................... 5

III-

Các thuật toán cơ bản của Black and Red Tree ............................................... 7

1-

Thêm một Node mới ........................................................................................... 7

Cây Đỏ Đen Tháng 6 năm 2005
Nguyễn Hoài Phương 4 Nguyễn Hồng Phú
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. 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

Mộ
nhị
hơn
sun
Tro
tử
kh
ô
cân
Cây
Kh
đen
y Đỏ Đen
guyễn Hoài
hững node n
n node đã đ
ng hoàn toà
n trái của no
Độ phức tạp
hi cây một n
i chiều. Tro
i với cây câ
bảo đảm th
ôn luôn cân
y phải có xấ
ột cách tiếp
ị phân vì th
n node cha,
ng một số đ
ong cây đỏ

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
xếp thành m
vào trước
chèn những
a chúng - câ
ở thành mộ
hợp này, t
uy xuất nhan
cũng là cây
de con bên p
uyết vấn đề
c tính chất c
nhỏ hơn no
ân bằng đư
kiểm tra xem
dựng lại cấu
hĩa:

hị phân tìm
phải là đỏ
và các no
d
node là đỏ,
ng dẫn từ gố

m) theo thứ
t cân bằng v
h liên kết, d
uy xuất giả
) của cây, ch
ằng). Điều
số node con
lại cây: đó l
m kiếm nhị p
ải, bên cạnh
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

Thá
n
Nguy
n nhánh. Bở
phải. Khi ấ
ứ tự giảm dầ
về phía bên
dữ liệu sẽ là
ảm về O(N
húng ta cần
này có ngh

ợng node đe
-gọi là quy
005
Phú
node lớn
mất cân
de sẽ là
u thay vì
O(logN)
đảm cây
ode trên
ìm kiếm
trái nhỏ
được bổ
một phần
hạm hay
ược giữ
3.2)
en.
y tắc đỏ
Cây
Ng
y Đỏ Đen
guyễn Hoài
M

Phương
Số lượng n
cao đen (b
l

ột ví dụ về c
ng dẫn từ gố
phát biểu q
hải có cùng
Thán
Nguy
ây đỏ đen
ốc đến lá đư
quy tắc 4 th
g chiều cao
ng 6 năm 20
yễn Hồng P

ược gọi là c
eo một cách
đen.
005
Phú
chiều
h khác
Cây Đỏ Đen Tháng 6 năm 2005
Nguyễn Hoài Phương 7 Nguyễn Hồng Phú

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.

mà
Mặ
nod
đen
là đ
y Đỏ Đen
guyễn Hoài
ép thêm vào
theo một đư
của khóa no
y nhiên, tro
ay.
bảo đảm
k
n. Theo quy
hai node co
de cha là no
ột phép lật m
m giác, node
de con trái v
nh 3.4. Lật
nh 3.4a. trư
húng ta nhận
àu không vi
ặc dù quy tắ
de cha khôn
n, không có
đỏ, thì sau k
Phương
o trong cây

khi lật màu
tắc 4.
bị vi phạm
g màu đỏ) lạ
phạm khi P
u, ta sẽ có h
8
t đầu như trê
đến vị trí cầ

ược điểm ch
y tắc màu, c
p thêm vào
c node con t
ữ màu là đe
ác quy tắc đ
p lật là P (P
à X2. Xem h
3.4b sau khi
chiếu con đ
qua phép lậ
ại có khả nă
chuyển từ
hai node đỏ
ên cây tìm k
ần chèn, đi
hèn là phức
ần phải tiế
n
làm xuất hi

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ọ
. Như vậy p
một node con
ode cha của
ếu node cha
005
Phú
hường:
vào giá
màu và
àu khi
de đen
trừ khi
ở đỉnh
ọi hai
phép lật
n và
a P là
a của P
Cây
Ng
Điề
ta c
Đố

phép quay
n node mới c
i kiểm tra x
trên, node m
ững vị trí kh
chuẩn bị tru
ng hợp này b
p lật màu n
on có màu đ
ng trường hợ
y tắc 4 cũng
khi chèn
có thể làm c
xem có phạm
mới được ch
hác nhau đố
9
uớc khi đi x
bằng một p
node gốc và
đen. Điều n
ợp này, chiề
g không bị v
node
cho quy tắc
m quy tắc k
hèn mà ta g
ối với P và G
xuống theo c
hép quay.

Phú
. Chúng
o node
quy
tắc
node
khi
c hợp
e X có
Cây
Ng
Hìn
X l
Điề
nod
Ng
Nế
no
d
chá
Tha
và
Hì
n
i) K
ii) K
iii)
y Đỏ Đen
guyễn Hoài
nh 3.5. Các

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
au khi chèn
X là cháu ng
X là cháu n
10
ược chèn
ằm cùng bên
u ngoại nếu
e con phải c
ể hoặc bên t
G. Có hai k
trình bày tr
ược xác địn
năng xảy ra

nú
t
goại của G
nội của G
n node cha
u hoặc nó là
của P và no
trái hoặc bê

node
ode X
Cây
Ng
Ch
i) K
P đ
xun
Do
ii) K
Nế
th
a
cần
Bây
phả
Tro
cân
Đ
Đ
Q
phé
Kh
Tro
đối
này
bằn
cây
y Đỏ Đen
guyễn Hoài

ỏ và X là no
àu. Bắt đầu
một phép lậ
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
node X là n
h tạo nên câ
màu node
cân bằng.
c khả năng c
giản. Node
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
X là 6. (hìn
sau: (hình 3
a có thể áp d

5, 87, 93 (v
và quay trái
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.
ất hiện lỗi:
ớ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
Thá
n
Nguy
ếu node cha
vào số nod
đã hoàn tất
quay đơn gi
hèn các node
cha và con
hồi tính đ

vậy cần
m cho
là một
ờng hợp
m điều
sửa cây
ần nữa
Cây
Ng
Hìn
iii)
Nế
phé
lật
Lư
u
y Đỏ Đen
guyễn Hoài
nh 3.7. Nod
Khả năng
u node P đ
ỏ
ép đổi màu.
màu trước
u ý là node

Phương
de P đỏ và X
3: P đỏ và X
ỏ và X là no

a và con đề
005
Phú
một vài
n phải
ều đỏ).