›

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

pdf 13 trang huongle 4400
Download
Bạn đang xem tài liệu "Bài giảng cấu trúc dữ liệu và giải thuật - Cây AVL", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_cau_truc_du_lieu_va_giai_thuat_cay_avl.pdf

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

  1. 47 AVL tree Cấu trúc dữ liệu và giải thuật - HCMUS 2011 48  Do G.M. Adelsen Velskii và E.M. Lendis đưa ra vào năm 1962, đặt tên là cây AVL. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 1
  2. 49  Cây cân bằng AVL là cây nhị phân tìm kiếm mà tại mỗi đỉnh của cây, độ cao của cây con trái và cây con phải không chênh lệch quá 1. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 50  Ví dụ : 12 12 8 18 8 18 5 11 17 5 11 17 4 7 4 7 Cây AVL? 2 Cây AVL? Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 2
  3. 51  Việc xây dựng cây cân bằng dựa trên cây nhị phân tìm kiếm, chỉ bổ sung thêm 1 giá trị cho biết sự cân bằng của các cây con như thế nào.  Cách làm gợi ý: struct NODE { Data key; NODE *pLeft, *pRight; int bal; };  Trong đó giá trị bal (balance, cân bằng) có thể là: 0: cân bằng; 1: lệch trái; 2: lệch phải Cấu trúc dữ liệu và giải thuật - HCMUS 2011 52  Mất cân bằng trái-trái (L-L)  Mất cân bằn trái-phải (L-R)  Mất cân bằng phải-phải (R-R)  Mất cân bằng phải-trái (R-L) Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 3
  4. 53  Mất cân bằng trái-trái (L-L) 12 18 5 17 4 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 54  Mất cân bằng trái-phải (L-R) 12 18 5 17 7 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 4
  5. 55  Mất cân bằng phải-phải (R-R) 12 8 5 11 22 4 7 25 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 56  Mất cân bằng phải-trái (R-L) 12 8 5 11 22 4 7 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 5
  6. 57  Giả sử tại một node cây xảy ra mất cân bằng bên phải (cây con phải chênh lệch với cây con trái hơn một đơn vị):  Mất cân bằng phải-phải (RR)  Quay trái  Mất cân bằng phải-trái (R-L)  Quay phải  Quay trái Cấu trúc dữ liệu và giải thuật - HCMUS 2011 58  P mất cân bằng phải-phải (RR): P Quay trái cây P P Q h+1 h h h+1 h h Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 6
  7. 59  P mất cân bằng phải-phải (RR): Quay trái cây P P 18 35 Q 8 35 18 50 20 50 8 20 55 55 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 60  P mất cân bằng phải-trái (RL):  Bước 1: quay phải Q P  Bước 2: quay trái cây P Q h h h h-1 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 7
  8. 61  P mất cân bằng phải-trái (RL):  Bước 1: quay phải cây Q P Quay phải cây Q P Q Q h h h h h h-1 h- 1 h Cấu trúc dữ liệu và giải thuật - HCMUS 2011 62  P mất cân bằng phải-trái (RL):  Bước 2: quay trái cây P P Quay trái cây P P Q h h h h h- 1 h h- 1 h Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 8
  9. 63  P mất cân bằng phải-trái (RL) – Bước 1: P Quay phải cây Q 35 35 Q 40 18 50 18 8 20 40 55 8 20 37 50 37 45 65 36 45 55 36 65 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 64  P mất cân bằng phải-trái (RL) - Bước 2: P Quay trái cây P 35 40 Q 18 40 35 50 37 50 45 55 8 20 18 37 36 45 55 8 20 36 65 65 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 9
  10. 65  Khi một node cây xảy ra mất cân bằng bên trái (cây con trái chênh lệch với cây con phải hơn một đơn vị): (thực hiện đối xứng với trường hợp mất cân bằng bên phải)  Mất cân bằng trái-trái (LL)  Quay phải  Mất cân bằng trái-trái (L-R)  Quay trái  Quay phải Cấu trúc dữ liệu và giải thuật - HCMUS 2011 66 Theo Wikipedia Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 10
  11. 67  Thực hiện hoàn toàn tương tự cây nhị phân tìm kiếm. 4 10 2 6 9 23 5 7 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 68  Thực hiện tương tự với việc thêm phần tử của cây nhị phân tìm kiếm.  Nếu xảy ra việc mất cân bằng thì xử lý bằng các trường hợp mất cân bằng đã biết. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 11
  12. 69  Thực hiện tương tự cây nhị phân tìm kiếm: xét 3 trường hợp, và tìm phần tử thế mạng nếu cần.  Sau khi xóa, nếu cây mất cân bằng, thực hiện cân bằng cây.  Lưu ý: việc cân bằng sau khi hủy có thể xảy ra dây chuyền. Cấu trúc dữ liệu và giải thuật - HCMUS 2011 70  Ví dụ: xóa 35 Phần tử thế mạng là 36 40 40 35 50 36 50 18 37 45 55 18 37 45 55 8 20 36 65 8 20 65 Cây vẫn cân bằng nên không phải hiệu chỉnh Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 12
  13. 71  Xóa phần tử 45 40 40 36 50 36 50 18 37 45 55 18 37 55 8 20 65 8 20 65 Node 50 bị lệch phải !!! Cấu trúc dữ liệu và giải thuật - HCMUS 2011 72  Xóa phần tử 45: cân bằng lại cây Quay trái tại node 50 40 40 55 36 50 36 50 65 18 37 55 18 37 8 20 65 8 20 Cấu trúc dữ liệu và giải thuật - HCMUS 2011 ©FIT-HCMUS 13