Academia.eduAcademia.edu
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++, nhưng không sử dụng class. • Công cụ: VS C++, ứng dụng dạng console. 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 xây dựng thuật toán tốc độ cao định tuyến gói tin trong router. • Ứng dụng khai phá dữ liệu hiện năng cao trong CSDL lớn, nhiều chiều. • Ứ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% • Kiểm tra giữa học phần (bắt buộc): 20% • 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. Cambridge University Press - 2008; PETER BRASS. • Introduction to Algorithms. McGraw Hill - 1990; Thomas H. C., Charles E.L., and Ronald L.R. • Giáo trình thuật toán. Thống kế 2002. Nhóm Ngọc Anh Thư dịch • Data Structures, Algorithms, and Object-Oriented Programming; McGraw Hill; Gregory Heilleman 1996. • Algorithms and Data Structures in C++; 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. • Khi đó thời gian tìm kiếm là O(N). Để 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). Các cây NPTK như thế gọi là balanced binary search trees. • Examples are AVL tree, red-black tree. 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. • Theo định nghĩa, ta có N h ≥ N h −1 + N h − 2 + 1 ≥ 2 N h−2 + 1 > 2 N h−2 N h > 2i N h − 2*i i=(h-1)/2; N > 2( h −1) / 2 log N > ( h − 1) / 2 (log N + 1) * 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. • Có hai dạng quay single rotations or double rotations. x y x y C A B A Before Rotation B C After Rotation e.g. Single Rotation TS Nguyễn Mạnh Hùng – BM CNPM 11 Các phép quay (cont.) • Khi thêm/xóa có thể làm thay đổi chiều cao của cây. • Khi đó điều kiện cân bằng có thể bị vi phạm. Chẳng hạn tại nút x sự khác nhau của left(x) và right(x) là 2. • Áp dụng các phép quay tại nút x để hiệu chỉnh 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.) • Các trường hợp cây bị lệch phải ta thực hiện các phép quay đơn và quay kép tương tự như trương hợp cây lệch trái nhưng theo chiều ngược lại. 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. Với mỗi nút x bắt gặp trên path kiểm tra left(x) và right(x). Nếu đã thỏa mãn đk cân bằng thì bỏ qua và xét tiếp nút ở trên. Nếu không thỏa mãn thì phải tiến hành quay đơn hoặc kép. • 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). ĐK cân bằng bị vi phạm tại nút x. chiều cao của left(x) is h+2 chiều cao của right(x) is h. quay phải nút y quanh nút x. 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. ĐK cân bằng bị vi phạm tại nút x. Single rotation takes O(1) time. Insertion takes O(log N) time. 22 TS Nguyễn Mạnh Hùng – BM CNPM AVL Tree x 5 5 8 3 4 1 4 1 8 y 3 C B A 0.8 Insert 0.8 3 1 0.8 5 4 8 After rotation 23 TS Nguyễn Mạnh Hùng – BM CNPM Double rotation Thêm nút vào cây con B1 or B2. ĐK cân bằng bị vi phạm tại nút x. Quay trái z quanh y; 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. ĐK cân bằng bị vi phạm tại nút x. Quay phải z quanh y; quay trái z quanh x also called right-left rotate 25 TS Nguyễn Mạnh Hùng – BM CNPM 5 5 AVL Tree y 8 3 A 4 1 x C 8 3 4 1 B z 3.5 Insert 3.5 4 5 3 1 3.5 8 After Rotation 26 TS Nguyễn Mạnh Hùng – BM CNPM An Extended Example Insert 3,2,1,4,5,6,7, 16,15,14 Single rotation 3 3 2 3 2 2 Fig 1 1 3 Fig 4 Fig 2 1 2 2 Single rotation Fig 3 1 1 3 3 Fig 5 Fig 6 4 4 5 27 TS Nguyễn Mạnh Hùng – BM CNPM 2 2 Single rotation 1 1 4 4 3 5 3 5 Fig 8 Fig 7 6 4 2 1 4 Single rotation 2 5 6 3 6 3 1 4 5 Fig 10 Fig 9 2 1 7 6 7 3 5 Fig 11 28 TS Nguyễn Mạnh Hùng – BM CNPM 4 2 6 7 3 1 16 5 Fig 12 4 Double rotation 2 4 6 2 1 16 5 Fig 13 6 7 3 1 3 5 15 16 15 Fig 14 7 29 TS Nguyễn Mạnh Hùng – BM CNPM 4 2 1 Double rotation 5 7 2 6 3 4 15 1 3 15 6 16 7 5 Fig 15 14 14 16 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ới mỗi nút x bắt gặp trên path, kiểm tra left(x) và right(x). Nếu thõa mãn ĐK cân bằng thì xét tiếp nút ở trên, nếu không thõa mãn thì thực hiện phép quay tương ứng. • Với phép xóa nút thì sau khi thực hiện phép quay ở nút x, chúng ta vẫn có thể phải thực hiện phép quay ở các nút trên của x. 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