Giáo trình Cấu trúc dữ liệu và thuật toán

MỤC LỤC
CHƯƠNG 1: GIỚI THIỆU CHUNG
1.1. Thuật toán và cấu trúc dữ liệu:
	Theo Niklaus Wirth: Thuật toán + Cấu trúc dữ liệu = Chương trình.
	Ví dụ: Cho 1 dãy các phần tử, có thể biểu diễn dưới dạng mảng hoặc danh sách.
	Cấu trúc dữ liệu và thuật toán có mối quan hệ mật thiết với nhau. do đó việc nghiên cứu các cấu trúc dữ liệu sau này đi đôi với việc xác lập các thuật toán xử lý trên các cấu trúc ấy.
1.2. Một số vấn đề liên quan:
	Lựa chọn một cấu trúc dữ liệu thích hợp để tổ chức dữ liệu vào ra và trên cơ sở đó xây dựng được thuật toán xử lý hữu hiệu nhằm đưa tới kết quả mong muốn cho bài toán là một khâu rất quan trọng.
	Ta cần phân biệt 2 loại quy cách dữ liệu: 
Quy cách biểu diễn hình thức: Còn được gọi là cấu trúc logic của dữ liệu. Đối với mỗi ngôn ngữ lập trình xác định sẽ có một bộ cấu trúc logic của dữ liệu. Dữ liệu thuộc loại cấu trúc nào thì cần phải có mô tả kiểu dữ liệu tương ứng với cấu trúc dữ liệu đó. Ví dụ: Trong C có các kiểu dữ liệu: Struct, Union, File,..
Quy cách lưu trữ: là cách biểu diễn một cấu trúc dữ liệu trong bộ nhớ. Ví dụ: Cấu trúc dữ liệu mảng được lưu trữ trong bộ nhớ theo quy tắc lưu trữ kế tiếp. Có 2 quy cách lưu trữ:
 Lưu trữ trong: ví dụ RAM.
 Lưu trữ ngoài: ví dụ đĩa (disk).
1.3. Ngôn ngữ diễn đạt thuật toán:
	Ngôn ngữ diễn đạt thuật toán được quy ước sử dụng trong giáo trình này là ngôn ngữ tựa C++.
	Đặc điểm: Gần giống với Turbo C++, do đó dễ dàng trong việc chuyển một chương trình viết bằng ngôn ngữ tựa C++ sang ngôn ngữ C++.
1.3.1. Cấu trúc của một chương trình chính:
void main()
{
	S1;
Các lệnh của chương trình dùng để diễn tả thuật toán
	S2;
	...
	Sn;
}
Lưu ý:
Để đơn giản, chương trình có thể không cần viết khai báo. Tuy nhiên có thể mô tả trước chương trình bằng ngôn ngữ tự nhiên.
Phần thuyết minh được đặt giữa 2 dấu /* , */ hoặc // để ghi chú trên 1 dòng.
Ví dụ:	
void main() /* Chuong trinh chuyen so he 10 thanh he 2*/
{
cout << "n = ";
cin >> n; /* Nhap n la so he cs 10*/
T=0;
while (n!=0)
	{
	r = n % 2;
	Push(T, r);
	n = n / 2;
	}
cout << "Ket qua chuyen doi sang he co so 2 la: ";
while (T!=0)
	{
	Pop(T, r);
	cout << r;
	}
}
1.3.2. Các ký tự:
 Các ký tự sử dụng trong chương trình là tương tự như trong C++.
Lưu ý: Trong C++ là có sự phân biệt giữa chữ hoa và chữ thường.
1.3.3. Các câu lệnh:
-	Lệnh gán: V = E;
	Trong đó: V là biến (variable), và E là biểu thức (expression).
	Lưu ý: Có thể dùng phép gán chung. Ví dụ: a=b=1; 
-	Lệnh ghép: {S1; S2; ...; Sn;} coi như là một câu lệnh (trong đó Si là các câu lệnh).
-	Lệnh if: Tương tự như lệnh if của ngôn ngữ C.
 if () ;
hoặc: if () ;
 else ;	
-	Lệnh switch: Theo cấu trúc sau:
	switch () 
	{
	case gt1: S1;
	case gt2: S2; 
	...
	case gtn: Sn; 
	[default : Sn+1;]
	}
