Giáo trình Giải thuật

Th.s. NGUYỄN VĂN LINH 
GIẢI THUẬT 
Được biên soạn trong khuôn khổ dự án ASVIET002CNTT 
”Tăng cường hiệu quả đào tạo và năng lực tự đào tạo của sinh viên 
khoa Công nghệ Thông tin - Đại học Cần thơ” 
ĐẠI HỌC CẦN THƠ - 12/2003 
LỜI NÓI ÐẦU 
N. Wirth, một nhà khoa học máy tính nổi tiếng, tác giả của ngôn 
ngữ lập trình Pascal, đã đặt tên cho một cuốn sách của ông là 
“Cấu trúc dữ liệu + Giải thuật = Chương trình”. 
Ðiều đó nói lên tầm quan trọng của giải thuật trong lập trình nói 
riêng và trong khoa học máy tính nói chung. Vì lẽ đó giải thuật, với tư 
cách là một môn học, cần phải được sinh viên chuyên ngành tin học 
nghiên cứu một cách có hệ thống. 
Môn học “Giải thuật” được bố trí sau môn “Cấu trúc dữ liệu” 
trong chương trình đào tạo kỹ sư tin học nhằm giới thiệu cho sinh viên 
những kiến thức cơ bản nhất, những kỹ thuật chủ yếu nhất của việc 
PHÂN TÍCH và THIẾT KẾ giải thuật. Các kỹ thuật được trình bày ở 
đây đã được các nhà khoa học tin học tổng kết và vận dụng trong cài đặt 
các chương trình. Việc nắm vững các kỹ thuật đó sẽ rất bổ ích cho sinh 
viên khi phải giải quyết một vấn đề thực tế. 
Giáo trình này được hình thành trên cơ sở tham khảo cuốn sách 
“Data Structure and Algorithms” của A.V Aho, những kinh nghiệm 
giảng dạy của bản thân và các bạn đồng nghiệp. 
Mặc dù đã có nhiều cố gắng trong quá trình biên soạn nhưng chắc 
chắn còn nhiều thiếu sót, rất mong nhận được sự đóng góp của quý bạn 
đọc. 
 Cần thơ, ngày 8 tháng 12 năm 2003 
 Nguyễn Văn Linh 
Giải thuật Mục lục 
MỤC LỤC 
................................................. i PHẦN TỔNG QUAN
.......................... 1 Chương 1: KĨ THUẬT PHÂN TÍCH GIẢI THUẬT
1.1 ................................................................................................................... 1 TỔNG QUAN
1.2 ....................................................... 2 SỰ CẦN THIẾT PHẢI PHÂN TÍCH GIẢI THUẬT
1.3 .............................................................. 2 THỜI GIAN THỰC HIỆN CỦA GIẢI THUẬT
1.4 .......................................... 3 TỶ SUẤT TĂNG VÀ ÐỘ PHỨC TẠP CỦA GIẢI THUẬT
1.5 .......................................................................................... 4 CÁCH TÍNH ÐỘ PHỨC TẠP
1.6 ............................................................. 7 PHÂN TÍCH CÁC CHƯƠNG TRÌNH ÐỆ QUY
1.7 ............................................................................................... 16 TỔNG KẾT CHƯƠNG 1
................................................................................................................. 16 BÀI TẬP CHƯƠNG 1
............................................. 18 Chương 2: SẮP XẾP
2.1 ................................................................................................................. 18 TỔNG QUAN
2.2 ..................................................................................................... 19 BÀI TOÁN SẮP XẾP
2.3 .............................................................. 20 CÁC PHƯƠNG PHÁP SẮP XẾP ÐƠN GIẢN
2.4 ................................................................................................................. 25 QUICKSORT
2.5 .................................................................................................................... 31 HEAPSORT
2.6 ....................................................................................................................... 39 BINSORT
2.7 ............................................................................................... 44 TỔNG KẾT CHƯƠNG 2
................................................................................................................. 44 BÀI TẬP CHƯƠNG 2
........................... 45 Chương 3: KĨ THUẬT THIẾT KẾ GIẢI THUẬT
3.1 ................................................................................................................. 45 TỔNG QUAN
3.2 ............................................................................................. 45 KĨ THUẬT CHIA ÐỂ TRỊ
3.3 ............................................................................................... 50 KĨ THUẬT “THAM ĂN”
3.4 .................................................................................................... 56 QUY HOẠCH ÐỘNG
3.5 ................................................................................................. 63 KĨ THUẬT QUAY LUI
3.6 ........................................................................ 78 KĨ THUẬT TÌM KIẾM ÐỊA PHƯƠNG
3.7 ............................................................................................... 82 TỔNG KẾT CHƯƠNG 3
................................................................................................................. 82 BÀI TẬP CHƯƠNG 3
......... 85 Chương 4: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT LƯU TRỮ NGOÀI
4.1 ................................................................................................................. 85 TỔNG QUAN
4.2 ............................................................................................ 85 MÔ HÌNH XỬ LÝ NGOÀI
4.3 ......................................................... 86 ÐÁNH GIÁ CÁC GIẢI THUẬT XỬ LÝ NGOÀI
4.4 ........................................................................................................... 87 SẮP XẾP NGOÀI
4.5 ................................................................. 93 LƯU TRỮ THÔNG TIN TRONG TẬP TIN
4.6 ............................................................................................. 103 TỔNG KẾT CHƯƠNG 4
............................................................................................................... 104 BÀI TẬP CHƯƠNG 4
Giải thuật Tổng quan 
PHẦN TỔNG QUAN 
1. Mục đích yêu cầu 
 Môn học giải thuật cung cấp cho sinh viên một khối lượng kiến thức tương đối 
