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

CẤU TR TRƯỜNG ĐẠI HỌC ĐÀ LẠT 
F 7 G 
GIÁO TRÌNH 
ÚC DỮ LIỆU VÀ THUẬT
TỐN 2 
Trương Chí Tín 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 2 – 
MỤC LỤC 
MỤC LỤC........................................................................................................................................2 
LỜI NÓI ĐẦU .................................................................................................................................5 
CHƯƠNG I.......................................................................................................................................7 
I/. GIỚI THIỆU TẬP TIN ...........................................................................................................7 
I.1. Định nghĩa tập tin (file) .....................................................................................................7 
I.2. Các thao tác sơ cấp trên tập tin trong C++ .......................................................................7 
A/. Các phương thức dùng chung cho cả hai kiểu tập tin văn bản và nhị phân.................7 
1) Mở tập tin.........................................................................................................................8 
2) Đóng tập tin. ....................................................................................................................9 
3) Kiểm tra cuối tập tin........................................................................................................9 
4) Kiểm tra trạng thái đọc, ghi dữ liệu: ..............................................................................9 
B/. Các phương thức dùng cho tập tin kiểu văn bản...........................................................9 
1/ Đọc 1 chuỗi ký tự: ...........................................................................................................9 
2/ Ghi 1 chuỗi ký tự: ............................................................................................................9 
3/ Ghi 1 ký tự. ....................................................................................................................10 
4) Đọc 1 ký tự. ...................................................................................................................10 
C/. Các phương thức dùng cho tập tin kiểu nhị phân........................................................10 
1/ Ghi một số bytes: ...........................................................................................................10 
2/ Đọc một số bytes: ..........................................................................................................10 
3/ Chuyển con trỏ định vị việc ghi trong file: ...................................................................10 
4/ Chuyển con trỏ định vị việc đọc trong file: ..................................................................11 
I.3. Tổ chức tập tin .............................................................................................................11 
II. CÁC THAO TÁC CƠ BẢN TRÊN FILE.............................................................................13 
II.1. Tập tin tuần tự ................................................................................................................13 
II.2. Tập tin chỉ mục...............................................................................................................16 
III. SẮP XẾP TRÊN FILE.........................................................................................................23 
III.1. Trộn trực tiếp (Straight Merge) ....................................................................................23 
III.2. Trộn tự nhiên (Natural Merge).....................................................................................27 
III.3. Trộn nhiều đường cân bằng (Balanced Multiway Merge) ...........................................29 
CHƯƠNG II: CẤU TRÚC CÂY ...................................................................................................31 
I. ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM CƠ BẢN..................................................................31 
I.1. Định nghĩa cây.................................................................................................................31 
I.2. Các khái niệm khác.........................................................................................................31 
II. CÂY NHỊ PHÂN...................................................................................................................33 
II.1. Định nghĩa: cây nhị phân là cây (có thứ tự) mà số lớn nhất các nút con của các nút là 
2. .............................................................................................................................................33 
II.2. Vài tính chất của cây nhị phân ......................................................................................33 
II.3. Biểu diễn cây nhị phân ..................................................................................................34 
II.4. Duyệt cây nhị phân ........................................................................................................35 
II.4.1. Định nghĩa: ..............................................................................................................35 
II.4.2. Các thuật toán duyệt cây nhị phân.........................................................................35 
II.4.3. Cài đặt thuật toán duyệt qua cây nhị phân LNR ...................................................36 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 3 – 
II.5. Một cách biểu diễn khác của cây nhị phân ..................................................................38 
II.7. Xây dựng cây nhị phân cân bằng hoàn toàn.................................................................39 
II.7.1. Định nghĩa: ..............................................................................................................39 
II.7.2. Xây dựng cây nhị phân cân bằng hoàn toàn..........................................................39 
III.CÂY NHỊ PHÂN TÌM KIẾM (BST)....................................................................................40 
III.1. Định nghĩa cây nhị phân tìm kiếm (BST) ....................................................................40 
III.2. Tìm kiếm một phần tử trên cây BST ...........................................................................41 
III.2.1. Thuật toán tìm kiếm dạng đệ qui: .........................................................................41 
III.2.2. Thuật toán tìm kiếm dạng lặp: ..............................................................................41 
III.3. Chèn một phần tử vào cây BST, xây dựng cây BST...................................................42 
III.3.1. Thao tác chèn một nút Item vào cây BST (dạng lặp): ........................................43 
III.3.2. Thủ tục chèn một nút Item vào cây BST (dạng đệ qui):.....................................43 
III.3.3. Xây dựng cây BST.................................................................................................44 
III.4. Phương pháp sắp xếp bằng cây BST............................................................................44 
III.5. Xóa một phần tử khỏi cây BST, hủy cây nhị phân .....................................................45 
IV. CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG .......................................................................48 
IV.1. Định nghĩa.....................................................................................................................48 
IV.2. Chiều cao của cây cân bằng ........................................................................................49 
IV.3. Chỉ số cân bằng và việc cân bằng lại cây AVL..........................................................50 
IV.4. Chèn một phần tử vào cây AVL..................................................................................56 
IV.5. Xóa một phần tử khỏi cây AVL...................................................................................57 
CHƯƠNG III: B - CÂY .................................................................................................................60 
I. ĐẶC ĐIỂM CÂY NHIỀU NHÁNH......................................................................................60 
II. ĐỊNH NGHĨA B – CÂY (bậc n)...........................................................................................61 
III. TÌM KIẾM MỘT PHẦN TỬ TRÊN B - CÂY....................................................................61 
IV. THÊM MỘT PHẦN TỬ VÀO B - CÂY ...........................................................................63 
Quá trình tìm kiếm và thêm một phần tử vào trên B - cây......................................................64 
IV.1. Giải thuật tìm và thêm một phần tử vào B - cây........................................................64 
IV.2. Giải thuật xây dựng B - cây .........................................................................................65 
V. XÓA MỘT PHẦN TỬ KHỎI B - CÂY ...............................................................................67 
V.1. Hai tình huống loại bỏ một khóa trên B-cây .............................................................67 
V.2. Giải thuật loại bỏ một khóa trên B-cây .....................................................................68 
CHƯƠNG IV: BẢNG BĂM..........................................................................................................72 
I.ĐẠT VẤN ĐỀ, MỤC ĐÍCH, Ý NGHĨA................................................................................72 
II. PHƯƠNG PHÁP BIẾN ĐỔI KHÓA....................................................................................72 
H : K → A ....................................................................................................................................72 
III. HÀM BIẾN ĐỔI KHÓA (hàm băm) ..................................................................................73 
H[k] = k mod M....................................................................................................................73 
IV. GIẢI QUYẾT SỰ ĐỤNG ĐỘ.............................................................................................75 
IV.1. Phương pháp băm liên kết............................................................................................75 
IV.1.1. Phương pháp băm liên kết trực tiếp......................................................................75 
IV.1.2. Phương pháp băm liên kết kết hợp .......................................................................77 
IV.2. Băm theo phương pháp địa chỉ mở ..............................................................................78 
IV.2.1. Phương pháp băm (thử) tuyến tính........................................................................79 
IV.2.2. Phương pháp băm (thử) bậc hai ...........................................................................80
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 4 – 
IV.2.3. Phương pháp băm kép ...........................................................................................81 
BÀI TẬP “CẤU TRÚC DỮ LIỆU & THUẬT TOÁN 2” ............................................................85 
Bài tập chương 1 (File) ..............................................................................................................85 
Bài tập chương 2 (Cấu trúc cây) ...............................................................................................88 
Bài tập chương 3 (B - cây).........................................................................................................91 
Bài tập chương 4 (Bảng băm)....................................................................................................91 
TÀI LIỆU THAM KHẢO .............................................................................................................93 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 5 – 
LỜI NÓI ĐẦU 
 Giáo trình này nhằm cung cấp cho sinh viên các kiến thức nâng cao về cấu trúc 
