›
›

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

pdf 94 trang phuongnguyen 6120
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và thuật toán 2", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_cau_truc_du_lieu_va_thuat_toan_2.pdf

Nội dung text: Giáo trình Cấu trúc dữ liệu và thuật toán 2

  1. TRƯỜNG ĐẠI HỌC ĐÀ LẠT F 7 G GIÁO TRÌNH CẤU TRÚC DỮ LIỆU VÀ THUẬT TỐN 2 Trương Chí Tín
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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 cuối tập tin ta nhận được mã kết thúc tập tin EOF. - Tập tin văn bản: các tập tin này lưu trữ các từ trên dòng. Nó khác tập tin kiểu nhị phân khi xử lý ký tự chuyển dòng và ký tự kết thúc tập tin văn bản trong các thao tác đọc và ghi. C++ là một trong những ngôn ngữ phục vụ cho phương pháp lập trình hướng đối tượng. Trong phương pháp này, một trong những khái niệm quan trọng là lớp. Có thể xem lớp là công cụ để lưu trữ các đối tượng thông qua cấu trúc dữ liệu để biểu diễn chúng và cả những phương thức cơ bản thao tác trên chúng. Khi làm việc với tập tin trong C++, các thao tác trên tập tin là các phương thức thuộc các lớp ifstream, ofstream, fstream, ios. 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 Trương Chí Tín Khoa Toán - Tin
  8. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 8 – 1) Mở tập tin. * Trước khi làm việc với tập tin (đọc hay ghi) ta phải mở nó để nhận một tên ngoài (tên file thực tế nằm trên đĩa), thực hiện một số việc kiểm tra và phân tích cú pháp, trao đổi với hệ điều hành rồi tạo ra một tên nội bộ đại diện (biến file hình thức) để dùng về sau trong việc đọc hay ghi lên tập tin. Tên nội bộ này là một con trỏ (gọi là con trỏ tập tin), trỏ tới cấu trúc chứa thông tin tập tin, chẳng hạn như: vị trí bộ đệm file, vị trí byte hiện tại trong bộ đệm, tập tin đang đọc hay ghi, nối thêm, * Khai báo và mở tập tin theo cú pháp sau: fstream BienFileHinhThuc(const char *FileName, int mode); trong đó FileName là tên tập tin có kiểu hằng xâu ký tự, mode nhận một số trong các giá trị sau (và chúng nối kết nhau bằng toán tử logic trên bit ¦ ): ios::in: mở một tập tin để đọc. Nếu tập tin chưa tồn tại sẽ bị lỗi. Phần chọn này có thể bỏ qua nếu thay lớp fstream bởi ifstream. ios::out: mở một tập tin để ghi mới. Nếu tập tin đã tồn tại thì nó bị xóa. Phần chọn này có thể bỏ qua nếu thay lớp fstream bởi ofstream. ios::app: mở một tập tin để ghi bổ sung. Nếu tập tin chưa tồn tại thì tạo tập tin mới. ios::binary: mở một tập tin theo kiểu nhị phân. Nếu không có phần này thì tập tin được mở theo kiểu văn bản. * Chú ý: - Nếu mở một tập tin chưa tồn tại để ghi hay nối thêm thì tập tin sẽ được tạo ra. - Mở một tập tin đã có để ghi mới làm cho nội dung cũ sẽ bị mất trước khi ghi mới! - Mở một tập tin chưa có để đọc sẽ sinh lỗi. - Nếu có lỗi khi mở tập tin thì BienFileHinhThuc sẽ nhận giá trị NULL. * Ví dụ: Khai báo char TenFile[] = “Tam.dat”; fstream f(TenFile, ios::in ¦ios::out ¦ ios::binary); if (!f) cout <<”\nLoi mo file ” << TenFile << “ de doc va ghi !”; có tác dụng mở file TenFile theo kiểu nhị phân, vừa để đọc và để ghi và kiểm tra việc mở file có tốt không. Trương Chí Tín Khoa Toán - Tin
  9. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 9 – 2) Đóng tập tin. Sau khi mở tập tin và làm các thao tác đọc ghi xong, ta phải đóng tập tin theo cú pháp: BienFileHinhThuc.close(); Phương thức này phá vỡ mối liên hệ giữa BienFileHinhThuc và tên ngoài đã được thiết lập. Ngoài ra, nó còn có tác dụng đẩy nốt nội dung bộ đệm ra file (an toàn dữ liệu). 3) Kiểm tra cuối tập tin. BienFileHinhThuc.eof (); Hàm cho giá trị khác 0 nếu gặp cuối tập tin khi đọc, trái lại hàm cho trị 0 (ta thường dùng phương thức này để kiểm tra cuối tập tin sau lệnh đọc sẽ trình bày ở phần sau). 4) Kiểm tra trạng thái đọc, ghi dữ liệu: BienFileHinhThuc.good(); Hàm này trả về 0 nếu gặp lỗi đọc hay ghi và một giá trị khác không trong trường hợp ngược lại. B/. Các phương thức dùng cho tập tin kiểu văn bản 1/ Đọc 1 chuỗi ký tự: char *BienFileHinhThuc.getline(char *line, int maxLine, char delim); Hàm này đọc một dòng (kể cả dấu xuống dòng và các khoảng trắng) từ tập tin được chỉ định bởi BienFileHinhThuc vào chuỗi ký tự line, nhiều nhất là maxLine-1 ký tự được đọc vào; việc đọc sẽ kết thúc nếu gặp ký tự delim . Dòng kết qủa sẽ được kết thúc bởi ‘\0’. Thông thường hàm này trả về địa chỉ chuỗi line, trừ khi gặp cuối tập tin hoặc gặp lỗi nó sẽ cho trị NULL. Phương thức int BienFileHinhThuc.gcount() trả về số ký tự vừa đọc được. 2/ Ghi 1 chuỗi ký tự: BienFileHinhThuc << Chuỗi; Toán tử này xuất Chuỗi ra file được chỉ định bởi BienFileHinhThuc. Trương Chí Tín Khoa Toán - Tin
  10. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 10 – 3/ Ghi 1 ký tự. BienFileHinhThuc.put(char c); Hàm ghi một ký tự ra file được chỉ định bởi BienFileHinhThuc. 4) Đọc 1 ký tự. char BienFileHinhThuc.get(); * Hàm này đọc một ký tự từ file được chỉ định bởi BienFileHinhThuc và làm dời chỗ vị trí con trỏ định vị việc đọc trong tập tin đến vị trí kế tiếp. * Hàm get trả về ký tự đọc được, nếu thành công. C/. Các phương thức dùng cho tập tin kiểu nhị phân 1/ Ghi một số bytes: BienFileHinhThuc.write(const char *buf, int size); Hàm này ghi vào file được chỉ định bởi BienFileHinhThuc một số size bytes, bắt đầu từ địa chỉ buf. 2/ Đọc một số bytes: BienFileHinhThuc.read(char *buf, int size); Hàm này đọc từ file được chỉ định bởi BienFileHinhThuc một số size bytes và gán chúng vào mảng các ký tự được xác định bởi buf. Có thể dùng phương thức int BienFileHinhThuc.gcount() để biết số bytes vừa đọc được. 3/ Chuyển con trỏ định vị việc ghi trong file: BienFileHinhThuc.seekp(long offset, int origin); Để truy cập ngẫu nhiên tập tin khi ghi ta dùng hàm này để đặt con trỏ định vị việc ghi trong tập tin được chỉ định bởi BienFileHinhThuc di chuyển offset bytes từ vị trí xuất phát được xác định theo một trong các giá trị sau của origin: ios::beg tìm từ đầu tập tin ios::cur tìm từ vị trí hiện hành ios::end tìm từ cuối tập tin Phương thức long BienFileHinhThuc.tellp(); trả về vị trí hiện hành của con trỏ định vị việc ghi trong tập tin. Trương Chí Tín Khoa Toán - Tin
  11. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 11 – 4/ Chuyển con trỏ định vị việc đọc trong file: BienFileHinhThuc.seekg(long offset, int origin); Để truy cập ngẫu nhiên tập tin khi đọc ta dùng hàm này để đặt con trỏ định vị việc đọc trong tập tin được chỉ định bởi BienFileHinhThuc di chuyển offset bytes từ vị trí xuất phát được xác định theo giá trị của origin. Phương thức long BienFileHinhThuc.tellg(); trả về vị trí hiện hành của con trỏ định vị việc đọc trong tập tin. Lưu ý khi truy cập ngẫu nhiên tập tin để đọc hay ghi, các bytes được đánh số bắt đầu từ 0. I.3. Tổ chức tập tin Dựa trên các thao tác sơ cấp truy nhập file trên đây, ta có thể xây dựng các thuật toán phức tạp và hữu ích khác trên file chứa các đối tượng có cùng cấu trúc. Khi xét đến độ hiệu quả của các thuật toán này (đặc biệt về mặt thời gian), ta có thể tổ chức file theo 2 kiểu: tuần tự hay có chỉ mục. * Khi lưu và truy cập các đối tượng theo kiểu tuần tự trong một file, ta có kiểu file tuần tự. Ví dụ 1: Giả sử ta cần lưu các đối tượng A, C, B cùng kiểu T vào file f. f ACB Tuy cách lưu trữ này rất đơn giản khi cài đặt nhưng ta sẽ gặp nhiều nhược điểm (về mặt thời gian) khi gặp các tình huống sau. Nếu ta cần chèn thêm 1 đối tượng D vào trước A thì ta phải dời mọi phần tử từ A qua phải một vị trí; nếu ta muốn xóa đối tượng A, thì ta phải dời mọi phần tử từ A qua trái một vị trí. Đối với các tập tin lưu nhiều đối tượng có cùng kiểu dữ liệu T (trên thực tế, ta thường gặp trường hợp T có kích thước (bytes) lưu trữ lớn), nếu phải dùng nhiều thao tác chèn và xóa sẽ mất rất nhiều thời gian cho việc dời chỗ các phần tử. Để khắc phục nhược điểm trên, ta có thể tổ chức tập tin theo kiểu chỉ mục đơn giản như sau: * Khi cần lưu một dãy các đối tượng có cùng kiểu T vào file f, ngoài việc dùng file f như cách tổ chức tuần tự như trên, ta dùng kèm thêm một file Trương Chí Tín Khoa Toán - Tin
  12. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 12 – chỉ mục f_idx tương ứng để chứa các địa chỉ (hay thứ tự) của các đối tượng thực sự trong file f. Khi đó, các thao tác chèn, xóa sẽ thực hiện nhanh hơn. Ví dụ 2: với cùng mục đích như ví dụ 1, ta dùng 2 file: file f để chứa các đối tượng thực sự A, B, C và file f_idx dùng để chứa số thứ tự bắt đầu của các đối tượng tương ứng trong f như sau: 0 1 2 f A B C f_idx 0 1 2 -1 trong đó: các phần tử của f_idx: 0,1,2 lần lượt chỉ số thứ tự (bắt đầu) của đối tượng A, B, C trong file f; còn –1 (EOF) để chỉ sự kiện kết thúc file. Việc chèn D vào f trước A, sẽ thực hiện như sau: 0 1 2 3 f A B C D f_idx 3 1 2 -1 0 Việc xóa A, ta có thể đánh dấu xóa A (nếu cần thiết !) bằng cách gán chỉ số –2 (XOA) cho mẩu tin tương ứng trong f_idx và đổi lại số thứ tự bắt đầu trong các mẩu tin tương ứng trong f trước A (là D) như sau: 0 1 2 3 f A B C D f_idx 3 -2 2 -1 1 Tất nhiên, việc dùng kèm thêm file chỉ mục như trên có ưu điểm là làm tăng tốc độ thực hiện các thao tác chèn, xóa; ngược lại, nó sẽ tốn thêm bộ nhớ cho f_idx và cũng làm phức tạp thêm khi viết các thao tác cơ bản trên file, đặc biệt là các thuật toán chèn, xóa một đối tượng. * Vài lưu ý khi thiết kế các thuật toán trên tập tin: Khi thiết kế các thuật toán trên tập tin, ngoài các phép toán cơ bản đặc trưng cho thuật toán (chẳng hạn: đối với các thuật toán tìm kiếm, ta cần để ý đến số các phép toán so sánh; đối với các thuật toán sắp xếp thì nên để ý đến số các phép toán so sánh và hoán vị hay phép gán; ), ta còn phải Trương Chí Tín Khoa Toán - Tin
  13. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 13 – chú ý nhiều tới số lần đọc và ghi đối tượng lên file, vì thời gian cho các thao tác này chiếm thời gian khá lớn. II. CÁC THAO TÁC CƠ BẢN TRÊN FILE Các thao tác cơ bản thường sử dụng khi làm việc trên file chứa các đối tượng có cùng cấu trúc là: tạo (xây dựng) file, duyệt và khai thác file, tìm hay xóa một đối tượng có một tính chất nào đó của file, chèn (thêm) một đối tượng vào sau một đối tượng thỏa một tính chất nào đó trên file, sửa (thay thế) một đối tượng thỏa một tính chất nào đó trên file bởi một đối tượng khác. II.1. Tập tin tuần tự * Thao tác tạo file (hay nhập liệu vào file) f : thao tác này xây dựng file mà dữ liệu lấy từ một nguồn nào đó, trong đó ta dùng hàm Boolean LấyĐượcMộtĐốiTượng(ĐT) Hàm này trả về trị true nếu còn lấy được một đối tượng và trả về trị false trong trường hợp ngược lại. TạoFile (f) - Bước 1: Mở file f để ghi mới (hay nối thêm); - Bước 2: Trong khi còn LấyĐượcMộtĐốiTượng(ĐT) GhiMộtĐốiTượng(ĐT) vào file f; - Bước 3: Đóng file f; * Thao tác duyệt file (hay khai thác file) f : thao tác này xử lý tất cả các đối tượng (mỗi đối tượng xét đúng một lần) thỏa một tính chất TC nào đó của file f. DuyệtFile (f, TC) - Bước 1: Mở file f để đọc - Bước 2: Trong khi còn ĐọcĐượcMộtĐốiTượng(ĐT) từ file f Nếu (ĐT có tính chất TC) thì XửLýĐốiTượng(ĐT); // không làm thay đổi ĐT trong f - Bước 3: Đóng file f; Trương Chí Tín Khoa Toán - Tin
  14. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 14 – * Thao tác tìm (tuần tự) một đối tượng A đầu tiên có một tính chất TC nào đó trên file f: thao tác này trả về trị True nếu tìm thấy và False trong trường hợp ngược lại. Ngoài ra trong trường hợp tìm thấy đối tượng A, nó còn trả lại vị trí bắt đầu ĐốiTượngThứ (các mẫu tin được đánh số bắt đầu từ 0) của A trong file f. Boolean Tìm (f, TC, &A, &ĐốiTượngThứ) - Bước 1: Mở file f để đọc; Thấy ← False; ĐốiTượngThứ ← -1; - Bước 2: Lặp lại các bước sau: Đọc một đối tượng B (từ file f ); ĐốiTượngThứ ← ĐốiTượngThứ +1; Nếu (B có tính chất TC) thì: A ← B; Thấy ← True; Cho đến khi: ((kết thúc file f) hoặc Thấy); - Bước 3: Đóng file f; - Bước 4: Trả về trị Thấy; * Thao tác sửa một đối tượng đầu tiên có một tính chất TC nào đó trên file f thành đối tượng B (cùng kiểu với A): thao tác này trả về trị True nếu tìm thấy và False trong trường hợp ngược lại. Boolean Sửa (f, TC, B) - Bước 1: Thấy ← Tìm(f, TC, A, Thứ); - Bước 2: If not(Thay) SửaĐược ← False; Else Bước 21: Mở file f để ghi (và đọc); Bước 22: Nhảy đến đầu đối tượng thứ Thứ; Ghi B vào file f; Bước 23: Đóng file f ; Bước 24: SửaĐược ←True; - Bước 3: Trả về trị SửaĐược; * Thao tác xoá một đối tượng đầu tiên có một tính chất TC nào đó trên file f : thao tác này trả về trị True nếu tìm thấy đối tượng có tính chất TC và False trong trường hợp ngược lại. Boolean Xoá (f, TC) - Bước 1: Thấy ← Tìm(f, TC, A, Thứ); - Bước 2: If not(Thay) XoáĐược ← False; Else Trương Chí Tín Khoa Toán - Tin
  15. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 15 – Bước 21: Mở file f để đọc; Mở file phụ f_phu để ghi; Bước 22: for (đếm←0; đếm<Thứ ; Thứ++) Đọc một đối tượng B từ file f ; Ghi đối tượng B lên file f_phu; Bước 23: Đọc một đối tượng B từ file f ; // bỏ qua đối tượng B có tính chất TC, không ghi lên file f_phu Bước 24: Lặp lại các bước sau: Đọc được một đối tượng B từ file f; Ghi đối tượng B lên file f_phu; Cho đến khi: kết thúc file f; Bước 25: Đóng file f ; Đóng file f_phu; Xoá file f ; Đổi tên file f_phu thành f; Bước 26: XoáĐược ←True; - Bước 3: Trả về trị XoáĐược; * Thao tác chèn một đối tượng C sau một đối tượng đầu tiên có một tính chất TC nào đó trên file f : thao tác này trả về trị True nếu tìm thấy đối tượng có tính chất TC và False trong trường hợp ngược lại. Boolean Chèn (f, C, TC) - Bước 1: Thấy ← Tìm (f, TC, A, Thứ); - Bước 2: If not(Thấy) ChènĐược ← False; Else Bước 21: Mở file f để đọc và ghi; Bước 22: Nhảy đến đầu đối tượng thứ (Thứ+1); Bước 23: Lặp lại các bước sau: Xem đối tượng B của file f ; // Đọc 1 đối tượng B và nhảy lại đầu đối tượng B vừa đọc được; Ghi đối tượng C lên file f ; C ← B; Cho đến khi: kết thúc file f; Bước 24: Ghi đối tượng C lên file f ; Bước 25: Đóng file f ; ChènĐược ←True; - Bước 3: Trả về trị ChènĐược; Nhận xét: Nếu thêm 1 trường đánh đấu xóa (kiểu logic) vào kiểu của đối tượng thì có nhận xét gì về các thao tác cơ bản trên file kiểu tuần tự ? Kiểm chứng lại bằng chương trình (bài tập). Trương Chí Tín Khoa Toán - Tin
  16. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 16 – II.2. Tập tin chỉ mục Khi làm việc với file chỉ mục, ta luôn xét file f (chứa các đối tượng thật sự) kèm với file chỉ mục f_idx tương ứng (chứa số thứ tự bắt đầu của các đối tượng tương ứng trong file f). Ký hiệu:F=(f,f_idx), EOF = -1 là chỉ số kết thúc file, CHỈSỐXÓA = -2 là chỉ số mẩu tin bị xóa. Trong các thuật toán cơ bản trình bày trong phần này, ta sẽ sử dụng những thao tác sơ cấp sau đây: - Đọc1ĐốiTượngTrongFileDat(f, Thứ_Dat, &ĐốiTượng): có tác dụng đọc 1 đối tượng ĐốiTượng ở vị trí thứ Thứ_Dat từ file dữ liệu f. Việc đọc bị thất bại nếu Thứ_Dat=EOF (hết file logic !) hoặc Thứ_Dat= CHỈSỐXÓA (mẩu tin đã bị xóa); 0 1 2=ThứDat 3 f E C = ĐốiTượng D A f_idx 3 -2 2 -1 1 Đã xóa Kết thúc file logic - Đọc1ĐốiTượngTrongFileIdx (f_idx, Thứ_Idx, &ChỉSốDat): có tác dụng đọc nội dung trong file chỉ mục f_idx tại vị trí thứ Thứ_Idx, cho kết quả là chỉ số ChỉSốDat trong file f (nếu ChỉSốDat =EOF: hết file logic !); 0 1 2 3 f E C D A f_idx 3 -2 2 -1 1 Thứ_Idx = 0; 1=Thứ_Idx; 2 3 Thứ_Idx = 4 ChỉSốDat = 3; ChỉSốDat = -2 = CHỈSỐXÓA; ChỉSốDat = -1 = EOF Đã xóa Kết thúc file logic Trương Chí Tín Khoa Toán - Tin
  17. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 17 – - Ghi_1_PTửTạiVịTrí(g, Thứ, PTử): có tác dụng ghi một phần tử PTử tại vị trí thứ Thứ vào file g. - ThứSau_Dat = NextDat(f_idx, ThứTrước_Dat): có tác dụng trả lại số thứ tự bắt đầu ThứSau_Dat của mẩu tin kế tiếp (theo chỉ mục) của mẩu tin tại vị trí thứ ThứTrước_Dat trong file f (chính là nội dung của mẩu tin thứ ThứTrước_Dat+1 trong file f_idx) (nếu ThứSau_Dat =EOF: hết file logic !); 0 ThứSau_Dat=1 2 ThứTrước_Dat=3 f E C D A f_idx 3 -2 2 -1 1 (nếu ThứTrước_Dat =2 thì ThứSau_Dat=-1=EOF: hết file lôgic) - ThứSau_Idx = NextIdx (f_idx, ThứTrước_Idx, &ChỉSốDat): có tác dụng trả lại nội dung ChỉSốDat của mẩu tin thứ ThứTrước_Idx trong file f_idx và số thứ tự bắt đầu ThứSau_Idx (ThứSau_Idx chính là ChỉSốDat +1) của mẩu tin kế tiếp theo thứ tự chỉ mục của mẩu tin tại vị trí thứ ThứTrước_Idx trong file f_idx. 0 1 2 ChỉSốDat=3 f E C D A f_idx 3 -2 2 -1 1 ThứTrước_Idx = 0 1 2 3 ThứSau_Idx=4 * Thao tác tạo file (hay nhập liệu vào file) chỉ mục F : thao tác này xây dựng file mà dữ liệu lấy từ một dãy các đối tượng nào đó, trong đó ta dùng hàm Boolean LấyĐượcMộtĐốiTượng(ĐT) Hàm này trả về trị true nếu còn lấy được một đối tượng và trả về trị false trong trường hợp ngược lại. Tạo 0 1 2 3 Trương Chí Tín Khoa Toán - Tin
  18. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 18 – f B C D A f_idx 0 1 2 3 -1 0 1 2 3 4 TạoFileIdx (f) - Bước 1: Mở file F để ghi; SốĐốiTượngLấyĐược ← 0; - Bước 2: Trong khi còn (LấyĐượcMộtĐốiTượng(ĐT)), lặp lại các bước sau: Bước 21: GhiMộtĐốiTượng(ĐT) vào cuối file f; Bước 22: GhiMộtSố (SốĐốiTượngLấyĐược) vào cuối file f_idx; Bước 23: SốĐốiTượngLấyĐược ← SốĐốiTượngLấyĐược + 1; - Bước 3: GhiMộtSố (EOF) vào cuối file f_idx; Đóng file F; * Thao tác duyệt file chỉ mục F: thao tác này xử lý tất cả các đối tượng thỏa một tính chất TC nào đó của file F. Duyệt 0 1 2 3 F E C D A f_idx 3 -2 2 -1 1 ChỉSốDat = 3 0 1 2 3 Thứ_Idx = 4 Đã xóa Kết thúc file logic DuyệtIdx (F, TC) - Bước 1: Mở file F để đọc; Đọc1ĐốiTượngTrongFileIdx (f_idx, 0, &ChỉSốDat); // hay: Đọc 1 mẩu tin (đầu) ChỉSốDat của f_idx; - Bước 2: Trong khi (ChỉSốDat ≠ EOF) // hay chưa hết file lôgic lặp lại các bước sau: Đọc1ĐốiTượngTrongFileDat(f,ChỉSốDat,ĐốiTượng); If (ĐốiTượng có tính chất TC) XửLý(ĐốiTượng); ChỉSốDat = NextDat(f_idx, ChỉSốDat); - Bước 3: Đóng file F; Trương Chí Tín Khoa Toán - Tin
  19. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 19 – * Thao tác tìm (tuần tự) một đối tượng đầu tiên (chưa bị xóa) A có một tính chất TC nào đó trên file chỉ mục F: thao tác này trả về trị True nếu tìm thấy và False trong trường hợp ngược lại. Ngoài ra, trong trường hợp tìm thấy, nó còn trả lại vị trí Thứ_Idx của mẩu tin trong file chỉ mục f_idx mà nội dung của nó là vị trí bắt đầu của đối tượng tìm thấy A. Tìm 0 (TC) 1 2 3 f B C D A f_idx 3 1 2 -1 0 0 1 2 3 Thứ_Idx = 4 Boolean TìmIdx (F, TC, &A, &Thứ_Idx) - Bước 1: Mở file F để đọc; Thấy ← False; Thứ_Idx ← 0; ThứSau_Idx = NextIdx (f_idx, Thứ_Idx,ChỉSốDat); - Bước 2: Trong khi (ChỉSốDat ≠ EOF or Chưa Thấy) lặp lại các bước sau: Đọc1ĐốiTượngTrongFileDat(f,ChỉSốDat,ĐốiTượn g); If (ChỉSốDat == CHỈSỐXÓA) Thông báo lỗi cập nhật sai đối tượng đã bị xoá; Chuyển sang bước 3; If (ĐốiTượng có tính chất TC) A ← ĐốiTượng; Thấy ← True; Else Thứ_Idx ← ThứSau_Idx; ThứSau_Idx = NextIdx (f_idx, Thứ_Idx,ChỉSốDat); - Bước 3: Đóng file F; - Bước 4: Trả về trị Thấy; * Thao tác sửa một đối tượng đầu tiên (chưa bị xoá) có một tính chất TC nào đó trên file chỉ mục F thành đối tượng B: thao tác này trả về trị True nếu tìm thấy đối tượng cần sửa và False trong trường hợp ngược lại. Tìm 0 (TC) 1 2 3 Trương Chí Tín Khoa Toán - Tin
  20. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 20 – f E C D A f_idx 3 1 2 -1 0 0 1 2 3 Thứ_Idx = 4 Sửa ChỉSốDat = 0 (TC) 1 2 3 F E C D B f_idx 3 1 2 -1 0 0 1 2 3 Thứ_Idx = 4 Boolean SửaIdx (F, TC, B) - Bước 1: Thấy ← TìmIdx (F, TC, A, Thứ_Idx); - Bước 2: If not(Thấy) SửaĐược ← False; Else Bước 21: Mở file F để ghi (và đọc); Bước 22: Đọc1ĐốiTượngTrongFileIdx (f_idx,Thứ_Idx,ChỉSốDat); Ghi_1_PTửTạiVịTrí(f, ChỉSốDat, B); Bước 23: Đóng file F; SửaĐược ←True; - Bước 3: Trả về trị SửaĐược; * Thao tác xoá một đối tượng đầu tiên (chưa bị xoá) có một tính chất TC nào đó trên file chỉ mục F: thao tác này trả về trị True nếu tìm thấy đối tượng cần xóa và False trong trường hợp ngược lại. Tìm 0 (TC) 1 2 3 f B C D A f_idx 3 1 2 -1 0 0 1 2 3 Thứ_Idx = 4 ThứSau_Idx = 1; ChỉSốDatSau=1 Trương Chí Tín Khoa Toán - Tin
  21. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 21 – Xóa 0 (TC) 1 2 3 f B C D A f_idx 3 -2 2 -1 1 0 1 2 3 Thứ_Idx = 4 Boolean XoáIdx (F, TC) - Bước 1: Thấy ← TìmIdx (F, TC, A, Thứ_Idx); - Bước 2: If not(Thay) XoáĐược ← False; Else Bước 21: Mở file F để ghi và đọc; Bước 22:ThứSau_Idx = NextIdx (f_idx, Thứ_Idx,ChỉSốDat); Đọc1ĐốiTượngTrongFileIdx(f_idx,ThứSau_Idx,ChỉSốDatSau) ; Ghi_1_PTửTạiVịTrí(f_idx, Thứ_Idx, ChỉSốDatSau); Ghi_1_PTửTạiVịTrí(f, ThứSau_Idx, CHỈSỐXÓA); Bước 23: Đóng file F ; Bước 24: XoáĐược ←True; - Bước 3: Trả về trị XoáĐược; * Thao tác chèn một đối tượng C sau một đối tượng đầu tiên (chưa bị xoá) có một tính chất TC nào đó trên file chỉ mục F: thao tác này trả về trị True nếu tìm thấy đối tượng có tính chất TC và False trong trường hợp ngược lại. Tìm ChỉSốDat = 0 (TC) 1 2 3 F B E D A f_idx 3 1 2 -1 0 0 1 2 3 Thứ_Idx = 4 =TổngSốĐTượng ThứSau_Idx =1 ChỉSốDatSau =1 Chèn 0 (TC) 1 2 3 4 f B E D A C Trương Chí Tín Khoa Toán - Tin
  22. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 22 – f_idx 3 4 2 -1 0 1 0 1 2 3 Thứ_Idx = 4 5 Boolean ChènIdx (F, C, TC) - Bước 1: Thấy ← TìmIdx (F, TC, A, Thứ_Idx); - Bước 2: If not(Thấy) ChènĐược ← False; Else Bước 21: Mở file F để đọc và ghi; Bước 22: Tìm TổngSốĐốiTượng trong file (cũ trước khi chèn) f; Ghi C vào cuối f; ThứSau_Idx = NextIdx (f_idx, Thứ_Idx,ChỉSốDat); Đọc1ĐốiTượngTrongFileIdx(f_idx,ThứSau_Idx,ChỉSốDatSau); Ghi ChỉSốDatSau vào cuối file f_idx; Ghi_1_PTửTạiVịTrí(f_idx, ThứSau_Idx, TổngSốĐốiTượng); Bước 23: Đóng file F ; ChènĐược ←True; - Bước 3: Trả về trị ChènĐược; * Nhận xét: • Lưu ý rằng, trong các thuật toán trên, ta không cập nhât lại những mẩu tin (đối tượng) đã bị xoá. Nếu muốn truy cập hoặc phục hồi lại các mẩu tin này thì cần viết thêm các thủ tục tương ứng (bài tập). • Khi tổ chức file f theo kiểu chỉ mục như trên, tuy phải dùng thêm bộ nhớ phụ cho file f_idx, nhưng kiểu của mỗi mẩu tin của nó chỉ kiểu nguyên, nên nếu kích thước của mỗi đối tượng của file f khá lớn (thường gặp trong thực tế) thì dung lượng bộ nhớ phụ cho file f_idx là không đáng kể ! • Bù lại, nếu phải dùng nhiều phép chèn, xóa các đối tượng trên file f, thì thời gian thực hiện sẽ rất nhanh. Ngoài ra, khi cần viết các thuật toán phức tạp trên tập tin, chẳng hạn sắp xếp, thì thời gian đáng kể để thực hiện cho các thuật toán này là để sao chép các đối tượng từ tập tin này sang tập tin khác. Nếu tổ chức file theo kiểu chỉ mục, thì chỉ phải sao chép các kiểu dữ liệu nguyên (file chứa dữ liệu thật sự không đổi !). Khi đó thời gian cho các thuật toán này (thường cần dùng nhiều file phụ) sẽ rút ngắn đáng Trương Chí Tín Khoa Toán - Tin
  23. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 23 – kể và bộ nhớ cần dùng cho các file phụ (chỉ cần dùng thêm file chỉ mục dạng idx) sẽ giảm đáng kể ! III. SẮP XẾP TRÊN FILE Giả sử ta cần sắp (tăng) các đối tượng có cùng kiểu T trong file f cho trước, với điều kiện là trong kiểu T có một trường (gọi là trường khóa key) mà trên miền trị của trường đó có một quan hệ thứ tự ⋉ cho trước (một quan hệ hai ngôi có các tính chất: phản xạ, phản xứng và bắc cầu; ta thường gặp quan hệ ⋉ là quan hệ ≤ thông thường). * Định nghĩa 1: (đường chạy với chiều dài cố định) Một đường chạy (theo trường khóa key) có chiều dài cố định k là một dãy gồm k đối tượng d1, d2, ,dk được sắp theo một trường khóa đó: d1.key ⋉ d2.key ⋉ ⋉ dk.key * Định nghĩa 2: (đường chạy tự nhiên với chiều dài không cố định) Một đường chạy (tự nhiên) r (theo trường khóa key) trên file f là một dãy con gồm các đối tượng r = {dm, dm+1, ,dn } thỏa các tính chất sau: di.key ≤ di+1.key , ∀ i ∈ [m,n) dm-1.key > dm.key dn.key > dn+1.key * Định nghĩa 3: (thao tác trộn) Trộn 2 đường chạy r1, r2 có chiều dài lần lượt là d1 và d2 là tạo ra đường chạy mới r (gồm tất cả các đối tượng từ r1 và r2) có chiều dài d1+d2. III.1. Trộn trực tiếp (Straight Merge) * Ýù tưởng phương pháp: Sử dụng thêm 2 file phụ f1 và f2 để thực hiện các phép phân phối luân phiên các đường chạy có chiều dài k là lũy thừa của 2 của f vào f1 và f2. Sau đó trộn luân phiên các đường chạy có chiều dài k từ f1 và f2 thành các đường chạy dài gấp đôi 2*k vào f. Gấp đôi chiều dài đường chạy k ← 2*k. Lặp lại các phép phân phối và trộn luân Trương Chí Tín Khoa Toán - Tin
  24. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 24 – phiên các đường chạy như trên cho đến khi chiều dài đường chạy k ≥ số phần tử của file f (trong f chỉ còn lại một đường chạy !) thì các phần tử trong f được sắp. * Thuật toán: SắpXếpTrộnTrựcTiếp(&f) - Bước 1: DàiĐườngChạy ← 1; - Bước 2: Lặp lại các bước sau: Bước 21: Gọi thuật toán “PhânPhốiTrựcTiếp” để phân phối lần lượt các đường chạy có chiều dài DàiĐườngChạy từ f vào f[1] và f[2]; Bước 22: Gọi thuật toán “TrộnTrựcTiếp” để trộn lần lượt các đường chạy có chiều dài DàiĐườngChạy tương ứng trong f[1] và f[2] vào f. Bước 23: DàiĐườngChạy ← 2 * DàiĐườngChạy; Cho đến khi (DàiĐườngChạy >= số phần tử của file f); + PhânPhốiTrựcTiếp(f, &f1, &f2, DàiĐườngChạy) - Bước 1: Mở file f[1] và f[2] để ghi, mở file f để đọc; FileThứ←1;PTửThứ←0; - Bước 2: Trong khi (chưa kết thúc f) lặp lại các bước sau: PTửThứ ← PTửThứ +1; Sao một phần tử của f vào f[FileThứ]; If (PTửThứ == DàiĐườngChạy) PTửThứ←0; If (FileThứ < 2) FileThứ ← FileThứ+1; Else FileThứ ← 1; - Bước 3: Đóng các file f, f[1] và f[2]. + TrộnTrựcTiếp(f[1], f[2], &f, DàiĐườngChạy) - Bước 1: SốPTửCầnChépVàoFilef ← SốPTửCủaFilef; Mở file f[1] và f[2] để đọc, mở file f để ghi; Đọc1ĐTượng x1 của f[1]; Đọc1ĐTượng x2 của f[2]; // gọi r[i] là chiều dài đường chạy của f[i], i=1,2 - Bước 2: Lặp lại các bước sau: . If (DàiĐườngChạy ≤ SốPTửCầnChépVàoFilef) r[1]← DàiĐườngChạy; else r[1]← SốPTửCầnChépVàoFilef; . SốPTửCầnChépVàoFilef ← SốPTửCầnChépVàoFilef – r[1]; Trương Chí Tín Khoa Toán - Tin
  25. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 25 – . If (DàiĐườngChạy ≤ SốPTửCầnChépVàoFilef) r[2]← DàiĐườngChạy; else r[2]← SốPTửCầnChépVàoFilef; . SốPTửCầnChépVàoFilef ← SốPTửCầnChépVàoFilef – r[2]; . Trong khi (r[1]>0 và r[2]>0) thực hiện:// chưa hết 2 đường chạy If (x1 0) thực hiện:// f[1] chưa hết đường chạy GhiĐTượng x1 vào f; r[1] ← r[1]-1; If (chưa kết thúc file f[1]) Đọc1ĐTượng x1 của f[1]; . Trong khi (r[2]>0) thực hiện:// f[2] chưa hết đường chạy GhiĐTượng x2 vào f; r[2] ← r[2]-1; If (chưa kết thúc file f[2]) Đọc1ĐTượng x2 của f[2]; Cho đến khi (SốPTửCầnChépVàoFilef==0); - Bước 3: Đóng các file f, f[1] và f[2]. Ví dụ 3: giả sử ta cần sắp tăng file f sau: f : 2, 1, 4, 5, 7 - DàiĐườngChạy = 1: Phân phối f thành: f1 : 2; 4; 7 f2 : 1; 5 Trộn f1 và f2 vào f: f : 1, 2; 4, 5; 7 - DàiĐườngChạy = 2: Phân phối f thành: f1 : 1, 2; 7 Trương Chí Tín Khoa Toán - Tin
  26. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 26 – f2 : 4, 5 Trộn f1 và f2 vào f: f : 1, 2, 4, 5; 7 - DàiĐườngChạy = 4: Phân phối f thành: f1 : 1, 2, 4, 5 f2 : 7 Trộn f1 và f2 vào f: f : 1, 2, 4, 5, 7 - DàiĐườngChạy = 8 (>5): dừng ! * Nhận xét: • Với phương pháp trộn trực tiếp, số lần phân phối và trộn khoảng: k=log2(n). Do mỗi lần phân phối hoặc trộn, ta cần n lần sao chép các đối tượng từ tập tin này sang tập tin khác , nên tổng số các đối tượng cần sao chép trong trường hợp xấu nhất là: Txấu(n) = 2 * n * log 2 (n) • Trong giải thuật trộn trên đây, để đơn giản cho việc trình bày, ta chỉ sử dụng 2 file phụ f1 và f2 trong các giai đoạn phân phối và trộn. Thật ra, vẫn với các ý tưởng cơ bản trên đây, ta có thể mở rộng thuật toán trộn trên đây khi sử dụng đồng thời nhiều hơn 2 tập tin phụ f1, f2, ,ft (t>2) để thực hiện các giai đoạn phân phối và trộn với độ dài các đường chạy k là lũy thừa của t. Khi đó, tổng số các đối tượng cần sao chép trong trường hợp xấu nhất là: Txấu(n) = 2 * n * log t (n) • Qua ví dụ trên, ta thấy phương pháp trộn trực tiếp có nhược điểm sau: do luôn sử dụng chiều dài đường chạy cố định k tại mỗi vòng lặp phân phối và trộn nên không tận dụng được tình trạng “tốt tự nhiên” của dữ liệu (trong ví dụ trên, đáng lẽ ta có thể dừng ngay khi vừa thực hiện xong bước lặp với DàiĐườngChạy = 2; lúc đó: 1,2,4,5,7 là một đường chạy tự nhiên !). Vì lẽ đó, ta có thể cải tiến phương pháp trộn trực tiếp thành phương pháp trộn tự nhiên sau Trương Chí Tín Khoa Toán - Tin
  27. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 27 – III.2. Trộn tự nhiên (Natural Merge) * Ýù tưởng phương pháp: Sử dụng thêm 2 file phụ f1 và f2 để thực hiện các phép phân phối luân phiên các đường chạy tự nhiên của f vào f1 và f2. Sau đó trộn luân phiên các đường chạy tự nhiên từ f1 và f2 thành các đường chạy dài hơn vào f. Lặp lại các phép phân phối và trộn luân phiên các đường chạy tự nhiên như trên cho đến khi trong f chỉ còn lại một đường chạy thì các phần tử trong f được sắp. * Thuật toán: SắpXếpTrộnTựNhiên (f) Lặp lại các bước sau: Bước 1: Gọi thuật toán “PhânPhốiTự Nhiên(f,f1,f2)” để phân phối các đường chạy (tự nhiên) trong f lần lượt vào f1 và f2. Bước 2: Gán SốĐườngChạy ← 0; gọi thuật toán “TrộnTựNhiên (f1,f2,f,SốĐChạy)” để trộn các đường chạy (tự nhiên) tương ứng trong f1 và f2 vào f. Cho đến khi SốĐườngChạy = 1. PhânPhốiTựNhiên(f,f1,f2) /* Thuật toán phân phối luân phiên các đường chạy tự nhiên của f vào f1 và f2 */ - Bước 1: Mở file f1 và f2 để ghi, mở file f để đọc. - Bước 2: Trong khi (chưa kết thúc f) lặp lại các bước sau: Bước 21: Sao một đường chạy (tự nhiên) từ f vào f1 (lặp lại việc đọc một ĐốiTượng_1 của f và ghi nó vào f1 cho đến khi ĐốiTượng_2 tiếp theo trong f nhỏ hơn ĐốiTượng_1 vừa được sao hay đến kết thúc file f); Bước 22: Nếu chưa đạt đến kết thúc f, sao một đường chạy (tự nhiên) tiếp theo của f vào f2; - Bước 3: Đóng các file f, f1, f2. TrộnTựNhiên(f1,f2,f, &SốĐChạy) /* Thuật toán trộn các đường chạy tự nhiên tương ứng trong f1 và f2 vào f. SốĐườngChạy là số các đường chạy tự nhiên tạo ra trong f */ - Bước 1: Mở file f1 và f2 để đọc, mở file f để ghi. Khởi động SốĐườngChạy=0. Trương Chí Tín Khoa Toán - Tin
  28. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 28 – - Bước 2: Trong khi (chưa kết thúc f1 và chưa kết thúc f2) lặp lại các bước sau: Bước 21: Trong khi chưa hết đường chạy trong f1 và chưa hết đường chạy trong f2 làm các bước sau: Nếu ĐốiTượng_1 tiếp theo trong f1 nhỏ hơn ĐốiTượng_2 tiếp theo trong f2 thì chép ĐốiTượng_1 vào f ; nếu ngược lại chép ĐốiTượng_2 vào f. Bước 22: Nếu hết đường chạy trong f1, sao phần còn lại của đường chạy tương ứng trong f2 vào f ; nếu ngược lại, sao phần còn lại của đường chạy tương ứng trong f1 vào f. Bước 23: Tăng SốĐườngChạy thêm 1. - Bước 3: Sao tất cả các đường chạy còn lại trong f1 hay f2 vào f, với mỗi đường chạy tăng SốĐườngChạy lên 1. - Bước 4: Đóng các file f, f1, f2. + SaoMộtĐườngChạy(f_Nguon,&f_Đích) // sao một đường chạy từ f_Nguồn đã mở để đọc đến f_Đích đã mở để ghi - Lặp lại bước sau: KếtThúcĐườngChạy ← False; SaoMộtĐốiTượng(f_Nguon,f_Đích, KếtThúcĐườngChạy) Cho đến khi (KếtThúcĐườngChạy); + SaoMộtĐốiTượng(f_Nguon, &f_Đích, &KếtThúcĐườngChạy) /*sao một đối tượng từ f_Nguồn vào f_Đích và cho biết đã KếtThúcĐườngChạy trong f_Nguồn hay chưa */ - Bước 1: Đọc một ĐốiTượng HTại từ file f_Nguồn và ghi vào file f_Đích; - Bước 2: If (KếtThúcFile(f_Nguồn)) KếtThúcĐườngChạy ← True; Else XemĐốiTượngTiếpTheo Sau của file f_Nguồn If (Sau < HTại) KếtThúcĐườngChạy ← True; Else KếtThúcĐườngChạy ← False; * Ví dụ: Sắp xếp tăng dần bằng phương pháp trộn tự nhiên tập tin f có nội dung như sau: f: 75 55 15 20 85 30 35 10 60 40 50 25 45 80 70 65 - Phân phối (Tách hay Chia) (lần 1): f1: 75 15 20 85 10 60 25 45 80 65 f2: 55 30 35 40 50 70 Trộn: f : 55 75 15 20 30 35 40 50 70 85 10 60 25 45 80 65 Trương Chí Tín Khoa Toán - Tin
  29. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 29 – - Phân phối (lần 2): f1: 55 75 10 60 65 f2: 15 20 30 35 40 50 70 85 25 45 80 Trộn: f: 15 20 30 35 40 50 55 70 75 85 10 25 45 60 65 80 - Phân phối (lần 3): f1: 15 20 30 35 40 50 55 70 75 85 f2: 10 25 45 60 65 80 Trộn: f: 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 III.3. Trộn nhiều đường cân bằng (Balanced Multiway Merge) Trong các giải thuật trộn trực tiếp và tự nhiên trên đây, thời gian thực hiện chủ yếu dựa vào số lần duyệt tập tin để phân phối và trộn các đường chạy, do mỗi lần duyệt tập tin thì toàn bộ các đối tượng của tập tin sẽ được sao chép lại. Ta có thể cải tiến chúng nhờ giảm số lần duyệt tập tin, bằng cách chủ yếu chỉ dùng các quá trình trộn mà hạn chế dùng quá trình phân phối các đường chạy. Trong phương pháp trộn nhiều đường cân bằng để sắp xếp các đối tượng của tập tin f[0], ta dùng thêm N (N chẵn) tập tin phụ f[1], f[2], , f[N]. Gọi nh=N/2. TrộnNhiềuĐường CânBằng(f[0]) - Bước 1: Phân phối luân phiên các đường chạy (tự nhiên) từ f[0] lần lượt vào các tập tin phụ f[1], f[2], , f[nh]; - Bước 2: Lặp lại các bước sau: Bước 21: Trộn các đường chạy (tự nhiên) của f[1], f[2], , f[nh] và lần lượt luân phiên phân phối vào các tập tin f[nh+1], f[nh+2], , f[N]; Bước 22: Nếu số đường chạy (tự nhiên) sau khi trộn lớn hơn 1 thì trộn các đường chạy của f[nh+1], f[nh+2], , f[N] và lần lượt luân phiên phân phối vào các tập tin f[1], f[2], , f[nh]; Trương Chí Tín Khoa Toán - Tin
  30. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 30 – Cho đến khi số đường chạy (tự nhiên) sau khi trộn bằng 1; * Nhận xét: Với phương pháp trộn N đường cân bằng, số lần duyệt tập tin là: k=log nh (n). Do mỗi lần duyệt tập tin, ta cần n lần sao chép, nên tổng số các đối tượng cần sao chép trong trường hợp xấu nhất là: Txấu(n) = n * log nh (n), với nh = N/2 * Ví dụ: Sắp xếp tăng dần bằng phương pháp trộn với N = 4 đưỡng cân bằng cho tập tin f có nội dung như sau: f: 75 55 15 20 85 30 35 10 60 40 50 25 45 80 70 65 - Bước 1: (Phân phối f vào 2 file f1 và f2) f1: 75 15 20 85 10 60 25 45 80 65 f2: 55 30 35 40 50 70 - Bước 2: Lặp . Lần 1: Phân phối luân phiên các đường chạy (tự nhiên) từ f1, f2 lần lượt vào f3 và f4: f3 : 55 75 10 60 65 f4 : 15 20 30 35 40 50 70 85 25 45 80 Phân phối luân phiên các đường chạy (tự nhiên) từ f3, f4 lần lượt vào f1 và f2: f1: 15 20 30 35 40 50 55 70 75 85 f2: 10 25 45 60 65 80 . Lần 2: Phân phối luân phiên các đường chạy (tự nhiên) từ f1, f2 lần lượt vào f3 và f4: f3: 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 f4: trống. Chỉ còn 1 đường chạy: f3 đã được sắp, đổi f3 thành f. Trương Chí Tín Khoa Toán - Tin
  31. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 31 – CHƯƠNG II: CẤU TRÚC CÂY Trong cấu trúc dữ liệu động được tổ chức theo kiểu tuần tự như danh sách liên kết, tuy có ưu điểm trong các thao tác chèn, xóa, nhưng tốc độ thực hiện trong các thao tác truy cập đến các phần tử của nó hay tìm kiếm thường rất chậm. Để khắc phục các nhược điểm trên nhưng vẫn duy trì các ưu điểm của cấu trúc dữ liệu động trong các thao tác chèn, xóa, ta có thể dùng một cấu trúc dữ liệu động khác là cây tìm kiếm được xét trong chương này để lưu trữ và khai thác dữ liệu hiệu quả hơn. I. ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM CƠ BẢN I.1. Định nghĩa cây Cây là một tập hợp N các phần tử gọi là nút (hay đỉnh), trong đó có duy nhất một đỉnh đặc biệt gọi là gốc, và một tập hợp các cạnh có hướng A (A ⊂ NxN) nối các cặp nút với nhau gọi là cung hay nhánh. Mỗi nút trên cây đều được nối với gốc bằng duy nhất một dãy các cặp cung liên liếp. 1 nút gốc ; mức 1 2 3 cha của 5,6,7; mức 2 nút trong 4 5 6 7 mức 3 8 9 nút lá (con của 4); mức 4 (Cây tam phân, có chiều cao là 4) Bậc của nút 1 là 2, bậc của nút 2 là 1, bậc của nút 3 là 3, bậc của nút 8 là 0. I.2. Các khái niệm khác * Mỗi cung ai = (ni , ni+1) ∈ A có hai nút ở đầu, nút trên ni gọi là cha, nút dưới ni+1 gọi là con. Trương Chí Tín Khoa Toán - Tin
  32. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 32 – * Nút gốc là nút (duy nhất) không có nút cha. Mọi nút khác có đúng một nút cha. * Một đường đi p từ n1 đến nk là một dãy các đỉnh {n1, n2, , nk} sao cho: ai = (ni , ni+1) ∈ A, ∀ i = 1, , k-1 * Độ dài đường đi Lx,y từ x đến y là số cung trên đường đi từ x đến y. Ký hiệu Lx là độ dài đường đi từ gốc đến x. * Độ dài đường đi trung bình của cây là: ( Σ Lx )/n, n là số nút của cây hay số phần tử của N x ∈ N trong đó, Lx là độ dài đường đi từ gốc đến đỉnh x. * Mọi nút khác gốc được nối với gốc bằng một đường đi duy nhất bắt đầu từ gốc và kết thúc ở nút đó. Trong cây không có chu trình. * Bậc của nút là số cây con của nút đó. * Bậc của cây là bậc lớn nhất của các nút của cây. Cây bậc n gọi là cây n - phân. * Nút trong là nút có bậc lớn hơn không. Nút lá là nút có bậc bằng không. Mỗi nút trong cùng với các con của nó tạo thành cây con. * Mức của 1 nút (khác nút gốc) là số đỉnh trên đường đi từ gốc đến nút đó. Mức của nút gốc bằng 1: Mức(gốc) = 1; Mức(con) = Mức(cha) + 1, ∀ (cha,con) ∈ A * Chiều cao của một cây là mức lớn nhất của các nút lá. * Ví dụ: cây có nhiều ứng dụng để biểu diễn các loại dữ liệu trong thực tế. Chẳng hạn: - Biểu thức số học: ((a*b)+c)/((d*e)+(f-g)) được biểu diễn dưới dạng cây. Ta biểu diễn: toán tử bởi nút gốc và tóan hạng bởi nút lá. / + + * c * - a b d e f g - Sơ đồ tổ chức của một quốc gia, địa phương hay cơ quan cũng có dạng cây. - Mục lục sách theo hệ thống phân loại nào đó, * Cây có thứ tự : là cây mà các nút của nó được xếp theo thứ tự nào đó và có để ý đến vị trí (thứ tự) của các nút con. Trương Chí Tín Khoa Toán - Tin
  33. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 33 – Trong cây có thứ tự khi ta thay đổi vị trí của các cây con thì ta sẽ có một cây mới. Chẳng hạn, hai cây có thứ tự sau đây được xem là khác nhau: + + * c c * a b a b * Cây nhị phân: là cây mà mỗi nút có tối đa 2 nút con (con trái và con phải; do phân biệt vị trí các nút nên cây nhị phân được xem là cây có thứ tự ). * Từ một cây có tổng quát (cây n- phân) ta có thể chuyển về cây nhị phân (xem II.6.) nghĩa là có thể dùng cây nhị phân để biểu diễn cây tổng quát. Do tính chất đơn giản và tầm quan trọng như vậy, trước hết ta khảo sát cây nhị phân. II. CÂY NHỊ PHÂN 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. Ta còn có thể xem cây nhị phân như là một cấu trúc dữ liệu đệ qui. * Định nghĩa đệ qui: Một cây nhị phân (Binary tree) : + hoặc là rỗng ( phần neo hay trường hợp cơ sở); + hoặc là một nút mà nó có 2 cây con nhị phân không giao nhau, gọi là cây con bên trái và cây con bên phải (phần đệ qui). II.2. Vài tính chất của cây nhị phân Gọi h và n lần lượt là chiều cao và số phần tử của cây nhị phân. - Số nút ở mức i ≤ 2i-1, hay nói chính xác hơn số nút tối đa ở mức i là 2i-1. Do đó, số nút lá tối đa của nó là 2h-1. - Số nút tối đa trong cây nhị phân là 2h –1, hay n ≤ 2h –1. Do đó, chiều cao của nó: n ≥ h ≥ log2(n+1) Trương Chí Tín Khoa Toán - Tin
  34. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 34 – II.3. Biểu diễn cây nhị phân Ta chọn cấu trúc động để biểu diễn mỗi nút trên cây nhị phân: LChild RChild Data trong đó: LChild, RChild lần lượt là các con trỏ chỉ đến nút con bên trái và nút con phải. LChild hay RChild là con trỏ rỗng nếu không có nút con bên trái hay bên phải. Nút lá có dạng: LChild RChild • Data • Trong ngôn ngữ C hay C++, ta khai báo kiểu dữ liệu cho một nút của cây nhị phân như sau: typedef ElementType; /* Kiểu mục dữ liệu của nút */ typedef struct TN { ElementType Data; //Để đơn giản, ta xem Data là trường khóa của dữ liệu struct TN * LChild, *RChild; } TreeNode; typedef TreeNode *TreePointer; * Ví dụ: Ta biểu diễn biểu thức số học: a * b + c bởi cây nhị phân: + * c a b + Nút gốc Trương Chí Tín Khoa Toán - Tin
  35. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 35 – * • c • • a • • b • Trong các thuật toán thuộc chương này, ta sẽ sử dụng hàm CấpPhát() để cấp phát vùng nhớ cho một nút mới của cây nhị phân. Hàm trả về địa chỉ bắt đầu vùng nhớ đựoc cấp phát cho một nút nếu việc cấp phát thành công và trả trị NULL nếu ngược lại. Trong C++, hàm trên có thể được viết như sau: TreePointer CấpPhát () {TreePointer Tam= new TreeNode; if (Tam == NULL) cout << “\nLỗi cấp phát vùng nhớ cho một nút mới của cây nhị phân !”; return Tam; } II.4. Duyệt cây nhị phân II.4.1. Định nghĩa: Duyệt qua cây nhị phân là quét qua mọi nút của cây nhị phân sao cho mỗi nút được xử lý đúng một lần. Dựa vào định nghĩa đệ qui ta chia cây nhị phân ra làm 3 phần: gốc, cây con bên trái, cây con bên phải. Ta có 3 phương pháp chính duyệt cây nhị phân tùy theo trình tự duyệt 3 phần trên: + Duyệt qua theo thứ tự giữa (LNR) + Duyệt qua theo thứ tự đầu (NLR) + Duyệt qua theo thứ tự cuối (LRN). trong đó: L : quét cây con trái của một nút R : quét cây con phải của một nút N : xử lý nút. II.4.2. Các thuật toán duyệt cây nhị phân * Thuật toán duyệt qua theo thứ tự giữa (LNR: Trái - Gốc - Phải) : +Duyệt qua cây con trái theo thứ tự giữa; +Duyệt qua gốc; +Duyệt qua cây con phải theo thứ tự giữa. Trương Chí Tín Khoa Toán - Tin
  36. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 36 – * Thuật toán duyệt qua theo thứ tự đầu (NLR: Gốc - Trái - Phải): +Duyệt qua gốc; +Duyệt qua cây con trái theo thứ tự đầu; +Duyệt qua cây con phải thứ tự đầu. Thuật toán NLR sẽ duyệt cây theo chiều sâu. * Thuật toán duyệt qua theo thứ tự cuối (LRN: Trái - Phải - Gốc): +Duyệt qua cây con trái theo thứ tự cuối; +Duyệt qua cây con phải theo thứ tự cuối; +Duyệt qua gốc. * Ví dụ: Biểu diễn biểu thức: A - B * C + D lên cây nhị phân: + - D A * B C Duyệt cây theo các thứ tự khác nhau: LNR: A - B * C + D ( biểu thức trung tố ) NLR: + - A * B C D ( biểu thức tiền tố ) LRN: A B C * - D + ( biểu thức hậu tố ) Với cách biểu diễn một biểu thức số học dưới dạng cây nhị phân, dựa trên cách duyệt LRN ta có thể tính giá trị của biểu thức đó (Bài tập). Do định nghĩa đệ quy của cây nhị phân, các thuật toán duyệt qua cây theo kiểu đệ quy là thích hợp. II.4.3. Cài đặt thuật toán duyệt qua cây nhị phân LNR a. Cài đặt thuật toán LNR dưới dạng đệ qui : /* Input: - Root : con trỏ chỉ đến nút gốc của cây nhị phân Output: - Duyệt qua và xử lý mọi nút của cây nhị phân theo thứ tự giữa LNR */ void LNRĐệQuy (TreePointer Root) { if (Root != NULL) { LNRĐệQuy (Root->LChild); Xử lý (Root);// Xử lý theo yêu cầu cụ thể, chẳng hạn: Xuất(Root- >Data); Trương Chí Tín Khoa Toán - Tin
  37. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 37 – LNRĐệQuy (Root->RChild) ; } return; } Thuật toán duyệt cây nhị phân theo thứ tự giữa (LNR) có thể viết lại dưới dạng lặp, bằng cách sử dụng một stack để lưu lại địa chỉ các nút gốc trước khi đi đến cây con trái của nó. Trước hết, ta khai báo cấu trúc một nút của stack trên: typedef struct NS { TreePointer Data; struct NS * Next; } NodeStack; typedef NodeStack * StackType; b. Cài đặt thuật toán LNR dưới dạng lặp : /* Input: - Root : con trỏ chỉ đến nút gốc của cây nhị phân Output: - Duyệt qua và xử lý mọi nút của cây nhị phân theo thứ tự giữa LNR */ void LNRLap(TreePointer Root) { TreePointer p; int TiepTuc = 1; StackType S; p = Root; S = CreateEmptyStack(); // Khởi tạo ngăn xếp rỗng do { while (p != NULL) { Push(S,p); // Đẩy p vào stack S p = p->LChild; } if (!EmptyStack(S)) // Nếu stack S khác rỗng { Pop(S,p); // Lấy ra phần tử p ở đỉnh stack S XuLy(p); p = p->RChild; } else TiepTuc = 0; } while (TiepTuc); return ; } Với hai trường hợp duyệt cây còn lại (NLR và LRN), ta cũng có thể cài đặt chúng dưới dạng đệ quy và lặp (bài tập). Một cách tổng quát, ta có thể viết lại ba thuật toán duyệt này dưới một dạng lặp duy nhất (bài tập). Trương Chí Tín Khoa Toán - Tin
  38. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 38 – II.5. Một cách biểu diễn khác của cây nhị phân Trong một số trường hợp, khi biểu diễn cây nhị phân, người ta không chỉ quan tâm đến quan hệ một chiều từ cha đến con mà cả chiều ngược lại: từ con đến cha. Khi đó, ta có thể dùng cấu trúc sau: Parent Data LChild RChild trong đó: LChild, RChild lần lượt là các con trỏ chỉ đến nút con trái và nút con phải. Parent là con trỏ chỉ đến nút cha. Trong ngôn ngữ C hay C++, ta khai báo kiểu dữ liệu cho một nút của cây nhị phân dạng này như sau: typedef ElementType; /* Kiểu mục dữ liệu của nút */ typedef struct TNP {ElementType Data; //Để đơn giản, ta xem Data là trường khóa của dữ liệu struct TNP * LChild, *Rchild, *Parent; } TreeNodeP; typedef TreeNodeP *TreePointerP; * Ví dụ: e f c a b d II.6. Biểu diễn cây n - phân bởi cây nhị phân. Phương pháp cài đặt cây n - phân bằng mảng có n vùng liên kết chỉ có lợi khi hầu hết các nút của cây có bậc là n. Khi đó n vùng liên kết đều được sử dụng, nhưng với cây có nhiều nút có bậc nhỏ hơn n sẽ gây nên việc lãng phí bộ nhớ vì có nhiều vùng liên kết không sử dụng tới. Do cây nhị phân là cấu trúc dữ liệu cây cơ bản và đơn giản đã được nghiên cứu, nên để mô tả cây n-phân, người ta tìm cách biểu diễn nó thông qua cây nhị phân. Gọi: T là cây n-phân, T2 là cây nhị phân tương ứng với T. Ta gọi các nút con của cùng một nút là anh em với nhau. Để biểu diễn T bằng T2, ta theo các qui tắc sau: + Nút gốc trong T được biểu diễn tương ứng với nút gốc của T2. Trương Chí Tín Khoa Toán - Tin
  39. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 39 – + Con đầu tiên (trái nhất) của một nút trong T là con trái của nút tương ứng trong T2. + Nút anh em kề phải P của một nút Q trong T tương ứng với một nút P2 trong T2 qua liên kết phải của nút Q2 tương ứng trong T2. Cây n-phân T a Q b P c d e f g h i j k l m n a cây nhị phân T2 tương ứng Q2 P2 b c d e f g h i j k l m n II.7. Xây dựng cây nhị phân cân bằng hoàn toàn II.7.1. Định nghĩa: Cây nhị phân cân bằng hoàn toàn (CBHT) là cây nhị phân mà đối với mỗi nút của nó, số nút của cây con trái chênh lệch không quá 1 so với số nút của cây con phải. * Ví dụ: e f c a b d II.7.2. Xây dựng cây nhị phân cân bằng hoàn toàn Xây dựng cây nhị phân cân bằng hoàn toàn có n phần tử: Trương Chí Tín Khoa Toán - Tin
  40. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 40 – TreePointer TạoCâyCBHT(Nguyên n) { TreePointer Root; Nguyên nl, nr; ElementType x; if (n Data = x; Root->LChild = TạoCâyCBHT(nl); Root->RChild = TạoCâyCBHT(nr); return Root; } * Nhận xét: - Một cây CBHT có n nút sẽ có chiều cao bé nhất h ≈ log2n. - Một cây CBHT rất dễ mất cân bằng sau khi thêm hay hủy các nút trên cây, việc chi phí cân bằng lại cây rất lớn vì phải thao tác lại trên toàn bộ cây. Do đó cây CBHT có cấu trúc kém ổn định, ít được sử dụng trong thực tế. III.CÂY NHỊ PHÂN TÌM KIẾM (BST) III.1. Định nghĩa cây nhị phân tìm kiếm (BST) Cây BST là một cây nhị phân có tính chất giá trị khóa ở mỗi nút lớn hơn giá trị khoá của mọi nút thuộc cây con bên trái (nếu có) và nhỏ hơn giá trị khoá của mọi nút thuộc cây con bên phải (nếu có) của nó. * Ví dụ: Xét cây BST sau đây lưu các giá trị: 46, 17, 63,2, 25, 97. Ta biểu diễn quá trình tìm kiếm 2 phần tử 25, 55 trên cây BST qua hình dưới đây: 46 25 46 (không thấy 55) 17 63 25>17 (thấy 25) 2 25 97 Trương Chí Tín Khoa Toán - Tin
  41. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 41 – Với loại cấu trúc dữ liệu động danh sách liên kết, ta rất khó áp dụng hiệu qủa ý tưởng tìm kiếm nhị phân trên mảng. Nhưng với loại cấu trúc dữ liệu động cây BST thì việc thể hiện ý tưởng này là đơn giản. III.2. Tìm kiếm một phần tử trên cây BST (Thuật toán tìm kiếm nhị phân sau đây tương tự phép tìm kiếm nhị phân trên mảng). III.2.1. Thuật toán tìm kiếm dạng đệ qui: /* Input: - Root: con trỏ chỉ đến nút gốc của cây BST. - Item: giá trị khóa của phần tử cần tìm . Output: - Trả về con trỏ LocPtr chỉ đến 1 nút trên cây BST chứa Item nếu tìm thấy Item trên cây BST - Trả trị NULL nếu ngược lại */ TreePointer TìmBSTĐệQuy (TreePointer Root, ElementType Item) { if (Root) {if (Item== Root->Data) return Root; else if (Item > Root->Data) return TìmBSTĐệQuy (Root- >RChild,Item); else return TìmBSTĐệQuy (Root->LChild,Item); } else return(NULL); } * Thủ tục được viết dưới dạng đệ qui thích hợp với lối tư duy tự nhiên của giải thuật và định nghĩa đệ qui của cây nhị phân. Song trong trường hợp này thủ tục viết dưới dạng lặp lại tỏ ra hiệu quả hơn. III.2.2. Thuật toán tìm kiếm dạng lặp: /* Input: - Root: con trỏ chỉ đến nút gốc của cây BST. - Item: giá trị khóa của phần tử cần tìm . Output: - Trả về con trỏ LocPtr chỉ đến 1 nút trên cây BST chứa Item và con trỏ Parent chỉ đến nút cha của nút chứa Item đó nếu tìm thấy Item trên cây BST - Trả trị NULL nếu ngược lại */ TreePointer TìmBSTLặp(TreePointer Root, ElementType Item, TreePointer &Parent) { TreePointer LocPtr = Root; Parent = NULL; Trương Chí Tín Khoa Toán - Tin
  42. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 42 – while (LocPtr != NULL) if (Item==LocPtr->Data) return (LocPtr); else {Parent = LocPtr; if (Item > LocPtr->Data) LocPtr = LocPtr->RChild; else LocPtr = LocPtr->LChild; } return(NULL); } Với cấu trúc cây, việc tìm kiếm theo khóa sẽ nhanh hơn nhiều so với cấu trúc danh sách liên kết. Chi phí tìm kiếm (độ phức tạp) trung bình trên cây nhị phân có n nút khoảng log2 n. III.3. Chèn một phần tử vào cây BST, xây dựng cây BST Việc chèn thêm một phần tử Item vào cây BST cần phải thỏa ràng buộc trong định nghĩa cây BST. Trước khi chèn Item, ta cần tìm khóa của Item có trong cây BST hay không, nếu cóthì khỏi chèn (do trên cây BST ta chỉ chứa những phần tử có khóa khác nhau); nếu ngược lại, khi chấm dứt thao tác tìm kiếm thì ta cũng biết được vị trí chèn (ở nút lá). * Ví dụ: Giả sử ta đã có cây BST (với các nút có khóa khác nhau): O E T C M P U Ta cần thêm phần tử ‘R’: O (R > O) E (R P) R Parent Yêu cầu “vào – ra” của thao tác chèn: /* Input: - Root: con trỏ chỉ đến nút gốc của cây BST. Trương Chí Tín Khoa Toán - Tin
  43. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 43 – - Item: giá trị dữ liệu của nút cần chèn Output: - Trả trị 1 và con trỏ Root chỉ đến nút gốc mới của cây BST nếu chèn được - Trả trị -1 nếu Item đã có trên cây - Trả trị 0 nếu gặp lỗi cấp phát bộ nhớ cho một nút mới của cây */ III.3.1. Thao tác chèn một nút Item vào cây BST (dạng lặp): int ChènBSTLặp(TreePointer &Root, ElementType Item) { TreePointer LocPtr, Parent; if (TìmBSTLặp(Root, Item, Parent)) { cout Data = Item; LocPtr->LChild = NULL; LocPtr->RChild = NULL; if (Parent == NULL) Root = LocPtr; // cây rỗng else if (Item Data) Parent->LChild = LocPtr; else Parent->RChild = LocPtr; return 1; } } III.3.2. Thủ tục chèn một nút Item vào cây BST (dạng đệ qui): int ChènBSTĐệQui(TreePointer &Root, ElementType Item) { TreePointer LocPtr; if (Root == (TreePointer) NULL) // chèn nút vào cây rỗng { if ((Root = CấpPhát ()) == NULL) return 0; Root ->Data = Item; Root ->LChild = NULL; Root ->RChild = NULL; } else if (Item Data) ChènBSTĐệQui (Root->LChild,Item); else if (Item > Root->Data) ChènBSTĐệQui(Root->RChild,Item); else { cout << “\nĐã có phần tử “<< Item << “ trong cây”; return -1; } return 1; } Trương Chí Tín Khoa Toán - Tin
  44. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 44 – III.3.3. Xây dựng cây BST Ta có thể xây dựng cây BST bằng cách lặp lại thao tác chèn một phần tử vào cây BST trên đây, xuất phát từ cây rỗng. Hàm TạoCâyBST(Root) sau đây trả về trị 0 nếu gặp lỗi cấp phát vùng nhớ cho một nút mới của cây Root và trả về trị 1 nếu việc chèn các nút vào cây thành công (không chèn các nút có khóa đã trùng với khóa của nút đã chèn). int TạoCâyBST(PointerType &Root) { ElementType Item; Root = NULL; while (CònLấyDữLiệu(Item)) if (!ChènBSTLặp(Root, Item)) return 0; return 1; } III.4. Phương pháp sắp xếp bằng cây BST Ta nhận xét rằng sau khi duyệt một cây BST theo thứ tự giữa LNR thì ta sẽ thu được một dãy tăng theo khóa. Từ đó, ta có phương pháp sắp xếp dựa trên cây BST như sau. Giả sử ta cần sắp xếp dãy X các phần tử. * Giải thuật BSTSort: - Bước 1: Đưa lần lượt mọi phần tử của dãy X lên cây BST. - Bước 2: Khởi tạo lại dãy rỗng X. Duyệt cây BST theo thứ tự giữa (LNR), trong đó thao tác XửLý(Nút) là lưu Nút->Data vào phần tử tiếp theo của dãy X. * Ví dụ: Giả sử cần sắp xếp một dãy gồm n phần tử được lưu trong mảng X. Khi đó ta có thuật toán sau: 1.Khởi tạo cây BST rỗng. 2.for (i = 0; i Data; - Tăng i lên 1; Trương Chí Tín Khoa Toán - Tin
  45. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 45 – III.5. Xóa một phần tử khỏi cây BST, hủy cây nhị phân Giả sử ta cần xóa một nút (trên cây BST) được trỏ bởi x. Việc xoá một phần tử trên cây BST cũng cần phải thoả các ràng buộc về cây BST, nhưng việc xóa phức tạp hơn so với chèn. Ta phân biệt 3 trường hợp : x trỏ đến nút lá, x trỏ đến nút chỉ có một con, x trỏ đến nút có hai con. a). Xoá nút lá: C x C Xoá nút lá D B D B NULL - Đặt con trỏ phải (hay trái) của nút cha của x thành NULL - Giải tỏa nút D b). Xoá nút có một nút con: - Đặt con trỏ phải (hoặc trái) của nút cha của nút cần xóa trỏ đến nút con khác rỗng của nút cần xóa - Giải tỏa nút cần xóa Giả sử ta cần xóa nút trong E có một nút con: C x C Xoá nút E B E có 1 nút con B D D Kết hợp hai trường hợp trên thành một trường hợp: x trỏ đến nút có nhiều nhất một cây con khác rỗng. Gọi: + x chỉ đến nút cần xóa + SubTree chỉ đến cây con (khác rỗng , nếu có) của x + Parent chỉ đến nút cha của nút được trỏ bởi x (nếu x chỉ đến gốc thì Parent=NULL). Ta có giải thuật xóa cho trường hợp này là: SubTree = x->LChild; if (SubTree == NULL ) SubTree = x->RChild; //SubTree là cây con khác rỗng (nếu có) của x if (Parent == NULL) Root = SubTree; // xoá nút gốc Trương Chí Tín Khoa Toán - Tin
  46. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 46 – else if (Parent->LChild == x) Parent->LChild = SubTree ; else Parent->RChild = SubTree; delete x; c). Xoá nút có hai nút con: Giả sử ta cần xoá nút E có 2 nút con của cây BST sau : C x B E D K (Nút kế tiếp của E I L theo thứ tự giữa) J Đưa về 1 trong 2 trường hợp đầu bằng cách sau: Thay trị của nút mà x trỏ đến bởi trị của nút kế tiếp theo thứ tự giữa (nút kế tiếp là nút cực trái xa nhất theo nhánh con phải của x, hay là nút nhỏ nhất (tất nhiên là theo trường khóa) trong số những nút lớn hơn x->Data). Sau đó xoá nút kế tiếp này (nút kế tiếp này sẽ là nút có tối đa 1 nút con ). C x B E (Thay E bởi I) D K (Xóa nút I) I L J C x B I D K J L Trương Chí Tín Khoa Toán - Tin
  47. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 47 – * Sau đây ta xây dựng thủ tục XóaBST để xoá một nút Item trong một cây BST. Trong thủ tục này có dùng đến thủ tục TìmBSTLặp. Thủ tục XoáBST tìm nút có khóa Item và xoá nó khỏi cây BST. Gọi: - x: trỏ đến nút chứa Item - xSucc: phần tử kế tiếp của x theo thứ tự giữa (nếu x có 2 con) - Parent: trỏ đến cha của x hay xSucc - SubTree: trỏ đến cây con của x. /* Input: - Root: con trỏ chỉ đến nút gốc của cây BST. - Item: giá trị dữ liệu của nút cần xóa Output: - Trả trị 1 và con trỏ Root chỉ đến nút gốc mới của cây BST nếu tìm thấy nút chứa Item và xoá được - Trả trị 0 nếu ngược lại */ int XóaBST (TreePointer &Root, ElementType Item) { TreePointer x,Parent, xSucc,SubTree; if ((x = TìmBSTLặp(Root,Item,Parent)) == NULL) return 0; //không thấy Item else { if ((x->LChild != NULL) && (x->RChild != NULL)) { xSucc = x->RChild; Parent = x; while (xSucc->LChild != NULL) { Parent = xSucc; xSucc = xSucc->LChild; } x->Data = xSucc->Data; x = xSucc; } // đã đưa nút có 2 con về nút có tối đa 1 con SubTree = x->LChild; if (SubTree == NULL) SubTree = x->RChild; if (Parent == NULL) Root = SubTree; // xoá nút gốc else if (Parent->LChild == x) Parent->LChild = SubTree; else Parent->RChild = SubTree; delete x; return 1; } } Ta có thể hủy toàn bộ cây BST bằng cách sử dụng ý tưởng duyệt cây theo thứ tự cuối LRN: hủy cây con trái, hủy cây con phải rồi mới hủy nút gốc. Trương Chí Tín Khoa Toán - Tin
  48. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 48 – void HủyCâyNhịPhân (PointerType &Root) { if (Root) { HủyCâyNhịPhân (Root->LChild); HủyCâyNhịPhân (Root->RChild); delete Root; } return ; } IV. CÂY NHỊ PHÂN TÌM KIẾM CÂN BẰNG Trên cây nhị phân tìm kiếm BST có n phần tử mà là cây CBHT (cân bằng hoàn toàn), phép tìm kiếm một phần tử trên nó sẽ thực hiện rất nhanh: trong trường hợp xấu nhất, ta chỉ cần thực hiện log2n phép so sánh. Nhưng cây CBHT có cấu trúc kém ổn định trong các thao tác cập nhật cây, nên nó ít được sử dụng trong thực tế. Vì thế, người ta tận dụng ý tưởng cây CBHT để xây dựng một cây nhị phân tìm kiếm có trạng thái cân bằng yếu hơn, nhưng việc cân bằng lại chỉ xảy ra ở phạm vi cục bộ đồng thời chi phí cho việc tìm kiếm vẫn dạt ở mức O(log2n). Đó là cây nhị phân tìm kiếm cân bằng. IV.1. Định nghĩa Cây nhị phân tìm kiếm gọi là cây nhị phân tìm kiếm cân bằng (gọi tắt là cây cân bằng hay cây AVL do 3 tác giả Adelson-Velskii-Landis đưa ra vào năm 1962) nếu tại mỗi nút của nó, độ cao của cây con trái và độ cao của cây con phải chênh lệch không quá 1. Rõ ràng, một cây nhị phân tìm kiếm cân bằng hoàn toàn là cây cân bằng, nhưng điều ngược lại không đúng. Chẳng hạn cây nhị phân tìm kiếm trong ví dụ sau là cân bằng nhưng không phải là cân bằng hoàn toàn: Trương Chí Tín Khoa Toán - Tin
  49. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 49 – * Ví dụ: (cây nhị phân tìm kiếm cân bằng nhưng không cân bằng hoàn toàn) O E T C M Cây cân bằng AVL vẫn thực hiện việc tìm kiếm nhanh tương đương cây (nhị phân tìm kiếm) cân bằng hoàn toàn và vẫn có cấu trúc ổn định hơn hẳn cây cân bằng hoàn toàn mà nó được thể hiện qua các thao tác cơ bản sẽ được trình bày trong các phần tiếp theo. IV.2. Chiều cao của cây cân bằng * Định lý (AVL): Gọi hb(n) là độ cao của cây AVL có n nút, khi đó: log2(n+1) ≤ hb(n) 1, gốc của cây T(h) sẽ có hai cây con cũng có số nút ít nhất, một cây có chiều cao là h -1, cây con kia có chiều cao là h -2. Do đó: N(h) = 1 + N(h –1) + N(h –2), ∀ h >1 N(0) = 0, N(1) = 1. Đặt F(h) = N(h) + 1. Khi đó: F(h) = F(h –1) + F(h –2), ∀ h >1 F(0) = 1, F(1) = 2. Giải hệ thức truy hồi trên (bằng cách nào ? Bài tập), ta được: h+2 h+2 h+2 n + 1 ≥ N(h) + 1 = F(h) = (r1 – r2 ) / √5 > (r1 – 1) / √5 với: r1 = (1+ √5) /2, r2 = (1 - √5) /2 ∈ (-1; 1) => h +2 < log r1 (1+ √5 (n + 1)) < log r1 (√5 (n + 2)) < logr1 (n + 2) + log r1 (√5) Trương Chí Tín Khoa Toán - Tin
  50. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 50 – h hL(p) : cây lệch phải CSCB(p) = LH Ù hR(p) < hL(p) : cây lệch trái Với mỗi nút của cây AVL, ngoài các thuộc tính thông thường như cây nhị phân, ta cần lưu thêm thông tin về chỉ số cân bằng trong cấu trúc của một nút: typedef ElementType; /* Kiểu mục dữ liệu của nút */ typedef struct AVLTN { ElementType Data; //Ở đây ta xem Data là trường khóa của dữ liệu int Balfactor; //Chỉ số cân bằng struct AVLTN * Lchild, *Rchild; } AVLTreeNode; typedef AVLTreeNode *AVLTree; Việc thêm hay hủy một nút trên cây AVL có thể làm cây tăng hay giảm chiều cao, khi đó ta cần phải cân bằng lại cây. Để giảm tối đa chi phí cân bằng lại cây, ta chỉ cân bằng lại cây AVL ở phạm vi cục bộ. Các trường hợp mất cân bằng Ngoài các thao tác thêm và hủy, đối với cây cân bằng, ta còn có thêm thao tác cơ bản là cân bằng lại cây AVL trong trường hợp thêm hoặc hủy một nút của nó. Khi đó, độ lệch giữa chiều cao cây con phải và trái sẽ là 2. Do các trường hợp cây lệch trái và phải tương ứng là đối xứng nhau, nên ta chỉ xét trường hợp cây AVL lệch trái. Trương Chí Tín Khoa Toán - Tin
  51. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 51 – Trường hợp a: cây con T1 lệch trái T T1 h-1 L R R h L1 R1 h-1 Trường hợp b: cây con T1 lệch phải T T1 h-1 L R R h-1 L1 R1 h Trường hợp c: cây con T1 không lệch T T1 h-1 L R h L1 R1 h Việc cân bằng lại trong trường hợp b (cây con T1 lệch phải) là phức tạp nhất. Trương Chí Tín Khoa Toán - Tin
  52. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 52 – Trường hợp a: cây con T1 lệch trái T T1 h-1 L R R h L1 R1 h-1 Cân bằng lại bằng phép quay đơn Left-Left, ta được cây T1 không lệch: T1 T h L1 h+1 h-1 R1 R h-1 Trường hợp c: cây con T1 không lệch T T1 h-1 L R R h L1 R1 h Trương Chí Tín Khoa Toán - Tin
  53. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 53 – Cân bằng lại bằng phép quay đơn Left-Left (khi đó ta được cây T1 lệch phải): T1 T h L1 h+2 h R1 R h-1 Trường hợp b: cây con T1 lệch phải, biểu diễn lại cây R1 = như sau: T T1 h-1 L R T2 h-1 L1 R1 h L2 R2 Cân bằng lại bằng phép quay kép Left – Right, ta được cây T2 không lệch như sau: T2 T1 T h+1 h-1 L1 L2 R2 R h-1 Trương Chí Tín Khoa Toán - Tin
  54. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 54 – * Nhận xét: - Trước khi cân bằng lại, cây T lệch (và mất cân bằng) và có chiều cao là h+2 trong cả 3 trường hợp. Nhưng sau khi cân bằng lại cây T, nó vẫn lệch (lệch phải, nhưng tất nhiên vẫn cân bằng) và có chiều cao là h+2 chỉ trong trường hợp c; còn trong hai trường hợp a và b, cây T mới (là T1 hay T2 tương ứng với trường hợp a hay b) không lệch và có chiều cao là h+1. - Các thao tác cân bằng lại trong mọi trường hợp đều có độ phức tạp là O(1). Sau đây là phần cài đặt các phép quay đơn và kép cho cây T mất cân bằng trong hai trường hợp nó bị lệch trái và lệch phải. //Phép quay đơn Left – Left void RotateLL(AVLTree &T) { AVLTree T1 = T->Lchild; T->Lchild = T1->Rchild; T1->Rchild = T; switch (T1->Balfactor) {case LH: T->Balfactor = EH; T1->Balfactor = EH; break; case EH: T->Balfactor = LH; T1->Balfactor = RH; break; } T = T1; return ; } //Phép quay đơn Right – Right void RotateRR (AVLTree &T) { AVLTree T1 = T->Rchild; T->Rchild = T1->Lchild; T1->Lchild = T; switch (T1->Balfactor) {case RH: T->Balfactor = EH; T1->Balfactor = EH; break; case EH: T->Balfactor = RH; T1->Balfactor = LH; break; } T = T1; return ; Trương Chí Tín Khoa Toán - Tin
  55. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 55 – } //Phép quay kép Left – Right void RotateLR(AVLTree &T) { AVLTree T1 = T->Lchild, T2 = T1->Rchild; T->Lchild = T2->Rchild; T2->Rchild = T; T1->Rchild = T2->Lchild; T2->Lchild = T1; switch (T2->Balfactor) {case LH: T->Balfactor = RH; T1->Balfactor = EH; break; case EH: T->Balfactor = EH; T1->Balfactor = EH; break; case RH: T->Balfactor = EH; T1->Balfactor = LH; break; } T2->Balfactor = EH; T = T2; return ; } //Phép quay kép Right-Left void RotateRL(AVLTree &T) { AVLTree T1 = T->RLchild, T2 = T1->Lchild; T->Rchild = T2->Lchild; T2->Lchild = T; T1->Lchild = T2->Rchild; T2->Rchild = T1; switch (T2->Balfactor) {case LH: T->Balfactor = EH; T1->Balfactor = RH; break; case EH: T->Balfactor = EH; T1->Balfactor = EH; break; case RH: T->Balfactor = LH; T1->Balfactor = EH; break; } T2->Balfactor = EH; T = T2; return ; } Sau đây là thao tác cân bằng lại khi cây bị lệch trái hay lệch phải. //Cân bằng lại khi cây bị lệch trái int LeftBalance(AVLTree &T) { AVLTree T1 = T->Lchild; switch (T1->Balfactor) { case LH : RotateLL(T); return 2; //cây T không bị lệch Trương Chí Tín Khoa Toán - Tin
  56. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 56 – case EH : RotateLL(T); return 1;//cây T bị lệch phải case RH : RotateLR(T); return 2; } return 0; } //Cân bằng lại khi cây bị lệch phải int RightBalance(AVLTree &T) { AVLTree T1 = T->Rchild; switch (T1->Balfactor) { case LH : RotateRL(T); return 2; //cây T không bị lệch case EH : RotateRR(T); return 1; //cây T bị lệch trái case RH : RotateRR(T); return 2; } return 0; } IV.4. Chèn một phần tử vào cây AVL Việc chèn một phần tử vào cây AVL xảy ra tương tự như trên cây nhị phân tìm kiếm. Tuy nhiên, sau thi chèn xong, nếu chiều cao của cây thay đổi tại vị trí thêm vào, ta phải lần ngược lên gốc để kiểm tra xem có nút nào bị mất cân bằng hay không. Nếu có, ta chỉ phải cân bằng lại ở nút này. (Việc cân bằng lại chỉ cần thực hiện một lần tại nơi mất cân bằng) Hàm chèn trả về các trị –1, 0, 1 hay 2 tương ứng khi: không đủ bộ nhớ cấp phát cho một nút của cây hoặc gặp nút đã có trên cây hoặc thành công hoặc chiều cao của cây bị tăng sau khi chèn. Khi chèn một nút vào cây AVL, ta cần sử dụng hàm cấp phát bộ nhớ cho một nút của cây AVL. AVLTree CấpPhátAVL() { AVLTree Tam= new AVLTreeNode; if (Tam == NULL) cout Data == x) return 0; //Đã có nút trên cây Trương Chí Tín Khoa Toán - Tin
  57. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 57 – if (T-> Data > x) { Kqủa = ChènAVL(T->Lchild,x);//chèn x vào cây con trái của T if (Kqủa Balfactor) { case LH: LeftBalance(T); return 1;//trước khi chèn,T lệch trái case EH: T->Balfactor=LH;return 2;//trước khi chèn,T không lệch caseRH:T->Balfactor=EH; return 1;//trước khi chèn,T lệch phải } } else // T-> Data Rchild,x);//chèn x vào cây con phải của T if (Kqủa Balfactor) { case LH: T->Balfactor = EH; return 1; //trước khi chèn,T lệch trái case EH:T->Balfactor=RH; return 2;//trước khi chèn,T không lệch case RH : RightBalance(T); return 1; //trước khi chèn,T lệch phải } } } else //T==NULL { if ((T = CấpPhátAVL()) == NULL) return –1; //Thiếu bộ nhớ T->Data = x; T->Balfactor = EH; T->Lchild = T->Rchild = NULL; return 2; //thành công và chiều cao của cây tăng } } IV.5. Xóa một phần tử khỏi cây AVL Việc xóa một phần tử ra khỏi cây AVL diễn ra tương tự như đối với cây nhị phân tìm kiếm; chỉ khác là sau khi hủy, nếu cây AVL bị mất cân bằng, ta phải cân bằng lại cây. Việc cân bằng lại cây có thể xảy ra phản ứng dây chuyền. Trương Chí Tín Khoa Toán - Tin
  58. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 58 – Hàm XóaAVL sẽ trả về trị 1 hoặc 0 hoặc 2 tùy theo việc hủy thành công hoặc không có x trên cây hoặc sau khi hủy, chiều cao của cây bị giảm. int XóaAVL(AVLTree &T, ElementType x) { int Kqủa; if (T== NULL) return 0; // không có x trên cây if (T-> Data > x) { Kqủa = XoáAVL(T->Lchild,x); // tìm và xóa x trên cây con trái của T if (Kqủa Balfactor) { case LH : T->Balfactor = EH; return 2; //trước khi xóa,T lệch trái case EH : T->Balfactor = RH; return 1; //trước khi xóa,T không lệch case RH : return RightBalance(T); //trước khi xóa,T lệch phải } } else if (T-> Data Rchild,x); // tìm và xóa x trên cây con phải của T if (Kqủa Balfactor) { case LH : return LeftBalance(T); //trước khi xóa,T lệch trái case EH : T->Balfactor = LH; return 1; //trước khi xóa,T không lệch case RH : T->Balfactor = EH; return 2; //trước khi xóa,T lệch phải } } else //T->Data== x { AVLTree p = T; if (T->Lchild == NULL) { T = T->Rchild; Kqủa = 2; } else if (T->Rchild == NULL) { T = T->Lchild; Kqủa = 2; } else // T có cả 2 con { Kqủa = TìmPhầnTửThayThế(p,T->Rchild); // tìm phần tử thay p để xóa trên nhánh phải của T if (Kqủa Balfactor) { case LH : return LeftBalnce(T); case EH : T->Balfactor = LH; return 2; Trương Chí Tín Khoa Toán - Tin
  59. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 59 – case RH : T->Balfactor = EH; return 2; } } delete p; return Kquả; } } // Tìm phần tử thay thế int TìmPhầnTửThayThế(AVLTree &p, AVLTree &q) { int Kqủa; if (q->Lchild) { Kqủa = TìmPhầnTửThayThế(p, q->Lchild); if (Kqủa Balfactor) { case LH : q->Balfactor = EH; return 2; case EH : q->Balfactor = RH; return 1; case RH : return RightBalance(q); } } else { p->Data = q->Data; p = q; q = q->Rchild; return 2; } } * Nhận xét: - Thao tác thêm một nút có độ phức tạp O(1). - Thao tác huỷ một nút có độ phức tạp O(h) - Với cây cân bằng, trung bình: 2 lần thêm vào cây thì cần 1 lần cân bằng lại, 5 lần hủy thì cần 1 lần cân bằng lại. - Việc hủy một nút có thể phải cân bằng dây chuyền các nút từ gốc đến phần tử bị hủy, trong khi thêm vào 1 nút chỉ cần 1 lần cân bằng cục bộ. - Độ dài đường tìm kiếm trung bình trong cây AVL gần bằng cây cân bằng hoàn toàn (log2 n), nhưng việc cân bằng lại đơn giản hơn nhiều. - Một cây cân bằng AVL không bao giờ cao hơn 45% cây cân bằng hoàn toàn tương ứng. Trương Chí Tín Khoa Toán - Tin
  60. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 60 – - CHƯƠNG III: B - CÂY Cấu trúc dữ liệu cây nhị phân hay cây BST được dùng cho các sơ đồ tìm kiếm nội trú: nghĩa là khối dữ liệu cần tìm phải đủ nhỏ để có thể lưu trữ toàn bộ vào bộ nhớ trong. Để giải quyết cho sơ đồ tìm kiếm ngoại trú, với khối lượng dữ liệu lớn, phải lưu trữ trên bộ nhớ ngoài, người ta nghiên cứu cây chứa những nút có nhiều nhánh gọi là cây nhiều nhánh. I. ĐẶC ĐIỂM CÂY NHIỀU NHÁNH - Các nút của cây được lưu trữ trên bộ nhớ ngoài - Các con trỏ được biểu diễn bởi địa chỉ bộ nhớ ngoài (thay vì địa chỉ bộ nhớ trong) - Nếu có một phần tử trên bộ nhớ ngoài được truy xuất thì toàn bộ một nhóm nào đó các phần tử có liên quan cũng được truy xuất theo mà không tốn nhiều thời gian. Điều này dẫn đến một cây được chia thành nhiều cây con và các cây con được biểu diễn thành các đơn vị mà các phần tử của đơn vị được truy xuất đồng thời. Ta gọi các cây con này là các trang. * Ví dụ: Cây nhị phân được chia thành nhiều trang. Mỗi trang gồm 7 nút. Những nút thuộc cùng một trang được truy xuất đồng thời. O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O Trương Chí Tín Khoa Toán - Tin
  61. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 61 – Trang Một trong những cây nhiều nhánh quan trọng là: cấu trúc dữ liệu B - cây bậc n (do R. Bayer đề xuất vào năm 1970). II. ĐỊNH NGHĨA B – CÂY (bậc n) B-cây bậc n là một cây tổng quát thỏa các tính chất sau: - Mỗi trang có tối đa 2* n phần tử (khóa). - Mỗi trang (ngọai trừ trang gốc) có ít nhất n phần tử. - Mỗi trang hoặc là trang lá, hoặc có m+1 trang con với m là số khóa của trang này. - Mọi trang lá phải có cùng mức. - Các khóa trên mỗi trang được sắp thứ tự và phân các khoá lưu trữ trong các trang con (nếu có) * Ví dụ: B - cây cấp 2 , có 3 mức: Trang gốc 25 10 20 30 40 Trang con 2 5 7 8 13 14 15 18 22 24 26 27 28 32 37 38 41 42 45 III. TÌM KIẾM MỘT PHẦN TỬ TRÊN B - CÂY * Ví dụ2: Xét B - cây cấp 2 lưu trữ các số nguyên trong ví dụ trên đây. Giả sử ta cần tìm phần tử 22 có trong cây hay không ? So sánh với nút gốc ta thấy 22 < 25, ta tìm 22 trong nhánh con bên trái của nút 25: 10 20 2 5 7 8 13 14 15 18 22 24 Trương Chí Tín Khoa Toán - Tin
  62. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 62 – Ta lại so sánh 22 với các phần tử trong nút gốc của cây mới, ta thấy 22 > 20, ta sẽ tìm trong nhánh con phải của phần tử 20: 22 24 Trong việc ứng dụng cài đặt lưu trữ B- cây, mỗi trang sẽ được lưu trữ trên bộ nhớ thứ cấp như một khối file (một lượng thông tin lớn nhất có thể nạp vào bộ nhớ trong ở một lần truy nhập). Mỗi khi cần tìm kiếm, một trang nào đó sẽ được nạp vào bộ nhớ trong, phần còn lại của cây vẫn nằm lại trên bộ nhớ thứ cấp. * Tổng quát, xét một trang e có dạng sau và cần tìm khoá x e p0 k1 p1 k2 p2 k3 pm-1 km pm (Trang chứa các (Trang chứa các (Trang chứa các phần tử k1 và km) Giả sử trang trên đã được nạp vào bộ nhớ trong. Trước hết, tìm x trong dãy khoá k1, k2, , km (Nếu m lớn thì tìm theo phương pháp nhị phân). Nếu thấy, việc tìm kết thúc. Nếu không tìm thấy (x ≠ ki, ∀ i=1 m) thì ta sẽ gặp một trong các tình huống sau : + ki < x < ki+1 với 1 ≤ i ≤ m-1 : tiếp tục tìm trên trang có địa chỉ do con trỏ pi chỉ đến. + km < x : tiếp tục tìm trên trang do pm trỏ đến. + x < k1 : tiếp tục tìm trên trang do p0 trỏ đến. Trong trường hợp nếu có con trỏ pi nào đó chỉ đến NULL, nghĩa là không còn trang con nữa thì trong B - cây không có phần tử có khoá x, việc tìm kiếm chấm dứt. Định nghĩa cấu trúc trang const n = ; // cấp của B-cây #define nn 2*n // kích thước tối đa của một trang typedef KeyType; Trương Chí Tín Khoa Toán - Tin
  63. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 63 – typedef Page *Ref ; // địa chỉ của trang typedef struct { KeyType Key; // khóa Ref p; // chứa địa chỉ đến trang con bên phải của khóa int Count; // đại diện cho các dữ liệu còn lại } Item; // phần tử của trang typedef struct { int m; // số phần tử của trang Ref p0; // địa chỉ trang con có các khoá < e1.key Item e[nn]; // các phần tử của trang } Page; // trang IV. THÊM MỘT PHẦN TỬ VÀO B - CÂY * Ví dụ: Xét B - cây cấp 2 như sau và ta cần thêm phần tử 22: Trang A 20 B 7 10 15 18 C 26 30 35 40 Ta nhận thấy: - không có khoá 22 trong cây - không thể thêm 22 vào trang C vì nó đã đầy - khi đó trang C được tách thành 2 trang (1 trang D mới được cấp phát) - 2*n+1 khoá (kể cả khóa mới) trên trang C cũ được phân bố đều lên C và D mới, khoá giữa được chuyển lên một mức ở trang cha A. Trang A 20 30 B 7 10 15 18 C 22 26 D 35 40 Nếu thêm phần tử x vào Trương Chí Tín Khoa Toán - Tin
  64. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 64 – Quá trình tìm kiếm và thêm một phần tử vào trên B - cây Qúa trình thêm một phần tử x vào B - cây xảy ra như sau : Tìm x trên B-cây. • Nếu tìm thấy, không cần thêm x vào B-cây (hoặc tăng số lần xuất hiện của x lên 1 đơn vị). • Nếu không tìm thấy x, thì sẽ biết địa chỉ trang lá L cần thêm x vào. Giả sử trang lá L có m phần tử: - nếu m < 2n (trang lá L chưa đầy) thì việc thêm x chỉ xảy ra trên trang lá đó. - nếu m=2n (trang lá L đầy) thì phải cấp phát thêm trang lá mới L2. Phân phối đều 2*n+1 phần tử (sắp tăng 2*n phần tử trên L và kể cả x) trên L cũ vào L, L2 mới và trang cha của L như sau: n phần tử nhỏ nhất của L cũ vẫn giữ lại trên trang L mới, đưa n phần tử lớn nhất của L cũ vào trang lá mới L2, còn phần tử giữa – phần tử thứ n+1 trên L cũ – được đưa vào trang cha và chỉnh lại các địa chỉ trên trang cha chỉ đến các trang con cho phù hợp. Khi đó, nếu trang cha có số phần tử : . không lớn hơn 2*n (trang cha chưa tràn): thì việc thêm x vào B-cây kết thúc. . bằng 2*n +1 (trang cha bị tràn): thì trang cha bị tách thành 2 trang mới và làm tương tự như trên. Trong trường hợp tồi nhất, việc tách trang có thể lan truyền đến trang gốc, làm cho trang gốc tách thành hai trang, trang gốc mới được cấp phát và B - cây sẽ tăng độ cao . Do sự kiện này người ta nói B - cây có thói quen tăng trưởng lạ lùng: nó lớn lên từ lá cho đến gốc. IV.1. Giải thuật tìm và thêm một phần tử vào B - cây * Input: - x: khoá cần tìm và thêm vào B-cây - root: địa chỉ trang gốc * Output: - Nếu việc thêm thành công, trả về trị đúng 1: nếu có sự tách trang và dẫn đến chiều cao của cây tăng thì: . h = 1 (true) Trương Chí Tín Khoa Toán - Tin
  65. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 65 – . u là phần tử đựơc thêm vào trang cha của a. - Trả về trị sai 0 trong trường hợp ngược lại. Int Search_Insert (KeyType x, Ref a, Boolean &h, Item &u) { if (a == NULL) // x không có trên cây { h = 1; u.Key = x; u.p = NULL; } else { // tìm khóa x trên trang a "Tìm nhị phân x trên trang a"; if "Tìm thấy" then {"Tăng số lần xuất hiện khoá x lên 1"; h = 0; } else { Search (x,TrangCon(a),h,u); if (h) // chuyển u lên cây if (Số phần tử trên trang a < 2n) then {Chèn u vào trang a; h = 0;} else if (!"Tách trang và chuyển phần tử giữa lên") return 0; } } return 1; } - Khi gọi Search_Insert trong chương trình chính mà h mang trị true thì điều đó có nghĩa là việc tách trang lan truyền đến trang gốc và trang gốc có thể bị tách trang. - Vì trang gốc có vai trò đặc biệt nên việc tách trang gốc được lập trình riêng, nó bao gồm việc cấp phát trang mới và thêm vào một phần tử, kết quả là trang gốc mới chỉ chứa 1 phần tử. IV.2. Giải thuật xây dựng B - cây Trương Chí Tín Khoa Toán - Tin
  66. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 66 – Việc xây dựng B – cây cấp n bao gồm việc khởi tạo B – cây rỗng vào việc gọi liên tiếp thủ tục Search_Insert trên đây. int XâyDựng_B_Cây(Ref &root) {int h; Item u; KeyType x; root = NULL; while (CònNhậpLiệu(x)) { if (!Search_Insert(x,root,h,u)) return 0; if (h) // chiều cao của cây tăng { Ref q = root; if (! CấpPhátTrang(root,n)) return 0; root->m = 1; // số phần tử của trang gốc mới bằng 1 root->p0 = q; root->e[1] = u; // u là phần tử được đưa lên trên trang cha root } } return 1; } * Ví dụ: Tạo một B - cây cấp 2 từ dãy khoá sau : 20 ; 40 10 30 15 ; 35 7 26 18 22 ; 5 ; 42 13 46 27 8 32 ; 38 24 45 25; (Các dấu ‘;’ chỉ ra các vị trí "đột biến" mỗi khi có sự cấp phát trang). Các bước tạo chính khi có sự tách trang là: 20; 20 20 30 10 15; 30 40 7 10 15 18 22; 26 35 40 10 20 30 Trương Chí Tín Khoa Toán - Tin
  67. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 67 – 5; 7 15 18 22 26 35 40 10 20 30 40 5 7 8 13 15 18 22 26 27 32; 35 42 46 25; 10 20 30 40 5 7 8 13 15 18 22 24 26 27 32 35 38 42 45 46 (Hình 1) V. XÓA MỘT PHẦN TỬ KHỎI B - CÂY V.1. Hai tình huống loại bỏ một khóa trên B-cây + Phần tử cần loại bỏ thuộc trang lá : việc loại bỏ diễn ra đơn giản. + Phần tử cần loại bỏ không thuộc trang lá: việc loại bỏ phức tạp hơn. - Trong tình huống thứ 2, phần tử cần loại bỏ được thay thế bởi 1 trong 2 phần tử kề nó (về mặt giá trị) nằm ở trang lá và có thể loại bỏ dễ dàng. - Việc tìm phần tử kề được thực hiện bằng cách đi dọc trên nhánh con trái theo các con trỏ cực phải đến trang lá P và phần tử kề là phần tử mút phải trên trang P. Thay phần tử cần loại bỏ bởi phần tử này và giảm kích thước trang P đi 1. - Sau khi giảm, kiểm tra số phần tử m trên trang P. Nếu m < n thì cấu trúc B - cây bị vi phạm. Khi đó, thực hiện các thao tác để xử lý tình Trương Chí Tín Khoa Toán - Tin
  68. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 68 – trạng bị vi phạm này (trong trường hợp này dùng biến h kiểu boolean để chỉ ra điều kiện cạn này - underflow condition ). - Để xử lý trang bị cạn, người ta "nối" một phần tử thuộc trang lân cận. Ta gọi Q là trang anh em bên trái hay bên phải của trang P. Ta phân bố đều các phần tử trên cả 2 trang P và Q. Việc này gọi là "làm Cân Bằng" (balancing). - Tuy nhiên có thể có trường hợp trang anh em Q chỉ còn n phần tử, (lúc này tổng số phần tử trên trang P và Q là 2n-1). Khi đó ta trộn (merge) 2 trang thành 1 trang P, cộng thêm 1 phần tử giữa lấy từ trang cha của trang P và Q, sau đó bỏ trang Q. Đây là quá trình ngược của sự tách trang. - Một lần nữa, việc lấy đi một phần tử thuộc trang cha có thể làm cho kích thước trang < n (bị cạn). Khi đó cần phải cân bằng hay trộn trang ở mức thấp hơn và quá trình này có khả năng lan truyền đến trang gốc. Nếu kích thước trang gốc giảm xuống 0 thì bỏ trang gốc và như vậy chiều cao của cây bị giảm đi. Đây là cách duy nhất làm giảm chiều cao của B- cây. V.2. Giải thuật loại bỏ một khóa trên B-cây * Input: - x : khoá cần tìm để xóa. - a : trang hiện thời đang tìm. * Output: Nếu h == True : cho biết gặp tình trạng bị cạn cần phải điều chỉnh với trang kế hoặc trộn lại Delete (KeyType x, Ref &a, Boolean &h) { if (a == NULL) // x không có trên cây then h = 0; else { // tìm kiếm x trên trang a "Tìm kiếm nhị phân "; "Cho q là trang con trái của e[k] trong trang a"; /*Trang q được xác định sau khi tìm nhị phân : x = e[k].key hoặc e[k -1].key < x < e[k].key */ if "Tìm thấy " then // tìm thấy x ở vị trí k: - xóa e[k] của trang a if "q là trang lá" then "Bỏ e[k], giảm m đi 1, gán h bởi m < n"; Trương Chí Tín Khoa Toán - Tin
  69. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 69 – else {Del(a,q,k,h); // tìm phần tử bị xóa thế x if (h) then "Điều chỉnh với trang kế hoặc trộn lại"; // Underflow } else { // không tìm thấy Delete(x,q,h); if (h) then "Điều chỉnh với trang kế hoặc trộn lại"; // Underflow } } return ; } - Thủ tục Underflow thực hiện việc "Điều chỉnh với trang kế hoặc trộn lại". - Thủ tục Del thực hiện việc thay thế phần tử mép phải (cuối cùng) của trang lá cực phải cho phần tử cần bị xóa x=e[k].key. Del (Ref a, Ref p, int k, Boolean &h) { q = trang con phải của phần tử mép phải của p; if "q không phải là trang lá" then { Del (a,Trang_Con_Cuối(p), k, h); if (h) then "Điều chỉnh với trang kế hoặc trộn lại"; // Underflow } else { "Thay phần tử cuối cùng của trang p vào phần tử bị loại bỏ e[k], giảm m đi 1, gán h bởi m < n"; } return ; } * Ví dụ: Xét B-cây cấp 2 như hình 1 trong phần IV.4.4. Lần lượt loại bỏ các khóa : 25 45 24; 38 32; 8 27 46 13 42; 5 22 18 26; 7 35 15; Trương Chí Tín Khoa Toán - Tin
  70. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 70 – Dấu ‘;’ chỉ ra các vị trí “đột biến” tại đó có trang bị loại bỏ. (Việc điều chỉnh với trang kế xảy ra với trang anh em (ruột) phải trước, nếu không thể mới xét anh em trái; sau đó, nếu không thể, mới sát nhập với anh em phải; nếu không có anh em phải mới đến lượt sát nhập anh em trái). + Cây sau khi loại bỏ khoá 25: 24” 10 18 30 40 5 7 8 13 15 20 22 26 27 32 35 38 42 45’ 46 + Cây sau khi loại bỏ các khoá 45, 24: 10 22 30 40 5 7 8 13 15 18 20 26 27 32’’ 35 38’ 42 46 + Cây sau khi loại bỏ các khoá 38, 32: 10 22 30 5 7 8’ 13 15 18 20 26 27’’ 35 40 42 46 + Cây sau khi loại bỏ các khoá 8, 27 : 10 22 35 5 7 13” 15 18 20 26 30 40 42’’’ 46’ Trương Chí Tín Khoa Toán - Tin
  71. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 71 – + Cây sau khi loại bỏ các khóa 46, 13, 42: 10 22” 5’ 7 15 18 20 26 30 35 40 + Cây sau khi loại bỏ các khóa 5, 22: 15 26’’ 7 10 18’ 20 30 35 40 + Cây sau khi loại bỏ các khóa 18, 26: 15 7’ 10 20 30 35” 40 + Cây sau khi loại bỏ các khóa 7, 35: 20 10 15’ 30 40 + Cây sau khi loại bỏ khóa 15: 10 20 30 40 Trương Chí Tín Khoa Toán - Tin
  72. Giáo trình cấu trúc dữ liệu và thuật toán 2 - 72 – CHƯƠNG IV: BẢNG BĂM I.ĐẠT VẤN ĐỀ, MỤC ĐÍCH, Ý NGHĨA Một trong những nhiệm vụ chính của tin học, ngoài việc lưu trữ thông tin, là khai thác và xử lý thông tin. Trong việc khai thác thông tin, việc tìm kiếm đóng vai trò quan trọng. Ngoài các phương pháp tìm kiếm đã biết như tìm kiếm tuyến tính trên dãy các đối tượng chưa sắp hay tìm kiếm nhị phân trên dãy các đối tượng đã sắp, người ta còn xét các phương pháp khác rất hiệu quả. Phương pháp biến đổi khoá là một phương pháp tìm kiếm hữu hiệu như vậy. Sở dĩ các phương pháp tìm kiếm thông thường theo giá trị khóa không thật hiệu quả là do, trong các phương pháp này, việc truy nhập đến một đối tượng trong mảng ít liên quan trực tiếp đến chính bản thân giá trị khóa của đối tượng đó. Phương pháp biến đổi khóa (key transformation) là phương pháp tham khảo trực tiếp các đối tượng trong bảng thông qua phép biến đổi số học trên những khoá (key) để biết được địa chỉ tương ứng của các đối tượng trong bảng. Khi áp dụng các phương pháp biến đổi khóa trong việc xây dựng dãy các đối tượng trong bảng và tìm kiếm một đối tượng trên bảng đó, ta phải tốn thêm thời gian cho các phép biến đổi số học trên những khóa và cho việc giải quyết tình trạng đụng độ. II. PHƯƠNG PHÁP BIẾN ĐỔI KHÓA Xét dãy các đối tượng có kiểu T, để truy nhập đến một đối tượng thuộc dãy ta cần biết địa chỉ của nó. Gọi A là miền trị của các địa chỉ này. Giả sử trong kiểu T, có một trường khóa (key) thuộc vào miền trị K nào đó. Phép biến đổi khoá là một ánh xạ thích hợp H từ tập các khóa K đến tập các địa chỉ A: H : K → A Thông thường dãy các đối tượng được lưu trong một mảng. Khi đó H là ánh xạ biến đổi khóa thành chỉ số trong mảng. Trương Chí Tín Khoa Toán - Tin