Chương 4- Tìm kiếm

CHƯƠNG 4- TÌM KIẾM CHƯƠNG 4. TÌM KIẾM 4.1 Các phương pháp tìm kiếm trong danh sách 4.1.1 Tìm kiếm tuyến tính 4.1.2 Tìm kiếm nhị phân 4.1.1 Tìm kiếm nội suy 4.2 Cây nhị phân tìm kiếm 4.2.1 Định nghĩa 4.2.2 Các phép toán 4.1 Các phương pháp tìm kiếm trong danh sách Mô hình chung của bài toán tìm kiếm: Có một tập n đối tượng. Mỗi đối tượng có nhiều thuộc tính, được thể hiện bằng một kiểu bản ghi gồm nhiều trường. Trong đó có 1 trường mà giá trị của nó đặc trưng cho đối tượng, cho phép xác định hoàn toàn đối tượng, thường gọi là khóa. Bài toán tìm kiếm: Có một tập các đối tượng và cho trước một đối tượng x. Cần tìm xem x có mặt trong tập hợp đã cho hay không? 4.1 Các phương pháp tìm kiếm trong danh sách Mô hình toán học của bài toán tìm kiếm: Có tập hợp n giá trị khóa k1, k2, ..kn. Cho giá trị khóa x. Tìm xem x có tồn tại ki=x? Công việc tìm kiếm sẽ hoàn thành khi: Tìm được 1 bản ghi có giá trị khóa =x, lúc đó phép tìm kiếm được thành công successful. Không tìm thấy bản ghi nào có khóa bằng x, gọi là tìm kiếm không thành công unsuccessful. Lúc này có thể xuất hiện yêu cầu bổ sung giá trị x vào tập hợp, gọi là tìm kiếm có bổ sung. 4.1.1 Tìm kiếm tuần tự (sequential searching) Là phương pháp tìm kiếm đơn giản và cổ điển. Ý tưởng: Bắt đầu từ bản ghi thứ nhất, lần lượt so sánh khóa tìm kiếm với khóa tương ứng của bản ghi trong bảng, cho tới khi tìm được bản ghi mong muốn hoặc đã hết bảng mà chưa tìm thấy. 4.1.1 Tìm kiếm tuần tự (sequential searching) Giải thuật 1: SEQUEN-SEARCH(k,n,x) 1. //Khởi đầu i=1; k[i+1]=x 2. // Tìm khóa trong dãy while (k[i] !=x) do i++; 3. // Tìm thấy hay không If (i==n+1) return 0 //không tìm thấy else return i; 4.1.1 Tìm kiếm tuần tự (sequential searching) Giải thuật 2 (giải thuật đệ quy-tìm trong danh sách liên kết): Node *timdequy(struct node *first, element_type e) { if (first == NULL) return NULL; else if (first->element == e) return first; else return timdequy(first->next, e); } 4.1.1 Tìm kiếm tuần tự (sequential searching) Đánh giá giải thuật: Trường hợp tốt nhất: Tmin = 1; Trường hợp xấu nhất: Tmax = O(n); Trung bình Ttb= O(n) 4.1.2. Tìm kiếm nhị phân (Binary Serching) Là phương pháp tìm kiếm thông dụng. Ý tưởng: Dãy khóa đã được sắp xếp theo thứ tự (tăng dần hoặc giảm dần). Giả sử dãy khóa đang xét là kl và kr thì khóa ở giữa dãy sẽ là ki với i = (l+r)/2. Tìm kiếm sẽ kết thúc nếu x=ki. Ngược lại, nếu xki, phép tìm kiếm sẽ được thực hiện tiếp với ki+1 với kr. Quá trình tìm kiếm sẽ dừng khi tìm thấy khóa hoặc dãy đang xét trở nên rỗng. 4.1.2. Tìm kiếm nhị phân (Binary Serching) Giải thuật 1: BINARY-SEARCH(k,n,x) b1. l=1; r=n;//khởi đầu b2. while (l k[m] then l = m+1; else return m; } b3. return 0; // tìm không thấy. 4.1.2. Tìm kiếm nhị phân (Binary Serching) Giải thuật 2(giải thuật đệ quy): RBINARY-SEARCH(l,r,k,x) b1. if lk[m] then loc = RBINARY-SEARCH(m+1,r,k,x) else loc=m; B2: Return loc; 4.1.2. Tìm kiếm nhị phân (Binary Serching) Đánh giá giải thuật: Trường hợp tốt nhất Tmin =1, tìm được ngay lần đầu tiên. Trường hợp xấu nhất Tmax = k+w[n/2k) Chứng minh được Ttb = O(log2n). Trong tất cả các giải thuật tìm kiếm, tìm kiếm nhị phân là nhanh nhất, nhưng nó có nhược điểm là dãy phải được sắp xếp. Bài tập về nhà B1. Viết chương trình thực hiện các việc sau: Nhập các giá trị nguyên dương từ bàn phím (tổ chức theo kiểu danh sách liên kết). In ra màn hình dãy số đã nhập Nhập một giá trị X từ bàn phím, kiểm tra X có trong danh sách hay không. Nếu có thì trả về vị trí của X, nếu không chèn X vào vị trí cuối của danh sách.(Viết cả 2 giải thuật Tìm kiếm tuần tự và tìm kiếm nhị phân). 4.2. Cây nhị phân tìm kiếm Việc tổ chức tập hợp khóa theo cấu trúc danh sách thì phép tìm kiếm nói chung là chi phí cao, nếu khóa đã sắp xếp thì phép tìm kiếm nhị phân hiệu quả hơn nhưng bất tiện trong việc thêm, bớt phần tử. Cấu trúc cây nhị phân tìm kiếm được xây dựng để khắc phục các nhược điểm trên. 4.2.1 Định nghĩa Định nghĩa: Cây nhị phân tìm kiếm là cây nhị phân mà tại mỗi nút có một giá trị khóa thuộc kiểu dữ liệu có thứ tự nào đó, đồng thời thỏa mãn điều kiện sau: Mọi khóa thuộc cây con trái đều nhỏ hơn khóa ở nút cha. Mọi khóa thuộc cây con phải đều lớn hơn khóa ở nút cha. Theo định nghĩa, bất kỳ cây con nào của cây nhị phân tìm kiếm đều là cây tìm kiếm. 4.2.1 Định nghĩa Ví dụ: 4.2.1 Định nghĩa Bài tập tại lớp Vẽ 4 cây nhị phân tìm kiếm với các giá trị sau: 3, 4, 6, 8, 9, 10, 14, 15, 17. Vẽ cây nhị phân tìm kiếm cân đối cho các giá trị trên với số nút rỗng là ít nhất. 4.2.2 Các phép toán Phép tìm kiếm Phép chèn thêm một nút Phép gỡ loại bỏ một nút 4.2.2.1 Phép tìm kiếm Mô tả các bước: Bắt đầu từ gốc của cây, gọi nút đang xét là V. Nếu V rỗng, kết thúc và tìm không thấy. Ngược lại, so sánh x với khóa của nút hiện tại V: Nếu x khóa của V, lặp lại bước tìm kiếm với cây con phải; Nếu x = khóa của V, kết thúc và tìm thấy 4.2.2.1 Phép tìm kiếm int timdequy(int x,NODE *root) { int timthay =0; if ((root ==NULL) || (timthay)) return timthay; else { if (x element) timdequy(x,root->left); else if (x>root->element) timdequy (x,root->right); else timthay =1; } Thủ tục đệ quy: 4.2.2.1 Phép tìm kiếm int tim(int x,NODE *root) { int timthay =0; while ((root !=NULL) && (!timthay)) if (root ->element==x) timthay=1; else if (x element) root= root->left; else root= root->right; return timthay; } Thủ tục không đệ quy 4.2.2.2 Phép thêm một nút Đặt vấn đề: Tiến hành thêm một nút mới vào cây nhị phân tìm kiếm sao cho các khóa trên cây vẫn giữ đúng thứ tự. Ý tưởng: Thủ tục thêm một nút bắt đầu từ việc tìm kiếm, nếu tìm thấy thì kết thúc, nếu không tìm thấy thì tiến hành ở nhánh con bên trái hoặc bên phải để đảm bảo tính chất của cây nhị phân tìm kiếm 4.2.2.2 Phép thêm một nút Ví dụ: Thêm các nút 5, 2, 4, 6, 1, 7, 3 vào một cây rỗng theo đúng thứ tự. Qua từng bước thêm, ta có cây sau: 5 4.2.2.2 Phép thêm một nút void chen(int e, NODE **root) { NODE *tam; tam = new NODE; tam->element = e; tam->left = NULL; tam->right = NULL; if (*root == NULL) *root = tam; else 4.2.2.2 Phép thêm một nút if (tam->element element) if ((*root)->left) chen(e, &(*root)->left); else (*root)->left = tam; else if(tam->element > (*root)->element) if ((*root)->right) chen(e, &(*root)->right); else (*root)->right = tam; else cout element = X Xảy ra 2 trường hợp: V là nút lá: chỉ cần gỡ bỏ V bằng cách thay nút bên trái hoặc bên phải của nút cha V = Null V là nút một cành: gỡ bỏ V bằng cách sửa lại mối nối (left hoặc right) ở nút cha của V trỏ xuống nút cháu, cây còn lại vẫn là nhị phân tìm kiếm Nút V có đủ cả hai cây con: trường hợp này khá phức tạp 4.2.2.3 Phép xóa một nút Trường hợp này khóa của nút V chen giữa các khóa của nút cực phải của cây con trái và khóa của nút cực trái của cây con phải, vậy gỡ bỏ nút V phải thay thế một nút khác vào chỗ trống đó để đảm bảo điều kiện cây tìm kiếm, chỉ có thể thay thế bằng một trong hai nút con trên. Có thể xét trường hợp thay bằng nút cực phải của cây con trái. 4.2.2.3 Phép xóa một nút Giải thuật chi tiết: Với T : cây nhị phân tìm kiếm; X là giá trị cần xóa; V là con trỏ đến nút đang xét. Xuất phát từ cây gốc V, tìm nút chứa khóa x để loại bỏ, có các trường hợp sau: V=Null, không tìm thấy X V.element lặp lại việc tìm để loại bỏ cây bên phải, X = V.element, tiến hành gỡ bỏ nút V 4.2.2.3 Phép xóa một nút Giải thuật chi tiết: Gỡ bỏ nút V: Nếu V.right = Null, nối cây con trái của V vào nút cha Nếu V.left = Null, nối cây con phải của V vào nút cha V có đủ thì dò xuống nút cực phải của cây con trái và sửa cây để đảm bảo điều kiện của cây nhị phân tìm kiếm. Nút E là nút cực phải của cây con trái, xóa nút V bằng cách: Thay nội dung V = E Sửa F thành cây con của D Hủy nút E 4.2.2.3 Phép xóa một nút Ví dụ trong t/h đủ cả 2 cây con: 4.2.2.3 Phép xóa một nút int xoacuctrai (tree *root ) { int k; if ((*root)->left == NULL) { k=(*root)->element; (*root) = (*root)->right; return k; } else return xoacuctrai(&(*root)->left); } Hàm xóa phần tử 4.2.2.3 Phép xóa một nút void xoa(int x,tree *root) { if ((*root)!=NULL) if (x element) xoa(x,&(*root)->left) ; else if (x > (*root)->element) xoa(x,&(*root)->right); else if (((*root)->left==NULL)&&((*root)->right==NULL)) (*root)=NULL; else Thủ tục xóa 4.2.2.3 Phép xóa một nút if ((*root)->left == NULL) (*root) = (*root)->right; else if ((*root)->right==NULL) (*root) = (*root)->left; else (*root)->element = xoacuctrai(&(*root)->right); } Thủ tục xóa 4.3 Cây nhị phân cân đối (AVL) Định nghĩa: Cây nhị phân tìm kiếm được gọi là cân đối nếu như đối với mọi nút của nó chiều cao của hai cây con tương ứng chỉ lệnh nhau một đơn vị. 4.3 Cây nhị phân cân đối (AVL) Khai báo: Với cây cân đối AVL, tại mỗi nút ta ghi thêm một hệ số cân đối bal bal = -1 nếu cây con trái cao hơn cây con phải 0 - cao bằng - 1 - thấp hơn - 4.3 Cây nhị phân cân đối (AVL) Cấu trúc của một nút sẽ như sau: typedef int element_type; struct node { element_type element; struct node *left, *right; int bal[-1,0,1] } 4.3 Cây nhị phân cân đối (AVL) Các phép toán trên cây nhị phân (sinh viên tự nghiên cứu thêm) Bài tập Bài 1.Vẽ cây nhị phân tìm kiếm bằng cách thêm dần các khóa : 10, 7, 19, 11, 3, 16, 13, 4, 22, 1. Bài 2: Cài đặt chương trình thực hiện: Nhập một cây nhị phân tìm kiếm với các giá trị được nhập vào bàn phím như trên, thực hiện các phép duyệt cây để in ra các giá trị trên. Nhập giá trị x từ bàn phím, kiểm tra x có trong cây không? Bài tập Bài 3: Viết các thủ tục thêm, xoá một nút có khoá x trên cây tìm kiếm nhị phân bằng cách không đệ qui. Bài 4: a- Vẽ hình cây tìm kiếm nhị phân tạo ra từ cây rỗng bằng cách lần lượt thêm vào các khoá là các số nguyên: 54, 31, 43, 29, 65, 10, 20, 36, 78, 59. b- Vẽ lại hình cây tìm kiếm nhị phân ở câu a/ sau khi lần lượt xen thêm các nút 15, 45, 55. c- Vẽ lại hình cây tìm kiếm nhị phân ở câu a/ sau khi lần lượt xoá các nút 10, 20, 43, 65, 54.