-	Lệnh lặp: for, while, do ... while: Tương tự như các lệnh lặp của C.
-	Lệnh nhảy: goto n (n: số hiệu/nhãn của chương trình).
- 	Lệnh vào ra: cin và cout giống như C++.
1.3.4. Chương trình con: 
	 ()
 {
	S1;
	S2;
	...
	S3;
 [return (giá trị trả về) ]	 Báo kết thúc chương trình con
 }
Lưu ý: Nếu hàm có kiểu trả về khác kiểu void thì khi kết thúc hàm phải có câu lệnh return để gán kết quả cho hàm.
Sau đây là ví dụ về hàm có trả về giá trị.
Ví dụ: Viết chương trình con dạng hàm NamNhuan(x). Cho kết quả nếu số x là năm nhuận có giá trị là True(1), ngược lại có giá trị là False(0); chẳng hạn: NamNhuan(1996) cho giá trị 1, NamNhuan(1997) cho giá trị 0. Biết rằng x được gọi là năm nhuận nếu x chia hết cho 4 và x không chia hết cho 100 hoặc x chia hết cho 400.
	Cách 1: int namnhuan(x)
	{	if ((x % 4 == 0 && x % 100 != 0)||(x % 400 == 0))
	return 1;
	else
	 return 0;
	}
	Cách 2: int namnhuan(x)
	 { return(((x % 4 == 0) && (x % 100 != 0)) ||
	 (x % 400 = 0));
	}
Ví dụ viết về chương trình con không có giá trị trả về (hay còn gọi là thủ tục).
Ví dụ: Viết hàm Hoandoi(a, b) để hoán đổi giá trị của 2 biến số a và b cho nhau.
	Cách 1:	void hoandoi(&a, &b) //a và b là các tham biến
	 	{	tam=a;
	a=b;
	b=tam;
	}
	Cách 2:	void hoandoi(&a, &b)
	 	{	a= a+b;
	b= a-b;
	a= a-b;
	}
Lưu ý: Bên trong 1 chương trình con có thể dùng lệnh return; (thoát khỏi chương trình con), exit(1) (thoát khỏi chương trình chính).
CHƯƠNG 2: THIẾT KẾ VÀ PHÂN TÍCH THUẬT TOÁN
2.1. Thiết kế thuật toán:
2.1.1. Module hoá thuật toán:
	Các bài toán ngày càng đa dạng và phức tạp, do đó thuật toán mà ta đề xuất càng có quy mô lớn và việc viết chương trình cần có một lượng lập trình đông đảo. Muốn làm được việc này , người ta phân chia các bài toán lớn thành các bài toán nhỏ (module). Và dĩ nhiên một module có thể chia nhỏ thành các module con khác nữa,... bấy giờ việc tổ chức lời giải sẽ được thể hiện theo một cấu trúc phân cấp.
A
B
C
E
F
G
H
I
D
	Ví dụ:
	Quá trình module hoá bài toán được xem là nguyên lý “chia để trị” (divide & conquer) hay còn gọi là thiết kế từ đỉnh xuống (top-down) hoặc là thiết kế từ khái quát đến chi tiết (specialization).
	Việc module hoá trong l ...  danh sách tương ứng. Các nút ở trong danh sách i (trỏ bởi V[i]) biểu diễn các đỉnh lân cận của nút i. Mỗi nút có dạng:
Đỉnh
Tiếp
-	Mỗi danh sách i có một nút đầu danh sách (V[i]), các nút này thường được tổ chức thành một mảng để có thể truy cập được nhanh.
Lưu ý: Các nút trong từng danh sách thông thường sắp xếp theo thứ tự.
7.3. Phép duyệt một đồ thị:
7.3.1. Tìm kiếm theo chiều sâu:
	Xét đồ thị không định hướng và liên thông, phép tìm kiếm theo chiều sâu được thực hiện như sau:
	Đầu tiên thăm đỉnh V, sau đó thăm đỉnh W (đỉnh này chưa được thăm) là lân cận của V. Bấy giờ từ W, một phép tìm kiếm theo chiều sâu xuất phát từ W lại được thực hiện. Khi một đỉnh U vừa (đã) được thăm mà mọi đỉnh lân cận của nó được thăm rồi thì ta sẽ quay ngược lên đỉnh gần đây vừa được thăm (đây là thuật toán quay lui). Phép tìm kiếm sẽ kết thúc khi không còn một nút nào chưa được thăm mà vẫn có thể tới được một nút đã được thăm.