dữ liệu và các thuật toán có liên quan. Để có thể nắm bắt các kiến thức trình bày 
trong giáo trình, sinh viên cần nắm được các kiến thức về tin học đại cương, kỹ thuật 
lập trình, nhập môn cấu trúc dữ liệu và thuật toán. Các kiến thức này sẽ tạo điều kiện 
cho sinh viên học tiếp các kiến thức về kỹ thuật lập trình nâng cao, đồ họa, lập trình hệ 
thống, trí tuệ nhân tạo, ... 
 Nội dung giáo trình gồm 4 chương: 
 - Chương 1: Giới thiệu các thao tác cơ bản về file trong C++, cũng như về các kiểu 
file tuần tự và chỉ mục. 
 - Chương 2: Giới thiệu một loại cấu trúc dữ liệu động khác là cây và các thao tác 
cơ bản trên cây nhị phân, cây nhiều nhánh và đặc biệt là cây nhị phân tìm kiếm, cây 
AVL. 
 - Chương 3: Trình bày một loại cây nhiều nhánh đặc biệt là B – cây. Nó có nhiều 
ứng dụng trong việc lưu trữ và tìm kiếm trên các bộ dữ liệu lớn. 
 - Chương 4: Giới thiệu các phương pháp tìm kiếm hiệu quả trên các bộ dữ liệu lớn 
