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

GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 2 
Lời nói đầu 
 Sách này trình bày các cấu trúc dữ liệu (CTDL) và thuật toán. Các kiến thức 
về CTDL và thuật toán đóng vai trò quan trọng trong việc đào tạo cử nhân tin học. 
Sách này đựơc hình thành trên cơ sở các bài giảng về CTDL và thuật toán mà tôi 
đã đọc nhiều năm tại khoa Toán-Cơ-Tin học và khoa Công nghệ thông tin Đại học 
khoa học tự nhiên, Đại học quốc gia Hà nội. Sách được viết chủ yếu để làm tài liệu 
tham khảo cho sinh viên các Khoa Công nghệ thông tin, nhưng nó cũng rất bổ ích 
cho các độc giả khác cần có hiểu biết đầy đủ hơn về CTDL và thuật toán. 
 Chúng tôi mô tả các CTDL và các thuật toán trong ngôn ngữ Pascal, vì 
Pascal là ngôn ngữ được nhiều người biết đến và là ngôn ngữ được sử dụng nhiều 
để trình bày thuật toán trong sách báo. 
 Sách này gồm hai phần. Phần 1 nói về các CTDL, phần 2 nói về thuật toán. 
Nội dung của phần 1 gồm các chương sau đây. Chương 1 trình bày các khái niệm 
cơ bản về thuật toán và phân tích thuật toán. Chương 2 trình bày các khái niệm 
CTDL, mô hình dữ liệu, kiểu dữ liệu trừu tượng (DLTT). Chương 3 trình bày các 
mô hình dữ liệu, danh sách và các phương pháp cài đặt danh sách (bởi mảng và bởi 
CTDL danh sách liên kết). Hai kiểu DLTT đặc biệt quan trọng là hàng và ngăn xếp 
(stack) cũng được xét trong chương này. Chương này cũng trình bày một số ứng 
dụng của danh sách, hàng, ngăn xếp trong thiết kế thuật toán. Chương 4 trình bày 
mô hình dữ liệu cây, các phương pháp cài đặt cây, cây nhị phân, cây tìm kiếm nhị 
phân và cây cân bằng. Chương 5 nói về mô hình dữ liệu tập hợp, các phương pháp 
cài đặt tập hợp, từ điển và cài đặt từ điển bởi bảng băm, hàng ưu tiên và cài đặt 
hàng ưu tiên bởi heap. Chương 6 đề cập đến phương pháp cài đặt các dạng bảng 
khác nhau. Các CTDL ở bộ nhớ ngoài (file băm, file chỉ số, B-cây) được trình bày 
trong chương 7. 
 Tác giả 
 PTS Đinh Mạnh Tường. 
GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 3 
mục lục 
Chương I: Thuật toán và phân tích thuật toán 5 
1.1. Thuật toán 5 
1.1.1. Khái niệm thuật toán. 5 
1.1.2. Biểu diễn thuật toán. 7 
1.1.3. Các vấn đề liên quan đến thuật toán. 8 
1.2. Phân tích thuật toán 9 
1.2.1. Tính hiệu quả của thuật toán. 9 
1.2.2. Tại sao lại cần thuật toán có hiệu quả. 10 
1.2.3. Đánh giá thòi gian thực hiện thuật toán như thế náo. 11 
1.2.4. Ký hiệu ô lớn và đánh giá thời gian thực hiện 
 thuật toán bằng ký hiệu ô lớn. 12 
1.2.5. Các qui tắc đánh giá thời gian thực hiện thuật toán. 14 
1.2.6. Phân tích một số thuật toán. 17 
Chương II: Kiểu dữ liệu, cấu trúc dữ liệu và mô hình dữ liệu. 20 
2.1. Biểu diễn dữ liệu. 20 
2.2. Kiểu dữ liệu và cấu trúc dữ liệu. 21 
2.3. Hệ kiểu của ngôn ngữ Pascal. 23 
2.4. Mô hình dữ liệu và kiểu dữ liệu trừu tượng. 27 
Chương III: Danh sách 32 
3.1. Danh sách. 32 
3.2. Cài đặt danh sách bởi mảng. 34 
3.3. Tìm kiếm trên danh sách. 37 
3.3.1. Vấn đề tìm kiếm. 37 
3.3.2. Tìm kiếm tuần tự. 38 
3.3.3. Tìm kiếm nhị phân. 39 
3.4. Cấu trúc dữ liệu danh sách liên kết. 41 
3.4.1. Danh sách liên kết. 41 
3.4.2. Các phép toán trên danh sách liên kết. 42 
3.4.3. So sánh hai phương pháp. 47 
3.5. Các dạng danh sách liên kết khác. 47 
3.5.1. Danh sách vòng tròn. 47 
3.5.2. Danh sách hai liên kết. 51 
 3.6. ứng dụng danh sách. 53 
