Tổng quan về giáo trình

Tài liệu bài giảng "Cấu trúc dữ liệu và Giải thuật" (mã môn học: CO2003), chuyên đề "Chương 6: Cây" (Chapter 6 - Tree) được biên soạn bởi TS. Nguyễn Đức Dũng thuộc Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách Khoa – Đại học Quốc gia TP.HCM. Trong khung chương trình đào tạo kỹ sư và cử nhân ngành Khoa học Máy tính và Kỹ thuật Máy tính, môn học CO2003 giữ vai trò là khối kiến thức cơ sở ngành bắt buộc, làm nền tảng cho các học phần chuyên sâu về cấu trúc dữ liệu nâng cao, tối ưu hóa thuật toán, hệ quản trị cơ sở dữ liệu và kỹ thuật lập trình hệ thống.

Mục tiêu học tập của bài giảng (Learning Outcomes) được cụ thể hóa thành hệ thống các chuẩn đầu ra đo lường được:

  • Chuẩn L.1: Định nghĩa và mô tả các khái niệm cây nhị phân (binary tree), cây nhị phân hoàn chỉnh (complete binary tree), cây nhị phân cân bằng (balanced binary tree), cây AVL và cây đa phân loại (multi-way tree/B-tree).
  • Chuẩn L.2 & L.3: Mô tả cấu trúc lưu trữ và liệt kê, thiết kế các phương thức thao tác trên cây bằng mã giả (pseudocode).
  • Chuẩn L.4 & L.5: Phân tích tầm quan trọng của tính chất cân bằng, nhận diện các trường hợp mất cân bằng trên cây AVL và B-tree, đồng thời giải quyết từng bước bằng hình học minh họa.
  • Chuẩn L.6 & L.7: Cài đặt cây nhị phân và cây AVL bằng ngôn ngữ C/C++ nhằm ứng dụng giải quyết các bài toán tìm kiếm và xử lý dữ liệu thực tế.
  • Chuẩn L.8: Đánh giá thực nghiệm và phân tích độ phức tạp tính toán thông qua ký pháp Big-O.

Tài liệu tiếp cận cấu trúc cây từ các định nghĩa lý thuyết đồ thị cơ bản, quy tắc toán học, đến mô hình hóa dữ liệu (danh sách liên kết, mảng), thuật toán duyệt, cây biểu thức và cây tìm kiếm nhị phân (BST). Cấu trúc bài giảng 59 slide thể hiện tính sư phạm logic, kết hợp giữa định nghĩa chuẩn tắc, biểu đồ cây và mã giả có chú thích tiền điều kiện (Pre) và hậu điều kiện (Post).

Nội dung kiến thức cốt lõi

Các chương/chủ đề chính