hoàn chỉnh về phân tích và thiết kế các giải thuật lập trình cho máy tính. Sau khi 
học xong môn học này, sinh viên cần: 
- Nắm được khái niệm thời gian thực hiện của chương trình, độ phức tạp của 
giải thuật. Biết cách phân tích, đánh giá giải thuật thông qua việc tính độ 
phức tạp. 
- Nắm được các giải thuật sắp xếp và phân tích đánh giá được các giải thuật 
sắp xếp. 
- Nắm được các kĩ thuật thiết kế giải thuật, vận dụng vào việc giải một số bài 
toán thực tế. 
- Nắm được các phương pháp tổ chức lưu trữ thông tin trong tập tin và các giải 
thuật tìm, xen, xoá thông tin trong tập tin. 
2. Đối tượng sử dụng 
Môn học giải thuật được dùng để giảng dạy cho các sinh viên sau: 
- Sinh viên năm thứ 3 chuyên ngành Tin học. 
- Sinh viên năm thứ 3 chuyên ngành Điện tử (Viễn thông, Tự động hoá) 
- Sinh viên Toán-Tin. 
3. Nội dung cốt lõi 
Trong khuôn khổ 45 tiết, giáo trình được cấu trúc thành 4 chương 
- Chương 1: Kĩ thuật phân tích đánh giá giải thuật. Chương này đặt vấn đề tại 
sao cần phải phân tích, đánh giá giải thuật và phân tích đánh giá theo phương 
pháp nào. Nội dung chương 1 tập trung vào khái niệm độ phức tạp thời gian 
của giải thuật và phương pháp tính độ phức tạp giải thuật của một chương 
trình bình thường, của chương trình có gọi các chương trình con và của các 
chương trình đệ quy. 
- Chương 2: Sắp xếp. Chương này trình bày các giải thuật sắp xếp, một thao 
tác thường được sử dụng trong việc giải các bài toán máy tính. Sẽ có nhiều 
giải thuật sắp xếp từ đơn giản đến nâng cao sẽ được giới thiệu ở đây. Với 
mỗi giải thuật, sẽ trình bày ý tưởng giải thuật, ví dụ minh hoạ, cài đặt chương 
trình và phân tích đánh giá. 
- Chương 3: Kĩ thuật thiết kế giải thuật. Chương này trình bày các kĩ thuật 
phổ biến để thiết kế các giải thuật. Các kĩ thuật này gồm: Chia để trị, Quy 
hoạch động, Tham ăn, Quay lui và Tìm kiếm địa phương. Với mỗi kĩ thuật sẽ 
trình bày nội dung kĩ thuật và vận dung vào giải các bài toán khá nổi tiếng 
như bài toán người giao hàng, bài toán cái ba lô, bài toán cây phủ tối thiểu... 
- Chương 4: Cấu trúc dữ liệu và giải thuật lưu trữ ngoài. Chương này trình 
bày các cấu trúc dữ liệu được dùng để tổ chức lưu trữ tập tin trên bộ nhớ 
ngoài và các giải thuật tìm kiếm, xen xoá thông tin trên các tập tin đó. 
4. Kiến thức tiên quyết 
Để học tốt môn học giải thuật cần phải có các kiến thức sau: 
- Kiến thức toán học. 
- Kiến thức và kĩ năng lập trình căn bản. 
Giải thuật Tổng quan 
- Kiến thức về cấu trúc dữ liệu và các giải thuật thao tác trên các cấu trúc dữ 
liệu. 
Trong chương trình đào tạo, Cấu trúc dữ liệu là môn học tiên quyết của môn Giải 
thuật. 
5. Danh mục tài liệu tham khảo 
[1] A.V. Aho, J.E. Hopcroft, J.D. Ullman; Data Structures and Algorithms; 
Addison-Wesley; 1983. 
[2] Jeffrey H Kingston; Algorithms and Data Structures; Addison-Wesley; 
1998. 
[3] Đinh Mạnh Tường; Cấu trúc dữ liệu & Thuật toán; Nhà xuất bản khoa học 
và kĩ thuật; Hà nội-2001. 
[4] Đỗ Xuân Lôi; Cấu trúc dữ liệu & Giải thuật; 1995. 
[5] Nguyễn Đức Nghĩa, Tô Văn Thành; Toán rời rạc; 1997. 
[6] Trang web phân tích giải thuật: 
[7] Trang web bài giảng về giải thuật: 
[8] Trang tìm kiếm các giải thuật: 
Giải thuật Kĩ thuật phân tích giải thuật 
CHƯƠNG 1: KĨ THUẬT PHÂN TÍCH GIẢI THUẬT 
1.1 TỔNG QUAN 
1.1.1 Mục tiêu 
Sau khi học chương này, sinh viên cần phải trả lời được các câu hỏi sau: 
- Tại sao cần phân tích đánh giá giải thuật? 
- Tiêu chuẩn nào để đánh giá một giải thuật là tốt? 
- Phương pháp đánh giá như thế nào? (đánh giá chương trình không gọi 
chương trình con, đánh giá một chương trình có gọi các chương trình con 
không đệ quy và đánh giá chương trình đệ quy). 
1.1.2 Kiến thức cơ bản cần thiết 
Các kiến thức cơ bản cần thiết để học chương này bao gồm: 
- Kiến thức toán học: Công thức tính tổng n số tự nhiên đầu tiên, công thức 
tính tổng n số hạng đầu tiên của một cấp số nhân, phương pháp chứng minh 
quy nạp và các kiến thức liên quan đến logarit (biến đổi logarit, tính chất 
đồng biến của hàm số logarit). 
- Kĩ thuật lập trình và lập trình đệ quy. 
1.1.3 Tài liệu tham khảo 
A.V. Aho, J.E. Hopcroft, J.D. Ullman. Data Structures and Algorithms. Addison-
Wesley. 1983. (Chapters 1, 9). 
Jeffrey H Kingston; Algorithms and Data Structures; Addison-Wesley; 1998. 
(Chapter 2). 
Đinh Mạnh Tường. Cấu trúc dữ liệu & Thuật toán. Nhà xuất bản khoa học và kĩ 
thuật. Hà nội-2001. (Chương 1). 
Trang web phân tích giải thuật: 
1.1.4 Nội dung cốt lõi 
Trong chương này chúng ta sẽ nghiên cứu các vấn đề sau: 
• Sự cần thiết phải phân tích các giải thuật. 
• Thời gian thực hiện của chương trình. 
• Tỷ suất tăng và độ phức tạp của giải thuật. 
• Tính thời gian thực hiện của chương trình. 
• Phân tích các chương trình đệ quy. 
Nguyễn Văn Linh Trang 1 
Giải thuật Kĩ thuật phân tích giải thuật 
1.2 SỰ CẦN THIẾT PHẢI PHÂN TÍCH GIẢI THUẬT 
Trong khi giải một bài toán chúng ta có thể có một số giải thuật khác nhau, vấn đề 
là cần phải đánh giá các giải thuật đó để lựa chọn một giải thuật tốt (nhất). Thông 
thường thì ta sẽ căn cứ vào các tiêu chuẩn sau: 
 1.- Giải thuật đúng đắn. 
 2.- Giải thuật đơn giản. 
 3.- Giải thuật thực hiện nhanh. 