3.7. Stack. 57 
3.7.1. Stack. 57 
3.7.2. Cài đặt stack bởi mảng. 58 
3.7.3. Cài đặt stack bởi danh sách liên kết. 60 
3.8. Giá trị của một biểu thức. 63 
3.9. Hàng. 68 
GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 4 
3.9.1. Hàng. 68 
3.9.2. Cài đặt hàng bởi mảng. 68 
3.9.3. Cài đặt hàng bởi mảng vòng tròn. 71 
3.9.4. Cài đặt hàng bởi danh sách liên kết. 73 
Chương IV: Cây. 76 
4.1. Cây và các khái niệm về cây. 76 
4.2. Các phép toán trên cây. 79 
4.2.1. Các phép toán cơ bản trên cây. 79 
4.2.2. Đi qua cây(Diệt cây). 80 
4.3. Cài đặt cây. 84 
4.3.1. Biểu diễn cây bằng danh sách các con của mỗi đỉnh. 84 
4.3.2. Biểu diễn cây bằng con trưởng và em 
 liền kề của mỗi đỉnh. 90 
4.3.3. Biểu diễn cây bởi cha của mỗi đỉnh. 92 
4.4. Cây nhị phân. 93 
4.5. Cây tìm kiếm nhị phân. 99 
4.6. Thời gian thực hiện các phép toán trên cây tìm kiếm nhị phân. 106 
4.7. Cây cân bằng. 109 
4.8. Thời gian thực hiện các phép toán trên cây cân bằng. 120 
Chương V: Tập hợp. 122 
5.1. Tập hợp và các phép toán tập hợp. 122 
5.2. Cài đặt tập hợp. 125 
5.2.1. Cài đặt tập hợp bởi vecto bit. 125 
5.2.2. Cài đặt tập hợp bởi danh sách. 126 
5.3. Từ điển. 131 
5.4. Cấu trúc dữ liệu bảng băm. Cài đặt từ điển bởi bảng băm. 131 
5.4.1. Bảng băm mở. 132 
5.4.2. Bảng băm đóng. 
 136 
5.5. Phân tích và đánh giá các phương pháp băm. 142 
5.6. Hàng ưu tiên. 145 
5.7. Heap và cài đặt hàng ưu tiên bởi heap. 146 
Chương VI: Bảng. 154 
6.1. Kiểu dữ liệu trừu tượng bảng. 154 
6.2. Cài đặt bảng. 155 
6.3. Bảng chữ nhật. 157 
6.3.1. Bảng tam giác và bảng răng lược. 158 
6.3.2. Bảng thưa thớt. 160 
6.4. Trò chơi đời sống. 162 
Chương VII: Các cấu trúc dữ liệu ở bộ nhớ ngoài. 172 
7.1. Mô hình tổ chức dữ liệu ở bộ nhớ ngoài. 172 
7.2. File băm. 
174 
7.3. File có chỉ số. 175 
7.4. B-cây. 178 
GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 5 
Chương I 
Thuật toán và phân tích thuật toán 
 1.1. Thuật toán. 
 1.1.1. Khái niệm thuật toán. 
 Thuật toán (algorithm) là một trong những khái niệm quan trọng nhất trong tin 
học. Thuật ngữ thuật toán xuất phát từ nhà toán học A rập Abu Ja'far Mohammed ibn 
Musa al Khowarizmi (khoảng năm 825). Tuy nhiên lúc bấy giờ và trong nhiều thế kỷ sau, 
nó không mang nội dung như ngày nay chúng ta quan niệm. Thuật toán nổi tiếng nhất, có 
từ thời cổ Hy lạp là thuật toán Euclid, thuật toán tìm ước chung lớn nhất của hai số 
nguyên. Có thể mô tả thuật toán này như sau : 
 Thuật toán Euclid. 
 Input : m, n nguyên dương 
 Output : g, ước chung lớn nhất của m và n 
 Phương pháp : 
 Bước 1 : Tìm r, phần dư của phép chia m cho n 
 Bước 2 : Nếu r = O, thì g  n (gán giá trị của n cho g) và dừng lại. Trong trường 
hợp ngược lại (r 0), thì m  n, n  r và quay lại bước 1. 
 Chúng ta có thể quan niệm các bước cần thực hiện để làm một món ăn, được mô 
tả trong các sách dạy chế biến món ăn, là một thuật toán. Cũng có thể xem các bước cần 
tiến hành để gấp đồ chơi bằng giấy, được trình bầy trong sách dạy gấp đồ chơi bằng giấy, 
là thuật toán. Phương pháp thực hiện phép cộng, nhân các số nguyên, chúng ta đã học ở 
cấp I cũng là các thuật toán. 
 Trong sách này chúng ta chỉ cần đến định nghĩa không hình thức về thuật toán : 
 Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán 
hoặc hành động cần thực hiện, để giải quyết một số vấn đề. 
 (Từ điểm Oxford Dictionary định nghĩa, Algorithm: set of well - defined rules for 
solving a problem in a finite number of steps.) 
 Định nghĩa này, tất nhiên, còn chứa đựng nhiều điều chưa rõ ràng. Để hiểu đầy đủ 
ý nghĩa của khái niệm thuật toán, chúng ta nêu ra 5 đặc trưng sau đây của thuật toán 
(Xem D.E. Knuth [1968]. The Art of Computer Programming, vol. I. Fundamental 
Algorithms). 
 1. Input. Mỗi thuật toán cần có một số (có thể bằng không) dữ liệu vào (input). 
Đó là các giá trị cần đưa vào khi thuật toán bắt đầu làm việc. Các dữ liệu này cần được 
lấy từ các tập hợp giá trị cụ thể nào đó. Chẳng hạn, trong thuật toán Euclid trên, m và n là 
các dữ liệu vào lấy từ tập các số nguyên dương. 
 2. Output. Mỗi thuật toán cần có một hoặc nhiều dữ liệu ra (output). Đó là các giá 
