Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 3: Cấu trúc cây - Cây AA

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 3: Cấu trúc cây - Cây AA

1. 73 AA tree Cấu trúc dữ liệu và giải thuật - HCMUS 2011 74  Được đặt tên theo tác giả Arne Anderson (Thụy Điển).  Công trình được công bố năm 1993 (Balanced Search Trees Made Simple). Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 1
2. 75  Mức của node  Liên kết ngang Cấu trúc dữ liệu và giải thuật - HCMUS 2011 76  Mức của node:  Số liên kết trái từ node đó đến node NULL.  Mức của NULL là 0.  Mức của node lá là 1. Mức 2 15 Mức 1 5 10 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 2
3. 77  Liên kết ngang:  Liên kết giữa node cha và node con có cùng mức. 15 5 10 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 78  Cây AA là cây nhị phân tìm kiếm thỏa mãn các tính chất sau: [1] Mức của node con trái bắt buộc phải nhỏ hơn mức của node cha. [2] Mức của node con bên phải nhỏ hơn hoặc bằng mức của node cha. Liên kết ngang bắt buộc hướng sang phải. [3] Mức của node cháu bên phải bắt buộc nhỏ hơn mức của node ông. Không tồn tại 2 liên kết ngang liên tiếp. [4] Mọi node có mức lớn hơn 1 phải có 2 node con. [5] Nếu một node không có liên kết ngang phải thì cả hai node con của nó phải cùng mức. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 3
4. 79 30 70 15 50 60 85 35 40 55 65 80 90 5 10 20 Mức của các node? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 80 30 70 15 50 60 85 35 40 55 65 80 90 5 10 20 So sánh mức của node con trái với mức của node cha trực tiếp của nó? Các cặp node: 15 và 30, 5 và 15, 50 và 70, 35 và 50, 55 và 60, 80 và 85 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 4
5. 81 30 70 15 50 60 85 35 40 55 65 80 90 5 10 20 Các liên kết ngang? Hướng của liên kết ngang? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 82 30 70 15 50 60 85 35 40 55 65 80 90 5 10 20 Có tồn tại 2 liên kết ngang liên tiếp? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 5
6. 83 30 70 15 50 60 85 35 40 55 65 80 90 5 10 20 Mọi node có mức lớn hơn 1 đều có 2 node con? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 84 30 70 15 50 60 85 35 40 55 65 80 90 5 10 20 So sánh mức của các node con của các node: 15, 70, 60, 85? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 6
7. 85  Skew  Split Cấu trúc dữ liệu và giải thuật - HCMUS 2011 86  Skew:  Dùng để loại bỏ liên kết ngang trái. P X P X A B C A B C Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 7
8. 87  Split:  Dùng để loại bỏ 2 liên kết ngang liên tiếp P X P G X G A B C D A B C D Cấu trúc dữ liệu và giải thuật - HCMUS 2011 88  Skew: dùng để loại bỏ liên kết ngang bên trái.  Split: dùng để loại bỏ 2 liên kết ngang (phải) liên tiếp.  Biến đổi theo thứ tự Skew -> Split (nếu có).  Khi thực hiện thao tác Split, node giữa được tăng thêm một mức. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 8
9. 89  Duyệt cây, Tìm kiếm:  Tương tự cây nhị phân tìm kiếm  Thêm phần tử  Xóa phần tử Cấu trúc dữ liệu và giải thuật - HCMUS 2011 90  Thực hiện tương tự trên cây nhị phân tìm kiếm.  Phần tử được thêm vào luôn ở mức 1.  Sau khi thêm, thực hiện các thao tác Skew và/hoặc Split để đảm bảo tính chất của cây. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 9
10. 91  Vẽ cây AA theo thứ tự nhập sau đây: 4, 7, 6, 3, 5, 9, 15, 27, 8, 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 92 6 4 9 27 3 5 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 10
11. 93  Hãy vẽ cây AA theo thứ tự nhập sau đây:  40, 8, 27, 15, 9, 5, 3, 6, 7, 4 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 94 9 27 5 7 3 4 6 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 11
12. 95  Nếu không phải là node lá (mức của node là 1), tìm phần tử thế mạng:  Phần tử lớn nhất bên nhánh trái (node lá).  Xóa node lá:  Giảm mức của node cha nếu mức của node lá nhỏ hơn.  Thực hiện các thao tác Skew, Split cần thiết Cấu trúc dữ liệu và giải thuật - HCMUS 2011 96  Xóa phần tử 8 6 4 9 27 3 5 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 12
13. 97  Xóa phần tử 8 6 4 9 27 3 5 7 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 98  Xóa phần tử 5 6 4 9 27 3 5 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 13
14. 99  Xóa phần tử 5 6 4 9 27 Giảm mức của 4 3 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 100  Xóa phần tử 5 6 3 4 9 27 Skew tại 4 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 14
15. 101  Xóa phần tử 5 Giảm mức 6 3 4 9 27 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 102  Xóa phần tử 5 6 9 27 3 4 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 15
16. 103  Xóa phần tử 5 Split tại 6 6 9 27 3 4 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 104  Xóa phần tử 5 9 6 27 3 4 7 8 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 16