Với yêu cầu (1), để kiểm tra tính đúng đắn của giải thuật chúng ta có thể cài đặt giả ... ộ nhớ 
ngoài. Mỗi một nút biểu diễn cho một khối vật lý trong bộ nhớ ngoài. Trong đó các 
nút lá lưu trữ các mẩu tin của tập tin. Các nút trong lưu trữ m con trỏ, trỏ tới m nút 
con. 
Nếu ta dùng cây tìm kiếm nhị phân n nút để lưu trữ một tập tin thì cần trung bình 
logn phép truy xuất khối để tìm kiếm một mẩu tin. Nếu ta dùng cây tìm kiếm m-
phân để lưu trữ một tập tin thì chỉ cần logmn phép truy xuất khối để tìm kiếm một 
mẩu tin. Sau đây chúng ta sẽ nghiên cứu một trường hợp đặc biệt của cây tìm kiếm 
m-phân là B-cây. 
4.5.5.2 B-cây (B-tree) 
B-cây bậc m là cây tìm kiếm m-phân cân bằng có các tính chất sau: 
• Nút gốc hoặc là lá hoặc có ít nhất hai nút con, 
• Mỗi nút, trừ nút gốc và nút lá, có từ ⎡m/2⎤ đến m nút con và 
• Các đường đi từ gốc tới lá có cùng độ dài. 
Nguyễn Văn Linh Trang 98 
Giải thuật CTDL và giải thuật lưu trữ ngoài 
Tổ chức: Ta có thể sử dụng B-cây bậc m để lưu trữ tập tin như sau: 
Mỗi nút trên cây là một khối trên đĩa, các mẩu tin của tập tin được lưu trữ trong các 
nút lá trên B-cây và lưu theo thứ tự của khoá. Giả sử mỗi nút lá lưu trữ được nhiều 
nhất b mẩu tin. 
Mỗi nút không phải là nút lá có dạng (p0,k1,p1,k2,p2,...,kn,pn), với pi (0 ≤ i ≤ n) là con 
trỏ, trỏ tới nút con thứ i của nút đó và ki là các giá trị khóa. Các khoá trong một nút 
được sắp thứ tự, tức là k1 < k2 < ... < kn. 
Tất cả các khoá trong cây con được trỏ bởi p0 đều nhỏ hơn k1. Tất cả các khoá nằm 
trong cây con được trỏ bởi pi (0 < i < n) đều lớn hơn hoặc bằng ki và nhỏ hơn ki+1. 
Tất cả các khoá nằm trong cây con được trỏ bởi pn đều lớn hơn hoặc bằng kn. 
Ví dụ 4-8: Cho tập tin bao gồm 20 mẩu tin với giá trị khóa là các số nguyên được tổ 
chức thành B-cây bậc 5 với các nút lá chứa được nhiều nhất 3 mẩu tin. 
 GỐC 
 18 • • • 
 P P1 2
 10 12 • • 22 28 34 38 
 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42