V1
V2
V3
V5
V6
V4
V7
V8
Ví dụ:
Thứ tự duyệt như sau:
V1, V2, V4, V8, V5, V7, V3, V6
Từ đó ta có thể xây dựng thuật toán của phép duyệt này là như sau:
	void Tim_Kiem_Sau(V)
	1.	Visited[V]=1;
	cout << V;
	2.	For 
	if Visited[W]==0 	
	Tim_Kiem_Sau(W);
	return;
Chương trình chính:
	For (i=1;i<=n;i++) // n là số nút tối đa của mảng 
	Visited[i]=0;
	Tim_Kiem_Sau(1); // Giả sử đồ thị có đỉnh 1 
	=>	Kết quả in ra sẽ là những đỉnh liên thông với đỉnh 1.
Lưu ý:
Trong thủ tục tìm kiếm sâu, ở bước 1 ta có thể bổ sung thêm lệnh chứng tỏ nút V được thăm (ví dụ, lệnh cout << V). Lúc này ở chương trình chính chỉ cần thực hiện các lệnh:
Khởi tạo các phần tử của mảng Visited bằng 0.
Gọi thủ tục Tim_Kiem_Sau(1).
Chương trình này chỉ duyệt qua tất cả các nút liên thông với nút 1 mà thôi.
Phép duyệt cây theo thủ tục tìm kiếm theo chiều sâu tức là duyệt theo thứ tự trước (đối với cây).
§ Bài tập:
	Viết chương trình bằng C++ thể hiện việc tìm kiếm sâu trong một đồ thị bằng 2 cách biểu diễn đồ thị (ma trận kề, danh sách kề).
7.3.2.Tìm kiếm theo chiều rộng:
	Phép tìm kiếm theo chiều rộng cũng xuất phát từ một đỉnh V nào đó nhưng khác với phép tìm kiếm theo chiều sâu ở chỗ: các đỉnh là lân cận của V mà chưa được thăm sẽ được thăm kế tiếp nhau rồi mới đến các đỉnh chưa được thăm là lân cận lần lượt của các đỉnh này...
	Ví dụ:
V1
V2
V3
V5
V6
V4
V7
V8
Thứ tự duyệt như sau:
V1, V2, V3, V4, V5, V6, V7, V8
Thuật toán tìm kiếm theo chiều rộng sẽ dựa vào nguyên tắc hàng đợi (Queue):
	void Tim_Kiem_Rong(V)
	1.	Visited[V]=1; 
	2.	
	Insert_Queue(Q, V); // cout << V; 
	3.	do 
 {
	Delete_Queue(Q, V);
	For 
	if (Visited[W]==0) 
	{
	Insert_Queue(Q, W);
	Visited[W]=1; // cout << W; 
	}
 }
while ;
	return;
Nhận xét:
Tìm kiếm theo chiều rộng sử dụng cấu trúc hàng đợi (Queue). Còn tìm kiếm theo chiều sâu sử dụng Stack (đệ quy).
Cả 2 thuật toán này đều có độ phức tạp tính toán O(n2).
§ Bài tập:
	Viết chương trình bằng C++ thể hiện việc tìm kiếm theo chiều rộng bằng 2 cách biểu diễn đồ thị.
7.4. Cây khung và cây khung với giá cực tiểu:
	Định nghĩa: Khi một đồ thị G(V, E) liên thông thì một phép tìm kiếm theo chiều sâu hay chiều rộng xuất phát từ một đỉnh nào đó sẽ cho phép thăm được mọi đỉnh của đồ thị. Trong trường hợp này, các cung của E sẽ được phân thành 2 tập:
Tập T bao gồm tất cả các cung được dùng tới hoặc được duyệt qua trong phép tìm kiếm.
Tập B bao gồm các cung còn lại.
	Lúc này, tất cả các cung trong tập T cùng với các đỉnh tương ứng tạo thành một cây khung.
Ví dụ: Cây khung T ứng với ví dụ trong tìm kiếm theo chiều rộng như sau:
1
2
3
4
5
6
7
8
	Cây khung T ứng với ví dụ trong tìm kiếm theo chiều sâu như sau:
