- CẤU TRÚC DỮ LIỆU NÂNG CAO • Các kiến thức yêu cầu • Tóm tắt nội dung môn học • Phương pháp kiểm tra đánh giá • Tài liệu tham khảo 1 TS Nguyễn Mạnh Hùng – BM CNPM Các kiến thức yêu cầu • Các thuật toán và cấu trúc dữ liệu cơ bản • Ngôn ngữ lập trình: C. - 2 TS Nguyễn Mạnh Hùng – BM CNPM Tóm tắt nội dung môn học • Cây cân bằng • Cây đỏ đen (red black tree. - Cây 2-3-4 • Interval Heap • Priority Search Tree • B-Tree • Phương pháp phân tích khấu trừ • Cấu trúc đóng nhị thức • Cấu trúc đóng Fibonacci • Cấu trúc các tập rời nhau 3 TS Nguyễn Mạnh Hùng – BM CNPM Ứng dụng • Ứng dụng trong đánh chỉ mục các CSDL lớn. - Ứng dụng trong xử lý dữ liệu không gian • Ứng dụng trong xử lý dữ liệu Multimedia 4 TS Nguyễn Mạnh Hùng – BM CNPM Phương pháp kiểm tra đánh giá • Điểm chuyên cần: 10. - Thi kết thúc học phần (bắt buộc): 70% 5 TS Nguyễn Mạnh Hùng – BM CNPM Tài liệu tham khảo • Slides bài giảng môn học • Advanced Data Structures. - Tác giả Alan Parker,1993 6 TS Nguyễn Mạnh Hùng – BM CNPM Lecture 1: Cây cân bằng • Cây nhị phân tìm kiếm (NPTK) có thể bị suy biến thành danh sách tuyến tính. - Để tăng tốc độ tìm kiếm thì chiều cao của cây phải nhỏ. - Để tăng tốc độ tìm kiếm thì chiều cao của cây NPTK phải là O(log N). - 7 TS Nguyễn Mạnh Hùng – BM CNPM AVL Tree (Adelson-Velskii,Landis 1962 ) Chiều cao của nút. - Chiều cao của nút lá bằng 1 • The height of an internal node is the maximum height of its children plus 1 8 TS Nguyễn Mạnh Hùng – BM CNPM AVL Tree • Cây AVL là cây NPTK trong đó. - Mọi nút trên cây thì chiều cao của cây con trái và chiều cao của cây con phải chênh lệch nhau không quá 1 9 TS Nguyễn Mạnh Hùng – BM CNPM AVL Tree • X gốc của cây AVL có chiều cao h. - Nh số nút tối thiểu trên cây chiều cao h. - 2 > h 10 TS Nguyễn Mạnh Hùng – BM CNPM Các phép quay • Khi thực hiện các phép toán (insertion or deletion), chúng ta cần phải biến đổi cây để đảm bảo tích chất cân bằng. - Single Rotation 11 TS Nguyễn Mạnh Hùng – BM CNPM Các phép quay (cont. - Khi thêm/xóa có thể làm thay đổi chiều cao của cây. - 12 TS Nguyễn Mạnh Hùng – BM CNPM Case 1: Cây lệch trái 13 TS Nguyễn Mạnh Hùng – BM CNPM Case 1.1: Quay đơn phải T1 quanh T 14 TS Nguyễn Mạnh Hùng – BM CNPM Case 1.2: Quay đơn phải T1 15 TS Nguyễn Mạnh Hùng – BM CNPM Case 1.3: Quay kép Left-Right với T2 Quay trái T2 quanh T1, Quay phải T2 quanh T 16 TS Nguyễn Mạnh Hùng – BM CNPM Case 2: Cây lệch phải 17 TS Nguyễn Mạnh Hùng – BM CNPM Case 2: Cây lệch phải (Cont. - 18 TS Nguyễn Mạnh Hùng – BM CNPM Insertion • Tiến hành tương tự như thêm khóa trong CNPTK. - Kiểm tra các nút trên đường dẫn từ nút mới thêm đến gốc. - Nếu đã thỏa mãn đk cân bằng thì bỏ qua và xét tiếp nút ở trên. - Với phép thêm nút, phải quay tối đa một lần (hoặc quay đơn hoặc quay kép) 19 TS Nguyễn Mạnh Hùng – BM CNPM Insertion • Giả sử x là nút có sự chênh lệnh của left(x) và right(x) lớn hơn 1 (bằng 2. - Giả sử chiều cao của x là h+3 • Có 4 TH sau. - Chiều cao của left(x) là h+2 (height of right(x) is h. - H of left(left(x)) is h+1 ⇒ single rotate with left child • H of right(left(x)) is h+1 ⇒ double rotate with left child – Chiều cao của right(x) là h+2 (height of left(x) is h. - H of right(right(x)) is h+1 ⇒ single rotate with right child • H of left(right(x)) is h+1 ⇒ double rotate with right child 20 TS Nguyễn Mạnh Hùng – BM CNPM Single rotation Thêm nút mới vào cây con A làm cho chiều cao của cây con A tăng lên 1 (bằng h+1). - chiều cao của left(x) is h+2 chiều cao của right(x) is h. - Nghiêng trái Nghiêng phải 21 TS Nguyễn Mạnh Hùng – BM CNPM Single rotation Thêm nút vào cây con C. - Single rotation takes O(1) time. - 22 TS Nguyễn Mạnh Hùng – BM CNPM AVL Tree 5 x 5 3 y 8 C B A 0.8 Insert 0.8 3 1 5 After rotation TS Nguyễn Mạnh Hùng – BM CNPM Double rotation Thêm nút vào cây con B1 or B2. - quay phải z quanh x also called left-right rotate 24 TS Nguyễn Mạnh Hùng – BM CNPM Double rotation Thêm nút vào cây con B1 or B2. - quay trái z quanh x also called right-left rotate 25 TS Nguyễn Mạnh Hùng – BM CNPM 5 x AVL Tree 5 C y 8 3 3 8 A 1 4 z 1 4 B 3.5 Insert After Rotation 1 3.5 26 TS Nguyễn Mạnh Hùng – BM CNPM An Extended Example Insert Single rotation Fig 1 2 3 Fig 4 Fig 2 2 1 2 Single rotation Fig 3 1 1 3 3 Fig 5 Fig TS Nguyễn Mạnh Hùng – BM CNPM 2 2 Single rotation Fig 8 Fig 7 6 4 4 Single rotation Fig 9 Fig Fig 11 28 TS Nguyễn Mạnh Hùng – BM CNPM Fig 12 4 Double rotation Fig 13 7 15 Fig 14 29 TS Nguyễn Mạnh Hùng – BM CNPM 4 4 Double rotation Fig 15 14 14 Fig 16 30 TS Nguyễn Mạnh Hùng – BM CNPM Deletion • Xóa nút x như trong CNPTK. - Kiểm tra các nút trên path từ nút thay thế đến nút gốc. - Vì vậy sau khi quay chúng ta vẫn phải tiếp tục xét các nút ở phía trên 31 TS Nguyễn Mạnh Hùng – BM CNPM Single rotations in deletion Xóa nút trên cây con C. - rotate with left child 32 TS Nguyễn Mạnh Hùng – BM CNPM Single rotations in deletion Xóa nút trên cây con A. - rotate with right child 33 TS Nguyễn Mạnh Hùng – BM CNPM Double rotation Xóa nút trên cây con C. - also called left-right rotate 34 TS Nguyễn Mạnh Hùng – BM CNPM Double rotation Xóa nút trên cây con A. - also called right-left rotate 35 TS Nguyễn Mạnh Hùng – BM CNPM Ví dụ xóa nút X X 36 TS Nguyễn Mạnh Hùng – BM CNPM