Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 6: Tìm kiếm - Nguyễn Đức Nghĩa
Chương 6
TÌM KIẾM
1
NỘI DUNG
6.1. Tìm kiếm tuần tự và tìm kiếm nhị phân
6.2. Cây nhị phân tìm kiếm
6.3. Cây AVL
6.4. Tìm kiếm xâu mẫu
6.5. Bảng băm
2
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
6.1. Tìm kiếm tuần tự và tìm kiếm nhị phân
6.1.1. Tìm kiếm tuần tự (Linear Search or Sequential
Search)
6.1.2. Tìm kiếm nhị phân
3
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Bài toán tìm kiếm
Cho danh sách a gồm n phần tử a1, a2, ..., an và
một số x.
Hỏi x có mặt trong danh sách đã cho hay không?
Nếu câu trả lời là khẳng định, hãy đưa ra vị trí
xuất hiện của x trong dãy đã cho, nghĩa là đưa ra
chỉ số i sao cho ai = x.
4
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
6.1.1. Tìm kiếm tuần tự
current
-7
9
-5
2
2
3
8
4
3
5
-4
6
0
1
• Bắt đầu từ phần tử đầu tiên, duyệt qua từng phần tử cho đến
khi tìm được đích hoặc kết luận không tìm được.
• Các số không cần sắp thứ tự
• Làm việc được với cả danh sách móc nối (Linked Lists)
Độ phức tạp: O(n)
5
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Linear Search
int linearSearch(float a[], int size, int target)
{
int i;
for (i = 0; i < size; i++)
{
if (a[i] == target)
{
return i;
}
}
return -1;
}
6
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Phân tích thời gian tính
. Cần đánh giá thời gian tính tốt nhất, tồi nhất, trung bình của thuật
toán với độ dài đầu vào là n. Rõ ràng thời gian tính của thuật toán
có thể đánh giá bởi số lần thực hiện phép so sánh
(*)
(a[i] == target)
trong vòng lặp for.
. Nếu a[1] = target thì phép so sánh (*) phải thực hiện 1 lần. Do đó
thời gian tính tốt nhất của thuật toán là (1).
. Nếu target không có mặt trong dãy đã cho, thì phép so sánh (*)
phải thực hiện n lần. Vì thế thời gian tính tồi nhất của thuật toán là
(n).
7
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Phân tích thời gian tính
. Cuối cùng, ta tính thời gian tính trung bình của thuật toán. Nếu
target tìm thấy ở vị trí thứ i của dãy (target = a[i]) thì phép so
sánh (*) phải thực hiện i lần (i = 1, 2, ..., n), còn nếu target không
có mặt trong dãy đã cho thì phép so sánh (*) phải thực hiện n lần.
Từ đó suy ra số lần trung bình phải thực hiện phép so sánh (*) là
[(1 + 2 + . . . + n) + n] /(n+1)
= [n+ n(n+1)/2]/(n+1)
= (n2 + 3n)/[2(n+1)] .
. Ta có:
n/4 (n2+3n)/[2(n+1)] n
. Vì vậy, thời gian tính trung bình của thuật toán là (n).
8
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
6.1.2. Tìm kiếm nhị phân- Binary Search
mid
• Điều kiện:
– Danh sách phải được sắp thứ tự.
– Phải cho phép trực truy.
Độ phức tạp: O(log n)
9
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Tình huống 1: target < list[mid]
target
list:
lower
New
mid
upper
upper
Tình huống 2: list[mid] < target
target
list:
lower
mid
upper
New
lower
10
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Cài đặt trên C
int binarySearch(float array[], int size, int target)
{
int lower = 0, upper = size - 1, mid;
while (lower <= upper) {
mid = (upper + lower)/2;
if (array[mid] > target)
{ upper = mid - 1; }
else if (array[mid] < target)
{ lower = mid + 1; }
else
Đoạn cần khảo sát
có độ dài giảm đi một nửa
sau mỗi lần lặp
{ return mid; }
}
return -1;
}
Độ phức tạp: O(log n)
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
11
Ví dụ minh hoạ ứng dụng BS
• Dãy cấp ba
Bộ gồm ba số nguyên (a1, a2, a3) được gọi là một cấp số cộng tăng nếu như:
a2 – a1 = a3 – a2 và a2 – a1 > 0.
Bộ ba (a1, a2, a3) được gọi là đi trước bộ ba (b1, b2, b3) trong thứ tự từ điển nếu
như một trong ba điều kiện sau đây được thực hiện:
1) a1 < b1;
2) a1 = b1 và a2 < b2;
3) a1 = b1 , a2 = b2 và a3 < b3.
• Dãy số nguyên c1, c2, …, cn ( | ci | < 231, i = 1, 2, …, n) được gọi là dãy cấp ba
nếu như có thể tìm được ba số hạng của nó để lập thành một bộ ba cấp số cộng
tăng.
• Ví dụ: Dãy 3, 1, 5, 2, -7, 0, -1 là một dãy cấp ba, vì nó chứa bộ ba cấp số cộng
tăng, chẳng hạn (1, 3, 5) hay (-7, -1, 5). Bộ ba (-7, -1, 5) là bộ ba cấp số cộng
tăng đầu tiên theo thứ tự từ điển trong số các bộ ba cấp số cộng tăng của dãy đã
cho.
• Yêu cầu: Hãy kiểm tra xem dãy số nguyên cho trước có phải là dãy cấp ba hay
không. Nếu câu trả lời là khẳng định hãy đưa ra bộ ba cấp số cộng tăng đầu tiên
trong thứ tự từ điển
12
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Thuật toán trực tiếp
• Sắp xếp dãy a[1..n] theo thứ tự không giảm
• Duyệt tất cả các bộ ba a[i], a[j], a[k], 1 <= i < j < k <= n
for(i = 1; i < n-1; i++) {
for(int j = i+1; j < n; j++){
long key = 2*a[j] - a[i];
for (k=j+1; k<=n; k++)
if (a[k]==key) {
printf("\n YES %li %li %li", a[i], a[j], key);
halt;
}
}
}
• Thời gian tính: O(n3)
13
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Thuật toán nhanh hơn
• Sắp xếp dãy a[1..n] theo thứ tự không giảm
• Với mỗi bộ
(a[i], a[j]), i=1,..., n-2; j=i+1,..., n-1,
tìm kiếm nhị phân giá trị key =2*a[j]-a[i] trong khoảng
từ j+1 đến n. Nếu tìm thấy thì (a[i], a[j], a[k]) là một bộ
ba thoả mãn điều kiện đầu bài.
• Bộ ba đầu tiên tìm được sẽ là bộ ba cần đưa ra. Nếu
không tìm được bộ ba nào thì dãy đã cho không là dãy
cấp ba.
• Thời gian tính: O(n2 log n)
14
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
NỘI DUNG
6.1. Tìm kiếm tuần tự và tìm kiếm nhị phân
6.2. Cây nhị phân tìm kiếm
6.3. Cây AVL
6.4. Tìm kiếm xâu mẫu
6.5. Bảng băm
15
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
6.2. Cây nhị phân tìm kiếm
Binary Search Tree
6.2.1. Định nghĩa
6.2.2. Biểu diễn cây nhị phân tìm kiếm
6.2.3. Các phép toán
16
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Đặt vấn đề
. Ta xây dựng cấu trúc để biểu diễn các tập biến động (dynamic sets)
Các phần tử có khoá (key) và thông tin đi kèm (satellite data)
Tập động cần hỗ trợ các truy vấn (queries) như:
Search(S, k): Tìm phần tử có khoá k
Minimum(S), Maximum(S): Tìm phần tử có khoá nhỏ nhất, lớn nhất
Predecessor(S, x), Successor(S, x): Tìm phần tử kế cận trước, kế cận
sau
đồng thời cũng hỗ trợ các thao tác biến đổi (modifying operations) như:
Insert(S, x): Bổ sung (Chèn)
Delete(S, x): Loại bỏ (Xoá)
. Cây nhị phân tìm kiếm là cấu trúc dữ liệu quan trọng để biểu diễn tập động,
trong đó tất cả các thao tác đều được thực hiện với thời gian O(h), trong đó h
là chiều cao của cây.
17
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
6.2.1. Định nghĩa cây nhị phân tìm kiếm
Binary Search Trees
Cây nhị phân tìm kiếm (sẽ viết tắt là BST) là cây nhị phân có các
tính chất sau:
– Mỗi nút x (ngoài thông tin đi kèm) có các trường:
• left : con trỏ đến con trái
• right: con trỏ đến con phải,
• parent: con trỏ đến cha (trường này là tuỳ chọn), và
• key: khoá (thường giả thiết là khoá của các nút là khác nhau từng đôi,
trái lại nếu có khoá trùng nhau thì cần chỉ rõ thứ tự của hai khoá trùng
nhau).
left key right parent
18
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Tính chất BST
– Tính chất BST (Binary-search-tree property):
Giả sử x là gốc của một cây con:
• y thuộc cây con trái của x: key(y) < key(x).
• y thuộc cây con phải của x: key(y) > key(x).
(Tất cả các khoá của các nút trong cây con trái (phải) của x
đều nhỏ hơn (lớn hơn) khoá của x.)
x
19
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Ví dụ 1:
khoá là số nguyên
20
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Ví dụ 2:
khoá là xâu ký tự
Fred
Dan
Mary
Len
Alan
Bill
Eve
Kate
Greg
Sue
Eric
21
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Các phép toán
Tìm kiếm (Search)
Tìm cực tiểu, cực đại (Minimum, Maximum)
Kế cận sau, Kế cận trước (Predecessor, Successor)
Chèn (Insert)
Xoá (Delete)
22
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
6.2. Cây nhị phân tìm kiếm
Binary Search Tree
6.2.1. Định nghĩa
6.2.2. Biểu diễn cây nhị phân tìm kiếm
6.2.3. Các phép toán
23
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
6.2.2. Biểu diễn BST
key
Sử dụng cấu trúc cây nhị phân
(Binary Tree Structure)
left
right NIL
1
1
left
right p
left
right p
2
3
2
NULL
3
left
right p
left
right p
4
5
4
5
left
right p
6
6
24
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Binary Search Tree Node
Ví dụ 1: Khoá là số nguyên
struct TreeNodeRec
{
int
key;
struct TreeNodeRec* leftPtr;
struct TreeNodeRec* rightPtr;
};
typedef struct TreeNodeRec TreeNode;
25
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Binary Search Tree Node
Ví dụ 2: Khoá là xâu ký tự
#define MAXLEN 15
struct TreeNodeRec
{
char
key[MAXLEN];
struct TreeNodeRec* leftPtr;
struct TreeNodeRec* rightPtr;
};
typedef struct TreeNodeRec TreeNode;
26
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Chú ý:
độ dài lớn nhất
của xâu là
cố định
#define MAXLEN 15
struct TreeNodeRec
{
char
key[MAXLEN];
struct TreeNodeRec* leftPtr;
struct TreeNodeRec* rightPtr;
};
typedef struct TreeNodeRec TreeNode;
27
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Chú ý:
• Cho phép dùng xâu độ dài tuỳ ý.
• Cần cấp phát bộ nhớ trước khi dùng.
• Sử dụng strcmpđể so sánh hai xâu.
struct TreeNodeRec
{
char* key;
struct TreeNodeRec* leftPtr;
struct TreeNodeRec* rightPtr;
};
typedef struct TreeNodeRec TreeNode;
28
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Ví dụ 4. Thông tin đi kèm:
Ta cần tổ chức lưu trữ thông tin về các cuốn sách hỗ trợ các thao
tác tra cứu của bạn đọc
29
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Giả sử thông tin về sách được ghi nhận trong các bản ghi có cấu
trúc như sau
struct BookRec
khoá
{
char* author;
char* title;
char* publisher;
/* etc.: other book information. */
};
typedef struct BookRec Book;
30
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Ví dụ 4: Khi đó ta có thể mô tả Binary Search Tree Node như sau
struct TreeNodeRec
{
Book
info;
struct TreeNodeRec* leftPtr;
struct TreeNodeRec* rightPtr;
};
typedef struct TreeNodeRec TreeNode;
31
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
6.2. Cây nhị phân tìm kiếm
Binary Search Tree
6.2.1. Định nghĩa
6.2.2. Biểu diễn cây nhị phân tìm kiếm
6.2.3. Các phép toán
32
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Tree Node
Trong phần tiếp theo ta sử dụng mô tả nút sau đây:
struct TreeNodeRec
{
float key;
struct TreeNodeRec* leftPtr;
struct TreeNodeRec* rightPtr;
};
typedef struct TreeNodeRec TreeNode;
33
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Các phép toán cơ bản
•
•
makeTreeNode( value) - Tạo một nút với khoá cho bởi value
search(nodePtr, k) - Tìm kiếm nút có giá trị khoá bằng k trên BST trỏ bởi
nodePtr
•
•
•
•
•
find_min(nodePtr): Trả lại nút có khoá nhỏ nhất trên BST trỏ bởi nodePtr
find_max: Trả lại nút có khoá lớn nhất trên BST trỏ bởi nodePtr
Successor(x): Trả lại nút kế cận sau của nút x
Predcessor(x): Trả lại nút kế cận trước của nút x
insert( nodePtr, float item) - Chèn một nút với khoá cho bởi item vào BST trỏ bởi
nodePtr
•
•
delete(nodePtr, item) - Xoá nút có giá trị khoá bằng item trên BST trỏ bởi
nodePtr
Ngoài ra có thể sử dụng các hàm cơ bản đối với cây nhị phân như:
– void printInorder( nodePtr); void printPreorder( nodePtr);
– void printPostorder( nodePtr); . . .
34
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Mô tả trên C
struct TreeNodeRec
{
float
key;
struct TreeNodeRec* leftPtr;
struct TreeNodeRec* rightPtr;
};
typedef struct TreeNodeRec TreeNode;
TreeNode* makeTreeNode(float value);
TreeNode* insert(TreeNode* nodePtr, float item);
TreeNode* search(TreeNode* nodePtr, float item);
void printInorder(const TreeNode* nodePtr);
void printPreorder(const TreeNode* nodePtr);
void printPostorder(const TreeNode* nodePtr);
35
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Tạo một nút mới (MakeNode)
• Đầu vào: phần tử cần chèn
• Các bước:
– cấp phát bộ nhớ cho nút mới
– kiểm tra lỗi cấp phát
– nếu cấp phát được thì đưa phần tử vào nút mới
– đặt con trái và phải là NULL
• Đầu ra: con trỏ tới (địa chỉ của) nút mới
36
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
makeTreeNode
TreeNode* makeTreeNode(float value) {
TreeNode* newNodePtr = NULL;
newNodePtr = (TreeNode*)malloc(sizeof(TreeNode));
if (newNodePtr == NULL)
{
fprintf(stderr, “Out of memory\n”);
exit(1);
}
else
{
newNodePtr->key = value;
newNodePtr->leftPtr = NULL;
newNodePtr->rightPtr = NULL;
}
return newNodePtr;
}
37
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Tìm phần tử nhỏ nhất, lớn nhất:
findMin, findMax
• Để tìm phần tử nhỏ nhất trên BST, ta đi theo con trái
cho đến khi gặp NULL.
• Để tìm phần tử lớn nhất trên BST, ta đi theo con phải
cho đến khi gặp NULL.
7
4
9
1
5
8
11
3
38
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Tìm phần tử nhỏ nhất, lớn nhất:
findMin, findMax
find-min(T)
find-max(T)
1. while left[T] NIL
2. do T left[T]
3. return T
1. while right[T] NIL
2.
do T right[T]
3. return T
39
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
find_min và find_max
TreeNode* find_min(TreeNode * T) {
/* luôn đi theo con trái */
if (T == NULL) return(NULL);
else
if (T->leftPtr == NULL) return(T);
else return(find_min(T->leftPtr));
}
TreeNode* find_max(TreeNode* T) {
/* luôn đi theo con phải */
if (T != NULL)
while (T->rightPtr != NULL)
T = T->rightPtr;
return(T);
}
40
Nguyễn Đức Nghĩa - Bộ môn KHMT ĐHBKHN
Tải về để xem bản đầy đủ
85 trang
22960
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 6: Tìm kiếm - Nguyễn Đức Nghĩa", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_thuat_toan_chuong_6_tim_kiem_n.pdf
