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
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 ự ệ
Sv: Nguy n Hoài Ph ng MSSV: 0212234ễ ươ
Sv:Nguy n H ng Phú MSSV: 0212226ễ ồ
Nguy n Hoài Ph ngễ ươ 2 Nguy n H ng Phúễ ồ
Cây Đ ĐenỏTháng 6 năm 2005
M c l c:ụ ụ
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).
Nguy n Hoài Ph ngễ ươ 3 Nguy n H ng Phúễ ồ
Cây Đ ĐenỏTháng 6 năm 2005
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 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. ố ớ ằ
Nguy n Hoài Ph ngễ ươ 4 Nguy n H ng Phúễ ồ
Cây Đ ĐenỏTháng 6 năm 2005
Đ 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.ượ ổ ộ ố ắ ể
Trong cây đ đen, vi c cân b ng đ c th c thi trong khi chèn, xóa. Khi thêm m tỏ ệ ằ ượ ự ộ
ph n t thì th t c chèn s ki m tra xem tính ch t cân b ng c a cây có b vi ph mầ ử ủ ụ ẽ ể ấ ằ ủ ị ạ
hay không. N u có, s xây d ng l i c u trúc cây. B ng cách này, cây luôn luôn đ cế ẽ ự ạ ấ ằ ượ
gi cân b ng.ữ ằ
II- Đ nh nghĩa:ị
Cây đ đen là m t cây nh phân tìm ki m( BST) tuân th các quy t c sau: (hình 3.2)ỏ ộ ị ế ủ ắ
M i node ph i là đ ho c đen.ọ ả ỏ ặ
Node g c và các node lá ph i luôn luôn đen.ố ả
N u m t node là đ , nh ng node con c a nó ph i đen.ế ộ ỏ ữ ủ ả
M i đ ng d n t g c đ n m t lá ph i có cùng s l ng node đen.ọ ườ ẫ ừ ố ế ộ ả ố ượ
Khi chèn (hay xóa) m t node m i, c n ph i tuân th các quy t c trên -g i là quy t cộ ớ ầ ả ủ ắ ọ ắ
đ đen. N u đ c tuân th , cây s đ c cân b ng. ỏ ế ượ ủ ẽ ượ ằ
Hình 3.2. M t ví d v cây đ đenộ ụ ề ỏ
Nguy n Hoài Ph ngễ ươ 5 Nguy n H ng Phúễ ồ