Báo cáo - Cây đỏ đen

Chia sẻ: Vo Kiem | Ngày: | Loại File: PDF | Số trang:31

Thêm vào BST

Báo xấu

189
lượt xem 73
download

Báo cáo - Cây đỏ đen

Mô tả tài liệu

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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)....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo - 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 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: 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 2- Xóa một node:.................................................................................................... 14 IV- Thuật toán cài đặt: ............................................................................................ 14 V- Nhận xét : ........................................................................................................... 31 Nguyễn Hoài Phương 3 Nguyễn Hồng Phú
Cây Đỏ Đen Tháng 6 năm 2005 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ầ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 Nguyễn Hoài Phương 4 Nguyễn Hồng Phú
Cây Đỏ Đen y Thán 6 năm 20 ng 005 Nhhững node này tự sắp x thành m đường không phân nhánh. Bở vì mỗi n n xếp một n ởi node lớn hơn node đã được chèn vào trước đó, mỗi no là con phải. Khi ấ cây bị m cân n đ ode ấy, mất bằn hoàn toà Nếu ta c ng àn. chèn những mục (item theo thứ tự giảm dầ mỗi node sẽ là g m) ứ ần, con trái của no cha của chúng - câ sẽ bị mất cân bằng v phía bên kia. n ode a ây t về n * Đ phức tạp Độ p: Kh cây một nhánh, sẽ trở thành mộ danh sách liên kết, d liệu sẽ là một chiều thay vì hi n ột h dữ à u hai chiều. Tro trường hợp này, t i ong thời gian tru xuất giả về O(N), thay vì O uy ảm O(logN) đối với cây câ bằng. i ân Để bảo đảm th gian tru xuất nhan O(logN) của cây, ch hời uy nh ) húng ta cần phải bảo đ cây n đảm luô luôn cân bằng (ít ra cũng là cây gần cân bằ ôn y ằng). Điều này có ngh là mỗi no trên hĩa ode cây phải có xấ xỉ số nod con bên p bằng s node con bên trái. y ấp de phải số n Mộ cách tiếp cận giải qu vấn đề cân bằng l cây: đó l cây đỏ đen-là cây tì kiếm ột uyết ề lại là ìm nhị phân vì th nó có các tính chất c cây tìm kiếm nhị p ị hế c của m phân ví dụ : node con trái nhỏ hơn node cha, node cha nhỏ hơn no con phả bên cạnh đó cây đỏ đen còn đ n , ode ải, h ỏ được bổ sun một số đắc điểm. ng đ Tro cây đỏ đen, việc cân bằng đư thực thi trong khi c ong ược chèn, xóa. K thêm m phần Khi một tử thì thủ tục chèn sẽ k c kiểm tra xem tính chấ cân bằng của cây c bị vi ph m ất g có hạm hay ông. Nếu có, sẽ xây d khô dựng lại cấu trúc cây. Bằng cách này, cây lu luôn đư giữ u uôn ược cân bằng. n II- Đị ngh ịnh hĩa: Cây đỏ đen là một cây nh phân tìm kiếm( BST tuân thủ c quy tắc sau: (hình 3.2) y hị T) các Mọi node phải là đỏ hoặc đen. Node gốc và các nod lá phải lu luôn đen de uôn n. node là đỏ, những nod con của n phải đen. Nếu một n de nó Mọi đườn dẫn từ gố đến một lá phải có c ng ốc cùng số lượ node đe ợng en. Kh chèn (hay xóa) một n hi y node mới, c phải tuâ thủ các q tắc trên -gọi là quy tắc đỏ cần ân quy y đen Nếu được tuân thủ, c sẽ được cân bằng. n. c cây c Ng guyễn Hoài Phương 5 Nguy Hồng P yễn Phú
Cây Đỏ Đen y Thán 6 năm 20 ng 005 Hình 3.2. Mộ ví dụ về cây đỏ đen H ột Số lượng node đen trên một đườn dẫn từ gố đến lá đư gọi là c ng ốc ược chiều cao đen (bl lack height) Ta có thể phát biểu q tắc 4 theo một cách khác ). quy h là mọi đườn dẫn từ g đến lá phải có cùng chiều cao đen. ng gốc g Bổ đề: Một cây đỏ đen n-nod M ỏ de Có: height
Cây Đỏ Đen Tháng 6 năm 2005 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ác phép quay khi node đã được chèn. · Các phép quay trên đường đi xuống. 1.1 Các phép lật màu trên đường đi xuống Nguyễn Hoài Phương 7 Nguyễn Hồng Phú
Cây Đỏ Đen y Thán 6 năm 20 ng 005 Phé thêm vào trong cây đỏ đen bắt đầu như trê cây tìm k ép o t ên kiếm nhị ph thông th hân hường: đi ttheo một đư ường dẫn từ node gốc đ vị trí cầ chèn, đi qua phải ha trái tùy v giá ừ đến ần ay vào trị của khóa no và khóa tìm kiếm. ode a Tuy nhiên, tro cây đỏ đ đến đư điểm ch là phức tạp bởi các phép lật m và y ong đen, ược hèn c màu qua ay. Để bảo đảm không vi phạ các quy tắc màu, cần phải tiến hành các p k ạm y n phép lật mà khi àu cần Theo quy tắc như sa nếu phép thêm vào làm xuất hi tình trạn một nod đen n. y au: p iện ng de có hai node co đỏ, chún ta đổi các node con t on ng c thành đen v node cha thành đỏ (trừ khi và a nod cha là no gốc, nó vẫn vẫn giữ màu là đe de ode en). Mộ phép lật màu ảnh hư ột m ưởng đến cá quy tắc đ ác đỏ-đen ra sa chúng ta gọi node ở đỉnh ao? a tam giác, node có màu đỏ trước phép lật là P (P thay cho n m e ỏ p P node cha). C Chúng ta gọ hai ọi nod con trái và phải của P là X1 và X2. Xem h de v a à hình 3.4a. Hìn 3.4. Lật màu nh Hìn 3.4a. trư khi lật m Hình 3 nh ước màu, 3.4b sau khi lật màu. i Ch húng ta nhận thấy sau k lật màu chiếu con đ của cây không đổi. Như vậy p n khi đen y phép lật mà không vi phạm quy tắc 4. àu Mặ dù quy tắ 4 không b vi phạm qua phép lậ nhưng q tắc 3 (m node con và ặc ắc bị ật, quy một n nod cha khôn thể đồng màu đỏ) lạ có khả nă bị vi ph de ng g ại ăng hạm. Nếu no cha của P là ode a đen không có vấn đề vi p n, ó phạm khi P chuyển từ đen sang đỏ nhưng nế node cha của P ỏ, ếu a là đ thì sau khi đổi màu ta sẽ có h node đỏ trên một hà đỏ, k u, hai àng. Ng guyễn Hoài Phương 8 Nguy Hồng P yễn Phú
Cây Đỏ Đen y Thán 6 năm 20 ng 005 Điề này cần phải được c ều p chuẩn bị tru khi đi x uớc xuống theo c để chèn node mới. Chúng cây n . ta c thể giải quyết trườn hợp này b có q ng bằng một phép quay. Đố với node gốc thì phép lật màu n ối g p node gốc và hai node co của nó v làm cho node on vẫn o gốc cũng như hai node co có màu đ Điều n tránh sự vi phạm qu tắc 2 và quy tắc c on đen. này ự uy 3 (x xung đột đỏ ỏ-đỏ). Tron trường hợ này, chiề cao đen t ng ợp ều trên mỗi đư ường đi từ n node gốc tăng lên 1, do đó quy tắc 4 cũng không bị v phạm. c y g vi 1.2 2 Các phép quay khi chèn node p Tha tác chèn node mới c thể làm c quy tắc đỏ-đen bị vi phạm. D vậy sau k ao n có cho c Do khi chè cần phải kiểm tra x có phạm quy tắc k èn, i xem m không và thự hiện nhữ thao tác hợp ực ững c lý. Nh đã xét ở trên, node m được ch mà ta g là node X luôn luô đỏ. Node X có hư t mới hèn gọi X, ôn e thể nằm ở nhữ vị trí kh nhau đố với P và G như tron hình 3.5. ể ững hác ối G, ng Ng guyễn Hoài Phương 9 Nguy Hồng P yễn Phú
Cây Đỏ Đen y Thán 6 năm 20 ng 005 Hìn 3.5. Các biến dạng của node đư chèn nh ược X l một node cháu ngoạ nếu nó nằ cùng bên node cha P và P cùng bên node cha G. là e ại ằm n g Điề này có nghĩa là, X l node cháu ngoại nếu hoặc nó là node con t của P v P là ều n là u u à trái và nod con trái của G, hoặc nó là node con phải c P và node P là nod con phải của G. de c c e của de Ng gược lại, X là một node cháu nội. l e Nếu X là node cháu ngoạ nó có thể hoặc bên t hoặc bê phải của P, tùy vào việc e ại, ể trái ên nod P ở bên trái hay bên phải node G. Có hai k năng tư de t n khả ương tự nếu X là một n u node chá nội. Bốn trường hợp này được trình bày tr áu n p rong hình 3.5. Tha tác phục hồi quy tắc đỏ-đen đư xác địn bởi các m và cấu h ao c c ược nh màu hình của no X ode và những bà con của nó. Có 3 khả n c năng xảy ra được xem x như sau xét u:(hình 3.6) Hìn 3.6. Ba khả năng sa khi chèn nút nh k au i) K năng 1: P đen Khả ii) K năng 2: P đỏ và X là cháu ng của G Khả 2 goại iii) Khả năng 3: P đỏ và X là cháu n của G nội Ng guyễn Hoài Phương 10 Nguy Hồng P yễn Phú
Cây Đỏ Đen y Thán 6 năm 20 ng 005 Ch húng ta lần lượt xét các khả năng c thể như s l c cụ sau: i) K năng 1: P đen Khả P đ là trườn hợp đơn giản. Node thêm vào l đen ng luôn đỏ. Nế node cha đen, không có ếu a g xun khắc đỏ- (quy tắc 3), và khô có việc cộng thêm vào số nod đen (quy tắc 4). ng -đỏ c ông de Do vậy, không bị vi phạm quy tắc về màu. Tha tác chèn đã hoàn tất. o g m ao ii) K năng 2: P đỏ và X là cháu ng của G Khả 2 goại Nếu node P đỏ và X là no cháu ng ỏ ode goại, ta cần một phép qquay đơn gi và một v iản vài tha đổi về mà Bắt đầu với giá trị 50 tại node gốc, và ch các node 25, 75 và 12. Ta ay àu. u e hèn e cần phải làm một phép lậ màu trước khi chèn n n m ật c node 12. Bây giờ, chèn node mới X là 6. (hìn 3.7a. )xuấ hiện lỗi: cha và con đều đỏ, vì v cần y nh ất vậy phả có các thao tác như sau: (hình 3 ải 3.7) Tro trường hợp này, ta có thể áp d ong a dụng ba bướ để phục hồi tính đỏ ớc ỏ-đen và làm cho m cân bằng cây. Sau đây là các bước ấ n ấy: Đổi Đ màu nod G - node ông bà của node X (tr de e a rong thí dụ này là node 25). e Đổi Đ màu nod P - node cha của node X (node 12) de e Quay với node G (25) ở vị trí đỉnh, theo huớn làm nâng node X lên (6). Đây l một Q ng g n là phé quay phả ép ải. Kh ta hoàn tấ ba buớc tr sẽ bảo t hi ất rên toàn cây đỏ đen. Xem hình 3.7b. Tro thí dụ này, node X là node ch ngoại củ một node con trái. C một trườ hợp ong n háu ủa e Có ờng đối xứng khi node X là n i n node cháu ng nhưng của một no con phả Thử làm điều goài g ode ải. m này bằng cách tạo nên câ 50, 25, 75 87, 93 (v phép lật màu khi cầ Chỉnh s cây y h ây 5, với ần). sửa bằn cách đổi màu node 75 và 87, v quay trái với node 75 là node đỉnh. Một lầ nữa ng và ần cây lại được cân bằng. y c Ng guyễn Hoài Phương 11 Nguy Hồng P yễn Phú
Cây Đỏ Đen y Thán 6 năm 20 ng 005 Hìn 3.7. Nod P đỏ và X là node ch ngoại nh de háu iii) Khả năng 3: P đỏ và X là cháu n của G nội Nếu node P đỏ và X là no cháu nộ chúng ta cần thực h hai phé quay và m vài ỏ ode ội, a hiện ép một phé đổi màu. Cây đỏ đe được tạo thành từ cá node 50, 25, 75, 12 và 18. (cần phải ép . en ác n lật màu trước khi chèn no 12). Xe hình 3.8a. ode em Lưu ý là node 18 là node cháu nội. N u Node này và node cha đều đỏ (cha và con đề đỏ). a ều Ng guyễn Hoài Phương 12 Nguy Hồng P yễn Phú
Cây Đỏ Đen y Thán 6 năm 20 ng 005 hình 3.8.c Hìn 3.8. Khả năng 3: P đỏ và X là n nh ả node cháu n nội hỉnh lại sự sắ xếp này cũng khá rắ rối hơn. Nếu ta cố q Ch ắp ắc quay phải n node ông bà G (25) à ởđđỉnh, như ta đã làm tron khả năng 2, node ch trong X (18) đi ng a ng g háu gang hơn là đi lên, như thế cây sẽ không còn cân bằng n trước. ( ư ẽ n như (Thử làm điều này, rồi quay trở lạ với i ại, nod 12 ở đỉnh để phục h cây nhu cũ). Phải c một giả pháp khác de h, hồi u cần ải c. Ng guyễn Hoài Phương 13 Nguy Hồng P yễn Phú
Cây Đỏ Đen y Thán 6 năm 20 ng 005 Thủ thuật cần dùng khi X là node ch nội là ti hành ha phép quay hơn là mộ phép. ủ háu iến ai y ột Phé quay đầu biến X từ một node c ép u cháu nội thà node ch ngoại, n trong h ành háu như hình 3.8 Bây giờ, trường hợp là tương t như khả n 8b. , p tự năng 1, và t có thể áp dụng cùng một ta p g phé quay, vớ node ông bà ở đỉnh, như đã làm trước đây. Kết quả nh trong hìn 3.8c. ép ới m hư nh Ch húng ta cũng cần tô mà lại các nú Ta làm đ này trư khi làm bất cứ phép quay g àu út. điều ước p nào (thứ tự kh o hông quan tr rọng, nhưng nếu ta đợi đến khi sa khi quay mới tô màu lại g i au u nod thì khó mà biết phải gọi chúng như thế nà Các bướ là: de m i g ào). ớc Đổi Đ màu nod ông bà củ node X ( node 25). de ủa Đ màu nod X (không phải màu của node cha; node X đây là nod 18). Đổi de g de Quay với node P - node cha của X - ở đỉnh (k Q e không phải v node ôn bà; node cha với ng đây là 12). y Quay lần nữa với node ông bà của X (25) ở đỉ về hướ nâng X lên (quay p Q a ỉnh, ớng phải). 2- Xóa m node: một : Chú ta đã bi trong cậy nhị phân t kiếm vi xóa 1 ph tử ra kh cây úng iết y tìm iệc hần hỏi thì khó khăn ph tạp hơn việc insert 1 phần tử vào cậy, và ở cây đỏ đ k hức n à đen cũn vậy, thậm chí còn ph tạp hơn vì trong qu trình thê vào phải đảm ng m hức n uá êm i bảo qui tắc của cây đỏ đen o a n. IV- Th huật toá cài đ án đặt: typ pedef enum { STATUS_OK K, STATUS_ME EM_EXHAU USTED, STATUS_DU UPLICATE_ _KEY, STATUS_KE EY_NOT_FOUND }S StatusEnum m; Ng guyễn Hoài Phương 14 Nguy Hồng P yễn Phú
Cây Đỏ Đen Tháng 6 năm 2005 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 */ Nguyễn Hoài Phương 15 Nguyễn Hồng Phú
Cây Đỏ Đen Tháng 6 năm 2005 /************************** * 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; Nguyễn Hoài Phương 16 Nguyễn Hồng Phú
Cây Đỏ Đen Tháng 6 năm 2005 } 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; Nguyễn Hoài Phương 17 Nguyễn Hồng Phú
Cây Đỏ Đen Tháng 6 năm 2005 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*/ Nguyễn Hoài Phương 18 Nguyễn Hồng Phú
Cây Đỏ Đen Tháng 6 năm 2005 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; Nguyễn Hoài Phương 19 Nguyễn Hồng Phú
Cây Đỏ Đen Tháng 6 năm 2005 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; Nguyễn Hoài Phương 20 Nguyễn Hồng Phú

CÓ THỂ BẠN MUỐN DOWNLOAD