Phân Tích Giáo Trình: Cấu Trúc Cây (Trees) Trong Cấu Trúc Dữ Liệu Và Giải Thuật

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

Tài liệu bài giảng thuộc học phần Cấu trúc Dữ liệu và Giải thuật (Data Structures and Algorithms) do Lương Thế Nhân và Trần Giang Sơn biên soạn, 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 (Faculty of Computer Science and Engineering, University of Technology, VNU-HCM). Trong chương trình đào tạo kỹ sư và cử nhân các ngành Khoa học Máy tính, Kỹ thuật Máy tính và Công nghệ Thông tin, học phần này giữ vị trí kiến thức cơ sở ngành cốt lõi, làm cầu nối giữa kỹ thuật lập trình căn bản và các lĩnh vực chuyên sâu như lý thuyết đồ thị, trình biên dịch và hệ quản trị cơ sở dữ liệu.

Tài liệu tập trung vào Chương 6: Cấu trúc Cây (Chapter 6: Trees). Mục tiêu học tập (learning outcomes) của chương bao gồm:

  • Định nghĩa và phân loại cấu trúc cây tổng quát cùng các thuật ngữ toán học liên quan.
  • Xác định các đặc tính định lượng của cây nhị phân (chiều cao, số nút, tính cân bằng).
  • Trình bày và cài đặt các giải thuật duyệt cây theo chiều sâu (Depth-First Traversal) và theo chiều rộng (Breadth-First Traversal).
  • Xây dựng cấu trúc cây biểu thức (Expression Trees) và chuyển đổi các dạng biểu diễn tiền tố, trung tố, hậu tố.
  • Cài đặt và thao tác trên cấu trúc cây tìm kiếm nhị phân (Binary Search Trees - BST), bao gồm tìm kiếm (đệ quy và lặp), tìm giá trị cực trị và chèn nút.

Cấu trúc tài liệu tiếp cận theo hướng hình thức hóa toán học kết hợp mã giải thuật chuẩn mực (pseudocode). Tài liệu phân tách nội dung theo tiến trình tuyến tính từ lý thuyết tổng quát đến mô hình nhị phân, sau đó ứng dụng vào các bài toán cụ thể như xử lý biểu thức và tìm kiếm dữ liệu. Điểm đặc thù trong văn bản là việc cung cấp song ngữ các thuật ngữ chuyên ngành cùng các đặc tả tiền điều kiện (Pre-condition) và hậu điều kiện (Post-condition) cho từng thuật toán.

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

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

Chương 6 được tổ chức thành 4 phân phần lý thuyết và thuật toán chính:

Chapter 6: Trees

1. Khái niệm cơ bản về cây (Basic Tree Concepts - Mục 6.1 đến 6.11)

  • Định nghĩa hình thức: Một cây ($Tree$) gồm một tập hữu hạn các phần tử gọi là nút ($nodes$) và một tập hữu hạn các đường nối có hướng gọi là nhánh ($branches$) dùng để liên kết các nút.
  • Bậc và nhánh:
    • Bậc của nút ($Degree$): Tổng số nhánh liên kết với nút.
    • Nhánh vào ($Indegree\ branch$): Nhánh hướng về phía nút.
    • Nhánh ra ($Outdegree\ branch$): Nhánh hướng ra xa khỏi nút.
    • Ví dụ mẫu trên nút $d$: Có $1$ nhánh vào ($ad$) và $3$ nhánh ra ($dg, dh, di$), do đó bậc tổng cộng là $4$.
  • Hệ thống phân loại nút và quan hệ:
    • Nút gốc ($Root$): Nút đầu tiên có $Indegree = 0$. Mọi nút khác đều có $Indegree = 1$ và $Outdegree \ge 0$.
    • Nút lá ($Leaf$): Nút có $Outdegree = 0$.
    • Nút nội ($Internal\ node$): Nút không phải là gốc và không phải là lá, đóng vai trò đồng thời là con của một nút và là cha của nút khác.
    • Quan hệ phụ huynh - con cái ($Parent - Child$), nút anh em ($Siblings$ - các nút có cùng cha), tổ tiên ($Ancestor$) và hậu duệ ($Descendent$).
  • Thước đo cấu trúc:
    • Đường đi ($Path$): Chuỗi các nút kế tiếp nhau qua các nhánh.
    • Mức ($Level$): Khoảng cách từ nút đến gốc (gốc ở Level 0). Các nút anh em luôn nằm cùng một mức.
    • Chiều cao ($Height$): Mức của nút lá trên đường đi dài nhất từ gốc cộng thêm $1$.
    • Cây con ($Subtree$): Cấu trúc liên thông nằm phía dưới nút gốc.
  • Phương pháp biểu diễn cây: Sơ đồ tổ chức ($Organization\ chart$), danh sách thụt lề ($Indented\ list$), và danh sách lồng ngoặc ($Parenthetical\ listing$).
  • Ứng dụng thực tế: Biểu diễn dữ liệu phân cấp, lưu trữ dữ liệu tối ưu hóa cho tìm kiếm, biểu diễn danh sách có thứ tự và thuật toán định tuyến mạng ($Network\ routing\ algorithms$).

