Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 7: Tìm kiếm

ớc, giải 
thuật giảm kích thước của phần này đi khoảng một nửa. Để tiện theo dõi tiến 
trình của giải thuật, chúng ta cần xác nhận một điều rằng, trước mỗi lần lặp có 
một điều kiện luôn đúng: khoá đích, nếu có trong danh sách, phải luôn nằm trong 
khoảng từ bottom đến top, có kể cả hai vị trí này. Điều kiện này lúc đầu được bảo 
đảm bằng cách đặt bottom bằng 0 và top là the_list.size()–1. 
Trước tiên , giải thuật tìm vị trí phần tử ở giữa bottom và top theo công thức 
 (bottom + top) 
mid = 
 2 
Kế đó giải thuật so sánh khoá đích với khoá của phần tử tại vị trí mid và thay 
đổi top hoặc bottom dựa theo kết quả của phép so sánh này. 
Chúng ta lưu ý rằng giải thuật nên kết thúc khi top ≤ bottom; tức là khi 
phần danh sách cần tìm còn không quá một phần tử (giả sử rằng giải thuật đã 
không chấm dứt sớm hơn trước đó trong trường hợp khoá đích đã được tìm thấy). 
Cuối cùng, để chắc chắn rằng giải thuật dừng, số phần tử cần tìm của danh 
sách (top – bottom + 1) phải giảm sau mỗi lần lặp của giải thuật. 
7.3.3. Phiên bản thứ nhất 
Cách cài đặt đơn giản nhất của giải thuật là cứ tiếp tục chia đôi danh sách, 
bất kể khoá đích có được tìm thấy hay chưa, cho tới khi danh sách còn lại có 
chiều dài là 1. 
Hàm sau đây được viết đệ qui. 
Error_code recursive_binary_1(const Ordered_list &the_list, const Key 
&target, int bottom, int top, int &position) 
/* 
pre: Các chỉ số bottom và top chỉ ra dãy các phần tử trong danh sách phục vụ cho việc tìm 
kiếm target. 
post: Nếu phần tử có khóa trùng với target được tìm thấy thì trả về success, position chỉ 
vị trí tìm thấy. Ngược lại phương thức trả về not_present, position không có nghĩa. 
uses: recursive_binary_1 và các phương thức của lớp List và Record. 
Chương 7 – Tìm kiếm 
Giáo trình Cấu trúc dữ liệu và Giải thuật 144
*/ 
{ 
 Record data; 
 if (bottom < top) { // List có nhiều hơn 1 phần tử. 
 int mid = (bottom + top) / 2; 
 the_list.retrieve(mid, data); 
 if (data < target) // Cần loại bỏ một nửa số phần tử bên phải. 
 return recursive_binary_1(the_list, target, mid + 1, top, position); 
 else // Cần loại bỏ một nửa số phần tử bên trái. 
 return recursive_binary_1(the_list, target, bottom, mid, position); 
 } 
 else if (top < bottom) 
 return not_present; // List rỗng. 
 else { // List có chính xác 1 phần tử. 
 position = bottom; 
 the_list.retrieve(bottom, data); 
 if (data == target) return success; 
 else return not_present; 
 } 
} 
Sự phân chia của danh sách trong quá trình tìm kiếm có thể được minh hoạ 
như sau: 
Lưu ý rằng trong sơ đồ này phần đầu tiên chỉ chứa các phần tử nhỏ hơn khoá 
đích còn phần cuối có thể chứa các phần tử lớn hơn hoặc bằng khoá đích. Bằng 
cách này, khi phần giữa của danh sách chỉ còn một phần tử mà lại là phần tử 
chứa khóa đích thì phần tử này luôn là phần tử đầu tiên nếu có nhiều phần tử có 
khoá trùng với nó trong danh sách. 
Nếu danh sách là rỗng thì hàm trên thất bại, ngược lại nó tính giá trị của 
mid. Vì mid được tính là trung bình của top và bottom nên nó nằm giữa top và 
bottom, và do đó nó là chỉ số hợp lệ của một phần tử của danh sách. 
Biểu thức chia nguyên luôn làm tròn xuống, nên chúng ta có 
bottom ≤ mid < top 
Sau khi quá trình đệ qui kết thúc, giải thuật phải kiểm tra xem khoá đích đã 
được tìm thấy hay chưa vì quá trình đệ qui không thực hiện phép kiểm tra này. 
Để chuyển hàm trên về dạng hàm tìm kiếm chuẩn mà chúng ta định ra ở trên 
chúng ta định nghĩa hàm sau: 
Chương 7 – Tìm kiếm 
Giáo trình Cấu trúc dữ liệu và Giải thuật 145
Error_code run_recursive_binary_1(const Ordered_list &the_list, 
 const Key &target, int &position) 
{ 
 return recursive_binary_1(the_list, target, 0, the_list.size() - 1, 
position); 
} 
Vì phép đệ qui được sử dụng trong hàm trên là đệ qui đuôi (tail recursion) nên 
có thể chuyển thành vòng lặp một cách dễ dàng. Đồng thời chúng ta có thể làm 
cho các thông số của hàm trở nên thống nhất với các hàm tìm kiếm khác. 
ErrorCode binary_search_1 (const Ordered_list &the_list, 
 const Key &target, int &position) 