trị có quan hệ hoàn toàn xác định với các dữ liệu vào và là kết quả của sự thực hiện thuật 
GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 6 
toán. Trong thuật toán Euclid có một dữ liệu ra, đó là g, khi thực hiện đến bước 2 và phải 
dừng lại (trường hợp r = 0), giá trị của g là ước chung lớn nhất của m và n. 
 3. Tính xác định. Mỗi bước của thuật toán cần phải được mô tả một cách chính 
xác, chỉ có một cách hiểu duy nhất. Hiển nhiên, đây là một đòi hỏi rất quan trọng. Bởi vì, 
nếu một bước có thể hiểu theo nhiều cách khác nhau, thì cùng một dữ liệu vào, những 
người thực hiện thuật toán khác nhau có thể dẫn đến các kết quả khác nhau. Nếu ta mô tả 
thuật toán bằng ngôn ngữ thông thường, không có gì đảm bảo người đọc hiểu đúng ý của 
người viết thuật toán. Để đảm bảo đòi hỏi này, thuật toán cần được mô tả trong các ngôn 
ngữ lập trình (ngôn ngữ máy, hợp ngữ hoặc ngôn ngữ bậc cao như Pascal, Fortran, C, ...). 
Trong các ngôn ngữ này, các mệnh đề được tạo thành theo các qui tắc cú pháp nghiêm 
ngặt và chỉ có một ý nghĩa duy nhất. 
 4. Tính khả thi. Tất cả các phép toán có mặt trong các bước của thuật toán phải 
đủ đơn giản. Điều đó có nghĩa là, các phép toán phải sao cho, ít nhất về nguyên tắc có thể 
thực hiện được bởi con người chỉ bằng giấy trắng và bút chì trong một khoảng thời gian 
hữu hạn. Chẳng hạn trong thuật toán Euclid, ta chỉ cần thực hiện các phép chia các số 
nguyên, các phép gán và các phép so sánh để biết r = 0 hay r 0. 
 5. Tính dừng. Với mọi bộ dữ liệu vào thoả mãn các điều kiện của dữ liệu vào (tức 
là được lấy ra từ các tập giá trị của các dữ liệu vào), thuật toán phải dừng lại sau một số 
hữu hạn bước thực hiện. Chẳng hạn, thuật toán Euclid thoả mãn điều kiện này. Bởi vì giá 
trị của r luôn nhỏ hơn n (khi thực hiện bước 1), nếu r 0 thì giá trị của n ở bước 2 là giá 
trị của r ở bước trước, ta có n > r = n1 > r1 = n2 > r2 ... Dãy số nguyên dương giảm dần 
cần phải kết thúc ở 0, do đó sau một số bước nào đó giá trị của r phải bằng 0, thuật toán 
dừng. 
 Với một vấn đề đặt ra, có thể có một hoặc nhiều thuật toán giải. Một vấn đề có 
thuật toán giải gọi là vấn đề giải được (bằng thuật toán). Chẳng hạn, vấn đề tìm nghiệm 
của hệ phương trình tuyến tính là vấn đề giải được. Một vấn đề không tồn tại thuật toán 
giải gọi là vấn đề không giải được (bằng thuật toán). Một trong những thành tựu xuất sắc 
nhất của toán học thế kỷ 20 là đã tìm ra những vấn đề không giải được bằng thuật toán. 
 Trên đây chúng ta đã trình bày định nghĩa không hình thức về thuật toán. Có thể 
xác định khái niệm thuật toán một cách chính xác bằng cách sử dụng các hệ hình thức. 
Có nhiều hệ hình thức mô tả thuật toán : máy Turing, hệ thuật toán Markôp, văn phạm 
Chomsky dạng 0, ... Song vấn đề này không thuộc phạm vi những vấn đề mà chúng ta 
quan tâm. Đối với chúng ta, chỉ sự hiểu biết trực quan, không hình thức về khái niệm 
thuật toán là đủ. 
 1.1.2. Biểu diễn thuật toán. 
 Có nhiều phương pháp biểu diễn thuật toán. Có thể biểu diễn thuật toán bằng 
danh sách các bước, các bước được diễn đạt bằng ngôn ngữ thông thường và các ký hiệu 
toán học. Có thể biểu diễn thuật toán bằng sơ đồ khối. Tuy nhiên, như đã nói, để đảm bảo 
tính xác định của thuật toán, thuật toán cần được viết trong các ngôn ngữ lập trình. Một 
chương trình là sự biểu diễn của một thuật toán trong ngôn ngữ lập trình đã chọn. Để đọc 
dễ dàng các phần tiếp theo, độc giả cần làm quen với ngôn ngữ lập trình Pascal. Đó là 
ngôn ngữ thường được chọn để trình bày các thuật toán trong sách báo. 
 Trong sách này chúng ta sẽ trình bày các thuật toán bởi các thủ tục hoặc hàm 