L L L L L L L L1 2 3 4 5 6 7 8
Hình 4-5: Tập tin B-cây bậc 5 
4.5.5.3 Tìm kiếm 
Ðể tìm kiếm một mẩu tin r có khoá là x chúng ta sẽ lần từ nút gốc đến nút lá chứa r 
(nếu r tồn tại trong tập tin). Tại mỗi bước ta đưa nút trong (p0, k1, p1, ..., kn, pn) vào 
bộ nhớ trong và xác định mối quan hệ giữa x với các giá trị khóa ki. 
• Nếu ki ≤ x < k (0 < i < n) chúng ta sẽ xét tiếp nút được trỏ bởi pi+1 i, 
• Nếu x < k1 ta sẽ xét tiếp nút được trỏ bởi p0 và 
• Nếu x ≥ kn ta sẽ xét tiếp nút được trỏ bởi pn. 
Quá trình trên sẽ dẫn đến việc xét một nút lá. Trong nút lá này ta sẽ tìm mẩu tin r 
với khóa x bằng tìm kiếm tuần tự hoặc tìm kiếm nhị phân. 
4.5.5.4 Thêm mẩu tin 
Ðể thêm một mẩu tin r có khoá là x vào trong B-cây, trước hết ta áp dụng thủ tục 
tìm kiếm nói trên để tìm r. Việc tìm kiếm này sẽ dẫn đến nút lá L. Nếu tìm thấy thì 
thông báo “Mẩu tin đã tồn tại”, ngược lại thì L là nút lá mà ta có thể xen r vào trong 
đó. Nếu khối L này còn đủ chỗ cho r thì ta thêm r vào sao cho đúng thứ tự của nó 
trong khối L và giải thuật kết thúc. Nếu L không còn chỗ cho r thì ta yêu cầu hệ 
thống cấp phát một khối mới L'. Dời ⎡b/2⎤ (b là số mẩu tin nhiều nhất có thể lưu 
Nguyễn Văn Linh Trang 99 
Giải thuật CTDL và giải thuật lưu trữ ngoài 
trong một khối) mẩu tin nằm ở phân nửa cuối khối L sang L' rồi xen r vào L hoặc 
L' sao cho việc xen đảm bảo thứ tự các khoá trong khối. Giả sử nút P là cha của L 
(P phải được biết vì thủ tục tìm đi từ gốc đến L phải thông qua P). Bây giờ ta áp 
dụng thủ tục xen đệ quy để xen vào P một khóa k’ và con trỏ p’ tương ứng của nút 
lá L’ (k’ là khoá của mẩu tin đầu tiên trong L'). Trong trường hợp trước khi xen k' 
và p’, P đã có đủ m con thì ta phải cấp thêm một khối mới P’ và chuyển một số con 
của P sang P’ và xen con mới vào P hoặc P’ sao cho cả P và P’ đều có ít nhất ⎡m/2⎤ 
con. Việc chia cắt P này đòi hỏi phải xen một khóa và một con trỏ vào nút cha của 
P... Quá trình này có thể sẽ dẫn tới nút gốc và cũng có thể phải chia cắt nút gốc, 
trong trường hợp này phải tạo ra một nút gốc mới mà hai con của nó là hai nửa của 
nút gốc cũ. Khi đó chiều cao của B-cây sẽ tăng lên 1. 
Ví dụ 4-9: Thêm mẩu tin r có khoá 19 vào tập tin được biểu diễn bởi B-cây trong ví 
dụ 4-8 (hình 4-5) 
• Quá trình tìm kiếm sẽ xuất phát từ GỐC đi qua P2 và dẫn tới nút lá L4 
• Trong nút lá L4 còn đủ chỗ để xen r vào đúng vị trí và giải thuật kết thúc.
Kết quả việc xen ta được B-cây trong hình 4-6: 
 GỐC 
 18 • • • 
 P P1 2
 10 12 • • 22 28 34 38 
 4 6 8 10 12 14 16 18 19 20 22 24 26 28 30 32 34 36 38 40 42
L L L L L L L L1 2 3 4 5 6 7 8
Hình 4-6: Xen thêm mẩu tin r có khoá 19 vào trong B-cây hình 4-5 
Ví dụ 4-10: Thêm mẩu tin r có khoá 23 vào trong tập tin biêu diễn bởi B-cây trong 
ví dụ 4-8 (hình 4-5) 
• Quá trình tìm kiếm đi từ nút GỐC, qua P2 và tới nút lá L5. 
• Vì L5 đã đủ 3 mẩu tin nên phải tạo ra một nút lá mới L’5 và chuyển 2 mẩu 
tin có khóa 24, 26 sang L’5 sau đó xen r vào L5. 
• Giá trị khóa của mẩu tin đầu tiên trong L’5 là 24, ta phải xen 24 và con trỏ 
của L’5 vào P2, nhưng P2 đã có đủ 5 con, vậy cần tạo ra một nút mới P’2, 
chuyển các cặp khóa, con trỏ tương ứng với 34 và 38 sang P’2 và xen cặp 
con trỏ, khóa 24 vào P2. 
• Do có một nút mới P’2 nên phải xen vào cha của P2 (Ở đây là nút GỐC) 
một cặp khóa, con trỏ trỏ tới P’2. Con trỏ p0 của nút P’2 trỏ tới nút lá L6, 
Nguyễn Văn Linh Trang 100 
Giải thuật CTDL và giải thuật lưu trữ ngoài 
giá trị khóa đầu tiên của L6 là 28. Giá trị này phải được xen vào nút GỐC 
cùng với con trỏ của P’2. 
GỐC 
 18 28 • • 
 P1 P2 P’2
 10 12 22 24 34 38 • • • • • •
 4 6 8 10 12 14 16 18 20 22 23 24 26 28 30 32 34 36 38 40 42
L L L L L L’ L L L1 2 3 4 5 5 6 7 8
Hình 4-7: Xen thêm mẩu tin r có khoá 23 vào trong B-cây hình 4-5 
4.5.5.5 Xóa một mẩu tin 
Ðể xóa mẩu tin r có khóa x, trước hết ta tìm mẩu tin r. Nếu không tìm thấy thì thông 
báo « Mẩu tin không tồn tại », ngược lại ta sẽ xác đinh được mẩu tin r nằm trong 
nút lá L và xóa r khỏi L. Nếu r là mẩu tin đầu tiên của L, thì ta phải quay lui lên nút 
P là cha của L để đặt lại giá trị khóa của L trong P, giá trị mới này bằng giá trị khóa 
của mẩu tin mới đầu tiên của L. Trong trường hợp L là con đầu tiên của P, thì khóa 
của L không nằm trong P mà nằm trong tổ tiên của P, chúng ta phải quay lui lên mà 
sửa đổi. 
Nếu sau khi xóa mẩu tin r mà L trở nên rỗng thì giải phóng L và quay lui lên nút P 
là cha của L để xoá cặp khoá-con trỏ của L trong P. Nếu số con của P bây giờ (sau 
khi xoá khoa-con trỏ của L) nhỏ hơn ⎡m/2⎤ thì kiểm tra nút P’ ngay bên trái hoặc 
bên phải và cùng mức với P. Nếu P’ có ít nhất ⎡m/2⎤+1 con, chúng ta chuyển một 
con của P’ sang P. Lúc này cả P và P’ có ít nhất ⎡m/2⎤. Sau đó ta phải cập nhật lại 
giá trị khóa của P hoặc P’ trong cha của chúng, và nếu cần chúng ta phải sửa cả 
trong tổ tiên của chúng. 
Nếu P’ có đúng ⎡m/2⎤ con, ta nối P và P’ thành một nút có đúng m con. Sau đó ta 
phải xóa khóa và con trỏ của P’ trong nút cha của P’. Việc xóa này có thể phải quay 
lui lên tổ tiên của P’. Kết quả của quá trình xóa đệ quy này có thể dẫn tới việc nối 
hai con của nút gốc, tạo nên một gốc mới và giải phóng nút gốc cũ, độ cao của cây 
khi đó sẽ giảm đi 1. 
Ví dụ 4-11: Xóa mẩu tin r có khóa 38 trong tập tin biểu diễn bởi B-cây kết quả của 
ví dụ 4-10 (hình 4-7). 
• Quá trình tìm kiếm, xuất phát từ nút GỐC, đi qua P’2 và đến nút lá L , 8
• Xóa mẩu tin r khỏi L8. 
• Mẩu tin đầu tiên của L8 bây giờ có khóa 40, 
Nguyễn Văn Linh Trang 101 
Giải thuật CTDL và giải thuật lưu trữ ngoài 
• Sửa lại giá trị khóa của L8 trong P’2 (thay 38 bởi 40) ta được kết quả là 
B-cây sau: 
GỐC 
 18 28 • • 
 P1 P2 P’2
 10 12 22 24 34 40 • • • • • •
4 6 8 10 12 14 16 18 20 22 23 24 26 28 30 32 34 36 40 42 
L1 L2 L3 L4 L5 L’5 L6 L7 L8
Hình 4-8: Xoá mẩu tin r có khoá 38 vào trong B-cây hình 4-7 
Ví dụ 4-12 : Xoá mẩu tin r có khoá 10 trong tập tin biểu diễn bởi B-cây trong ví dụ 
4-8 (hình 4-5). 
• Quá trình tìm kiếm, xuất phát từ nút GỐC, đi qua P1 và đến nút lá L2. 
• Xóa mẩu tin r khỏi L2. 
• L2 bây giờ trở nên rỗng, giải phóng L2. 
• Xóa giá trị khóa 10 và con trỏ của L2 trong P1, P1 bây giờ chỉ có 2 con 
(Thiếu con do 2 < ⎡5/2⎤). 
• Xét nút P2, bên phải và cùng cấp với P1, P2 có 5 con nên ta chuyển một 
con từ P2 sang P1. 
• Cập nhật lại khoá của P2 trong nút GỐC, ta được B-cây kết quả như sau: 
 GỐC 
 22 • • • 
 P1 P2
 12 18 28 34 38 • • •
 4 6 8 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 
L L L L L L L1 3 4 5 6 7 8
Hình 4-9: Xoá mẩu tin có khoá 10 trong B-cây hình 4-5 
Ví dụ 4-13: Xóa mẩu tin r có khóa 10 trong tập tin biểu diễn bởi B-cây kết quả của 
ví dụ 4-10 (hình 4-7). 
Nguyễn Văn Linh Trang 102 
Giải thuật CTDL và giải thuật lưu trữ ngoài 
• Quá trình tìm kiếm, xuất phát từ nút GỐC, đi qua P1 và lần đến nút lá L2. 
• Xóa mẩu tin r khỏi L2. 
• L2 bây giờ trở nên rỗng, giải phóng L2. 
• Xóa giá trị khóa 10 và con trỏ của L2 trong P1, P1 bây giờ chỉ có 2 con 
(Thiếu con do 2 < ⎡5/2⎤). 
• Xét nút P2, bên phải và cùng cấp với P1, P2 có đúng ⎡5/2⎤ = 3 con nên ta 
nối P1 và P2 để P1 có đúng 5 con, giải phóng P2. 
• Xóa khóa và con trỏ của P2 trong nút GỐC, ta được B-cây kết quả như 
sau: 
GỐC 
 28 • • • 
 P1 P2 
 12 18 22 24 34 38 • • 
4 6 8 12 14 16 18 20 22 23 24 26 28 30 32 34 36 38 40 42
L L L L L’ L L L1 3 4 5 5 6 7 8
Hình 4-10: Xoá mẩu tin r có khoá 10 trong B-cây hình 4-7 
4.6 TỔNG KẾT CHƯƠNG 4 
Để đánh giá các giải thuật xử lí ngoài, cần phải xác định số phép truy xuất khối (đọc 
và ghi khối) mà giải thuật đó thực hiện. Theo đó, một giải thuật được xem là tốt nếu 
số lượng phép truy xuất khối nhỏ và để cái tiến giải thuật, ta cần tìm cách giảm số 
phép truy xuất khối. Các giải thuật sắp xếp trộn minh hoạ khá rõ ràng cho việc cải 
tiến giải thuật xử lí ngoài. 
Đối với việc tổ chức lưu trữ thông tin trong tập tin, chúng ta cần chú ý đến các loại 
tập tin bảng băm và tập tin B-cây, đây là hai loại tập tin rất hiệu quả. 
Nguyễn Văn Linh Trang 103 
Giải thuật CTDL và giải thuật lưu trữ ngoài 
BÀI TẬP CHƯƠNG 4 
Bài 1: Cho tập tin bao gồm các mẩu tin với giá trị khóa là các số nguyên được tổ 
chức thành B-cây bậc 5 với các nút lá chứa được nhiều nhất 3 mẩu tin như sau. 
 GỐC 
 14 • • •
 P1 P2 
 8 12 19 27 35 • • 40 
5 7 8 9 10 12 14 16 17 19 22 27 28 35 36 38 40 42 
L1 L2 L3 L4 L5 L6 L7 L8 
a) Xen mẩu tin R có giá trị khóa là 37 vào tập tin được biểu diễn bởi B-cây nói 
trên. 
b) Xóa mẩu tin R có giá trị khóa là 12 của tập tin được biểu diễn bởi B-cây nói 
trên. 
c) Xóa mẩu tin R có giá trị khóa là 12 của tập tin được biểu diễn bởi B-cây là kết 
quả của câu a). 
Bài 2: Giả sử ta dùng B-cây bậc 3 với các nút lá chứa được nhiều nhất 2 mẩu tin để 
tổ chức tập tin. Khởi đầu tập tin rỗng, hãy mô tả quá trình hình thành tập tin B-cây 
(bằng hình vẽ) khi thực hiện tuần tự các thao tác sau: 
1. Xen mẩu tin R có khóa 8 
2. Xen mẩu tin R có khóa 2 
3. Xen mẩu tin R có khóa 10 
4. Xen mẩu tin R có khóa 1 
5. Xen mẩu tin R có khóa 12 
6. Xen mẩu tin R có khóa 3 
7. Xen mẩu tin R có khóa 5 
8. Xóa mẩu tin R có khóa 8 
9. Xóa mẩu tin R có khóa 1 
Nguyễn Văn Linh Trang 104