dựa vào bảng băm: phương pháp băm liên kết, băm theo địa chỉ mở. 
 Chắn chắn rằng trong giáo trình sẽ còn nhiều khiếm khuyết, tác giả mong muốn 
nhận được và rất biết ơn các ý kiến quí báu đóng góp của đồng nghiệp cũng như bạn 
đọc để giáo trình này có thể hoàn thiện hơn nữa về mặt nội dung cũng như hình thức 
trong lần tái bản sau. 
 Đà lạt, 06/2002 
 Tác giả 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 6 – 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 7 – 
CHƯƠNG I 
I/. GIỚI THIỆU TẬP TIN 
 I.1. Định nghĩa tập tin (file) 
Tập tin là tập các thông tin về các đối tượng nào đó có quan hệ với 
nhau, được lưu giữ thành một đơn vị trên bộ nhớ ngoài. 
 Trên thực tế, ta thường cần dùng đến tập tin để lưu lâu dài thông tin 
với số lượng lớn. Các phương pháp sắp xếp và tìm kiếm được giới thiệu 
trong giáo trình “Cấu trúc dữ liệu và thuật toán 1” được áp dụng khi lượng 
dữ liệu không lớn lắm được lưu giữ ở bộ nhớ trong. 
I.2. Các thao tác sơ cấp trên tập tin trong C++ 
Ta xét hai kiểu tập tin trong ngôn ngữ C++: tập tin nhị phân và tập 
tin văn bản. 
 - Tập tin nhị phân: dữ liệu ghi trên tập tin theo các bytes nhị phân 
giống như khi chúng được lưu trữ trong bộ nhớ và chúng không bị biến đổi 
trong quá trình nhập xuất. Khi đọc đến  ... file khác có cùng cấu trúc (sao 
chép file) hoặc được tạo tự động một cách ngẫu nhiên khi số lượng các các mẫu tin 
cần nhập khá lớn. 
c. Khai thác file theo một tiêu chuẩn nào đó mà không thay đổi file nguồn, chẳng 
hạn: 
- Tìm mẫu tin đầu tiên (bắt đầu từ mẫu tin tại vị trí xác định) thỏa một tính chất 
nào đó. Trong trường hợp tìm thấy, hãy trả về số thứ tự của mẫu tin vừa tìm 
thấy trong file. 
- Tìm và xuất các mẫu tin trên file thỏa một tính chất nào đó trong hai trường 
hợp: 
. tính chất chỉ phụ thuộc vào một thuộc tính của mẫu tin (ví dụ: mẫu tin có 
trường HọTên trùng với một chuỗi ký tự cho trước) 
. tính chất phụ thuộc vào nhiều thuộc tính của mẫu tin (ví dụ: mẫu tin có: trường 
HọTên trùng với một chuỗi ký tự cho trước và có điểm trung bình lớn hơn 5.0) 
d. Cập nhật các mẫu tin của file nguồn (và có thể làm thay đổi file nguồn, có thể sử 
dụng hoặc không sử dụng các file phụ), chẳng hạn: 
- Sửa mọi mẫu tin trong file nguồn thỏa một tính chất nào đó 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 86 – 
- Thay thế mọi mẫu tin trong file nguồn thỏa một tính chất nào đó bởi một mẫu 
tin khác. 
- Chèn một mẫu tin mới vào sau mẫu tin đầu tiên trong file nguồn thỏa một tính 
chất nào đó. 
- Xoá mẫu tin đầu tiên trong file nguồn thỏa một tính chất nào đó 
- Xoá mọi mẫu tin trong file nguồn thỏa một tính chất nào đó (khi xóa chú ý có 
thể: chỉ đánh dấu xóa hoặc xóa hẳn mẫu tin tìm thấy) 
e. (*) Sắp xếp file tăng dần theo một tiêu chuẩn nào đó bằng một trong các phương 
pháp: 
- chèn 
- trộn: trộn trực tiếp, trộn tự nhiên, trộn nhiều đường cân bằng (*) 
Kiểm tra lại các hàm sắp xếp trên với bộ dữ liệu sau: 
 66 31 22 97 36 15 6 32 79 44 
 26 19 45 46 75 8 13 17 62 88 
 76 33 72 