trong ngôn ngữ tựa Pascal. Nói là tựa Pascal, bởi vì trong nhiều trường hợp, để cho ngắn 
gọn, chúng ta không hoàn toàn tuân theo các qui định của Pascal. Ngoài ra, có trường 
GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 7 
hợp, chúng ta xử dụng cả các ký hiệu toán học và các mệnh đề trong ngôn ngữ tự nhiên 
(tiếng Anh hoặc tiếng Việt). Sau đây là một số ví dụ. 
 Ví dụ 1 : Thuật toán kiểm tra số nguyên n(n > 2) có là số nguyên tố hay không. 
 function NGTO (n : integer) : boolean ; 
 var a : integer ; 
 begin NGTO : = true ; 
 a : = 2 ; 
 while a <= sqrt (n) do 
 if n mod a = 0 then NGTO : = false 
 else a : = a +1 ; 
 end ; 
 Ví dụ 2 : Bài toán tháp Hà Nội. Có ba cọc A, B, C. Lúc đầu, ở cọc A có n đĩa được 
lồng vào theo thứ tự nhỏ dần từ thấp lên cao. Đòi hỏi phải chuyển n đĩa từ cọc A sang cọc 
B, được quyền sử dụng cọc C làm vị trí trung gian, nhưng không được phép đặt đĩa lớn 
lên trên đĩa nhỏ. 
 Để chuyển n đĩa từ cọc A sang cọc B, ta thực hiện thủ tục sau : đầu tiên là chuyển 
n - 1 đĩa bên trên từ cọc A sang cọc C, sau đó chuyển đĩa lớn nhất từ cọc A sang cọc B. 
Đến đây, chỉ cần cuyển n - 1 đĩa từ cọc C sang cọc B. Việc chuyển n-1 đĩa từ cọc này 
sang cọc kia được thực hiện bằng cách áp dụng đệ qui thủ tục trên. 
 Procedure MOVE (n, A, B, C) ; 
 {thủ tục chuyển n đĩa từ cọc A sang cọc B} 
 begin 
 if n=1 then chuyển một đĩa từ cọc A sang cọc B 
 else 
 begin 
 MOVE (n-1, A, C, B) ; 
 Chuyển một đĩa từ cọc A sang cọc B ; 
 MOVE (n-1, C, B, A) ; 
 end 
 end ; 
 A B C 
GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 8 
 1.1.3. Các vấn đề liên quan đến thuật toán. 
 Thiết kế thuật toán. 
 Để giải một bài toán trên MTĐT, điều trước tiên là chúng ta phải có thuật toán. 
Một câu hỏi đặt ra là, làm thế nào để tìm ra thuật toán cho một bài toán đã đặt ra ? Lớp 
các bài toán được đặt ra từ các ngành khoa học kỹ thuật từ các lĩnh vực hoạt động của con 
ngươì là hết sức phong phú và đa dạng. Các thuật toán giải các lớp bài toán khác nhau 
cũng rất khác nhau. Tuy nhiên, có một số kỹ thuật thiết kế thuật toán chung như chia-để-
trị (divide-and-conquer), phương pháp tham lam (greedy method), qui hoạch động 
(dynamic programming), ... Việc nắm được các chiến lược thiết kế thuật toán này là hết 
sức cần thiết, nó giúp cho bạn dễ tìm ra các thuật toán mới cho các bài toán của bạn. Các 
đề tài này sẽ được đề cập đến trong tập II của sách này. 
 Tính đúng đắn của thuật toán. 
 Khi một thuật toán được làm ra, ta cần phải chứng minh rằng, thuật toán khi đựoc 
thực hiện sẽ cho ta kết quả đúng với mọi dữ liệu vào hợp lệ. Điều này gọi là chứng minh 
tính đúng đắn của thuật toán. Việc chứng minh một thuật toán đúng đắn là một công việc 
không dễ dàng. Trong nhiều trường hợp, nó đòi hỏi ta phải có trình độ và khả năng tư duy 
toán học tốt. 
 Sau đấy ta sẽ chỉ ra rằng, khi thực hiện thuật toán Euclid, g sẽ là ước chung lớn 
nhất của hai số nguyên dương m và n bất kỳ. Thật vậy khi thực hiện bước 1, ta có m = qn 
+ r, trong đó q là số nguyên nào đó. Nếu r = 0 thì n là ước của m và hiển nhiên n (do đó 
g) là ước chung lớn nhất của m và n. Nếu r 0, thì một ước chung bất kỳ của m và n 
cũng là ước chung của n và r (vì r = m - qn). Ngược lại một ước chung bất kỳ của n và r 
cũng là ước chung của m và n (vì m = qn + r). Do đó ước chung lớn nhất của n và r cũng 
là ước chung lớn nhất của m và n. Vì vậy, khi thực hiện lặp lại bước 1 với sự thay đổi giá 
trị của m bởi n giá trị của n bởi r (các phép gán m , nr ở bước 2) cho tới khi r = 0, ta 
sẽ nhận được giá trị của g là ước chung lớn nhất của các giá trị m và n ban đầu. 
 Phân tích thuật toán. 
 Giả sử đối với một bài toán nào đó chúng ta có một số thuật toán giải. Một câu 
