Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 11: Cây AVL

Nội dung text: Bài giảng Cấu trúc dữ liệu & giải thuật (Data Structures & Algorithms) - Bài 11: Cây AVL

1. Cây AVL Nguyễn Mạnh Hiển Khoa Công nghệ thông tin hiennm@tlu.edu.vn
2. Mở đầu • Khi xây dựng cây nhị phân tìm kiếm, ta muốn có kiểu cây nào hơn? • Ví dụ: dựng cây từ dãy {3, 5, 8, 20, 18, 13, 22} 3 5 13 8 20 13 5 18 3 8 18 22 20 22
3. Mở đầu (tiếp) • Cây nhị phân đầy đủ khó xây dựng khi có các phép chèn và xóa • Ta muốn một cây có các tính chất sau: − Độ sâu của cây = O(logN) − Cho phép chèn và xóa với độ phức tạp O(logN) • Cây AVL là một kiểu cây như vậy!
4. Cây AVL (Adelson-Velskii & Landis) • Cây AVL là một cây nhị phân tìm kiếm trong đó: − với mọi nút, chiều cao của hai cây con (trái & phải) của nó sai khác không quá 1 − quy ước cây rỗng có chiều cao -1 8 5 18 3 13 20 22
5. Cây AVL • Cây AVL là cây nhị phân tìm kiếm với điều kiện cân bằng: − nhằm đảm bảo độ sâu của cây là O(logN) − và vì vậy, các thao tác tìm kiếm, chèn và xóa có độ phức tạp O(logN) • Điều kiện cân bằng: − Đối với mọi nút trong cây, chiều cao của các cây con trái và phải sai khác không quá 1
6. Cây nào là cây AVL ?
7. Chèn và xóa trên cây AVL • Thực hiện chèn và xóa như trong cây nhị phân tìm kiếm thông thường • Thỉnh thoảng điều kiện cân bằng bị vi phạm: − Sửa nó bằng phép xoay − Sau phép xoay, cây trở lại cân bằng
8. Ví dụ phép chèn Chèn 6 làm điều kiện cân Sửa bằng phép xoay bằng bị vi phạm
9. Vi phạm điều kiện cân bằng • Nếu điều kiện cân bằng bị vi phạm sau khi chèn một nút: − Những nút nào cần được xoay? − Chỉ những nút trên đường đi từ điểm chèn ngược về gốc có thể bị ảnh hưởng (chiều cao thay đổi) • Chỉ cần tái cân bằng dùng phép xoay tại nút sâu nhất có điều kiện cân bằng bị vi phạm − Toàn bộ cây sẽ được tái cân bằng
10. Các trường hợp vi phạm • Có bốn trường hợp có thể xảy ra tại nút k 1. trái-trái: chèn vào cây con trái của con trái của k 2. trái-phải: chèn vào cây con phải của con trái của k 3. phải-trái: chèn vào cây con trái của con phải của k 4. phải-phải: chèn vào cây con phải của con phải của k • Hai trường hợp 1 và 4 (chèn “ngoài”) tương tự nhau: − Phép xoay đơn để tái cân bằng • Hai trường hợp 2 và 3 (chèn “trong”) tương tự nhau: − Phép xoay kép để tái cân bằng
11. Độ phức tạp trên cây AVL • Chi phí: − Thêm không gian lưu trữ thông tin chiều cao ở mỗi nút − Chèn và xóa trở nên phức tạp hơn, nhưng vẫn là O(logN) • Lợi ích: − Chèn, xóa và tìm kiếm trong trường hợp tồi nhất chỉ là O(logN)
12. Phép xoay đơn (trường hợp 1) • Thay nút k2 bằng nút k1 • Cho nút k2 trở thành con phải của nút k1 • Cho cây con Y trở thành con trái của nút k2 • Trường hợp 4, cách làm tương tự
13. Ví dụ • Sau khi chèn 6: − Điều kiện cân bằng ở nút 8 bị vi phạm
14. Phép xoay đơn (trường hợp 1)
15. Ví dụ • Chèn tuần tự 3, 2, 1 và sau đó 4, 5, 6, 7 vào một cây AVL rỗng
16. Ví dụ (tiếp) • Chèn 4, 5:
17. Ví dụ (tiếp) • Chèn 6:
18. Ví dụ (tiếp) • Chèn 7:
19. Phép xoay đơn không giải quyết được các trường hợp khác • Đối với trường hợp 2: − Sau phép xoay đơn, nút k1 không cân bằng • Ta cần dùng phép xoay kép cho hai trường hợp 2 và 3
20. Phép xoay kép (trường hợp 2) • Phép xoay kép trái-phải để sửa trường hợp 2 • Đầu tiên xoay giữa nút k1 và nút k2 • Sau đó xoay giữa nút k2 và nút k3 • Trường hợp 3, cách làm tương tự
21. Ví dụ • Chèn tuần tự 16, 15 và 14 vào cây sau:
22. Ví dụ (tiếp) • Chèn 16, 15:
23. Ví dụ (tiếp) • Chèn 14:
24. Phép xoay kép (trường hợp 2)