Yêu cầu thực hiện các thao tác cơ bản trên đây khi file được tổ chức theo kiểu: 
i) tuần tự (cho phép hoặc không cho phép đánh dấu xóa) 
ii) chỉ mục (*). 
(File văn bản) 
2) Giả sử ta cần lưu trữ các chuỗi ký tự theo từng dòng vào một file văn bản 
“DữLiệu.Txt” và khai thác thông tin trên file này. Hãy lập chương trình có các 
chức năng sau: 
a. Lưu vào file văn bản “DữLiệu.Txt” các dòng chuỗi ký tự được lấy từ bàn phím 
hoặc từ một file văn bản cho trước. 
b. Khai thác file văn bản theo một tiêu chuẩn nào đó mà không làm thay đổi file 
nguồn (các thông tin thỏa tiêu chuẩn được kết xuất ra màn hình hoặc một file 
khác). Chẳng hạn: tính tần số xuất hiện của các từ hay dòng trong file thỏa một 
tính chất nào đó; xuất ra (màn hình theo từng trang 23 dòng) các từ hay dòng 
của file nguồn thỏa một tính chất nào đó 
c. Sao chép file “DữLiệu.Txt” vào một file văn bản khác 
d. Nối hai file văn bản f1.txt và f2.txt cho trước trong hai trường hợp: 
- file f2.txt được nối vào cuối file f1.txt (file f1.txt có thể thay đổi) 
- tạo file f3.txt kết qủa mới, còn hai file đầu không bị thay đổi 
e. (*) Chia file văn bản nguồn thành nhiều file văn bản con thỏa hay không thỏa 
một tính chất nào đó. Chẳng hạn tách file văn bản chương trình nguồn trong 
C++ thành hai file con: một file chứa tất cả các chú thích trên dòng và trên 
đoạn (giả sử các chú thích không lồng nhau), file còn lại không chứa các chú 
thích. 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 87 – 
f. (*) Cập nhật thông tin của file văn bản nguồn (và có thể làm thay đổi file 
nguồn, có thể sử dụng hoặc không sử dụng các file phụ), chẳng hạn: 
- Thay thế (hay sửa) các đơn vị (ký tự, từ hoặc dòng) của file văn bản nguồn 
bởi các đơn vị xác định khác. 
- Xóa các đơn vị (ký tự, từ hoặc dòng) của file văn bản nguồn bởi các đơn vị 
xác định khác. 
- Chèn một đơn vị (ký tự, từ hoặc dòng) xác định vào sau những đơn vị trong 
file nguồn thỏa một tính chất nào đó. 
3) a. Tạo ra các file văn bản mt.txt, day.txt và dt.txt chứa các giá trị của: 
- ma trận cấp n có dạng sau: 
3 
12 32 -4 
-1 45 9 
27 -87 34 
trong đó: dòng đầu lưu cấp n của ma trận, các dòng kế tiếp lưu các dòng 
tương ứng của ma trận 
- dãy gồm n số thực có dạng sau: 
5 
1.3 5.67 7.23 0.12 -9.67 
trong đó: dòng đầu lưu số phần tử n của dãy, dòng kế tiếp lưu các phần tử 
tương ứng của dãy. 
- Dãy n đường thẳng trong mặt phẳng có dạng sau: 
2 
1.3 5.67 7.23 0.12 
-9.67 12 32 -4 
trong đó: dòng đầu lưu số đường thẳng n của dãy, các dòng kế tiếp lưu các 
cặp tọa độ của hai điểm (x1, y1), (x2, y2) trên từng đường thẳng tương ứng 
của dãy. 
 b. Đọc nội dung của các file văn bản trên, kiểm tra tính hợp lệ của dữ liệu và: 