hỏi mới xuất hiện là, chúng ta cần chọn thuật toán nào trong số các thuật toán đó để áp ...  trong đó b là địa chỉ của khối, còn v là giá trị 
khoá nhỏ nhất của các bản ghi trong khối b. Từ các khối của file chính, ta sẽ tạo ra file 
chỉ số (index file), file này gồm các chỉ số khối của file chính. Các chỉ số khối được sắp 
xếp theo thứ tự tăng dần của khoá vào một số khối cần thiết. Các khối này có thể được 
móc nối với nhau tạo thành một danh sách liên kết. Trong trường hợp này file chỉ số gồm 
một danh sách liên kết các khối, các khối chứa các chỉ số khối của file chính. Một cách 
khác ta cũng có thể sử dụng một bảng để lưu giữ địa chỉ của các khối trong file chỉ số. 
Hình 7.2 minh hoạ cấu trúc của file có chỉ số. 
file chỉ số 
file chính 
 Hình 7.2. Cấu trúc file có chỉ số 
 Sau đây chúng ta sẽ xét sự thực hiện các phép toán trên file được tổ chức dưới 
dạng file có chỉ số 
 Tìm kiếm : 
5 17 35 49 
5 9 12 17 21 33 35 37 42 49 51 56 
GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 155 
 Giả sử ta cần tìm bản ghi x với khoá v cho trước. Trước hết ta cần tìm trên file chỉ 
số một chỉ số (v1, b1) sao cho v1 là giá trị khoá lớn nhất trong file chỉ số thoả mãn điều 
kiện v1 v. Ta sẽ nói v1 phủ v. 
 Việc tìm kiếm trên file chỉ số một giá trị khoá v1 phủ giá trị khoá v cho trước có 
thể thực hiện bằng cách tìm kiếm tuần tự hoặc tìm kiếm nhị phân. 
 Trong tìm kiếm tuần tự, ta cần xem xét tất cả các bản ghi của file chỉ số cho tới 
khi tìm thấy một chỉ số (v1, b1) với v1 phủ v. Nếu v nhỏ hơn giá trị khoá của bản ghi đầu 
tiên trong file chỉ số thì điều đó có nghĩa là trong file chỉ số không chứa giá trị khoá phủ 
v. 
 Phương pháp có hiệu quả hơn là tìm kiếm nhị phân. Giả sử các bản ghi của file 
chỉ số được sắp xếp vào các khối được đánh số từ 1 đến m. Xét khối thứ m/2 . Giả sử 
(v2, b2) là bản ghi đầu tiên trong khối. So sánh giá trị khoá cho trước v với giá trị khoá v2. 
Nếu v < v2 ta tiến hành tìm kiếm trên các khối 1,2, . . ., m/2 - 1. Còn nếu v v2, ta tiến 
hành tìm kiếm trên các khối m/2 , m/2 . + 1, . . . , m. Quá trình trên được lặp lại cho 
tới khi ta chỉ cần tìm kiếm trên một khối. Lúc này ta chỉ việc lần lượt so sánh giá trị khoá 
v cho trước với giá trị khoá chứa trong khối này. 
 Để tìm ra bản ghi x với khoá v cho trước, trước hết ta tìm trên file chỉ số một chỉ 
số (v1, b1) với v1 phủ v. Sau đó lần lượt xét các bản ghi trong khối có địa chỉ b1 để phát 
hiện ra bản ghi có khoá v, hoặc không nếu trong khối không có bản ghi nào với khoá là v. 
Nếu trên file chỉ số không chứa giá trị khoá v1 phủ v, thì file chính không chứa bản ghi có 
khoá v. 
 Xen vào : 
 Giả sử ta cần thêm vào file bản ghi r với giá trị khoá v. 
 Giả sử file chính được chứa trong các khối B1, B2, . . . , B k và các giá trị khoá của 
các bản ghi trong khối Bi nhỏ hơn các giá trị khoá trong khối B i +1. 
 Trước hết ta cần tìm ra khối Bi cần phải xếp bản ghi r vào đó. Muốn vậy ta áp 
dụng thủ tục tìm kiếm trên file chỉ số để tìm ra chỉ số (v1, b1) với v1 phủ v. Nếu tìm thấy 
thì B i là khối có địa chỉ b 1, ngược lại B i là khối B 1. 
 Trong trường hợp B i chưa đầy và r còn chưa có ở trong khối B i thì ta xếp bản ghi r 
vào đúng vị trí của nó, tức là phải đảm bảo trật tự tăng dần theo khoá. 
 Nếu Bi là B1 thì sau khi thêm vào bản ghi r, nó trở thành bản ghi đầu tiên trong 
khối B1, do đó ta cần phải tiến hành sửa đổi chỉ số của khối B1 trong file chỉ số. 
 Trong trường hợp B i đã đầy, ta tiến hành xếp bản ghi r vào đúng vị trí của nó 
trong B i, khi đó còn thừa ra một bản ghi. Tìm đến khối B i + 1 (ta biết được địa chỉ của khối 
B i + 1 bằng cách tìm trong chỉ số). Nếu B i + 1 chưa đầy thì ta xếp bản ghi thừa ra của B i 
vào vị trí đầu tiên trong khối B i + 1 đồng thời sửa lại chỉ số của B i + 1 trong file chỉ số. 
Nếu khối cũng đầy hoặc không tồn tại khi B i là B k thì ta thêm vào file chính một khối 
mới và xếp bản ghi r vào khối mới này. Chỉ số của khối mới thêm vào cần phải được xen 
vào file chỉ số. 
 Loại bỏ : 
 Để loại bỏ bản ghi r với khoá v, ta cần áp dụng thủ tục tìm kiếm để định vị bản 