8
1
2
3
4
5
6
7
Nhận xét:
Một cây khung T cho ta một đồ thị liên thông nhưng không tồn tại chu trình nào bên trong đồ thị này.
Khi ta bổ sung thêm một cung bất kỳ vào một cây khung thì sẽ xuất hiện một chu trình.
Đồ thị có n đỉnh thì cây khung có n-1 cung.
Ứng dụng (Xác định cây khung với giá cực tiểu):
	Xét bài toán sau:
	Giả sử cho 1 đồ thị liên thông có trọng số, vấn đề được đặt ra: Xác định cây khung với giá cực tiểu (cây khung mà tổng các trọng số trên cây khung đó là nhỏ nhất so với các cây khung khác). 
Giải quyết: Ta có thể sử dụng thuật toán của Kruscal.
Ý tưởng:
Các cung được xét để đưa vào T dựa vào thứ tự không giảm của trọng số tương ứng của chúng. Một cung được đưa vào T nếu nó không tạo nên chu trình với các cung đã có ở trong T.
2
5
1
4
3
5
7
4
2
10
2
5
1
4
3
2
5
Ở đây, nếu đồ thị có n đỉnh thì chỉ cần bổ sung n-1 cung.
Thuật toán:
	void	Kruscal(G)
T= Æ; 	//T là tập chứa các cung
while (½T½<n-1) 
	{
	;
	;
	if ( )
	T = T U {(V, W)} //Bổ sung cung (V, W) vào T
 }
	return;
CHƯƠNG 8: SẮP XẾP
8.1. Đặt vấn đề:
	Sắp xếp là quá trình bố trí lại các phần tử của một tập đối tượng nào đó theo một thứ tự nhất định. Yêu cầu về sắp xếp thường xuyên xuất hiện trong tin học nhằm giúp quản lý dữ liệu được dễ dàng.
	Các thuật toán sắp xếp được phân chia thành 2 nhóm chính:
+	Sắp xếp trong: Toàn bộ dữ liệu sắp xếp được đưa vào bộ nhớ trong. do đó dữ liệu không nhiều lắm nhưng ngược lại thời gian sắp xếp nhanh.
+	Sắp xếp ngoài: Một phần dữ liệu cần sắp xếp được đưa vào bộ nhớ trong, phần còn lại được lưu trữ ở bộ nhớ ngoài. do đó có thể sắp xếp dữ liệu với khối lượng lớn nhưng tiến trình sắp xếp sẽ chậm hơn.
	Nói chung, dữ liệu có thể xuất hiện dưới nhiều dạng khác nhau. Ở đây ta quy ước tập đối tượng được sắp xếp là tập các bản ghi. Tuy nhiên, khi sắp xếp, thường người ta chỉ quan tâm đến giá trị của 1 trường nào đó (gọi là trường khoá) và việc sắp xếp được tiến hành dựa vào trường khoá này. Để đơn giản, ở đây ta xem 1 bản ghi chỉ chứa 1 trường dữ liệu có kiểu số và thứ tự sắp xếp theo chiều tăng.