2. Cây nhị phân (Binary Trees - Mục 6.12 đến 6.29)

  • Định nghĩa: Cây nhị phân là cấu trúc rỗng hoặc bao gồm một nút gốc liên kết với tối đa hai cây con là cây con trái ($Left\ subtree$) và cây con phải ($Right\ subtree$).
  • Các tính chất toán học:
    • Với $N$ nút lưu trữ trong cây:
      • Chiều cao tối thiểu: $H_{min} = \lfloor \log_2 N \rfloor + 1$.
      • Chiều cao tối đa: $H_{max} = N$.
    • Với cây có chiều cao $H$:
      • Số nút tối thiểu: $N_{min} = H$.
      • Số nút tối đa: $N_{max} = 2^H - 1$.
  • Độ cân bằng ($Balance$): Hệ số cân bằng $B = H_L - H_R$ (chênh lệch chiều cao giữa cây con trái và cây con phải). Cây cân bằng có $B \in {0, -1, 1}$ và các cây con cũng phải cân bằng.
  • Phân loại:
    • Cây đầy đủ ($Complete\ tree$): Số nút đạt tối đa $N = 2^H - 1$, tất cả các mức đều chứa đầy đủ nút.
    • Cây gần đầy đủ ($Nearly\ complete\ tree$): Đạt chiều cao tối thiểu $H = \lfloor \log_2 N \rfloor + 1$, các nút ở mức cuối cùng được điền dồn về phía bên trái.
  • Cấu trúc lưu trữ:
    • Cài đặt liên kết ($Linked\ implementation$): Sử dụng con trỏ node gồm các trường data <dataType>, left <pointer>, right <pointer>.
    • Cài đặt dựa trên mảng ($Array-based\ implementation$): Phù hợp cho cây đầy đủ và cây gần đầy đủ.
  • Các giải thuật duyệt cây:
    • Duyệt theo chiều sâu (Depth-First Traversal):
      • Tiền tự ($Preorder\ traversal$ - NLR): Xử lý nút gốc trước, sau đó đến cây con trái và cây con phải (process(root) $\rightarrow$ preOrder(root->left) $\rightarrow$ preOrder(root->right)).
      • Trung tự ($Inorder\ traversal$ - LNR): Xử lý cây con trái, nút gốc, sau đó đến cây con phải (inOrder(root->left) $\rightarrow$ process(root) $\rightarrow$ inOrder(root->right)).
      • Hậu tự ($Postorder\ traversal$ - LRN): Xử lý cây con trái, cây con phải, sau đó đến nút gốc (postOrder(root->left) $\rightarrow$ postOrder(root->right) $\rightarrow$ process(root)).
    • Duyệt theo chiều rộng (Breadth-First Traversal): Duyệt theo từng mức ngang sử dụng hàng đợi phụ trợ (bfQueue), lần lượt đưa con trái và con phải vào hàng đợi (enqueue) và lấy ra xử lý (dequeue).

3. Cây biểu thức (Expression Trees - Mục 6.30 đến 6.35)

  • Cấu trúc: Mỗi nút lá chứa một toán hạng ($operand$); nút gốc và các nút nội chứa toán tử ($operator$); các cây con đóng vai trò là các biểu thức con ($sub-expressions$).
  • Thuật toán xuất biểu thức:
    • Xuất biểu thức trung tố (infix): Duyệt LNR kèm theo việc in dấu ngoặc đơn mở và đóng bao quanh các biểu thức con.
    • Xuất biểu thức hậu tố (postfix): Duyệt LRN.
    • Xuất biểu thức tiền tố (prefix): Duyệt NLR.