ghi trong file. Sau đó sẽ tiến hành xoá bỏ r bằng nhiều cách khác nhau, chẳng hạn có thể 
đặt lại giá trị của bit đầy/rỗng tương ứng với bản ghi cần xoá ở đầu khối. 
GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 156 
 Sửa đổi : 
 Giả sử ta cần sửa đổi bản ghi với khoá v. Nếu các giá trị cần sửa không là giá trị 
của các trường thuộc khoá, thì ta chỉ cần áp dụng thủ tục tìm kiếm để tìm ra bản ghi và 
tiến hành các sửa đổi cần thiết. Nếu các giá trị cần sửa thuộc khoá thì việc sửa đổi được 
thực hiện bằng cách loại bỏ bản ghi cũ, xen vào bản ghi mới. 
7.4. B - cây. 
 Mục đích của chúng ta là nghiên cứu các cấu trúc dữ liệu biểu diễn file sao cho 
các phép toán trên file được thực hiện hiệu quả, tức là với số lần thực hiện phép toán truy 
cập khối ít nhất có thể được, khi cần phải tìm kiếm, xen vào, loại bỏ hoặc sửa đổi các bản 
ghi trên file. B - cây là một cấu trúc dữ liệu đặc biệt thích hợp để biểu diễn file. Trong 
mục này chúng ta sẽ trình bày B - cây và các kỹ thuật để thực hiện các phép toán tìm 
kiếm, xen vào và loại bỏ trên B - cây. 
 Cây tìm kiếm đa nhánh ( Multiway Search Trees) 
 Cây tìm kiếm m nhánh là sự tổng quát hoá của cây tìm kiếm nhị phân, trong đó 
mỗi đỉnh của cây có nhiều nhất m con. Các đỉnh của cây được gắn với các giá trị khoá 
của các bản ghi. Nếu đỉnh a có r con ( r m) thì nó chứa đúng r - 1 khoá ( k1, k2, . . . , kr-
1), trong đó k1 < k2< . . . < kr-1 (Chúng ta giả thiết rằng các giá trị khoá được sắp xếp thứ 
tự tuyến tính). Tổng quát hoá tính chất về khoá gắn với các đỉnh của cây tìm kiếm nhị 
phân, cây tìm kiếm m nhánh phải thoả mãn tính chất sau đây. Nếu đỉnh a có r con và 
chứa các khoá ( k1, k2, . . . , kr-1) thì các khoá chứa trong các đỉnh của cây con thứ nhất 
của đỉnh a nhỏ hơn k1, còn các khoá chứa trong các đỉnh của cây con thứ i ( i = 2, . . . , r-
1) phải lớn hơn hoặc bằng k i - 1 và nhỏ hơn k i, các khoá chứa trong các đỉnh của cây con 
thứ r phải lớn hơn hoặc bằng k r-1. Mỗi lá của cây chứa một số khoá, tối đa là s. 
 Các phép toán tìm kiếm, xen vào và loại bỏ trên cây tìm kiếm m nhánh được thực 
hiện bằng các kỹ thuật tương tự như đối với cây tìm kiếm nhị phân. 
 B - cây ( B - Trees) 
 B - cây là một loại đặc biệt của cây tìm kiếm m nhánh cân bằng (xem lại khái 
niệm cây cân bằng trong mục 7, chương 4). Cụ thể, B - cây được định nghĩa như sau : 
 B - cây cấp m là cây tìm kiếm m nhánh thoả mãn các tính chất sau đây 
1. Nếu cây không phải là cây chỉ gồm có gốc thì gốc có ít nhất hai con và nhiều nhất m 
con. 
2. Mỗi đỉnh trong của cây, trừ gốc, có ít nhất m/2 con và nhiều nhất m con. 
3. Tất cả các lá của cây trên cùng một mức. (Nói cách khác, tất cả các đường đi từ gốc 
tới lá cây có cùng độ dài). 
 Tư tưởng của việc tổ chức file dưới dạng B - cây là như sau. Ta sắp xếp các bản 
ghi của file (file chính) vào một số khối cần thiết. Mỗi khối này sẽ là lá của B - cây. 
Trong mỗi khối các bản ghi được sắp xếp theo thứ tự tăng dần của khoá. Các chỉ số của 
các khối này (các lá) lại được sắp xếp vào một số khối mới. Trong mỗi khối này, các chỉ 
số được sắp xếp theo thứ tự tăng dần của khoá. Trong B - cây, các khối này sẽ là các đỉnh 
ở mức trên của mức các lá. Ta lại lấy chỉ số của các khối vừa tạo ra sắp xếp vào một số 
khối mới. Các khối này lại là các đỉnh ở mức trên của mức từ đó được tạo ra. Quá trình 
GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 157 
trên sẽ tiếp tục cho tới khi các chỉ số có thể xếp gọn vào một khối. Khối này là đỉnh của 
cây B - cây. 
 Như vậy, mỗi đỉnh của B - cây là một khối. Mỗi đỉnh trong của B - cây có dạng 
 (p0, v1, p1, v2, p2, . . . , vn, pn) 
