Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 3: Cấu trúc cây (P3) - Văn Chí Nam

©FIT-HCMUS 1 AA tree Cấu trúc dữ liệu và giải thuật - HCMUS 2011 73 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). ©FIT-HCMUS 2 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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. 5 10 15 20 Mức 1 Mức 2 ©FIT-HCMUS 3 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 77  Liên kết ngang:  Liên kết giữa node cha và node con có cùng mức. 5 10 15 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. ©FIT-HCMUS 4 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 79 30 70 85 5 60 80 10 90 15 20 50 35 40 6555 Mức của các node? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 80 30 70 85 5 60 80 10 90 15 20 50 35 40 6555 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 ©FIT-HCMUS 5 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 81 30 70 85 5 60 80 10 90 15 20 50 35 40 6555 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 85 5 60 80 10 90 15 20 50 35 40 6555 Có tồn tại 2 liên kết ngang liên tiếp? ©FIT-HCMUS 6 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 83 30 70 85 5 60 80 10 90 15 20 50 35 40 6555 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 85 5 60 80 10 90 15 20 50 35 40 6555 So sánh mức của các node con của các node: 15, 70, 60, 85? ©FIT-HCMUS 7 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 A B C P X A B C ©FIT-HCMUS 8 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 87  Split: Dùng để loại bỏ 2 liên kết ngang liên tiếp X P A B G X P A B G C D 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. ©FIT-HCMUS 9 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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. ©FIT-HCMUS 10 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 9 3 4 5 7 27 158 40 ©FIT-HCMUS 11 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 ©FIT-HCMUS 12 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 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 9 3 4 5 7 27 158 40 ©FIT-HCMUS 13 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 97  Xóa phần tử 8 6 9 3 4 5 7 27 15 40 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 98  Xóa phần tử 5 6 9 3 4 5 7 27 158 40 ©FIT-HCMUS 14 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 99  Xóa phần tử 5 6 9 3 4 7 27 158 40 Giảm mức của 4 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 100  Xóa phần tử 5 6 93 4 7 27 158 40 Skew tại 4 ©FIT-HCMUS 15 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 101  Xóa phần tử 5 6 943 7 27 158 40 Giảm mức Cấu trúc dữ liệu và giải thuật - HCMUS 2011 102  Xóa phần tử 5 6 9 43 7 27 158 40 ©FIT-HCMUS 16 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 103  Xóa phần tử 5 6 9 43 7 27 158 40 Split tại 6 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 104  Xóa phần tử 5 6 9 43 7 27 158 40