Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 4, Phần 1: Tìm kiếm - Nguyễn Duy Hiệp
3/14/2011
Bài toán tìm kiếm
Một số bài toán tìm kiếm:
Cho tên một người, tìm kiếm số điện thoại người đó trong danh bạ
Cho tên một tài khoản, tìm kiếm các giao dịch của tài khoản đó
Cho tên một sinh viên, tìm kiếm thông tin về kết quả học tập của
sinh viên đó
Chương 4
Tìm kiếm
(phần 1)
Khóa(key) là thông tin mà chúng ta dùng để tìm kiếm
Tìm kiếm trong và tìm kiếm ngoài
Số lượng dữ liệu
Tốc độ truy nhập dữ liệu
Nội dung
Bài toán tìm kiếm
Tìm kiếm tuần tự
Tìm kiếm nhị phân
Cây quyết định
Tìm kiếm tuần tự
1
3/14/2011
Tìm kiếm tuần tự
Tìm kiếm tuần tự
Tìm kiếm trên danh sách móc nối
typedef struct node
{
Tìm kiếm tuần tự:
Là phương pháp đơn giản nhất
char hoten[30];
char diachi[50];
float diemTB;
struct node *pNext;
} NODE;
Duyệt từ đầu đến cuối danh sách cho đến khi tìm được
bản ghi mong muốn
Hoặc là đến cuối mà không tìm được
Tìm kiếm tuần tự
Tìm kiếm tuần tự
int sequentialSearch(NODE *pHead, char key[], NODE *&retVal)
{
Tìm kiếm trên mảng
NODE *ptr=pHead;
while(ptr!=NULL)
int sequentialSearch(int records[], int key, int &position)
{
int i;
for(i=0;i<MAX; i++)
{
if(strcmp(ptr‐>hoten,key)==0)
{
{
if(records[i]==key)
retVal=ptr;
return 0;
{
position=i; //tim thay
}
return 0;
else ptr=ptr‐>pNext;
}
}
}
return ‐1;
return ‐1;//khong tim thay
}
}
2
3/14/2011
Phân tích
Giả sử tồn tại bản ghi chứa khóa cần tìm.
Trường hợp tốt nhất: chỉ cần 1 phép so sánh
Trường hợp tồi nhất: cần n phép so sánh
Trung bình cần :
1 2 3... n
Tìm kiếm nhị phân
n
Độ phức tạp :
O(n)
Chỉ phù hợp cho danh sách ít phần tử
Tìm kiếm tuần tự
Tìm kiếm nhị phân
Trường hợp các bản ghi đã được sắp xếp theo thứ tự, tìm
kiếm tuần tự không hiệu quả
Tìm kiếm từ “study” trong từ điển
Tìm kiếm “Tran Van C” trong danh ba điện thoại
Bài tập: Viết lại hàm tìm kiếm tuần tự để có thể đếm
được số lượng phép so sánh cần thiết trong quá trình
tìm kiếm (đối với danh sách móc nối).
Tìm kiếm nhị phân:
So sánh khóa với phần tử trung tâm danh sách, sau đó ta chỉ
xét nửa trái hoặc nửa phải danh sách căn cứ vào khóa đứng
trước hay sau phần tử trung tâm
3
3/14/2011
Tìm kiếm nhị phân
Tìm kiếm nhị phân
Yêu cầu: Danh sách phải được sắp xếp theo một thứ tự
nào đó trước (danh sách có thứ tự).
Ví dụ:
int binarySearch1_Re(int A[], int key, int begin,
int end, int &position)
{
if(begin>end)return ‐1;
int mid=(begin+end)/2;
các từ trong từ điển,
if(A[mid]==key)
{
tên người trong danh bạ điện thoại
position=mid;
return 0;
Danh sách có thứ tự: là danh sách trong đó mỗi mục
chứa một khóa theo thứ tự.
}
if(key<A[mid]) return binarySearch(A,key,begin,
Nếu mục ꢀ đứng trước ꢁ trong danh sách, thì khóa của
mục ꢀ sẽ nhỏ hơn hoặc bằng khóa của mục ꢁ
mid‐1,position);
else return binarySearch(A,key,mid+1,end,position);
}
Tìm kiếm nhị phân
Tìm kiếm nhị phân
int binarySearch1(int A[], int key, int begin, int end,
int &position)
{
khóa
int mid;
while(begin<=end)
{
Nửa phải
Nửa trái
mid=(begin+end)/2;
if(A[mid]==key)
{
position=mid;
return 0;
Phần tử trung tâm
}
if(key<A[mid]) end=mid‐1;
else begin=mid+1;
}
return ‐1;
}
4
3/14/2011
Ví dụ
VD1.Khi tìm kiếm bảng chứa 5000 dữ liệu bằng phép tìm
kiếm nhị phân (binary search method), số lần so sánh
bình quân sẽ là bao nhiêu?
Log102 = 0.3010
A. 8
B. 9
Cây quyết định
C. 10
D. 11
E. 12
Ví dụ
Cây quyết định
Tên khác: cây so sánh, cây tìm kiếm
Cây quyết định của một thuật toán thu được bằng cách
theo vết các hành động của thuật toán
Biểu diễn mỗi phép so sánh khóa bằng 1 nút của cây (biểu diễn
bằng hình tròn)
Cạnh vẽ từ đỉnh biểu diễn các khả năng có thể xảy ra của phép
Trong tìm kiếm nhị phân, khi số lượng dữ liệu đã sắp xếp
tăng gấp 4 lần thì số lượng phép so sánh tối đa tăng bao
nhiêu?
so sánh
Kết thúc thuật toán ta đặt F nếu không tìm thấy, hoặc là vị trí
tìm thấy khóa (đây gọi là các lá của cây)
5
3/14/2011
Cây quyết định
Cây quyết định
Cây quyết định là 2‐tree: các nút trong đều chỉ có 2 nút con.
Gốc: đỉnh của cây
Chiều cao của cây: số
lượng nút trên đường đi
dài nhất từ gốc đến lá
Số lượng phép so sánh trong thuật toán tìm kiếm nhị phân ở
trên trong trường hợp tìm không thấy là 2 log ꢂ ꢃ 1
Mức của đỉnh: số lượng
cạnh trên đường từ gốc
đến đỉnh đó
Số phép so sánh trung bình trong trường hợp tìm thấy là
2(n 1)
log(n 1) 3
Số lượng phép so sánh
trong một trường hợp
cụ thể là số lượng nút
trong
n
Cây quyết định của
thuật toán tìm kiếm
tuần tự trên danh sách
các số 1,2,3,..,n
Cây quyết định
Extra section
Cây quyết định cho thuật toán tìm kiếm nhị phân 1
trên dãy số 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
6
3/14/2011
Tìm kiếm nhị phân
Tìm kiếm nhị phân
Một cài đặt khác của tìm kiếm nhị phân
So sánh hai cài đặt của thuật toán tìm kiếm nhị phân
int binarySearch2(int A[], int key, int begin, int end, int &position)
{
int mid;
while(begin<end)
{
Tìm kiếm
Tìm kiếm không
mid=(begin+end)/2;
thành công
thành công
if(key<=A[mid]) end=mid‐1;
else begin=mid;
binarySearch1
binarySearch2
log ꢂ ꢃ 1
log ꢂ ꢃ 1
2 log ꢂ
}
if(begin>end) return ‐1;
else if(A[begin]=key) //begin=end
2log ꢂ ꢄ 3
{
position=begin;
return 0;
}
}
Tìm kiếm nhị phân
Cây tìm kiếm tương ứng với thuật toán tìm kiếm nhị phân 2
trên dãy 1,2,3,4,5,6,7,8,9,10
7
3/14/2011
Nhận xét
Thuật toán tìm kiếm nhị phân là thuật toán tốt nhất trong
các thuật toán tìm kiếm dựa trên việc so sánh giá trị các
khóa trong dãy.
Ý tưởng mở rộng thuật toán tìm kiếm: Nếu chúng ta biết
khoảng tìm kiếm của mỗi khóa thì chúng ta có thể thu
hẹp phạm vi của việc tìm kiếm
Cây tìm kiếm nhị phân
Thuật toán interpolation search :
ꢅꢆlog log ꢂꢇ trong trường hợp các khóa phân bố đều
ꢅ ꢂ trong trường hợp tồi nhất
Binary search tree
Áp dụng tìm kiếm nhị phân trên cấu
trúc liên kết (danh sách liên kết) ?
Thêm, xóa phần tử trên cấu trúc liên
tiếp (mảng) ?
Chi phí về thời gian?
Chi phí về bộ nhớ?
8
3/14/2011
Cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân – binary search tree (BST):
Thời gian thực hiện tìm kiếm nhanh (ꢅꢆlog ꢂꢇ)
Thêm, xóa các phần tử dễ dàng
Duyệt cây tìm kiếm nhị
phân
Thứ tự giữa
12
1, 3, 5, 7, 9, 12, 23, 34
Thứ tự trước
3
34
Cây tìm kiếm nhị phân là cây nhị phân rỗng hoặc mỗi nút
có một giá trị khóa thỏa mãn các điều kiện sau:
Giá trị khóa của nút gốc (nếu tồn tại) lớn hơn giá trị khóa của
bất kỳ nút nào thuộc cây con trái của gốc
Giá trị khóa của nút gốc (nếu tồn tại) nhỏ hơn giá trị khóa của
bất kỳ nút nào thuộc cây con phải của gốc
Cây con trái và cây con phải của gốc cũng là các cây nhị phân
tìm kiếm
12, 3, 1, 7, 5, 9, 34, 23
Thứ tự sau
1, 5, 9, 7, 3, 23, 34, 12
7
1
23
9
5
Cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân
Biểu diễn cây tìm kiếm nhị phân: giống biểu diễn cây nhị
phân thông thường
12
G
Biểu diễn bằng cấu trúc liên kết
3
34
A
B
S
struct TreeNode
{
DATA_TYPE info;
struct TreeNode *leftChild;
struct TreeNode *rightChild;
}
7
1
23
D
L
9
5
F
Các nút trên cây nhị phân phải có khóa phân biệt !
9
3/14/2011
typedef struct
TreeNode
{
Cây tìm kiếm nhị phân
Thao tác tìm kiếm trên cây
int info;
struct TreeNode
*leftChild;
struct TreeNode
*rightChild;
}NODE;
Cài đặt đệ quy
Tìm kiếm:
NODE* search_for_node(NODE *root, int key)
Nếu cây rỗng không tìm thấy
So sánh khóa cần tìm với khóa của nút gốc
Nếu bằng Tìm thấy
Ngược lại lặp lại quá trình tìm kiếm ở cây con trái (hoặc cây
con phải) nếu khóa cần tìm nhỏ hơn (lớn hơn) khóa của nút
gốc
{
if(root==NULL || root‐>info==key) return root;
if(key<root‐>info)
return search_for_node(root‐>leftChild, key);
else return search_for_node(root‐>rightChild, key);
}
Cây tìm kiếm nhị phân
Thao tác tìm kiếm trên cây
Cài đặt không đệ quy
Một số thao tác cơ bản của ADT cây tìm kiếm nhị phân
Search_for_node(): tìm kiếm xem một giá trị khóa có xuất
hiện trên cây không
NODE* search_for_node(NODE *root, int key)
{
while(root!=NULL && root‐>info!=key)
if(key<root‐>info) root=root‐>leftChild;
else root=root‐>rightChild;
return root;
Insert(): Chèn một nút mới vào cây
Remove(): Gỡ bỏ một nút trên cây
}
10
3/14/2011
(1)
(2)
(3)
G
F
G
Thêm nút mới vào cây
A
S
A
S
L
B
Nhận xét:
L
S
L
D
A
D
G
A
F
Thứ tự thêm các nút khác nhau có thể tạo ra các cây nhị phân
tìm kiếm khác nhau
Khóa đầu tiên thêm vào cây rỗng sẽ trở thành nút gốc của cây
Để thêm các khóa tiếp theo ta phải thực hiện tìm kiếm để tìm
ra vị trí chèn thích hợp
B
F
D
S
S
B
(4)
(5)
G
Các khóa được thêm tại nút lá của cây
Cây sẽ bị suy biến thành danh sách liên kết đơn nếu các nút
chèn vào đã có thứ tự (tạo ra các cây lệch trái hoặc lệch phải)
F
L
L
G
F
Cây nhị phân tìm
kiếm cân bằng cho
thời gian tìm kiếm là
nhỏ nhất ꢅꢆlog ꢂꢇ
B
D
B
D
A
Thêm nút mới vào cây
Khi thêm nút mới phải đảm bảo những đặc điểm của cây
nhị phân tìm kiếm không bị vi phạm
Thêm nút mới vào cây
Cài đặt đệ quy
int insert(NODE *&root, int value)
{
if(root==NULL)
Thêm lần lượt các khóa : G, A, S, D, L, B, F vào cây nhị phân tìm kiếm ban đầu rỗng
{
G
G
G
G
root = (NODE*)malloc(sizeof(NODE));
root‐>info = value;
A
A
G
S
A
S
S
root‐>leftChild = NULL;
root‐>rightChild = NULL;
Thêm G
Thêm A
Thêm S
D
return 0;// success
G
F
Thêm D
G
}
A
S
L
A
else if(value < root‐>info) insert(root‐>leftChild,value);
A
S
L
else if(value > root‐>info) insert(root‐>rightChild,value);
L
D
D
else return ‐1;//duplicate
D
}
B
B
Thêm L
Thêm B
Thêm F
11
3/14/2011
Thêm nút mới vào cây
Loại bỏ nút khỏi cây
Cài đặt không đệ quy
Loại bỏ nút trên cây: cần đảm bảo những đặc điểm của
cây không bị vi phạm
int insert(NODE *&root, int value)
{
NODE *pRoot = root;
while(pRoot!=NULL && pRoot‐>info!=key)
if(key<pRoot‐>info) pRoot=pRoot‐>leftChild;
else pRoot=pRoot‐>rightChild;
Trường hợp loại bỏ nút lá:
G
G
if(pRoot!=NULL) return ‐1;//duplicate
else
{
A
S
A
S
pRoot = (NODE*)malloc(sizeof(NODE));
pRoot‐>info = value;
L
D
D
pRoot‐>leftChild = NULL;
pRoot‐>rightChild = NULL;
return 0;// success
B
F
B
F
}
}
Thêm nút mới vào cây
Loại bỏ nút khỏi cây
Trường hợp loại bỏ nút trong: nút trong khuyết con trái
hoặc con phải
Nhận xét: Thời gian thực hiện của thuật toán phụ thuộc
vào dạng của cây
Cây cân bằng : thời gian cỡ ꢅꢆlog ꢂꢇ
F
F
Cây bị suy biến (lệch trái, phải hoặc zig‐zag): thời gian cỡ
ꢅꢆꢂꢇ
S
L
B
B
S
A
D
A
D
N
T
ꢅꢆlog ꢂꢇ ꢈ ꢉꢆꢂꢇ ꢈ ꢅꢆꢂꢇ
C
N
T
C
Thuật toán sắp xếp (treeSort): thêm lần lượt các phần tử
vào cây nhị phân tìm kiếm, sau đó duyệt theo thứ tự giữa.
Số phép so sánh: 1.39 ꢂ log ꢂ ꢃ ꢅꢆꢂꢇ
12
3/14/2011
Loại bỏ nút khỏi cây
Loại bỏ nút khỏi cây
Trường hợp loại bỏ nút trong: nút trong khuyết con trái
hoặc con phải
F
L
B
F
F
S
A
D
G
D
L
B
L
C
N
B
T
S
S
B
C
F
A
C
N
T
N
T
L
A
S
A
D
G
C
N
T
Loại bỏ nút khỏi cây
Loại bỏ nút khỏi cây
Trường hợp loại bỏ nút trong
Nhận xét:
G
Thực hiện tìm kiếm để xem khóa cần xóa có trên cây
Nếu nút có khóa cần xóa là nút lá: ngắt bỏ kết nối với nút cha của
nó, giải phóng bộ nhớ cấp phát cho nút đó
A
S
L
B
G
G
Nếu nút cần xóa là nút trong không đầy đủ (khuyết con trái hoặc
phải): Thay thế bằng cây con không khuyết
A
S
A
S
F
Nếu nút cần xóa là nút trong đầy đủ (có đủ các con): cần tìm một
nút thuộc để thay thế cho nó, sau đó xóa nút được thay thế. Nút
thay thế là nút ở liền trước (hoặc liền sau trong duyệt theo thứ
tự giữa)
G
L
L
D
?
A
S
B
F
B
F
L
F
Tìm nút phải nhất của cây con trái (*)
Hoặc, nút trái nhất thuộc cây con phải
B
13
3/14/2011
int remove_node(NODE *&root)
{
if(root == NULL) return ‐1; //remove null
NODE *ptr = root; //remember this node for delete later
if(root‐>leftChild == NULL) root=root‐>rightChild;
else if(root‐>rightChild == NULL) root=root‐>leftChild;
else //find the rightmost node on the left sub tree
{
NODE *preP = root;
ptr = root‐>leftChild;
while(ptr‐>rightChild != NULL)
{
preP = ptr;
ptr = ptr‐>rightChild;
}
root‐>info = ptr‐>info;
if(preP == root) root‐>leftChild = ptr‐>leftChild;
else preP‐>rightChild = ptr‐>leftChild;
}
free(ptr);
return 0;// remove success
}
Loại bỏ nút khỏi cây
int remove(NODE *&root, int key)
{
if(root==NULL || key==root‐>info)
return remove_node(root);
else if(key < root‐>info)
return remove_node(root‐>leftChild,key);
else return remove_node(root‐>rightChild,key);
}
14
14 trang
15340
Free
Bạn đang xem tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 4, Phần 1: Tìm kiếm - Nguyễn Duy Hiệp", để 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_phan_1_gioi_thieu_v.pdf