Nội dung bài giảng được cấu trúc tuần tự theo các khối chủ đề chính:

  1. Khái niệm cơ bản về cây (Basic Tree Concepts): Định nghĩa cây là tập hợp hữu hạn các phần tử (node) và các đường liên kết có hướng (branch). Xác định các thuật ngữ chuẩn xác: bậc của nút (degree), bậc vào (indegree), bậc ra (outdegree), nút gốc (root - có $indegree = 0$), nút lá (leaf - có $outdegree = 0$), nút nội (internal node), nút cha (parent), nút con (child), các nút anh em (siblings), tổ tiên (ancestor), hậu duệ (descendent), đường đi (path), mức của nút (level - khoảng cách từ gốc), chiều cao cây (height - mức lớn nhất của nút lá cộng 1) và cây con (subtree). Đồng thời, bài giảng phân loại ba hình thức biểu diễn cây: sơ đồ tổ chức (organization chart), danh sách mở ngoặc lồng nhau (parenthetical listing) và danh sách thụt đầu dòng (indented list).

  2. Cây nhị phân và các tính chất (Binary Trees & Properties): Khái niệm cây nhị phân là cấu trúc mà mỗi nút có tối đa 2 cây con (cây con trái và cây con phải). Hệ thống hóa các công thức toán học xác định biên số lượng nút và chiều cao: với $N$ nút, chiều cao tối thiểu $H_{min} = \lfloor \log_2 N \rfloor + 1$ và chiều cao tối đa $H_{max} = N$; với chiều cao $H$, số nút tối thiểu $N_{min} = H$ và số nút tối đa $N_{max} = 2^H - 1$. Hệ số cân bằng (balance factor) được định nghĩa qua công thức $B = H_L - H_R$, với cây cân bằng khi $B \in {-1, 0, 1}$. Phân biệt chính xác giữa cây hoàn chỉnh ($N = 2^H - 1$) và cây gần hoàn chỉnh (các nút ở mức cuối dồn về phía bên trái).

  3. Mô hình cài đặt cây nhị phân (Binary Tree Structure Implementations): Trình bày hai phương pháp tổ chức bộ nhớ:

    • Cài đặt bằng con trỏ liên kết (Linked implementation): Cấu trúc node gồm trường dữ liệu dataType (key và các field) cùng hai con trỏ left và right.
    • Cài đặt bằng mảng (Array-based implementation): Áp dụng tối ưu cho cây hoàn chỉnh hoặc gần hoàn chỉnh nhằm tiết kiệm chi phí con trỏ và truy xuất chỉ số nhanh.

  4. Các thuật toán duyệt cây (Binary Tree Traversals):

    • Duyệt theo chiều sâu (Depth-first traversal): Bao gồm Duyệt tiền thứ tự (Preorder - NLR: Node $\rightarrow$ Left $\rightarrow$ Right), Duyệt trung thứ tự (Inorder - LNR: Left $\rightarrow$ Node $\rightarrow$ Right), Duyệt hậu thứ tự (Postorder - LRN: Left $\rightarrow$ Right $\rightarrow$ Node). Mỗi thuật toán đều cung cấp giải thuật đệ quy chuẩn.
    • Duyệt theo chiều rộng (Breadth-first traversal - BFS): Thuật toán duyệt theo từng mức sử dụng hàng đợi bfQueue thông qua các thao tác createQueue(), enqueue(), dequeue(), emptyQueue(), destroyQueue().

  5. Cây biểu thức (Expression Trees): Mô hình biểu diễn biểu thức toán học với các nút lá là toán hạng (operand), nút gốc và các nút nội bộ là toán tử (operator), cây con là các biểu thức con. Cung cấp thuật toán chuyển đổi cây biểu thức sang ba dạng ký pháp: Trung tố (Infix - thuật toán infix có in dấu ngoặc), Hậu tố (Postfix/RPN - thuật toán postfix), Tiền tố (Prefix - thuật toán prefix).

  6. Cây tìm kiếm nhị phân (Binary Search Trees - BST): Định nghĩa tính chất BST: mọi khóa ở cây con trái nhỏ hơn khóa nút gốc; mọi khóa ở cây con phải lớn hơn hoặc bằng khóa nút gốc; các cây con đều là BST. Minh họa các mẫu cây BST hợp lệ và không hợp lệ. Đưa ra nguyên lý: duyệt Inorder trên BST tạo thành danh sách có thứ tự tăng dần. Cung cấp thuật toán tìm giá trị nhỏ nhất (findSmallestBST), giá trị lớn nhất (findLargestBST), tìm kiếm đệ quy (searchBST) và tìm kiếm lặp (iterativeSearchBST).

                    [Tree Concepts]
       [Binary Tree]              [Multi-way Tree / B-Tree]
[Properties]  [Traversals]      [Applications]

Kiến thức nền tảng được xây dựng

Giáo trình thiết lập hệ thống lý thuyết cấu trúc phân cấp dựa trên:

  • Nguyên lý phân cấp và quy nạp (Hierarchy & Induction): Mô hình hóa cấu trúc dữ liệu đệ quy (mỗi nút là gốc của một cây con).
  • Đại số quan hệ và logic cấu trúc: Hệ thống các ràng buộc về bậc, quan hệ cha - con, định tuyến nhánh đi, hệ thức cân bằng chiều cao $B = H_L - H_R$.
  • Mối liên hệ giữa cấu trúc lưu trữ và hiệu năng: So sánh không gian lưu trữ và truy cập giữa mảng tĩnh đối với cây gần hoàn chỉnh và con trỏ động đối với cây tổng quát.

Kỹ năng phát triển

Thông qua nội dung chuyên đề, người học được rèn luyện các kỹ năng cụ thể:

  • Kỹ năng kỹ thuật (Technical skills): Cài đặt cấu trúc dữ liệu trừu tượng (ADT) bằng ngôn ngữ C/C++, thao tác trên con trỏ động, xây dựng các hàm đệ quy và cấu trúc hàng đợi phụ trợ cho BFS.
  • Kỹ năng phân tích (Analytical skills): Phân tích hình thái cây, tính toán chiều cao, nhận diện các trạng thái mất cân bằng, đánh giá tính hợp lệ của cây tìm kiếm nhị phân.
  • Kỹ năng thực hành tính toán (Practical competencies): Đánh giá độ phức tạp thuật toán qua ký pháp Big-O đối với cấu trúc tuần tự, rẽ nhánh, lặp và đệ quy, phục vụ xây dựng hệ thống tìm kiếm dữ liệu.

Phương pháp giảng dạy và học tập