trong đó v1 < v2 < . . . < và ( vi, pi), 0 i n, là chỉ số của một khối, tức là vi là giá trị 
khoá nhỏ nhất trong một khối, còn pi là con trỏ trỏ tới khối chứa khoá nhỏ nhất vi, tức là 
con trỏ trỏ tới đỉnh con thứ i của đỉnh trong đang nói tới. Cần lưu ý rằng, giá trị của khoá 
v0 không được lưu giữ ở mỗi đỉnh trong, lý do là để tiết kiệm bộ nhớ. 
 Ví dụ : Hình 7.3 biểu diễn một B - cây cấp 3. B - cây được tạo thành từ 11 khối 
được đánh số B1, B2, . . . , B 11. Mỗi khối là đỉnh trong chứa được 3 chỉ số. Mỗi khối là lá 
chứa được 3 bảng ghi ( 3 số nguyên). File ở đây là file các số nguyên được lưu giữ ở các 
khối từ B5 đến B11. 
 B1 
B2 B3 B4 
B5 B6 B7 B8 -- B9 B10 B11 
 Hình 7.3 B - cây 
 Sau đây chúng ta sẽ nghiên cứu sự thực hiện các phép toán tìm kiếm, xen vào và 
loại bỏ trên B - cây. 
 Tìm kiếm 
 Giả sử chúng ta cần tìm bản ghi r có khoá v cho trước. Chúng ta cần phải tìm 
đường đi từ gốc của B - cây tới lá, sao cho lá này cần phải chứa bản ghi r nếu nó có ở 
trong file. 
 21 143 
 9 - 58 92 195 _ . 
3 5 - 9 15 - 21 36 49 58 - 92 121 - 143 169 195 211 232 
GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 158 
 Trong quá trình tìm kiếm, giả sử tại một thời điểm nào đó ta đạt tới đỉnh B. Nếu 
khối B là lá, ta tìm trong khối B xem nó có chứa bản ghi r hay không. Nhớ lại rằng các 
bản ghi của file được xếp vào các khối theo thứ tự tăng dần của khoá, do đó sự tìm kiếm 
trong khối B có thể tiến hành bằng kỹ thuật tìm kiếm tuần tự hoặc tìm kiếm nhị phân. 
 Nếu B là một đỉnh trong chứa ( p0, v1, p1, . . . , vn, pn) thì ta cần xác định vị trí của 
giá trị khoá v trong dãy giá trị khoá v1, v2, . . . , vn. Nếu v < v1 thì ta đi xuống đỉnh được 
trỏ bởi po. Nếu vi v < v i + 1 thì ta đi xuống đỉnh được trỏ bởi pi ( i = 1, 2, . . . n - 1). Còn 
nếu vn < v thì đi xuống đỉnh được trỏ bởi pn. 
 Xen vào : 
 Giả sử ta cần phải xen vào B - cây một bản ghi r với khoá là v. Đầu tiên ta áp 
dụng thủ tục tìm kiếm để tìm ra khối B cần phải xen bản ghi r vào đó. 
 Nếu khối B còn đủ chỗ cho bản ghi r thì ta xếp bản ghi r vào khối B sao cho thứ tự 
tăng dần của khoá được bảo tồn. Chú ý rằng, r không thể là bản ghi đầu tiên của khối B, 
trừ khi B là lá ngoài cùng bên trái. Nếu B là lá ngoài cùng bên trái thì giá trị khoá nhỏ 
nhất trong khối B không có mặt trong các đỉnh là tiền thân của đỉnh B. Vì vậy trong 
trường hợp này chỉ cần thêm bản ghi r vào khối B là xong, không cần sửa đổi gì với các 
đỉnh là tiền thân của khối B. 
 Nếu khối B không còn đủ không gian để lưu giữ bản ghi r thì ta thêm vào B - cây 
một lá mới, khối B'. Chuyển một nửa số bản ghi ở cuối của khối B sang khối B'. Sau đó 
xếp bản ghi r vào khối B hoặc khối B' sao cho vẫn đảm bảo được tính tăng dần của các 
giá trị khoá. Giả sử Q là cha của B, ta có thể biết được Q nếu trong quá trình tìm kiếm, ta 
lưu lại vết của đường đi từ gốc tới B. Giả sử chỉ số của khối B' là (v', p'), trong đó v' là giá 
trị khoá nhỏ nhất trong B', còn p' là địa chỉ của khối B'. áp dụng thủ tục trên để xen _v', 
p') vào khối Q. Nếu khối Q không còn đủ chỗ cho (v', p') thì ta lại phải thêm vào B - cây 
một đỉnh mới Q', nó là em liền kề của Q. Sau đó lại phải tìm đến cha của đỉnh Q để đưa 
vào chỉ số của khối mới Q'. Quá trình có thể tiếp diễn và dẫn đến việc phải phân đôi số 
giá trị khoá ở gốc, nửa sau được chuyển vào khối mới. Trong trường hợp này, ta phải tạo 
ra một gốc mới có đúng hai con, một con là gốc cũ, một con là đỉnh mới đưa vào. 
 Ví dụ. Giả sử ta cần xen vào B - cây trong hình 7.3 bản ghi có khoá 32. Trước hết 