8.2. Một số phương pháp sắp xếp đơn giản:
8.2.1. Sắp xếp kiểu lựa chọn:
Nguyên tắc:
Tại mỗi bước i ta chọn trong dãy ai+1, ..., an các phần tử lớn hơn ai, sau đó thực hiện hoán đổi vị trí của chúng với ai (sao cho ai có giá trị nhỏ nhất (i =1..n).
Thuật toán:
void Selection_Sort(a, n)
	For (i=1; i<=n-1; i++)
	For (j=i+1; j<=n; j++)
	if (a[i]>a[j]) 
	;
	return;
8.2.2. Sắp xếp kiểu chèn:
Nguyên tắc: Tương tự như khi sắp bài tiến lên. Chia làm 2 trường hợp:
Kết hợp việc sắp xếp với việc nhập dữ liệu:
	void SapXep(a, n)
	For (i=1; i<=n; i++)
	{
	cin >> a[i];
	Chen(a[i]);
	}
	return;
	Trong đó, ta có thủ tục Chen(X) như sau:
 void	Chen(X)
	if (i>1) 
	{
	j=1;
	while ((a[j]<=X) && (j<=i-1)) j=j+1;
	if (j<i) 
	{
	For (k=i;k>=j+1;k--)
	a[k]=a[k-1];
	a[j]=X;
	}
	}
	return;
Sắp xếp từ mảng đã có dữ liệu:
	void Insert_Sort(a, n)
	Const VoCuc = 106;
a[0]= -VoCuc;
For (i=1;i<n;i++)	
	{
	X=a[i]; j=i-1;
	while (x<a[j]) 
	{
	a[j+1]=a[j]; j=j-1;
	}
	a[j+1]=X;
	}
	return;
Lưu ý: Ý tưởng của thuật toán này có thể thực hiện dễ dàng hơn nếu sử dụng danh sách móc nối để lưu dãy số này.
8.2.3. Sắp xếp kiểu nổi bọt:
	void Bubble_Sort(a, n)
	For (i=1; i<n; i++)
	For (j=n; j>=i+1; j--)
	if (a[j]<a[j-1]) 
	;
	return;
Nhận xét: Cả 3 thuật toán trên đều có độ phức tạp tính toán là O(n2).
8.3. Sắp xếp kiểu phân đoạn (Sắp xếp nhanh - quick sort):
Nguyên tắc:
	Chọn ngẫu nhiên một phần tử X của dãy (chẳng hạn phần tử đầu tiên) và cố gắng phân chia dãy này thành 3 dãy con liên tiếp nhau:
	+	Dãy 1: Gồm những phần tử nhỏ hơn X.
	+	Dãy 2: Gồm những phần tử bằng X.
	+	Dãy 3: Gồm những phần tử lớn hơn X.
	Sau đó áp dụng lại thuật toán này cho dãy con thứ nhất và dãy con thứ ba (dãy con này có số phần tử lớn hơn 1).
	void Quick_Sort(a, Be, Lon)
	if (Be<Lon) 
	{	i=Be+1; j=Lon; X=a[Be];
do
 {	while ((a[i]<X) && (i<=Lon)) i=i+1;
	if (i>Lon) 
	{	;
	Quick_Sort(a, Be, Lon-1); return;
	}
	while (a[j]>X) j=j-1;
	if (j=Be )	
	{	Quick_Sort(a, Be+1, Lon);
	return;
	}
	if (i<=j)	
	{	;
	i=i+1;
	j=j-1;
	}
	}
	while (i<=j);
	;
if (Be<j-1) Quick_Sort (a, Be, j-1);
	if (Lon>i) Quick_Sort (a, i, Lon);
	}
	return;
Lưu ý: Tại chương trình chính, để sắp xếp mảng a từ phần tử thứ nhất đến phần tử thứ n thì ta gọi thủ tục sắp xếp như sau: Quick_Sort (a, 1, n);
Người ta chứng minh được trong trường hợp xấu nhất, thuật toán này có độ phức tạp là O(nlog2n) (xem sách). Do đó, với n khá lớn thuật toán Quick sort tỏ ra hữu hiệu hơn các thuật toán đơn giản.
8.4. Sắp xếp kiểu vun đống (Heap sort):
Nguyên tắc: Với phương pháp sắp xếp này dãy số được lưu ở trong mảng sẽ được coi như là cấu trúc của cây nhị phân hoàn chỉnh.
Đầu tiên, cây nhị phân biểu diễn sẽ được sắp xếp để tạo thành một đống (heap). Ta gọi đó là giai đoạn tạo đống (đống là cây nhị phân hoàn chỉnh mà mỗi nút được gán một giá trị sao cho nút cha luôn có giá trị lớn hơn hoặc bằng nút con). Bấy giờ giá trị ở gốc sẽ là các khoá lớn nhất (gọi là khóa trội).
Sau đó, các động tác sau đây sẽ được lặp đi lặp lại nhiều lần cho đến khi cây chỉ còn lại một lá: Đưa khóa trội về vị trí thực của nó (bằng cách đổi chỗ cho khóa ở cuối đống đang xét), sau đó vun lại đống đối với cây gồm các khóa còn lại.
Lưu ý:
	Vấn đề được đặt ra là: cần xây dựng một thuật toán để điều chỉnh một cây thành một đống với giả thiết rằng cây con trái và cây con phải của gốc đã là đống.
	Một cách tổng quát, ta có thuật toán để điều chỉnh lại cây con tại i, biết rằng cây con trái (2i) và cây con phải (2i+1) đã là đống (giả sử đống a có n phần tử):
	void DieuChinh(a, i, n)
Key=a[i];
	j=2*i; // j: chỉ số chỉ tới cây con trái của i 
while (j<=n)
	{
	if ((j<n) && (a[j]<a[j+1])) 
	j=j+1;	/*Chọn j ở vị trí con của i nhưng
	 có giá trị lớn nhất */
	if (Key>=a[j]) 	/*Cần thiết cho lần thực
	 hiện sau của vòng lặp*/
	{
	a[j/2]=Key;
	return;
	}
	a[j/2]=a[j];
	j=2*j;
	}
a[j/2]=Key;
	return;
Lúc này thủ tục sắp xếp theo kiểu vun đống như sau:
	void Heap_Sort(a, n);
//Giai đoạn 1
	For (i=n/2;i>=1;i--)
	DieuChinh(a, i, n);	/*1 lá có thể xem như là đống 
	 cho nên thủ tục này thực hiện
	 từ trên lá trở lên*/
//Giai đoạn 2
	For (i=n-1;i>=1;i--)
	{
	;
	Dieuchinh(a, 1, i);
	}
	return;	
Lưu ý: Người ta cũng chứng minh được rằng độ phức tạp của thuật toán này là O(nlog2n).
8.5. Sắp xếp kiểu trộn (Merge sort):
-	Phép hoà nhập 2 đường. Xét bài toán: 
	Giả sử ta có mảng X chia làm 2 phần đã được sắp xếp: (Xb, Xb+1,....,Xm) và (Xm+1, Xm+2,....,Xn). Viết thuật toán tạo ra mảng Z có chỉ số từ b tới n (Zb, Zb+1,....,Zn) được sắp xếp.
	void Tron(X, b, m, n, Z);
i=b; j=m+1; k=b;
while ((i<=m) && (j<=n))
	{
	if (X[i]<=X[j] ) 	
	{
	Z[k]=X[i]; i=i+1;
	}
	else
	{
	Z[k]=X[j]; j=j+1;
	}
	k=k+1;
	}
	3.	if i>m (Z[k], ..., Z[n])=(X[j], ..., X[n]);
	else (Z[k], ..., Z[n])=(X[i], ..., X[m]);
	return;
-	Sắp xếp kiểu hòa nhập 2 đường trực tiếp: Sau đây là thủ tục thực hiện một bước sắp xếp kiểu trộn bằng cách trộn từng cặp kế cận nhau có độ dài là L từ mảng X sang mảng Y, với n là số phần tử ở trong X.
	void Chuyen(X, Y, n, L)
i=1;
while (i<=n-2*L+1)
	{
	Tron(X, i, i+L-1, i+2*L-1, Y); // i+2*L-1 <= n 
	i=i+2*L;
	}
{Trộn phần còn dư với phần trước}
	if (i+L-1>=n) (Y[i], ..., Y[n])=(X[i], ..., X[n])
	else Tron(X, i, i+L-1, n, Y);
	return;	
=> Từ đây ta có thể suy ra thủ tục sắp xếp theo kiểu trộn như sau:
	void Merge_Sort(X, Y, n)
L=1;
while (L<n)
	{
	Chuyen(X, Y, n, L);
	L=L*2;
	X=Y;
	}
	return;
Lưu ý:
Người ta chứng minh được rằng độ phức tạp của thuật toán này là O(nlog2n). Tuy nhiên, do phải tạo ra mảng Y nên phương pháp này tốn bộ nhớ trong hơn so với 2 thuật toán trên.
Thuật toán này thường được áp dụng cho việc sắp xếp ngoài (có kết hợp với file).
CHƯƠNG 9: TÌM KIẾM
9.1. Bài toán tìm kiếm:
	Tìm kiếm là một yêu cầu rất thường xuyên trong đời sống hàng ngày cũng như trong tin học. Để đơn giản ta xét bài toán tìm kiếm như sau:
	Cho một dãy số gồm các phần tử a1, a2, ..., an. Cho biết trong dãy này có phần tử nào có giá trị bằng X (cho trước) hay không?
9.2. Tìm kiếm tuần tự:
	Thuật toán tìm kiếm tuần tự có sử dụng một biến logic, biểu thị một phần tử có tồn tại trong dãy cần tìm hay không. Ở đây ta cũng có thể giải quyết theo cách khác:
	int TimKiemTT(a, n, X)
i=1; a[n+1]=X;
while (a[i]!=X) i=i+1;
	if (i==(n+1)) return 0
	else return i;
=> Hàm này sẽ trả về giá trị là một chỉ số i nào đó trong dãy nếu tìm thấy, ngược lại hàm sẽ trả về giá trị 0.
Lưu ý: Thuật toán này có độ phức tạp là O(n).
9.3. Tìm kiếm nhị phân:
	Với giả thiết ban đầu dãy đã được sắp theo thứ tự tăng dần. Thuật toán tìm kiếm nhị phân bằng đệ quy ta đã biết trong phần đệ quy. Tuy nhiên ta có thể khử đệ quy thuật toán này như sau:
	int TKNP(a, n, X);
Be=1; Lon=n;
while (Be<=Lon) 
	{
	Giua=(Be+Lon)/ 2;
	if (a[Giua]==X) return Giua;
	if (a[Giua]<X) Be=Giua+1;
	else Lon=Giua-1;
	}
return 0;
Lưu ý: Thuật toán này có độ phức tạp là O(log2n).
9.4. Cây nhị phân tìm kiếm:
	Cây nhị phân tìm kiếm là cây được sắp xếp mà ta đã bàn đến.
³N
N
<N
	Bài toán: Giả sử dãy số trên đã được chuyển vào cây nhị phân tìm kiếm mà nút gốc được trỏ bởi T. Vấn đề đặt ra: Viết một hàm CNPTK(T, X) trả về giá trị NULL nếu không có nút nào mà trường Info có giá trị bằng X, ngược lại cho kết quả là con trỏ trỏ vào phần tử đó.
	Nut * CNPTK(T, X)
q=T;
while (q!=NULL)
	{
	if (q->Info == X) break;
	if (q->Info Right;
	else q=q->Left;
	} 
return q;
Lưu ý: Khi đã có sẵn cây nhị phân tìm kiếm, thuật toán bổ sung một nút vào cây này thì ta đã xét. Nếu cần loại bỏ một nút trong cây nhị phân tìm kiếm, ta xét các trường hợp sau:
	 : Chỉ nút cần xoá	 : Cây con
B
A
Trước khi xóa
B
A
Sau khi xóa
i)	Xoá nút lá:
ii)	Xoá nút nửa lá:
B
A
C
B
A
C
B
A
Sau khi xóa
C
hoặc
Trước khi xóa
-	Xoá 1 nút không là lá, không là nửa lá:
A
B
D
C
E
F
Q, P
T
S
Trước khi xóa
A
B
D
C
F
Sau khi xóa
Thuật toán: Giả sử ta đã có hàm bố Bo(p):
	void	XoaNut(Q)