Phương pháp tiếp cận sư phạm (Pedagogical approach)

Bài giảng áp dụng mô hình tiếp cận từ trực quan hình học đến hình thức hóa toán học và hiện thực hóa thuật toán:

  1. Định nghĩa hình thức & minh họa đồ thị: Mỗi khái niệm (bậc, chiều cao, nút lá, nút nội) đều đi kèm sơ đồ trực quan có gắn nhãn cụ thể (ví dụ: nút $d$ có $indegree = 1$, $outdegree = 3$).
  2. Trừu tượng hóa bằng mã giả (Pseudocode): Các thuật toán duyệt cây (preOrder, inOrder, postOrder, breadthFirst), chuyển đổi biểu thức (infix, postfix, prefix) và tìm kiếm BST (searchBST, iterativeSearchBST) được viết theo chuẩn mã giả chặt chẽ, nêu rõ các thông số đầu vào (Pre) và trạng thái đầu ra (Post).
  3. Chuyển tiếp cài đặt mã nguồn: Kết nối trực tiếp từ mã giả sang mã nguồn C/C++ thông qua các cấu trúc struct node và kiểu dữ liệu trừu tượng.

Bài tập và minh họa ứng dụng

Tài liệu lồng ghép các bài toán điển hình:

  • Xác thực cây tìm kiếm nhị phân: Bài giảng đưa ra các slide phân tích cụ thể các trường hợp "Valid Binary Search Trees" và "Invalid Binary Search Trees" để sinh viên rèn luyện tư duy nhận diện tính chất phân cấp khóa.
  • Chuyển đổi biểu thức số học: Minh họa cây biểu thức với các toán tử +, -, *, / tại nút nội và các biến/hằng tại nút lá, áp dụng duyệt LNR để xuất biểu thức trung tố có ngoặc, duyệt LRN để xuất ký pháp Ba Lan ngược.
  • So sánh tìm kiếm đệ quy và lặp: Trình bày song song hai giải thuật searchBST (đệ quy) và iterativeSearchBST (vòng lặp while (root is not NULL) AND (root->data.key <> target)), giúp người học đối chiếu cơ chế quản lý ngăn xếp (stack frame) và hiệu năng bộ nhớ.

Hướng dẫn tự học và đánh giá

  • Tự học: Sinh viên cần nắm vững quy trình lần vết (dry-run) thuật toán duyệt trên giấy đối với các cây nhị phân mẫu, xác định chính xác thứ tự ghé thăm các nút của từng kiểu duyệt NLR, LNR, LRN và BFS.
  • Đánh giá: Kết quả học tập được đánh giá thông qua khả năng viết mã giả giải quyết bài toán mới, chuyển đổi mã giả thành mã C/C++ có khả năng biên dịch, và phân tích độ phức tạp thời gian/không gian dựa trên Big-O.

Điểm nổi bật và cập nhật

Tính chuẩn hóa theo chuẩn đầu ra ABET

Tài liệu được thiết kế bám sát hệ thống chuẩn đầu ra ngành (Outcomes L.1 đến L.8) theo tiêu chuẩn kiểm định quốc tế của Khoa Khoa học và Kỹ thuật Máy tính - ĐH Bách Khoa TP.HCM. Việc phân rã mục tiêu từ mức độ nhận biết khái niệm (L.1), thiết kế mã giả (L.2, L.3), phân tích toán học và tính chất cân bằng (L.4, L.5) đến cài đặt C/C++ (L.6, L.7) và đánh giá thực nghiệm (L.8) bảo đảm tính liên kết đào tạo nhất quán.

Tính liên kết ứng dụng thực tế

Bài giảng chỉ rõ 4 nhóm ứng dụng tiêu biểu của cấu trúc cây trong ngành máy tính:

  • Biểu diễn dữ liệu phân cấp (Hierarchical data) như cấu trúc thư mục, sơ đồ tổ chức doanh nghiệp.
  • Lưu trữ dữ liệu tối ưu hóa cho thao tác tìm kiếm nhanh (điển hình là Binary Search Tree kết hợp ưu điểm tìm kiếm nhanh của mảng có thứ tự và khả năng thêm/xóa linh hoạt của danh sách liên kết).
  • Biểu diễn danh sách dữ liệu có thứ tự thông qua phép duyệt Inorder.
  • Ứng dụng trong các thuật toán định tuyến mạng (Network routing algorithms) và trình biên dịch (Cây phân tích cú pháp biểu thức).