4. Cây tìm kiếm nhị phân (Binary Search Trees - Mục 6.36 đến 6.49)

  • Đặc tính: Cây nhị phân trong đó mọi phần tử ở cây con trái có giá trị nhỏ hơn nút gốc; mọi phần tử ở cây con phải có giá trị lớn hơn hoặc bằng nút gốc; mỗi cây con bản thân nó cũng là một BST.
  • Tính chất duyệt: Phép duyệt trung tự ($Inorder\ traversal$) trên cây BST tạo ra một danh sách các phần tử đã được sắp xếp tăng dần.
  • Các thuật toán chuẩn:
    • findSmallestBST(root): Duyệt đệ quy sang nhánh trái (root->left) cho đến khi gặp nút không có con trái.
    • findLargestBST(root): Duyệt đệ quy sang nhánh phải (root->right) cho đến khi gặp nút không có con phải.
    • searchBST(root, target): Tìm kiếm đệ quy dựa trên so sánh khóa target với root->data.key.
    • iterativeSearchBST(root, target): Tìm kiếm dạng vòng lặp while (root is not NULL) AND (root->data.key <> target).
    • iterativeInsertBST(root, new): Chèn một nút mới vào vị trí lá hoặc vị trí tương đương nút lá (nút có một nhánh rỗng).

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

Tài liệu củng cố ba khối kiến thức nền tảng:

  1. Lý thuyết đồ thị và toán rời rạc ứng dụng: Cung cấp các công thức toán học về quan hệ giữa số lượng nút, số cạnh và chiều cao cây ($H_{min}, H_{max}, N_{min}, N_{max}$).
  2. Cơ chế quản lý bộ nhớ: Phân tích sự khác biệt về không gian và địa chỉ giữa mô hình mảng tuần tự và mô hình con trỏ liên kết động.
  3. Kỹ thuật thiết kế giải thuật: Vận dụng đệ quy cho các cấu trúc phân cấp và sử dụng cấu trúc dữ liệu bổ trợ (Queue) để khử đệ quy trong phép duyệt mức.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật: Khả năng phân tích mã giả, chuyển đổi giải thuật từ dạng đệ quy sang dạng vòng lặp lặp lại, và cài đặt cấu trúc dữ liệu dạng cây bằng ngôn ngữ lập trình cụ thể.
  • Kỹ năng phân tích: Đánh giá tính hợp lệ của cấu trúc BST, xác định hệ số cân bằng $B$ của từng nút, và tính toán độ phức tạp dựa trên chiều cao cây.
  • Năng lực thực hành: Ánh xạ biểu thức toán học thành cấu trúc cây biểu thức và áp dụng cây tìm kiếm trong việc quản lý tập dữ liệu có thứ tự.

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

Cách tiếp cận sư phạm

Tài liệu áp dụng phương pháp tiếp cận từ trừu tượng đến cụ thể:

  1. Xác lập hệ thống tiên đề và định nghĩa hình thức (nodes, branches, degree, path).
  2. Minh họa bằng sơ đồ hình học trực quan kèm nhãn ký hiệu cụ thể.
  3. Mô tả các tính chất toán học lượng hóa.
  4. Đưa ra giải thuật dưới dạng mã giả chuẩn hóa có đầy đủ tham số đầu vào (val, ref), kiểu dữ liệu (pointer, keyType, dataType), tiền điều kiện (Pre) và hậu điều kiện (Post).

Ví dụ và minh họa trong văn bản

  • Ví dụ cây tổng quát: Nút gốc $a$, các nút trung gian $b, d$, nút lá $c, e, f, g, h, i$ với chiều cao $H=3$, dùng để minh họa việc tính bậc, mức và phân loại nút cha - con - anh em.
  • Ví dụ cây tìm kiếm nhị phân: Cây số nguyên chứa các giá trị ${23, 18, 44, 12, 20, 35, 52}$:
    • Duyệt tiền tự (Preorder): $23, 18, 12, 20, 44, 35, 52$.
    • Duyệt hậu tự (Postorder): $12, 20, 18, 35, 52, 44, 23$.
    • Duyệt trung tự (Inorder): $12, 18, 20, 23, 35, 44, 52$ (chứng minh tính chất tạo danh sách có thứ tự).

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

  • Phương pháp tự học: Người học cần đối chiếu từng bước chuyển dịch trạng thái của con trỏ trong mã giả với sơ đồ trực quan, đặc biệt là các thuật toán đệ quy NLR, LNR, LRN và giải thuật duyệt theo chiều rộng có sử dụng hàng đợi.
  • Phương pháp đánh giá: Đánh giá dựa trên khả năng viết đúng thuật toán, vẽ đúng cây từ chuỗi dữ liệu đầu vào, và xác định chính xác thứ tự duyệt nút.

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

  • Chuẩn hóa thuật ngữ song ngữ: Tài liệu đối chiếu trực tiếp các thuật ngữ tiếng Anh và tiếng Việt (Bậc của nút – Degree of a node, Nhánh vào/ra – Indegree/Outdegree branch, Nút gốc – Root, Nút lá – Leaf, Nút nội – Internal node, Cây con – Subtree, Chiều cao – Height).
  • Đặc tả giải thuật chặt chẽ: Mỗi giải thuật đều xác định rõ trạng thái trước khi thực thi (Pre) và kết quả đạt được sau khi thực thi (Post), giúp hạn chế các lỗi ngoại lệ (như truy cập con trỏ null hoặc hàng đợi rỗng).
  • Phân tách rõ ràng giữa hai cơ chế tìm kiếm: Cung cấp song song cả giải thuật đệ quy (searchBST) và giải thuật lặp (iterativeSearchBST), tạo cơ sở để người học so sánh hiệu năng sử dụng vùng nhớ ngăn xếp (Call Stack) và vòng lặp tuần tự.
  • Gắn liền với các ứng dụng thực tế: Tài liệu chỉ rõ vai trò của cây trong việc tổ chức biểu thức toán học cho trình biên dịch (Expression Trees) và thuật toán định tuyến mạng viễn thông.

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