ta phải tìm khối cần phải đưa bản ghi này vào. Bắt đầu từ gốc B1, vì 21 < 32 < 143, ta đi 
xuống B3. Tại B3, 32 < 58, ta đi xuống B7. B7 là lá, vậy cần phải đưa bản ghi với khoá 32 
vào B7. Nhưng khối B7 đã đầy. Ta thêm vào khối mới B12 và xếp các bản ghi với khoá 21, 
32 vào khối B7, xếp các bản ghi với khoá 36, 49 vào khối B12. Chỉ số của khối B12 chứa 
giá trị khoá 36. Cần phải xếp chỉ số B12 vào cha của B7 là B3. Nhưng B3 cũng đầy. Thêm 
vào khối mới B13. Sau đó các chỉ số của các khối B7, B12 được xếp vào B3 còn các chỉ số 
của các khối B8, B9 được xếp vào B13. Bây giờ chỉ số của khối B13 là 58 và địa chỉ của khối 
B13 cần được xếp vào khối B1. Nhưng B1 cũng đầy thêm vào B - cây khối mới B14. Xếp 
các chỉ số của B2, B3 vào B1, các chỉ số của B 13, B4 vào B14. Vì B1 là gốc, ta phải thêm vào 
gốc mới, khối B15 và xếp các chỉ số của B1 và B14 vào B15. Kết quả là ta có B - cây trong 
hình 7.4. 
 B15 
 B1 B14 
 B2 B3 B13 B4 -- 
 58 - 
 21 - 143 - 
 9 - 36 - 92 - 195 - . 
3 5 - 9 15 - 21 32 - 36 49 - 58 - - 92 121 - 143169 -
169169 
GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 159 
 B5 B6 B7 B12 B8 B9 B10 
 Hình 7.4 B - cây sau khi thêm vào B - cây trong hình 7.3 
 bản ghi với giá trị khoá 32 
 Loại bỏ 
 Giả sử ta cần loại khỏi B - cây bản ghi r với khoá v. Đầu tiên áp dụng thủ tục tìm 
kiếm để tìm ra lá B chứa bản ghi r. Sau đó loại bỏ bản ghi r trong khối B. 
 Giả sử sau khi loại bỏ B không rỗng. Trong trường hợp này, nếu r không phải là 
bản ghi đầu tiên trong B, ta không phải làm gì thêm. Nếu r là bản ghi đầu tiên trong B, thì 
sau khi xoá r, chỉ số của B đã thay đổi. Do đó ta cần tìm đến đỉnh Q là cha của B. Nếu B 
là con trưởng của Q thì giá trị khoá v' trong chỉ số (v', p') của B không có trong Q. Trong 
trường hợp này ta cần tìm đến tiền thân A của B sao cho A không phải là con trưởng của 
cha mình A'. Khi đó giá trị khoá nhỏ nhất trong B được chứa trong A'. Do đó trong A', ta 
cần thay giá trị khoá cũ v bởi giá trị mới v'. 
 Giả sử sau khi loại bỏ bản ghi r, B trở thành rỗng. Loại bỏ lá B khỏi B - cây. 
Điều đó dẫn đến cần loại bỏ chỉ số của B trong đỉnh cha Q của B. 
 Nếu sau khi loại bỏ, số các con của đỉnh Q ít hơn m/2 thì ta tìm đến đỉnh Q' là 
anh em liền kề của đỉnh Q. Nếu Q' có nhiều hơn m/2 con thì ta phân phối lại các giá trị 
khoá trong Q và Q' sao cho cả hai có ít nhất m/2 con. Khi đó các chỉ số của Q hoặc 
Q' có thể thay đổi. Ta lại phải tìm đến các tiền thân của Q đến phản ánh sự thay đổi này. 
 Nếu Q' có đúng m/2 con, thì ta kết hợp hai đỉnh Q và Q' thành một đỉnh, một 
trong hai đỉnh bị loại khỏi cây, các khoá chứa trong đỉnh này được chuyển sang đỉnh còn 
lại. Điều này dẫn đến cần loại bỏ chỉ số của đỉnh bị loại ra khỏi cha của Q. Sự loại bỏ này 
được thực hiện bằng cách áp dụng thủ tục loại bỏ đã trình bày. 
 Quá trình loại bỏ có thể dẫn đến việc loại bỏ gốc cây, khi chúng ta cần kết hợp hai 
con của gốc thành một đỉnh, đỉnh này trở thành gốc mới của B-cây. 
 Ví dụ . Giả sử chúng ta cần loại bản ghi với khoá 58 khỏi B-cây trong hình 7.4. 
Đầu tiên tìm lá chứa khoá 58, đó là khối B8. Xoá bản ghi 58, khối B8 thành rỗng. Tìm đến 
cha của B8 là B13. Loại bỏ chỉ số của B8 khỏi B13, B13 chỉ còn một con. Số con của B13 ít 
hơn m/2 (ở đây m/2 = 3/2 = 2). Tìm đến em liền kề của B13 là B4, số con của 
B4 là hai. Kết hợp hai đỉnh này thành một đỉnh B13. Cần phải loại bỏ chỉ số của khối B4 
khỏi B14. B14 trở thành chỉ có một con. Tìm đến anh liền kề của B14 là B1. Số con của B1 là 
hai. Kết hợp B1 và B14 thành một đỉnh B1. B1 trở thành gốc mới của B - cây. Hình 7.5 
minh hoạ B-cây nhận được từ B-cây trong hình 7.4 sau khi loại đỉnh có khoá 58. 
195 211 232 
GT Cấu Trỳc Dữ Liệu – Thuật Toỏn PTS- Đinh Mạnh Tường 
Sưu Tầm Bởi : daihoc.com.vn 160