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

Cây AA (AA tree)  Đượ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ác khái niệm Tính chất Ví dụ Các phép biến đổi cây Các thao tác trên cây

pdf16 trang | Chia sẻ: candy98 | Lượt xem: 770 | Lượt tải: 0download
Bạn đang xem nội dung tài liệu 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, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
©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
Tài liệu liên quan