1 ページ
Đề tài cuối kì Môn: Cấu trúc dữ liệu 2 Lớp 0811cl2 Nhóm thực hiện: - Vũ Chí Phương - Nguyễn Nhân Nghĩa ThiNganHang.com
2 ページ
Phần I - Cây đỏ đen (Red Black Tree) Cây đỏ đen là một dạn cây tìm kiếm nhị phân tự cân bằng. Cấu trúc ban đầu của nó được đưa ra vào năm 1972 bởi Rudolf Bayer với tên là “B-cây cân bằng” còn tên hiện nay được đưa ra từ 1978 bởi Leo J. Guibas và Robert Sedgewick. Nó là một cấu trúc phức tạp nhưng cho kết quả tốt về thời gian thực hiện trong trường hợp xấu nhất. Các phép toán như tìm kiếm (search), chèn ( insert), và xóa (delete) thực hiện trong thời gian O(log n). Thay vì thời gian là O (n) như cây nhị phân thông thường trong trường hợp dữ liệu đã được sắp xếp trướThiNganHang.comc khi chèn.
3 ページ
Quy tắc của cây đỏ đen 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: 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 hay có cùng chiều cao đen black height(bh). ThiNganHang.com
4 ページ
Cây đỏ đen Các lá của cây đỏ đen khác với cây nhị phân thông thường, chúng là các lá NULL, không chứa dữ liệu và được gán màu đen. Chiều cao cây đỏ đen (height): - Height <= 2*log(n+1) - Height <= 2*bh ThiNganHang.com
5 ページ
Cấu trúc cây đỏ đen Khai báo một nút: typedef struct NodeTag { struct NodeTag *left; /* Con trái */ struct NodeTag *right; /* Con phải */ struct NodeTag *parent; /* Cha */ nodeColor color; /* Màunode (BLACK, RED) */ KeyType key; /* Khoá sử dụng tìm kiếm */ RecType rec; /* Dữ liệu node */ NIL } NodeType; Khai báo một nút lá NULL NIL NIL #define NIL &sentinel /* Node cầm canh */ static NodeType sentinel = { &sentinel, &sentinel, 0, BLACK, 0}; ThiNganHang.com
6 ページ
Cấu trúc cây đỏ đen Tạo một nút mới : NodeType *CreateNode(NodeType parent, KeyType key, RecType *rec) { NodeType*p = new NodeType; if(!p) exit(1); x->parent = parent; x->left = x->right = NIL; x->color = RED; //Nút thêm vào luôn được gán màu đỏ x->key = key; x->rec = *rec; } Khai báo một cây mới. static NodeType *root = NIL; ThiNganHang.com
7 ページ
Các thuật toán cơ bản của cây đỏ đen 1. Thêm một nút mới vào cây. 2. Xóa một nút khỏi cây. 3. Tìm kiếm một nút trên cây 4. In cây ra màn hình 5. Xóa cây. ThiNganHang.com
8 ページ
1. Thêm một nút mới - Việc chèn hay xóa được thực hiện giống với cây nhị phân thông thường - Tuy nhiên quá trình này, các quy tắc của cây đỏ đen có thể bị vi phạm, chúng ta sẽ thực hiện các thao tác sau đây để khôi phục tính chất cây đỏ đen: Các phép lật màu trên đường đi xuống. Các phép quay trên đường đi xuống. Thực tế chỉ cần không quá O (log n) phép đổi màu và không quá 2 phép quay cho phép chèn và 3 cho phép xóa. ThiNganHang.com
9 ページ
Các thao tác khôi phục cây Các thao tác này chỉ được thực hiện khi cây xuất hiện xung đột đỏ-đỏ ( vi phạm quy tắc con của nút đỏ phải là đen). Khi giải quyết xung đột đỏ-đỏ thì các xung đột khác cũng được giải quyết đồng thời: Nút gốc luôn luôn đen. Chiều cao đen từ gốc đến lá là như nhau ThiNganHang.com
10 ページ
Các trường hợp vi phạm chính Tính chất cây đỏ đen bị vi phạm khi xuất hiện xung đột đỏ-đỏ, ta có thể chia làm 3 trường hợp chính: 1. Nút N đỏ có cha P đỏ và có nút chú bác U đỏ. 2. Nút N đỏ có cha P đỏ và có nút chú bác U đen, G là ông nội của N.(N khác phía với P). 3. Nút N đỏ có cha P đỏ và có nút chú bác U đen, G là ông ngoại của N. (N cùng phía với P). ( Nút G có màu đen) ThiNganHang.com
11 ページ
1. Nút N đỏ có cha P đỏ và có nút chú bác U đỏ. Trường hợp này chỉ cần dùng phép lật màu để giải quyết - Có 4 vị trí để thêm N GG UUP UPP N N N N - Khi thêm N thì xuất hiện xung đột đỏ đỏ, ta thực hiện phép lật màu 3 nút G,P,U: P BLACK, U BLACK. - Nếu nút G là nút gốc thì giữ nguyên màu đen. Nếu G bị chuyển sang màu đỏ thì có thể vi phạm quy tắc đỏ-đỏ, khi đó coi G nhưThiNganHang.comN và xét lại.
12 ページ
2. Nút N đỏ có cha P đỏ và có nút chú bác U đen, nhưng N có ông nội G.(N khác phía với P). Trước tiên ta định nghĩa N là cháu ngoại và cháu nội: -N là cháu ngoại của G nếu nó cùng phía với P -N là cháu nội của G nếu nó khác phía với P. G P P Cháu ngoại N N Cháu ngoại N Cháu nội N ThiNganHang.com
13 ページ
2. Nút N đỏ có cha P đỏ và có nút chú bác U đen, nhưng N có ông nội G.(N khác phía với P). Ta thực hiện phép một phép quay để tạo một cháu mới là cháu ngoại, nghĩa là chuyển về trường hợp 3. G G P U U P N N Rotate Left Rotate Right ThiNganHang.com
14 ページ
3. Nút N đỏ có cha P đỏ và có nút chú bác U đen, nhưng N có ông ngoại G. (N cùng phía với P). Ta thực hiện đổi màu hai nút G và P, và dùng một phép xoay để giải quyết xung đột đỏ-đỏ. Đổi màu GGP GGP Đổi màu NPP UG UG NPP U U N N Rotate Right Rotate Left ThiNganHang.com
15 ページ
Nhận xét khi chèn Các nút chèn vào luôn là đỏ để chiều cao đen không đổi. Quá trình khôi phục tính chất của cây đỏ đen được thực hiện như sơ đồ sau: Trường hợp 1 Trường hợp 2 Trường hợp 3 End End ThiNganHang.com
16 ページ
Phép xóa một nút Ta tìm vị trí nút cần xóa như cây nhị phân. Nếu nút cần xóa có 2 con thì ta tìm phần tử thế mạng (có thể là nút lớn nhất bên trái hoặc nhỏ nhất bên phải). Phần tử thế mạng có thể không có con hoặc chỉ có một con. Do đó ta chỉ cần xét chung trường hợp nút bị xóa không có con hoặc chỉ có một con. Gọi nút đó là y. Nếu nút bị xóa y màu đỏ thì chắc chắn con và cha của nó phải là nút đen. Việc xóa y được thực hiện bình thường. Trường hợp phức tạp xảy ra khi nút bị xóa y màu đen. Ta thực hiện thay nó bằng con của nó hoặc bằng nút lá NULL (nếu nó không có con). Việc này sẽ làm giảm chiều cao đen của những nhánh chứa y. Nếu y không phải là gốc thì ta phải thực hiện khôi phục lại thuộc tính đỏ đen của cây. ThiNganHang.com
17 ページ
Phép xóa một nút Gọi nút mới thay thế cho y là N. Nếu N là màu đỏ thì chỉ cần đổi màu của N thành đen là thuộc tính của cây đỏ đen sẽ phục hồi. Nếu N là màu đen thì không thể đổi màu N. Phải thực hiện bằng cách khác. Có 4 trường hợp xảy ra: + Nút anh em với N màu đỏ. + Nút anh em với N màu đen và nút này có 2 con là đen + Nút anh em với N màu đen và có một con màu đỏ là cháu nội của P, một con màu đen. + Nút anh em với N màu đen và có một con màu đỏ là cháu ngoại của P. ThiNganHang.com
18 ページ
Nút anh em với N màu đỏ. Ta thực hiện đổi màu 2 nút S và P, rồi xoay nút cha của N để chuyển về các trường hợp khác với SL là anh em mới của N. Đổi màu PPS Xoay PPS Đổi màu NP SSSR SSSL NP N SSLL SR SL SSRR N ThiNganHang.com
19 ページ
Nút anh em với N màu đen và nút này có 2 con là đen Ta thực hiện đổi màu nút S, như thế chiều cao đen của nhánh bên phải P và bên trái P là như nhau. Nhưng tại P thì chiều cao đen lại giảm đi 1. Coi P là N và xét lại từ đầu. P Đổi màu P N SS SS N S S SL S L R R ThiNganHang.com
20 ページ
Nút anh em với N màu đen và có một con màu đỏ là cháu nội của P , một con màu đen. Ta thực hiện đổi màu, rồi quay nút S để chuyển về trường hợp 4. P ĐổXoayi màu P N SSSSL SSSSR N SS SS SSL SS LL R RR SR SL ThiNganHang.com
コメント (0)
まだコメントはありません。最初のコメントを書きましょう！