//Xử lý trong trường hợp nút lá và nửa lá
	p=Q;
	if (p->Left=NULL) 
	{
	R=Bo(Q); R->Left=p->Right;
	Free(p); return;
	}
	if (p->Right==NULL) 
	{
	R=Bo(Q); R->Left=p->Left;
	Free(p); return;
	}
	//Trường hợp Q là con phải của bố Q thì xử lý tương tự
T=p->Left;
	if (T->Right==NULL) 
	{
	R=Bo(Q);	 R->Left=T;
	T->Right=p->Right;	
	Free(p); return;
	}
	S=T->Right;
	while (S->Right!=NULL)	
	{
	T=S; S=S->Right;
	}
	S->Right=p->Right; T->Right=S->Left;
	S->Left=p->Left; R=Bo(Q); R->Left=S;
	Free(p);
return;
TÀI LIỆU THAM KHẢO
[1]	Cấu trúc dữ liệu và thuật toán (Đỗ Xuân Lôi)
[2]	Lập trình nâng cao bằng PASCAL với các cấu trúc dữ liệu (Larry Hoff - Lê Minh Trung dịch) - Tập 2
[3]	Cẩm nang thuật toán ( Robert Sedgewick) - 2 tập
[4]	The Art of Computer Programming (donald Knuth)
[5]	Algorithm + Data Structure = Program (Niklaus Wirth)
[6]	Cấu trúc dữ liệu và thuật toán, Đinh Mạnh Tường, Nhà Xuất bản ĐHQG Hà Nội, 2008
[7]	T. Cormen, C. E. Leiserson, R. L. Rivest, Introduction to Algorithms, Cambridge, MIT Press, 2nd Edition, 2005