Đối tượng sử dụng giáo trình

  1. Sinh viên đại học:

    • Dành cho sinh viên năm thứ hai chuyên ngành Khoa học Máy tính, Kỹ thuật Máy tính, Công nghệ Thông tin, Hệ thống Thông tin thuộc Trường Đại học Bách Khoa – ĐHQG-HCM và các trường kỹ thuật.
    • Điều kiện tiên quyết (Prerequisites): Đã hoàn thành học phần Kỹ thuật lập trình (ngôn ngữ C/C++), nắm vững kỹ thuật thao tác con trỏ, cấp phát bộ nhớ động, lập trình đệ quy và các cấu trúc dữ liệu tuyến tính cơ bản (Danh sách liên kết, Hàng đợi Queue, Ngăn xếp Stack).

  2. Giảng viên và cán bộ giảng dạy:

    • Sử dụng làm khung bài giảng chuẩn cho các buổi giảng lý thuyết trên lớp và các bài thực hành phòng lab môn Cấu trúc dữ liệu và Giải thuật.
    • Tài liệu cung cấp sẵn khung mã giả chuẩn tắc giúp đồng bộ hóa phương pháp đánh giá sinh viên trong các kỳ thi học kỳ và kiểm tra lab.

  3. Người tự học và kỹ sư phần mềm:

    • Dùng làm tài liệu tra cứu học thuật về định nghĩa toán học của cây, cấu trúc lưu trữ và giải thuật tìm kiếm nhằm phục vụ ôn luyện nền tảng thuật toán, chuẩn bị cho các kỳ đánh giá kỹ thuật chuyên môn.

Câu hỏi thường gặp

1. Giáo trình này phù hợp với ai?

Tài liệu được thiết kế trực tiếp cho sinh viên ngành Khoa học Máy tính và Kỹ thuật Máy tính học môn CO2003 tại Trường ĐH Bách Khoa – ĐHQG-HCM, đồng thời phù hợp cho tất cả người học cần trang bị kiến thức chuẩn mực về cấu trúc dữ liệu cây ở bậc đại học.

2. Cần kiến thức nền nào để học chuyên đề này?

Người học cần có nền tảng vững chắc về ngôn ngữ lập trình C/C++ (đặc biệt là con trỏ, struct, đệ quy) và các cấu trúc dữ liệu cơ bản như mảng, danh sách liên kết, hàng đợi (Queue). Ngoài ra, kiến thức toán rời rạc về đồ thị và ký pháp Big-O là bắt buộc.

3. Điểm khác biệt của tài liệu này so với các bài viết trực tuyến là gì?

Tài liệu mang tính học thuật chuẩn tắc, bám sát bộ chuẩn đầu ra đo lường được (Learning Outcomes L.1 - L.8). Nội dung cung cấp đầy đủ các công thức toán học về biên chiều cao/số nút, phân tích rõ tiền điều kiện/hậu điều kiện của thuật toán mã giả và đưa ra các hình thái cây biểu thức, cây BST hợp lệ và không hợp lệ cụ thể.

4. Làm sao để tự học nội dung này đạt hiệu quả cao nhất?

Người học nên kết hợp ba bước: (1) Đọc kỹ định nghĩa và tính toán lại các ví dụ về mức, bậc, chiều cao trên giấy; (2) Lần vết các thuật toán duyệt (NLR, LNR, LRN, BFS) trên các cây mẫu; (3) Tự viết lại mã giả thành chương trình C/C++ hoàn chỉnh và kiểm thử với các trường hợp dữ liệu biên.

5. Có tài liệu bổ trợ nào kèm theo bài giảng?

Bài giảng đi kèm hệ thống bài tập thực hành lập trình C/C++ môn CO2003, các đồ án môn học liên quan đến cấu trúc cây (AVL Tree, B-Tree), cùng các chương tài liệu trước về Danh sách liên kết, Ngăn xếp, Hàng đợi và các chương kế tiếp về Heap, Đồ thị trong cùng môn học.

Kết luận

Bài giảng "Chương 6: Cây" môn Cấu trúc dữ liệu và Giải thuật (CO2003) của TS. Nguyễn Đức Dũng cung cấp hệ thống tri thức hoàn chỉnh và chuẩn xác về cấu trúc dữ liệu phân cấp. Từ các tiên đề lý thuyết đồ thị cơ bản, các công thức toán học về chiều cao, tài liệu dẫn dắt người học qua các mô hình cài đặt bộ nhớ, các kỹ thuật duyệt cây theo chiều sâu/chiều rộng, cấu trúc cây biểu thức và cây tìm kiếm nhị phân (BST). Lộ trình học tập được thiết kế mạch lạc, kết nối chặt chẽ giữa lý thuyết thuật toán và kỹ năng lập trình thực tế trên C/C++, đáp ứng chuẩn mực đào tạo kỹ sư công nghệ thông tin.