Bài giảng Tìm kiếm - Searching

Tìm kiếm - Searching Các pp tìm kiếm cơ bản Tìm kiếm trên cây tìm kiếm nhị phân Cây cân bằng Phép băm (hashing) Bài toán tìm kiếm Tìm một hay nhiều mẩu thông tin từ một số lượng lớn thông tin được lưu trữ Tìm khóa X trong dãy khóa s={s1, s2,.., sn} Tìm kiếm kết thúc khi Tìm được khóa → tìm kiếm được thỏa Kô có khóa nào bằng X → tìm kiếm kô thỏa Tìm kiếm tuần tự Đơn giản Procedure SequentialSearching(s, n, x); begin i:=1; s[n+1]:=x; while s[i] x do i:=i+1; if i=n+1 then return(0) else return(i); End; độ phức tạp O(n) Tìm kiếm nhị phân Dãy khóa đã được sắp giả sử tăng dần Chọn khóa ở giữa ki để so sánh với khóa tìm kiếm. Nếu khóa x nhỏ hơn → tìm ở dãy trước, ngược lại tìm dãy sau, ngược lại → kết thúc – tìm thấy Procedure BinarySearch(s, n, x) Begin l:=1; r:=n; While l s[m] then l:=m+1 else return (m) end; return(0); End; Đánh giá O(logn) Yêu cầu sắp xếp Tìm kiếm trên cây tìm kiếm nhị phân Cây tìm kiếm M-đường (M-way search tree) Định nghĩa Ví dụ Tìm kiếm Các phép toán trên cây Định nghĩa Một cây M - đường T là tập hữu hạn khóa hoặc là rỗng hoặc là tập của n cây con M-đường T0, T1, .., Tn-1 và n-1 khóa k1, k2, .., kn-1, với 2  n  M sao cho các khóa và các nút thỏa mãn tính chất sau: Các khóa trên mỗi nút khác nhau và được sắp: ki ki với 1  i  n-1. Cây TI gọi là cây con phải ứng với khóa ki Ví dụ M=4 Tìm kiếm trên cây M-đường Tìm khóa x trên cây Bắt đầu từ gốc If cây rỗng → kết thúc → fail Else nút gốc chứa x → kết thúc → success Else xảy ra 3 trường hợp sau x kn-1: tìm trên cây Tn-1 i sao cho 1  i  n-1 mà ki tự tìm hiểu Problem: Tìm chuỗi lặp dài nhất trong xâu.