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

CHƯƠNG 4- TÌM KIẾM1CHƯƠNG 4. TÌM KIẾM4.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 suy4.2 Cây nhị phân tìm kiếm 4.2.1 Định nghĩa 4.2.2 Các phép toán24.1 Các phương pháp tìm kiếm trong danh sáchMô 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?34.1 Các phương pháp tìm kiếm trong danh sáchMô 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.44.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.54.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]=x2. // Tìm khóa trong dãy while (k[i] !=x) do i++;3. // Tìm thấy hay khôngIf (i==n+1) return 0 //không tìm thấyelse return i;64.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);}74.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)84.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.94.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 đầub2. while (l k[m] then l = m+1; else return m; }b3. return 0; // tìm không thấy.104.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;114.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.12Bà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ậpNhậ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).134.2. Cây nhị phân tìm kiếmViệ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.144.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.154.2.1 Định nghĩaVí dụ:3417256650687175164.2.1 Định nghĩaBài tập tại lớpVẽ 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.174.2.2 Các phép toánPhép tìm kiếmPhép chèn thêm một nútPhép gỡ loại bỏ một nút 184.2.2.1 Phép tìm kiếmMô 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ấy194.2.2.1 Phép tìm kiếmint 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:204.2.2.1 Phép tìm kiếmint 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 đệ quy214.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ếm224.2.2.2 Phép thêm một nútVí 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:5124367234.2.2.2 Phép thêm một nútvoid chen(int e, NODE **root){ NODE *tam; tam = new NODE; tam->element = e; tam->left = NULL; tam->right = NULL; if (*root == NULL) *root = tam; else244.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 = XXả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 = NullV 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ếmNút V có đủ cả hai cây con: trường hợp này khá phức tạp274.2.2.3 Phép xóa một nútTrườ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.284.2.2.3 Phép xóa một nútGiả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ấyX 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 V294.2.2.3 Phép xóa một nútGiả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 chaNếu V.left = Null, nối cây con phải của V vào nút chaV 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.30Nú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 = ESửa F thành cây con của DHủy nút E4.2.2.3 Phép xóa một nútVí dụ trong t/h đủ cả 2 cây con:AVBDECFAEBDCF314.2.2.3 Phép xóa một nútint 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ử324.2.2.3 Phép xóa một nútvoid xoa(int x,tree *root){if ((*root)!=NULL)if (x element) xoa(x,&(*root)->left) ;else if (x > (*root)->element) xoa(x,&(*root)->right);elseif (((*root)->left==NULL)&&((*root)->right==NULL))(*root)=NULL;elseThủ tục xóa 334.2.2.3 Phép xóa một nútif ((*root)->left == NULL) (*root) = (*root)->right;elseif ((*root)->right==NULL) (*root) = (*root)->left;else (*root)->element = xoacuctrai(&(*root)->right);}Thủ tục xóa 344.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ị.354.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 -364.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] } 374.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)38Bài tậpBà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?39Bài tậpBà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.40