- kiểm tra nó có phải là ma phương hay không ? (tổng mỗi dòng, mỗi cột và mội 
đường chéo của ma trận đều bằng nhau) 
- tính tổng các giá trị âm và tìm giá trị lớn nhất trong các phần tử của dãy. 
- (*) tìm 3 giá trị lớn nhất trong các phần tử của dãy. 
- viết phương trình các đường thẳng đã cho (trong mặt phẳng) 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 88 – 
(File nhị phân các bytes hay ký tự) 
4) (*) 
a) Tạo ra 2 file nhị phân chứa các ký tự trong các trường hợp sau: 
- mọi ký tự đều có mã ASCII lớn hơn 0x1F (‘\31’) 
- mọi ký tự đều có mã ASCII hoặc lớn hơn 0x1F (‘\31’), hoặc bằng 0x1A (chú ý 
trường hợp ở giữa file có chứa ký tự 0x1A (‘\26’) để kết thúc file văn bản) 
- các ký tự có mã ASCII bất kỳ 
b) Hỏi trong trường hợp nào có thể mở file ra đọc theo kiểu nhị phân, sau đó theo 
kiểu văn bản và xuất được nội dung vừa đọc ra màn hình ? So sánh và cho 
nhận xét. 
c) Sao chép hai file bất kỳ (nội dung và kích thước hai file giống hệt nhau) 
d) Chia một file bất kỳ thành n file con có kích thước bằng nhau (trừ file cuối cùng) 
e) Nối n file bất kỳ thành một file mới có kích thước đúng bằng tổng kích thước 
của n file đã cho. 
f) (*) Mã hóa và giải mã một file bất kỳ theo một phương pháp mã đơn giản nào 
đó. 
Bài tập chương 2 (Cấu trúc cây) 
1) Xuất ra theo thứ tự : giữa, đầu, cuối các phần tử trên cây nhị phân sau: 
A 
 P R 
 Q E T 
 M N D B C 
2) a. Tìm cây nhị phân thỏa đồng thời hai điều kiện kết xuất sau: 
theo thứ tự đầu NLR của nó là dãy ký tự sau: 
 A, B, C, D, E, Z, U, T, Y 
và theo thứ tự giữa LNR của nó là dãy ký tự sau: 
 D, C, E, B, A, U, Z, T, Y 
 b. (*) Khi cho trước 2 trong 3 kết quả duyệt NLR, LNR, LRN thì có luôn xác định 
duy nhất cây nhị phân thỏa điều kiện nêu ra không ? Dùng chương trình để kiểm chứng 
? 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 89 – 
3) a. Biểu diễn mỗi biểu thức số học dưới đây trên cây nhị phân, từ đó rút ra dạng 
biểu thức hậu tố của chúng: 
i. a/(b*c) 
 ii. a5 + 4a3 -3a2 + 7 
 iii. (a+b)*(c-d) 
iv. Sa+b 
 b. (*) Viết thuật toán và chương trình: 
