TRNG I HC KHOA HC T NHIấN
KHOA CễNG NGH THễNG TIN
B MễN CU TRC D LIU 2
NGUYN HOI PHNG -0212234
NGUYN HNG PH -0212226

BI BO CO MễN CU TRC D LIU 2
GVHD : Ths . Phm Phm Tuyt Trinh
TP HCM , 2005
THệ VIEN ẹIEN Tệ TRệẽC TUYEN
Cây Đỏ Đen Tháng 6 năm 2005
Nguyễn Hồ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

THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Cây Đỏ Đen Tháng 6 năm 2005
Nguyễn Hồ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 tốn cơ bản của Black and Red Tree ............................................... 7

1-

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

THƯ VIỆN ĐIỆN TỬ TRỰC TUYẾN
Cây Đỏ Đen Tháng 6 năm 2005
Nguyễn Hồ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 tố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ó

hn node cha, node cha nh hn node con phi, bờn cnh ú cõy en cũn c b
sung mt s c im.
Trong cõy en, vic cõn bng c thc thi trong khi chốn, xúa. Khi thờm mt phn
t thỡ th tc chốn s kim tra xem tớnh cht cõn bng ca cõy cú b vi phm hay
khụng. Nu cú, s xõy dng li cu trỳc cõy. Bng cỏch ny, cõy luụn luụn c gi
cõn bng.
II- nh ngha:Cõy en l mt cõy nh phõn tỡm kim( BST) tuõn th cỏc quy tc sau: (hỡnh 3.2)
Mi node phi l hoc en.
Node gc v cỏc node lỏ phi luụn luụn en.
Nu mt node l , nhng node con ca nú phi en.
Mi ng dn t gc n mt lỏ phi cú cựng s lng node en.
Khi chốn (hay xúa) mt node mi, cn phi tuõn th cỏc quy tc trờn -gi l quy tc
en. Nu c tuõn th, cõy s c cõn bng.
THệ VIEN ẹIEN Tệ TRệẽC TUYEN
Cõy en Thỏng 6 nm 2005
Nguyn Hoi Phng 6 Nguyn Hng Phỳ

Hỡnh 3.2. Mt vớ d v cõy en
S lng node en trờn mt ng dn t gc n lỏ c gi l chiu
cao en (black height). Ta cú th phỏt biu quy tc 4 theo mt cỏch khỏc
l mi ng dn t gc n lỏ phi cú cựng chiu cao en.
B :
Mt cõy en n-node
Cú: height <= 2 log(n+1)
height : Chiu cao cõy
Tớnh cht: height <= 2 * bh(x)
Thi gian tỡm kim: O( log n )

bo m khụng vi phm cỏc quy tc mu, cn phi tin hnh cỏc phộp lt mu khi
cn. Theo quy tc nh sau: nu phộp thờm vo lm xut hin tỡnh trng mt node en
cú hai node con , chỳng ta i cỏc node con thnh en v node cha thnh (tr khi
node cha l node gc, nú vn vn gi mu l en).
Mt phộp lt mu nh hng n cỏc quy tc -en ra sao? chỳng ta gi node nh
tam giỏc, node cú mu trc phộp lt l P (P thay cho node cha). Chỳng ta gi hai
node con trỏi v phi ca P l X1 v X2. Xem hỡnh 3.4a.
Hỡnh 3.4. Lt mu

Hỡnh 3.4a. trc khi lt mu, Hỡnh 3.4b sau khi lt mu.
Chỳng ta nhn thy sau khi lt mu chiu con en ca cõy khụng i. Nh vy phộp lt
mu khụng vi phm quy tc 4.
Mc dự quy tc 4 khụng b vi phm qua phộp lt, nhng quy tc 3 (mt node con v
node cha khụng th ng mu ) li cú kh nng b vi phm. Nu node cha ca P l
en, khụng cú vn vi phm khi P chuyn t en sang , nhng nu node cha ca P
l , thỡ sau khi i mu, ta s cú hai node trờn mt hng.
THệ VIEN ẹIEN Tệ TRệẽC TUYEN
Cõy en Thỏng 6 nm 2005
Nguyn Hoi Phng 9 Nguyn Hng Phỳ
iu ny cn phi c chun b truc khi i xung theo cõy chốn node mi. Chỳng
ta cú th gii quyt trng hp ny bng mt phộp quay.
i vi node gc thỡ phộp lt mu node gc v hai node con ca nú vn lm cho node
gc cng nh hai node con cú mu en. iu ny trỏnh s vi phm quy tc 2 v quy tc
3 (xung t -). Trong trng hp ny, chiu cao en trờn mi ng i t node
gc tng lờn 1, do ú quy tc 4 cng khụng b vi phm.
1.2 Cỏc phộp quay khi chốn node
Thao tỏc chốn node mi cú th lm cho quy tc -en b vi phm. Do vy sau khi
chốn, cn phi kim tra xem cú phm quy tc khụng v thc hin nhng thao tỏc hp
lý.
Nh ó xột trờn, node mi c chốn m ta gi l node X, luụn luụn . Node X cú

thay i v mu. Bt u vi giỏ tr 50 ti node gc, v chốn cỏc node 25, 75 v 12. Ta
cn phi lm mt phộp lt mu trc khi chốn node 12.
Bõy gi, chốn node mi X l 6. (hỡnh 3.7a. )xut hin li: cha v con u , vỡ vy cn
phi cú cỏc thao tỏc nh sau: (hỡnh 3.7)
Trong trng hp ny, ta cú th ỏp dng ba bc phc hi tớnh -en v lm cho
cõn bng cõy. Sau õy l cỏc bc y:
i mu node G - node ụng b ca node X (trong thớ d ny l node 25).
i mu node P - node cha ca node X (node 12)
Quay vi node G (25) v trớ nh, theo hung lm nõng node X lờn (6). õy l mt
phộp quay phi.
Khi ta hon tt ba buc trờn s bo ton cõy en. Xem hỡnh 3.7b.
Trong thớ d ny, node X l node chỏu ngoi ca mt node con trỏi. Cú mt trng hp
i xng khi node X l node chỏu ngoi nhng ca mt node con phi. Th lm iu
ny bng cỏch to nờn cõy 50, 25, 75, 87, 93 (vi phộp lt mu khi cn). Chnh sa cõy
bng cỏch i mu node 75 v 87, v quay trỏi vi node 75 l node nh. Mt ln na
cõy li c cõn bng.
THệ VIEN ẹIEN Tệ TRệẽC TUYEN
Cõy en Thỏng 6 nm 2005
Nguyn Hoi Phng 12 Nguyn Hng Phỳ

Hỡnh 3.7. Node P v X l node chỏu ngoi
iii) Kh nng 3: P v X l chỏu ni ca G
Nu node P v X l node chỏu ni, chỳng ta cn thc hin hai phộp quay v mt vi
phộp i mu. Cõy en c to thnh t cỏc node 50, 25, 75, 12 v 18. (cn phi
lt mu trc khi chốn node 12). Xem hỡnh 3.8a.
Lu ý l node 18 l node chỏu ni. Node ny v node cha u (cha v con u ).

THệ VIEN ẹIEN Tệ TRệẽC TUYEN