bài giảng các chuyên đề phần 5

Cấu trúc dữ liệu và giải thuậtTÌM KIẾM (SEARCHING)I. BÀI TOÁN TÌM KIẾM Cùng với sắp xếp, tìm kiếm là một đòi hỏi rất thường xuyên trong các ứng dụng tin học. Bài toán tìm kiếm có thể phát biểu như sau: Cho một dãy gồm n bản ghi r1, r2, ..., rn. Mỗi bản ghi ri (1 ≤ i ≤ n) tương ứng với một khoá ki. Hãy tìm bản ghi có giá trị khoá bằng X cho trước. X được gọi là khoá tìm kiếm hay đối trị tìm ...
Nội dung trích xuất từ tài liệu:
bài giảng các chuyên đề phần 5Cấu trúc dữ liệu và giải thuật 70 §8. TÌM KIẾM (SEARCHING)I. BÀI TOÁN TÌM KIẾMCùng với sắp xếp, tìm kiếm là một đòi hỏi rất thường xuyên trong các ứng dụng tin học. Bài toántìm kiếm có thể phát biểu như sau:Cho một dãy gồm n bản ghi r1, r2, ..., rn. Mỗi bản ghi ri (1 ≤ i ≤ n) tương ứng với một khoá ki. Hãytìm bản ghi có giá trị khoá bằng X cho trước.X được gọi là khoá tìm kiếm hay đối trị tìm kiếm (argument).Công việc tìm kiếm sẽ hoàn thành nếu như có một trong hai tình huống sau xảy ra:• Tìm được bản ghi có khoá tương ứng bằng X, lúc đó phép tìm kiếm thành công (successful).• Không tìm được bản ghi nào có khoá tìm kiếm bằng X cả, phép tìm kiếm thất bại (unsuccessful).Tương tự như sắp xếp, ta coi khoá của một bản ghi là đại diện cho bản ghi đó. Và trong một sốthuật toán sẽ trình bày dưới đây, ta coi kiểu dữ liệu cho mỗi khoá cũng có tên gọi là TKey.const {Số khoá trong dãy khoá, có thể khai dưới dạng biến số nguyên để tuỳ biến hơn} n = ...;type {Kiểu dữ liệu một khoá} TKey = ...; TArray = array[1..n] of TKey;var {Dãy khoá} k: TArray;II. TÌM KIẾM TUẦN TỰ (SEQUENTIAL SEARCH)Tìm kiếm tuần tự là một kỹ thuật tìm kiếm đơn giản. Nội dung của nó như sau: Bắt đầu từ bản ghiđầu tiên, lần lượt so sánh khoá tìm kiếm với khoá tương ứng của các bản ghi trong danh sách, chotới khi tìm thấy bản ghi mong muốn hoặc đã duyệt hết danh sách mà chưa thấy{Tìm kiếm tuần tự trên dãy khoá k1, k2, ..., kn; hàm này thử tìm xem trong dãy có khoá nào = X không, nếu thấy nó trả về chỉ số củakhoá ấy, nếu không thấy nó trả về 0. Có sử dụng một khoá phụ kn+1 được gán giá trị = X}function SequentialSearch(X: TKey): Integer;var i: Integer;begin i := 1; while (i X thì có nghĩa là đoạn từ kmedian tới ksup chỉ chứa toàn khoá > X, ta tiến hành tìm kiếm tiếp với đoạn từ kinf tới kmedian - 1.• Nếu kmedian = X thì việc tìm kiếm thành công (kết thúc quá trình tìm kiếm).Lê Minh HoàngCấu trúc dữ liệu và giải thuật 71Quá trình tìm kiếm sẽ thất bại nếu đến một bước nào đó, đoạn tìm kiếm là rỗng (inf > sup).{Tìm kiếm nhị phân trên dãy khoá k1 ≤ k2 ≤ ... ≤ kn; hàm này thử tìm xem trong dãy có khoá nào = X không, nếu thấy nó trả về chỉ sốcủa khoá ấy, nếu không thấy nó trả về 0}function BinarySearch(X: TKey): Integer;var inf, sup, median: Integer;begin inf := 1; sup := n; while inf ≤ sup do begin median := (inf + sup) div 2; if kmedian = X then begin BinarySearch := median; Exit; end; if kmedian < X then inf := median + 1 else sup := median - 1; end; BinarySearch := 0;end;Người ta đã chứng minh được độ phức tạp tính toán của thuật toán tìm kiếm nhị phân trong trườnghợp tốt nhất là O(1), trong trường hợp xấu nhất là O(log2n) và trong trường hợp trung bình cũng làO(log2n). Tuy nhiên, ta không nên quên rằng trước khi sử dụng tìm kiếm nhị phân, dãy khoá phảiđược sắp xếp rồi, tức là thời gian chi phí cho việc sắp xếp cũng phải tính đến. Nếu dãy khoá luônluôn biến động bởi phép bổ sung hay loại bớt đi thì lúc đó chi phí cho sắp xếp lại nổi lên rất rõ làmbộc lộ nhược điểm của phương pháp này.IV. CÂY NHỊ PHÂN TÌM KIẾM (BINARY SEARCH TREE - BST)Cho n khoá k1, k2, ..., kn, trên các khoá có quan hệ thứ tự toàn phần. Cây nhị phân tìm kiếm ứng vớidãy khoá đó là một cây nhị phân mà mỗi nút chứa giá trị một khoá trong n khoá đã cho, hai giá trịchứa trong hai nút bất kỳ là khác nhau. Đối với mọi nút trên cây, tính chất sau luôn được thoả mãn:• Mọi khoá nằm trong cây con trái của nút đó đều nhỏ hơn khoá ứng với nút đó.• Mọi khoá nằm trong cây con phải của nút đó đều lớn hơn khoá ứng với nút đó 4 2 6 1 3 5 7 9 Hình 17: Cây nhị phân tìm kiếmThuật toán tìm kiếm trên cây có thể mô tả chung như sau:Trước hết, khoá tìm kiếm X được so sánh với khoá ở gốc cây, và 4 tình huống có thể xảy ra:• Không có gốc (cây rỗng): X không có trên cây, phép tìm kiếm thất bại• X trùng với khoá ở gốc: Phép tìm kiếm thành công• X nhỏ hơn khoá ở gốc, phép tìm kiếm được tiếp tục trong cây con trái của gốc với cách làm tương tựLê Minh HoàngCấu trúc dữ liệu và giải thuật 72• X lớn hơn khoá ở gốc, phép tìm kiếm được tiếp tục trong cây con phải của gốc với cách l ...