- Chuyển một biểu thức số học ký hiệu lên cây nhị phân (có kiểm tra biểu thức 
đã cho có hợp cú pháp không ?). 
- Xuất ra biểu thức số học đó dưới dạng: trung tố, hậu tố, tiền tố. 
- Sau đó nhập trị cho các ký hiệu trong biểu thức, hãy đánh giá biểu thức hậu tố 
tương ứng. 
4) Xây dựng cây tìm kiếm nhị phân BST từ mỗi bộ mục dữ liệu đầu vào như sau: 
a. 1, 2, 3, 4, 5 
b. 5, 4, 3, 2, 1 
c. fe, cx, jk, ha, gc, ap, aa, by, my, da 
d. 8, 9, 11, 15, 19, 20, 21, 7, 3, 2, 1, 5, 6, 4, 13, 10, 12, 17, 16, 18. 
Sau đó xóa lần lượt các nút sau: 2, 10, 19, 8, 20. 
5) Viết một chương trình có các tác dụng sau: 
a. Nhập từ bàn phím các số nguyên vào một cây nhị phân tìmkiếm (BST) mà nút 
gốc được trỏ bởi con trỏ Root. 
b. Xuất các phần tử trên cây BST trên theo thứ tự : đầu, giữa, cuối theo dòng và 
vẽ sơ đồ cây (*) (chỉ yêu cầu trường hợp khi số phần tử của cây nhị phân không 
quá lớn !). 
c. Tìm và xóa (nếu có thể) phần tử trên cây Root có dữ liệu trùng với một mục dữ 
liệu Item cho trước được nhập từ bàn phím. 
d. Sắp xếp n mục dữ liệu (được cài đặt bằng mảng hay DSLK) bằng phương pháp 
cây nhị phân tìm kiếm BSTSort. 
Yêu cầu: viết các thao tác trên bằng 2 phương pháp: đệ quy và lặp (*). 
(**) Riêng với duyệt cây, hãy viết dưới dạng lặp cả 3 phương pháp duyệt trong 
một hàm duy nhất có tính khái quát. 
e. Kiểm tra lại kết quả của bài tập 4) bằng chương trình vừa xây dựng. 
6) Tương tự bài tập 5, nhưng mỗi nút có thêm trường con trỏ Parent chỉ đến nút cha 
của nó. 
7) (*) Xây dựng các thao tác cơ bản trên cây n-phân được biểu diễn bởi cây nhị phân: 
chèn một nút, tạo cây n-phân, xóa một nút, hủy cây n-phân. 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 90 – 
8) Cho cây nhị phân T. Viết chương trình chứa các hàm có tác dụng xác định: 
a. Tổng số nút của cây. Số nút tối đa của cây nhị phân có chiều cao h là bao 
nhiêu? Chứng minh điều khẳng định bằng qui nạp và kiểm nghiệm lại bằng 
chương trình. 
b. (*) Số nút của cây ở mức k. Số nút tối đa ở mức k của cây nhị phân là bao 
nhiêu ? Chứng minh điều khẳng định bằng qui nạp và kiểm nghiệm lại bằng 
chương trình. 
c. (*) Số nút lá. 
d. Chiều cao của cây. 
e. Tổng giá trị trường dữ liệu (số !) trên các nút của cây. 
f. Kiểm tra xem nó có phải là một cây nhị phân chặt (là cây nhị phân mà mỗi nút 
khác nút lá đều có đúng 2 con) hay không ? 
g. Kiểm tra xem T có phải là cây cân bằng hoàn toàn hay không ? 
h. Số nút có đúng 2 con khác rỗng 
i. Số nút có đúng 1 con khác rỗng 
j. Số nút có khóa nhỏ hơn x trên cây nhị phân hoặc cây BST 
k. Số nút có khóa lớn hơn x trên cây nhị phân hoặc cây BST 
l. Số nút có khóa nhỏ hơn x và lớn hơn y (y ≤ x) trên cây nhị phân hoặc cây BST 
m. Duyệt cây theo chiều rộng 
n. Duyệt cây theo chiều sâu 
o. Độ lệch lớn nhất trên cây (độ lệch của một nút là trị tuyệt đối của hiệu số giữa 
chiều cao của cây con phải và cây con trái của nó) 
p. Đảo nhánh trái và phải của một cây nhị phân 
Yêu cầu: viết các thao trên bằng 2 phương pháp: đệ quy và lặp (*). 
9) Viết chương trình xây dựng cây nhị phân tìm kiếm có chiều cao bé nhất từ một dãy 
có thứ tự tăng của các phần tử được lưu trữ trên một danh sách liên kết. 
10) a. Hãy vẽ cây AVL có chiều cao cực đại có 12 nút 
 b. Hãy tìm một ví dụ về một cây AVL có chiều cao là 6 và khi hủy một nút lá (chỉ ra 
cụ thể), việc cân bằng lại cây lan truyền lên tận gốc. 
c. (*) Viết chương trình thể hiện các thao tác cơ bản trên cây AVL: chèn một nút, 
xóa một nút, tạo cây AVL, hủy cây AVL. Kiểm tra lại bằng chương trình với dữ 
liệu của câu a. và b. trên đây. 
11) (*) Viết chương trình cho phép tạo, thêm, bớt, tra cứu, sửa chữa từ điển. 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 91 – 
Bài tập chương 3 (B - cây) 
1) a. Xây dựng B-cây cấp 2 từ các mục dữ liệu đầu vào như sau (trình bày từng bước 
khi chèn mỗi phần tử): 
i) 25, 17, 31, 42, 21, 19, 26, 33, 47, 44, 45, 43, 8, 9 
ii) 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 
iii) ca, ea, ba, da, bf, df, ah, cg, bi, cc, af, eg, bd, ec, ch, ai, dc, di, ce, ef, cf 
 b. Hãy trình bày từng bước của B-cây cấp 2 ở câu a.iii) khi xóa lần lượt các phần tử 
