Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 9: Tìm kiếm (Searching) - Nguyễn Thị Xuân Hương

Nội dung text: Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 9: Tìm kiếm (Searching) - Nguyễn Thị Xuân Hương

1. Chương 9: TÌM KIẾM (Searching) 9.1. Bài toán tìm kiếm Input: Cho một tập n đối tuợng, mỗi đối tượng có m thuộc tính. Cho một giá trị khóa của phần tử cần tìm là X. Output: Phần tử cần tìm có giá trị khóa X có hoặc không có trong danh sách các đối tượng. Để đơn giản ta qui về bài toán: Input: Cho n giá trị khóa (là các số nguyên), khóa cần tìm X Output: Phần tử có giá trị khóa X có hoặc không có trong dãy số. 1
2. Chương 9: TÌM KIẾM (Searching) 9.2. Tìm kiếm tuần tự Ý tưởng : duyệt tuần tự các phần tử trong dãy khóa để so sánh với khóa cần tìm. VD : Tìm X= 5 trên dãy sau : 10 2 8 5 3 9 7 6 15 l1 : i = 0 so sánh X != A[i] -> i++ l2: i = 1 so sánh X != A[i] -> i++ l2: i = 2 so sánh X != A[i] -> i++ l2: i = 3 so sánh X = A[i] -> tìm thấy X=5 ở vị trí 3 -> dừng 2
3. Chương 9: TÌM KIẾM (Searching) 9.2. Tìm kiếm tuần tự Thảo luận: -Viết hàm thực hiện cho giải thuật và tính độ phức tạp giải thuật. -Cho biết ưu, nhược điểm của giải thuật trên,và khi nào nên sử dụng giải thuật? 3
4. Chương 9: TÌM KIẾM (Searching) 9.3. Tìm kiếm nhị phân Ý tưởng: tìm bằng phương pháp chia đôi trên dãy khóa đã được xếp Giải thuật: tìm x trên dãy a[n] với l = 0; r= n-1 Nếu dãy tồn tại ít nhất một phần tử - Chia đôi dãy tại vị trí k = (l+r)/2 -So sánh khóa x cần tìm với khóa tại vị trí chia đôi -Nếu x tìm x ở nửa trái: từ l đến k-1 -Nếu x > a[k] -> tìm x ở nửa phải: từ k+1 đến r -Nếu x = a[k] -> đã tìm thấy Ở nửa trái và nửa phải cũng tìm bằng phương pháp chia đôi như trên. 4
5. Chương 9: TÌM KIẾM (Searching) 9.3. Tìm kiếm nhị phân VD1 : Tìm X= 5 trên dãy: 0 1 2 3 4 5 6 7 8 1 2 4 5 6 8 9 12 15 •Chia đôi dãy tại k=(l+r)/2 •l1 : k= (0+8)/2=4 ; so sánh 5 tìm 5 ở dãy trái : từ vị trí left đến k-1 (từ 0 đến 3) 0 1 2 3 1 2 4 5 •l2 : k=(0+3)/2=1 ; so sánh 5 > A[1] -> tìm 5 ở dãy phải : từ vị trí k+1 đến right (từ 2 đến 3) 2 3 4 5 l3 : k = (2+3)/2 = 2 ; so sánh 5 > A[2] -> tìm 5 ở dãy phải : từ 3 đến 3 3 5 l4 : k = (3+3)/2 = 3; so sánh 5 = A[3] -> tìm thấy 5
6. Chương 9: TÌM KIẾM (Searching) 9.4. Cây tìm kiếm nhị phân tối ưu 9.4.1. Khái niệm: Cây nhị phân tìm kiếm tối ưu là cây NPTK mà mỗi nút trên cây có cây con trái và cây con phải có độ cao chênh nhau không quá 1. -> cây AVL Lịch sử cây AVL - AVL là tên viết tắt của các tác giả người Nga đã đưa ra định nghĩa của cây cân bằng Adelson-Velskii và Landis (1962). - Từ cây AVL người ta đã phát triển thêm nhiều loại CTDL hữu dụng khác như cây đỏ-đen (Red-Black Tree), B-Tree, 6
7. Chương 9: TÌM KIẾM (Searching) 9.4.2. Biểu diễn trên máy tính cấu trúc cây NPTK tối ưu: struct AVLTree{ int key ; int bal ; //chỉ số cân bằng của các nút trên cây AVLTree *left, *right; } ; AVLTree *root ; •Ta định nghĩa một số hằng sau: •#define LH -1 //Cây con trái cao hơn •#define EH 0 //Hai cây con bằng nhau •#define RH 1 //Cây con phải cao hơn 7
8. Chương 9: TÌM KIẾM (Searching) 9.4.2. Biểu diễn trên máy tính cấu trúc cây NPTK tối ưu: Đánh giá cây AVL -Cây có n nút -> cây AVL có chiều cao O(log2(n)). - Cây AVL là CTDL ổn định hơn CCBHT - Cây AVL với chiều cao được khống chế sẽ cho phép thực thi các thao tác tìm, thêm, hủy với chi phí O (log2(n)) và bảo đảm không suy biến thành O(n). 8
9. Chương 9: TÌM KIẾM (Searching) 9.4.3. Các thao tác trên cây NPTK tối ưu: -Khởi tạo -Thêm một phần tử vào cây AVL -Cân bằng lại một cây vừa bị mất cân bằng. - Xóa một phần tử trên cây AVL. -Cân bằng lại một cây vừa bị mất cân bằng. - Tìm kiếm 9
10. Chương 9: TÌM KIẾM (Searching) 9.4.3. Các thao tác trên cây NPTK tối ưu: 9.4.3.1 CÁC TRƯỜNG HỢP MẤT CÂN BẰNG Trường hợp 1: cây T lệch về bên trái (có 3 khả năng) 10
11. Chương 9: TÌM KIẾM (Searching) 9.4.3. Các thao tác trên cây NPTK tối ưu: 9.4.3.1 CÁC TRƯỜNG HỢP MẤT CÂN BẰNG •Trường hợp 2: cây T lệch về bên phải 11
12. Chương 9: TÌM KIẾM (Searching) Trường hợp : cây T lệch về bên trái 1.cây T1 lệch về bên trái. Ta thực hiện phép quay đơn Left-Left 2. cây T1 không lệch. Ta thực hiện phép quay đơn Left-Left 12
13. Chương 9: TÌM KIẾM (Searching) Quay đơn left – left: B1: T là gốc; T1 = T->left; Quay: T->left = T1->right;T1->right = T; B2:// đặt lại chỉ số cân bằng Nếu T1->bal = LH thì: T->bal = EH; T1->bal = EH; break; Nếu T1->bal = EH thì: T->bal = LH; T1->bal = RH; break; B3:// T trỏ đến gốc mới T = T1; 13
14. Chương 9: TÌM KIẾM (Searching) 3: cây T1 lệch về bên phải. Ta thực hiện phép quay kép Left-Right 14
15. Chương 9: TÌM KIẾM (Searching) 3: cây T1 lệch về bên phải. Ta thực hiện phép quay kép Left-Right B1:gốc T; T1 = T->left; T2 = T1->right;; Quay: T->left = T2->right; T2->right = T; T1->right = T2->left;T2->left = T1; B2: //đặt lại chỉ số cân bằng Nếu T2->bal = LH: T->bal = RH; T1->bal = EH; break; Nếu T2->bal = EH: T->bal = EH; T1->bal = EH; break; Nếu T2->bal = RH:T->bal = EH; T1->bal = LH; break; B3: T2->balFactor = EH; T = T2; 15
16. Chương 9: TÌM KIẾM (Searching) 9.4.3. Chèn thêm một nút vào cây nhị phân tìm kiếm tối ưu. •Thực hiện tương tự như trên CNPTK, sau khi thêm xong, nếu chiều cao của cây thay đổi, từ vị trí thêm vào, ta phải tìm ngược lên gốc để kiểm tra các nút bị mất cân bằng không. Nếu có, ta phải cân bằng lại ở nút này. TToán: Giả sử cần thêm vào một nút mang thông tin X. 1. Tìm kiếm vị trí thích hợp để thêm nút X (đưa ra thông báo nếu đã có nút X rồi) 2. Thêm nút X vào cây 3. Cân bằng lại cây. 16
17. Chương 9: TÌM KIẾM (Searching) 9.4.4. Xóa một nút vào cây nhị phân tìm kiếm tối ưu. • Cũng giống như thao tác thêm một nút, việc hủy một phần tử X ra khỏi cây AVL thực hiện giống như trên CNPTK. Chỉ sau khi hủy, nếu tính cân bằng của cây bị vi phạm ta sẽ thực hiện việc cân bằng lại. 17
18. Chương 9: TÌM KIẾM (Searching) 9.5. Hàm băm (hash) Ý tưởng: thay vì so sánh giá trị khóa với các bản ghi, ta thực hiện phép tìm kiếm dựa vào chính giá trị của từng khóa. k -> h(k) :Từ giá trị khóa k -> Biến đổi thành một địa chỉ (lưu trữ thông tin đối tượng có khóa k -> dùng để tìm kiếm đối tượng). - h(k): hàm băm (Hash) dùng để ánh xạ tập các giá trị khóa k lên tập các địa chỉ tương đối 0 Bảng có m phần tử chứa các khóa k: là Bảng băm (Hash table) => Vấn đề: xây dựng h(k) như thế nào để các khóa phân bố đều trên bảng băm – không có hai hay nhiều khóa cùng băm vào một địa chỉ (hiện tượng xung đột) 18
19. Chương 9: TÌM KIẾM (Searching) 9.5.1. Một số phương pháp xây dựng hàm băm: 1/ Phương pháp chia: h(k) = k mod m Thảo luận: - Nếu có n giá trị khóa thì chọn m là bao nhiêu? VD: có dãy khóa sau: 154 125 215 361 492 629 184 Chọn m= 7; h(k) = k mod 7 -> Dãy địa chỉ tương ứng: 0 6 5 4 2 6 2 19
20. Chương 9: TÌM KIẾM (Searching) 9.5.1. Một số phương pháp xây dựng hàm băm: 2/ Phương pháp phân đoạn: Tách: tách các chữ số thành các đoạn, xếp mỗi đoạn thành hàng -> phối hợp các đoạn theo cách nào đó VD: có khóa: 14023485 tách: 485 023 014 Cộng 522 Gấp: 023 584 410 Cộng 1017 20
21. Chương 9: TÌM KIẾM (Searching) 9.5.1. Một số phương pháp xây dựng hàm băm: 3/ Phương pháp nhân: K k2 H(k) 1346 1811716 117 hoặc 171 2145 4601025 010 hoặc 102 0568 322624 226 hoặc 262 Thảo luận: - Tại sao lại chọn các cách phối hợp trên để xây dựng hàm băm? - Còn có cách nào khác để xây dựng hàm băm không? Có thể kết hợp các phương pháp trên được không? Tại sao? - Đánh giá ưu, nhược điểm của các phương pháp trên? - Với các khóa không phải là số thì băm như thế nào? 21
22. Chương 9: TÌM KIẾM (Searching) 9.5.2. Tổ chức bảng băm (Cấu trúc dữ liệu Bảng băm) 9.5.2.1. Bảng băm đóng: Sử dụng cấu trúc mảng để lưu trữ các khóa của bảng băm (địa chỉ của mảng chính là địa chỉ của các khóa. VD: có dãy khóa sau: 154 125 215 361 492 629 184 Với h(k) = k mod 7 Dãy địa chỉ tương ứng: 0 6 5 4 2 6 2 Nhận xét: có hai khóa cùng băm vào địa chỉ 6, hai khóa cùng băm vào địa chỉ 2 -> Hiện tượng xung đột h(k) = ((h(k) +i ) mod m =>Các phương pháp xử lý xung đột: 22
23. Chương 9: TÌM KIẾM (Searching) 9.5.2. Tổ chức bảng băm (Cấu trúc dữ liệu Bảng băm) 9.5.2.1. Bảng băm đóng: =>Các phương pháp xử lý xung đột: 1. Dò tìm tuyến tính: nếu có xung đột thì băm lại h(k) = ((h(k) +i ) mod m với i = 1-> m *Xây dựng Bảng băm 0 1 2 3 4 5 6 154 629 492 184 361 215 125 •154 băm vào địa chỉ 0, •125 băm vào địa chỉ 6, . •629 băm vào địa chỉ 6 -> xung đột •-> băm lại lần 1: ((629 mod 7)+1) mod 7 = 0 -> xung đột •-> băm lại lần 2: ((629 mod 7) + 2) mod 7) =1 -> địa chỉ 1 chứa 629 23
24. Chương 9: TÌM KIẾM (Searching) 1. Dò tìm tuyến tính: *Tìm kiếm trên bảng băm: Tìm khóa k dựa vào hàm băm Giải thuật: B1: Xác định địa chỉ h(k) = k mod m B2: Nếu Trên bảng băm có khóa k tại địa chỉ h(k) -> tìm thấy, dừng; Ngược lại - có xung đột: Dò tìm tuyến tính h(k) = ((h(k) +i ) mod m với i = 1-> m VD: tìm k = 154 0 1 2 3 4 5 6 Có h(k) = k Mod 7 = 1540 -> tìm629 thấy 492 184 361 215 125 Tìm k = 184 Có h(k) = k Mod 7 = 2 -> Xung đột Băm lại: h(k) = (2 +1) Mod 7 = 3 -> tìm thấy 24
25. Chương 9: TÌM KIẾM (Searching) 1. Dò tìm tuyến tính: Thảo luận: - Đánh giá độ phức tạp của phép băm và phép tìm kiếm trên bảng băm với phép dò tuyến tính? - Khai báo dữ liệu và viết hàm thực hiện các phép toán trên CTDL bảng băm (khởi tạo, chèn, xóa, kiểm tra đầy, rỗng, tìm kiếm) - Nhận xét về ưu, nhược điểm của bảng băm đóng với phương pháp dò tìm tuyến tính. Khi nào thì sử dụng phương pháp này? 25
26. Chương 9: TÌM KIẾM (Searching) 2.Dò tìm bình phương: nếu có xung đột thì băm lại h(k) = ((h(k) +i2 ) mod m với i = 1-> m *Xây dựng Bảng băm VD: có dãy khóa sau: 154 125 215 361 492 629 184 Dãy địa chỉ tương ứng: 0 6 5 4 2 6 2 0 1 2 3 4 5 6 154 492 629 361 215 125 •629 băm vào địa chỉ 6 -> xung đột •-> băm lại lần 1: ((629 mod 7)+12) mod 7 = 0 -> xung đột •-> băm lại lần 2: ((629 mod 7) + 22) mod 7) =3 -> địa chỉ 3 chứa 629 26
27. Chương 9: TÌM KIẾM (Searching) 2.Dò tìm bình phương: * Tìm kiếm trên bảng băm: Tìm khóa k dựa vào hàm băm Giải thuật: B1: Xác định địa chỉ h(k) = k mod m B2: Tìm trên bảng khóa k tại địa chỉ h(k) -> thấy, dừng; Ngược lại: có xung đột Dò tìm bình phương h(k) = ((h(k) +i2 ) mod m với i = 1-> m Thảo luận: -Đánh giá độ phức tạp của phép băm và phép tìm kiếm trên bảng băm với phép dò tìm bình phương? -Khai báo dữ liệu và viết hàm thực hiện các phép toán trên CTDL bảng băm (khởi tạo, chèn, xóa, kiểm tra đầy, rỗng, tìm kiếm) - Nhận xét về ưu, nhược điểm của bảng băm đóng với phương pháp dò tìm bình phương?. Khi nào thì sử dụng phương pháp này? 27
28. Chương 9: TÌM KIẾM (Searching) 9.5.2.1. Bảng băm mở: sử dụng phương pháp địa chỉ mở để giải quyết xung đột (Danh sách liên kết các khóa cùng băm vào một địa chỉ) VD: có dãy khóa sau: 154 125 215 361 492 629 184 Dãy địa chỉ tương ứng: 0 6 5 4 2 6 2 Xây dựng bảng băm: là m danh sách liên kết với mỗi phần tử trong danh sách là các khóa cùng băm vào địa chỉ i tương ứng với danh sách thứ i 28
29. Chương 9: TÌM KIẾM (Searching) 9.5.2.1. Bảng băm mở: Tìm kiếm trên bảng băm: Tìm kiếm khóa k trên bảng băm - B1: Tính h(k) - B2: Dò tìm k trên danh sách thứ i = h(k); Thảo luận: - Đánh giá độ phức tạp của phép băm và phép tìm kiếm trên bảng băm mở? - Khai báo dữ liệu và viết hàm thực hiện các phép toán trên CTDL bảng băm (khởi tạo, chèn, xóa, kiểm tra đầy, rỗng, tìm kiếm) - Nhận xét về ưu, nhược điểm của bảng băm mở? Khi nào thì sử dụng phương pháp này? 29