Đề tài cuối kì Môn: Cấu trúc dữ liệu 2

Đề 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 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ước khi chèn. 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). 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 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 */ } NodeType;  Khai báo một nút lá NULL #define NIL &sentinel /* Node cầm canh */ static NodeType sentinel = { &sentinel, &sentinel, 0, BLACK, 0}; NIL NIL NIL 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; 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. 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. 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 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) 1. Nút N đỏ có cha P đỏ và có nút chú bác U đỏ. UP N G N Trường hợp này chỉ cần dùng phép lật màu để giải quyết N N - Có 4 vị trí để thêm 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. U P - 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ư N và xét lại. Cháu ngoại Cháu nội Cháu ngoại 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: PP N N N N G -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. 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. UP N G PU N G Rotate RightRotate Left GPP G 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 đỏ-đỏ. U N U N Rotate LeftRotate Right Đổi màu Đổi màu U P N G NG U P End 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 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. 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. SP P S 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. N SRSL N SRSL Đổi màu XoayS P N SR S PSL N Đổi màu S S 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 N SRSL P N SR SL Đổi màu SSL S SR 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 N SR P N SL Đổi màuXoay SR SL L S SR S Đổi màu  Đổi màu S thành màu của P , màu của P thành đen, và màu của S con đỏ thành đen rồi xoay P sang trái. 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 S SL P N SR S SR P N SL Xoay SR S P N SL SL SR S P N Phần II - AA Tree 1. Giới thiệu chung:  AA Tree được đưa ra bởi Arne Andersson và lấy theo tên ông.  AA Tree là một biến dạng của cây đỏ đen. Nó cũng là một cây nhị phân tìm kiếm nhưng khác với cây đỏ đen là nó chỉ cho phép có con phải màu đỏ.  Ngoài ra các nút sẽ được gắn một cấp độ(mức) xác định thay vì màu như cây đỏ đen.  Để đảm bảo cây cân bằng thì các nút phải tuân theo các quy tắc được đặt ra. 1. Giới thiệu chung:  Các quy tắc của AA Tree: 1. Các nút lá có mức bằng 1. 2. Mức của nút con trái luôn nhỏ hơn mức của nút cha. 3. Nút con phải có mức nhỏ hơn hoặc bằng nút cha. 4. Nút cháu phải có mức nhỏ hơn nút ông. 5. Mọi nút có mức lớn hơn 1 phải có 2 con. (Nguồn: 1. Giới thiệu chung:  Thông thường, cây đỏ đen phải xét đến 7 trường hợp để cân bằng lại cây.  Nhưng AA Tree thì chỉ cần xét 2 trường hợp chính: 2. Các thao tác chính. Tương ứng với 2 trường hợp chính thì ta có 2 thao tác được sử dụng khi vi phạm các quy tắc. Đó là skew và split. Skew giống như phép xoay phải và split giống như phép quay trái của cây đỏ đen. Skew sử dụng khi xuất hiện nút con trái cùng mức với nút cha. Split sử dụng khi xuất hiện nút cháu phải cùng mức với nút ông. 2. Các thao tác chính. Skew:  L là con trái của T nhưng cùng mức với T nên vi phạm quy tắc 2..  Sau khi skew thì T trở thành con phải của L, cùng mức với L và các quy tắc được đảm bảo. 2. Các thao tác chính. Split:  X là cháu phải của nút T. X cùng mức với T nên vi phạm quy tắc 4.  Sau khi split thì T trở thành con trái của R, vẫn cùng mức cũ với X nhưng T và X là anh em nên các quy tắc vẫn được đảm bảo.  Chỉ có nút R là được tăng lên một mức. 3. Thêm một nút mới.  Việc thêm một nút mới thực hiện như cây nhị phân.  Khi tìm được vị trí chèn ở nút NULL thì ta tạo một nút mới ở đó.  Sau đó kiểm tra trên đường đi xuống bắt đầu từ cha của nút đã chèn rồi đi ngược lên đến nút gốc: - Nếu nút cha cùng mức với nút con trái, thì skew. - Nếu nút đó có nút cháu phải cùng mức , thì split.  Lệnh skew luôn được thực hiện trước lệnh split. 3. Thêm một nút mới.  Ví dụ: Chèn nút 6 vào cây có sẵn. Nút 6 đã được thêm thành công 4. Xóa một nút khỏi cây.  Việc tìm vị trí nút xóa được thực hiện như cây nhị phân.  Tuy nhiên việc xóa sẽ đơn giản hơn vì nút xóa sẽ không thể xảy ra trường hợp chỉ có con trái.  Do đó ta chỉ cần xét trường hợp nút xóa không có con và có con bên phải (bao gồm cả TH có 2 con).  Nếu không có con thì xóa bình thường.  Nếu có con bên phải thì tìm phần tử thế mạng nhỏ nhất bên phải để xóa(phần tử này không có con trái nên nó là nút lá).  Như vậy, nút thực sự bị xóa đi luôn là nút lá. 4. Xóa một nút khỏi cây.  Ta thực hiện khôi phục lại thuộc tính của cây bắt đầu từ nút cha của nút lá bị xóa và đi ngược lên đến nút gốc.  Với mỗi nút ta phải thực hiện lần lượt 3 bước nếu cần: 1. Giảm mức của nút đó và nút con phải. 2. Skew nút đó, nút con phải, nút cháu phải. 3. Split nút đó, nút con phải.  Theo Arne Anderson thì trường hợp xấu nhất chúng ta mới phải sử dụng cả 3 bước trên.  Như vậy, khi đến nút gốc thì chắc chắn các quy tắc của cây sẽ được đảm bảo. 4. Xóa một nút khỏi cây. Xóa thành công  Ví dụ: Xóa nút 1 khỏi cây.