sau: cf, ef, ce, di, dc, ai, ch, eg, af, cc, bi, cg, ah, df, bf 
2) (*) Viết chương trình cài đặt B-cây cấp n ở bộ nhớ trong có các chức năng sau: 
a. Tìm và chèn một phần tử vào B-cây cấp n 
b. Tạo B-cây cấp n với dữ liệu lấy từ bàn phím 
c. Tìm và xóa một phần tử khỏi B-cây cấp n 
d. Hủy B- cây cấp n 
Dùng chương trình để kiểm tra lại các bộ số liệu ở bài tập 1) trên đây. 
3) (**) Tương tự như bài 2 nhưng B-cây cấp n được cài đặt ở bộ nhớ ngoài 
Bài tập chương 4 (Bảng băm) 
1) Hãy tạo ra bảng băm khi lần lượt chèn từng phần tử từ các bộ số liệu đầu vào sau: 
534 702 105 523 959 699 821 883 842 686
 658 4 20 382 570 344 
 khi dùng phương pháp: 
a. Băm liên kết trực tiếp (dựa trên mảng hoặc danh sách liên kết) trong hai 
trường hợp: M=13, M=17 
b. Băm liên kết kết hợp khi M = 17 
c. Băm theo địa chỉ mở khi M = 19 
- Phương pháp thử tuyến tính 
- Phương pháp thử bậc hai 
- Phương pháp băm kép (dùng hàm băm thứ 2 là H2(k) = 1 + (k mod 17)) 
Trong mỗi trường hợp, tìm số trung bình các phép so sánh khi tìm kiếm 1 
khóa trong bảng băm. 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 92 – 
2) Viết chương trình để tạo bảng băm được cài đặt ở bộ nhớ trong theo các phương 
pháp đã nêu và kiểm tra lại các bộ dữ liệu đầu vào ở bài tập 1) trên đây 
3) (**) Tương tự như bài tập 2 nhưng bảng băm được cài đặt ở bộ nhớ ngoài 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 93 – 
TÀI LIỆU THAM KHẢO 
[1] A.V. AHO , J.E. HOPCROFT , J.D. ULMANN: Data structures and algorithms. 
Addition Wesley - 1983. 
[2] DONALD KNUTH: The Art of Programming. (vol. 1: Fundamental Algorithms, vol. 
3: Sorting and Searching). Addition Wesley Puplishing Company - 1973. 
[3] ĐINH MẠNH TƯỜNG: Cấu trúc dữ liệu và thuật toán. NXB KHKT – 2001. 
[4] ĐỖ XUÂN LÔI: Cấu trúc dữ liệu và giải thuật. NXB KHKT - 1995. 
[5] LARRY N. HOFF, SANFORD LEESTMA: Lập trình nâng cao bằng Pascal với các 
cấu trúc dữ liệu. Bản dịch của Lê Minh Trung. Công ty Scitec - 1991. 
[6] NGUYỄN TRUNG TRỰC: Cấu trúc dữ liệu, Trung tâm điện toán, ĐH Bách khoa 
TP HCM, 1992. 
[7] NIKLAUS WIRTH: Algorithms + Data Structures = Programs. Prentice - Hall INC 
- 1976. 
[8] ROBERT SEDGEWICK: Cẩm nang thuật toán, tập 1, Bản dịch của nhóm tác giả 
ĐHTH TP HCM, NXB KHKT, 1994. 
[9] TRẦN HẠNH NHI, DƯƠNG ANH ĐỨC: Nhập môn cấu trúc dữ liệu và thuật toán, 
Giáo trình của khoa Công nghệ Thông tin, Đại học Khoa học Tự nhiên TP HCM, 2000. 
Trương Chí Tín Khoa Toán - Tin 
Giáo trình cấu trúc dữ liệu và thuật toán 2 - 94 – 
Trương Chí Tín Khoa Toán - Tin