/* 
post: Nếu phần tử có khóa trùng với target được tìm thấy thì trả về success, position chỉ vị trí 
tìm thấy. Ngược lại phương thức trả về not_present, position không có nghĩa. 
uses: Các phương thức của lớp List và Record. 
*/ 
{ 
 Record data; 
 int bottom = 0, top = the_list.size() - 1; 
 while (bottom < top) { 
 int mid = (bottom + top) / 2; 
 the_list.retrieve(mid, data); 
 if (data < target) 
 bottom = mid + 1; 
 else 
 top = mid; 
 } 
 if (top < bottom) return not_present; 
 else { 
 position = bottom; 
 the_list.retrieve(bottom, data); 
 if (data == target) return success; 
 else return not_present; 
 } 
} 
7.3.4. Nhận biết sớm phần tử có chứa khóa đích 
Tuy binary_search_1 là một dạng đơn giản của giải thuật tìm kiếm nhị 
phân, nhưng nó thực hiện thừa một số lần so sánh vì nó không nhận ra trường 
hợp phần tử khoá được tìm thấy sớm hơn. Vì thế chúng ta có thể cải tiến giải 
thuật như sau. 
Error_code recursive_binary_2(const Ordered_list &the_list, const Key 
&target,int bottom, int top, int &position) 
/* 
pre: Các chỉ số bottom và top chỉ ra dãy các phần tử trong danh sách phục vụ cho việc tìm 
kiếm target. 
Chương 7 – Tìm kiếm 
Giáo trình Cấu trúc dữ liệu và Giải thuật 146
post: Nếu phần tử có khóa trùng với target được tìm thấy thì trả về success, position chỉ 
vị trí tìm thấy. Ngược lại phương thức trả về not_present, position không có nghĩa. 
uses: recursive_binary_2 và các phương thức của lớp List và Record. 
*/ 
{ 
 Record data; 
 if (bottom <= top) { 
 int mid = (bottom + top) / 2; 
 the_list.retrieve(mid, data); 
 if (data == target) { 
 position = mid; 
 return success; 
 } 
 else if (data < target) 
 return recursive_binary_2(the_list, target, mid + 1, top, position); 
 else 
 return recursive_binary_2(the_list, target, bottom, mid - 1, 
position); 
 } 
 else return not_present; 
} 
Error_code run_recursive_binary_2(const Ordered_list &the_list, 
 const Key &target, int &position) 
{ 
 return recursive_binary_2(the_list, target, 0, the_list.size() - 1, 
position); 
} 
Chúng ta có thể chuyển hàm này thành dạng không đệ qui như sau. 
Error_code binary_search_2(const Ordered_list &the_list, 
 const Key &target, int &position) 
/* 
post: Nếu phần tử có khóa trùng với target được tìm thấy thì trả về success, position chỉ 
vị trí tìm thấy. Ngược lại phương thức trả về not_present, position không có nghĩa. 
uses: Các phương thức của lớp List và Record. 
*/ 
{ 
 Record data; 
 int bottom = 0, top = the_list.size() - 1; 
 while (bottom <= top) { 
 position = (bottom + top) / 2; 
 the_list.retrieve(position, data); 
 if (data == target) return success; 
 if (data < target) bottom = position + 1; 
 else top = position - 1; 
 } 
 return not_present; 
} 
Các hoạt động này có thể được minh họạ như sau: 
Chương 7 – Tìm kiếm 
Giáo trình Cấu trúc dữ liệu và Giải thuật 147
Sơ đồ này là đối xứng theo nghĩa phần thứ nhất chỉ chứa các phần tử nhỏ hơn 
khoá, phần thứ ba chỉ chứa các phần tử lớn hơn khoá. Khi đó, nếu như khoá xuất 
hiện ở nhiều vị trí trong danh sách thì giải thuật có thể trả về bất kỳ vị trí nào 
trong số đó. Đây cũng là nhược điểm của cách cải tiến để nhận ra sớm phần tử 
cần tìm này, vì trong một số ứng dụng, vị trí tương đối giữa phần tử được tìm 
thấy so với các phần tử có khóa trùng với nó rất quan trọng. 
7.4. Cây so sánh 
Cây so sánh (comparison tree) của một giải thuật tìm kiếm, còn gọi là cây 
quyết định (decision tree) hay cây tìm kiếm (search tree), là một cây có được bằng 
cách lần theo vết các hành vi của giải thuật. Mỗi nút của cây biểu diễn một phép 
so sánh. Tên của nút là chỉ số của phần tử có khóa đang được so sánh với khóa 
đích. Các nhánh xuất phát từ mỗi nút là các kết quả có thể có của phép so sánh 
tại nút đó và được đặt tên tương ứng. Khi giải thuật kết thúc chúng ta có một nút 
lá. Nếu giải thuật thất bại thì nút lá này được đặt tên là F, ngược lại tên của nút 
là chỉ số của phần tử có khoá trùng với khoá đích. 
Cây so sánh cho giải thuật tìm kiếm tuần tự rất đơn giản: 
Hình 7.2- Cây so sánh cho tìm kiếm tuần tự 
Số lần so sánh mà một giải thuật tìm kiếm thực hiện khi tiến hành một phép 
tìm kiếm cụ thể là số nút trung gian mà giải thuật đi qua kể từ gốc (nút trên cùng 
của cây) để đi đến nút lá cần thiết. 
Chương 7 – Tìm kiếm 
Giáo trình Cấu trúc dữ liệu và Giải thuật 148
Hình dạng của cây so sánh cho tìm kiếm nhị phân: 
Giải thuật tìm kiếm tuần tự cần nhiều phép so sánh hơn giải thuật tìm kiếm 
nhị phân. Chúng ta dễ dàng nhận thấy điều này qua hình dạng các cây so sánh 
của chúng. Giải thuật tìm kiếm tuần tự có cây so sánh hẹp và cao trong khi cây 
so sánh của giải thuật tìm kiếm nhị phân rộng và thấp hơn nhiều. Hình dạng cây 
này giúp ta hiểu được tại sao số lần so sánh trong phép tìm kiếm nhị phân là ít 
hơn so với tìm kiếm tuần tự. 
Hình 7.3- Cây so sánh cho tìm kiếm nhị phân.