Nhóm đối tượng Yêu cầu và mục đích sử dụng
Sinh viên đại học Sinh viên năm thứ nhất hoặc năm thứ hai chuyên ngành Khoa học Máy tính, Kỹ thuật Máy tính, Hệ thống Thông tin, Kỹ thuật Phần mềm học môn Cấu trúc Dữ liệu và Giải thuật.
Kiến thức tiên quyết Kỹ thuật lập trình cơ bản (C/C++ hoặc Java), khái niệm con trỏ (pointer), cấp phát bộ nhớ động, hàm đệ quy, cấu trúc dữ liệu mảng (array) và hàng đợi (queue).
Giảng viên Sử dụng làm khung bài giảng lý thuyết chuẩn, cung cấp các ca kiểm thử mẫu và cấu trúc mã giả cho bài tập thực hành.
Người nghiên cứu / Tự học Sử dụng làm tài liệu tra cứu hệ thống các công thức toán về cây nhị phân và khuôn mẫu thuật toán thao tác trên BST.

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ế cho sinh viên trình độ đại học chuyên ngành kỹ thuật máy tính và công nghệ thông tin đang theo học học phần Cấu trúc Dữ liệu và Giải thuật, hoặc người học cần tài liệu chuẩn hóa về cấu trúc dữ liệu phân cấp.

2. Cần kiến thức nền nào trước khi học chương này?

Người học cần nắm vững kỹ thuật lập trình đệ quy, thao tác xử lý địa chỉ/con trỏ (pointer), quản lý cấu trúc dữ liệu tự định nghĩa (struct/record), và nguyên lý hoạt động của cấu trúc hàng đợi (Queue).

3. Điểm khác biệt của tài liệu này so với các tài liệu cấu trúc dữ liệu khác là gì?

Tài liệu tập trung vào tính chính xác toán học thông qua việc cung cấp các công thức tính giới hạn nút và chiều cao ($H_{min}, H_{max}, N_{min}, N_{max}$), hệ số cân bằng $B$, đồng thời chuẩn hóa mã giả đầy đủ từ định nghĩa cấu trúc dữ liệu (node, binaryTree) đến các điều kiện kiểm tra biên.

4. Làm sao để tự học hiệu quả các thuật toán trên cây?

Người học nên kết hợp vẽ cây mô phỏng và truy vết (trace) từng dòng mã giả. Cần bắt đầu từ các phép duyệt cơ bản (NLR, LNR, LRN), chuyển tiếp sang viết chương trình thực thi bằng ngôn ngữ lập trình cụ thể cho các thao tác tìm kiếm và chèn trên BST.

5. Có những phương pháp biểu diễn cây tổng quát nào được nêu trong tài liệu?

Tài liệu đưa ra 3 phương pháp biểu diễn chính cho cây tổng quát:

  1. Sơ đồ tổ chức (Organization chart).
  2. Danh sách thụt lề (Indented list).
  3. Danh sách lồng ngoặc (Parenthetical listing - ví dụ: a (b (e f ) c d (g h i))).

Kết luận

Chương 6 – Cấu trúc Cây (Trees) của tác giả Lương Thế Nhân và Trần Giang Sơn cung cấp khung kiến thức hoàn chỉnh về cấu trúc dữ liệu phi tuyến tính trong học phần Cấu trúc Dữ liệu và Giải thuật. Lộ trình học tập được định hình rõ ràng: đi từ việc hiểu các khái niệm cơ bản của cây tổng quát, tính toán các chỉ số chiều cao và độ cân bằng trên cây nhị phân, thao tác chuyển đổi biểu thức trên cây biểu thức, đến việc cài đặt giải thuật tìm kiếm và chèn trên cây tìm kiếm nhị phân. Tài liệu là học liệu tham khảo chuẩn mực phục vụ công tác đào tạo học phần tại Khoa Khoa học và Kỹ thuật Máy tính, Trường Đại học Bách Khoa – ĐHQG-HCM.