Chương 5: Cấu trúc dữ liệu Cây (ADT Tree) - Định nghĩa, thuật ngữ và ứng dụng

Trong khoa học máy tính, việc tổ chức dữ liệu một cách hiệu quả là yếu tố then chốt quyết định hiệu suất của chương trình. 72 trang.

• Đề tài: Cấu Trúc Dữ Liệu Và Thuật Toán Chapter05 ADT Tree

Mục lục chi tiết

• 1. GIỚI THIỆU CÂY
• 1.1. Ứng dụng của kiểu dữ liệu cây
• 1.2. Kiểu dữ liệu cây
• 1.3. Các thuật ngữ liên quan đến cây
• 1.4. Phân loại cây
• 1.5. Một số loại cây nhị phân
• 1.6. Các định lý về cây nhị phân
• 1.7. Cấu trúc dữ liệu biểu diễn cây
• 1.8. Duyệt cây nhị phân
• 1.9. Cây n-nhánh
• 2. CÂY NHỊ PHÂN TÌM KIẾM
• 2.1. Cây nhị phân tìm kiếm
• 2.2. Tìm kiếm trên cây nhị phân tìm kiếm
• 2.3. Minh họa tìm kiếm trên cây nhị phân tìm kiếm

Tóm tắt

I. Khám phá ADT Tree Nền tảng cấu trúc dữ liệu phân cấp

Trong khoa học máy tính, việc tổ chức dữ liệu một cách hiệu quả là yếu tố then chốt quyết định hiệu suất của chương trình. Cấu trúc dữ liệu và thuật toán cung cấp các công cụ để giải quyết vấn đề này, và Cấu trúc cây (Tree Data Structure) là một trong những cấu trúc quan trọng nhất. Cây không phải là một cấu trúc tuyến tính như mảng hay danh sách liên kết; thay vào đó, nó biểu diễn dữ liệu có tính phân cấp, tương tự như cây gia phả hay sơ đồ tổ chức công ty. Về bản chất, Tree là một kiểu dữ liệu trừu tượng (ADT - Abstract Data Type), định nghĩa một tập hợp các giá trị và các phép toán trên chúng mà không phụ thuộc vào cách cài đặt cụ thể. Theo định nghĩa đệ quy trong tài liệu của Bùi Tiến Lên (2017), một cây có thể là rỗng, hoặc bao gồm một phần tử đặc biệt gọi là nút gốc (root) và một tập hợp các cây con không giao nhau. Mỗi cây con (subtree) lại là một cây hoàn chỉnh. Mối quan hệ giữa các phần tử được xác định rõ ràng: một nút cha (parent node) có thể có nhiều nút con (child node), nhưng mỗi nút con chỉ có duy nhất một nút cha. Các nút không có con được gọi là nút lá (leaf). Sự trừu tượng hóa này cho phép chúng ta tập trung vào logic hoạt động của cây, chẳng hạn như thêm, xóa, tìm kiếm phần tử, mà không cần quan tâm đến việc nó được cài đặt bằng mảng hay con trỏ.

1.1. Giới thiệu tổng quan về kiểu dữ liệu trừu tượng cây

Một kiểu dữ liệu trừu tượng (Abstract Data Type) định nghĩa một mô hình toán học cho một kiểu dữ liệu, bao gồm tập hợp các giá trị có thể có và các phép toán có thể thực hiện trên các giá trị đó. Đối với ADT Tree, nó mô tả một tập hợp các nút được liên kết theo quan hệ phân cấp cha-con. Các phép toán cơ bản trên ADT Tree thường bao gồm: tạo một cây mới, kiểm tra cây rỗng, thêm một nút con vào một nút cha, xóa một nút, và các phương pháp duyệt cây (tree traversal). Ưu điểm của việc sử dụng ADT là tính đóng gói và che giấu thông tin. Người dùng chỉ cần biết các thao tác có thể thực hiện mà không cần biết chi tiết cài đặt bên trong. Ví dụ, một cây có thể được hiện thực bằng mảng hoặc bằng cấu trúc con trỏ, nhưng các phép toán như insert() hay search() vẫn giữ nguyên về mặt logic đối với người dùng. Điều này giúp mã nguồn trở nên linh hoạt và dễ bảo trì hơn.

1.2. Các thuật ngữ cơ bản trong cấu trúc dữ liệu cây

Để làm việc hiệu quả với cấu trúc cây, việc nắm vững các thuật ngữ là điều bắt buộc. Nút gốc (root) là nút cao nhất trong cây và là nút duy nhất không có nút cha. Nút lá (leaf) là những nút ở tận cùng, không có bất kỳ nút con nào. Các nút không phải gốc cũng không phải lá được gọi là nút trung gian. Mối quan hệ phân cấp được thể hiện qua nút cha (parent node) và nút con (child node). Cây con (subtree) là một cây hoàn chỉnh bắt đầu từ một nút con của cây lớn hơn. Chiều cao của cây (tree height) là độ dài đường đi dài nhất từ nút gốc đến một nút lá. Ngược lại, độ sâu của nút (node depth) là độ dài đường đi từ nút gốc đến nút đó. Các nút có cùng nút cha được gọi là anh em (siblings). Bậc của một nút là số lượng nút con của nó, và bậc của cây là bậc lớn nhất trong tất cả các nút.

II. Thách thức chính khi làm việc với cấu trúc dữ liệu cây

Mặc dù cấu trúc cây mang lại nhiều lợi ích trong việc biểu diễn dữ liệu phân cấp, việc triển khai và vận hành chúng cũng đi kèm với những thách thức đáng kể. Khác với cấu trúc tuyến tính, việc truy cập các phần tử trong cây không thể thực hiện bằng chỉ số đơn giản. Thay vào đó, phải sử dụng các thuật toán duyệt cây phức tạp hơn. Một trong những vấn đề lớn nhất là nguy cơ cây bị suy biến thành dạng danh sách liên kết, hay còn gọi là cây không cân bằng. Khi một cây tìm kiếm nhị phân (Binary Search Tree - BST) trở nên mất cân bằng, độ phức tạp thuật toán cho các thao tác tìm kiếm, chèn, xóa có thể tăng từ O(log n) lên O(n) trong trường hợp xấu nhất, làm mất đi lợi thế về hiệu suất. Việc duy trì một cây cân bằng (balanced tree) đòi hỏi các thuật toán phức tạp hơn như xoay cây (rotation) trong cây AVL hoặc cây Đỏ-Đen. Hơn nữa, việc quản lý bộ nhớ cho cây, đặc biệt là khi cài đặt bằng con trỏ, đòi hỏi sự cẩn thận để tránh rò rỉ bộ nhớ. Các thuật toán đệ quy, dù rất tự nhiên và thanh lịch khi áp dụng cho cây, lại có thể gây ra lỗi tràn bộ nhớ stack (stack overflow) nếu chiều cao của cây quá lớn.

2.1. Vấn đề về hiệu suất của cây không cân bằng Unbalanced Tree

Hiệu suất của nhiều loại cây, đặc biệt là cây tìm kiếm nhị phân (BST), phụ thuộc rất nhiều vào hình dạng của nó. Một cây được coi là cân bằng nếu chiều cao của cây là tối thiểu, xấp xỉ log₂(n) với n là số nút. Trong trường hợp này, các thao tác tìm kiếm, chèn và xóa có độ phức tạp thuật toán trung bình là O(log n). Tuy nhiên, nếu dữ liệu được chèn vào theo thứ tự đã được sắp xếp (ví dụ: 1, 2, 3, 4, 5), cây sẽ bị suy biến. Mỗi nút mới sẽ chỉ có con phải, tạo thành một cấu trúc giống như danh sách liên kết. Lúc này, chiều cao của cây trở thành n, và các thao tác tìm kiếm sẽ tương đương với việc quét qua một danh sách, với độ phức tạp là O(n). Đây là trường hợp xấu nhất, làm triệt tiêu hoàn toàn lợi thế của cấu trúc cây so với cấu trúc mảng hoặc danh sách.

2.2. Sự phức tạp trong các thuật toán duyệt và quản lý bộ nhớ

Việc duyệt cây (tree traversal) không đơn giản như duyệt một mảng. Cần có các chiến lược duyệt bài bản để đảm bảo mọi nút đều được truy cập đúng một lần. Ba phương pháp duyệt sâu phổ biến là duyệt tiền thứ tự (Pre-order), duyệt trung thứ tự (In-order), và duyệt hậu thứ tự (Post-order). Mỗi phương pháp phục vụ một mục đích khác nhau và thường được cài đặt bằng thuật toán đệ quy. Mặc dù đệ quy giúp mã nguồn ngắn gọn và dễ hiểu, nó lại tiêu tốn không gian trong bộ nhớ stack. Với những cây rất sâu, việc gọi đệ quy liên tục có thể dẫn đến tràn stack. Ngoài ra, khi cài đặt cây bằng con trỏ, việc xóa một nút đòi hỏi phải quản lý cẩn thận các con trỏ để kết nối lại cây một cách chính xác và giải phóng vùng nhớ của nút đã xóa, nếu không sẽ gây ra rò rỉ bộ nhớ hoặc con trỏ lơ lửng.

III. Phương pháp biểu diễn và phân loại cấu trúc dữ liệu cây

Để làm việc với một ADT Tree, trước hết cần chọn một phương pháp biểu diễn nó trong bộ nhớ máy tính. Có hai cách tiếp cận chính: sử dụng mảng và sử dụng con trỏ. Biểu diễn bằng mảng thường phù hợp với các loại cây đặc biệt như cây nhị phân hoàn chỉnh (complete binary tree), nơi vị trí của nút cha và các nút con có thể được tính toán dễ dàng từ chỉ số mảng. Tuy nhiên, phương pháp này không linh hoạt và gây lãng phí bộ nhớ nếu cây thưa thớt. Phương pháp phổ biến và linh hoạt hơn là sử dụng cấu trúc nút (node) và con trỏ. Mỗi nút chứa dữ liệu và các con trỏ trỏ đến các nút con của nó. Dựa trên số lượng con tối đa của một nút, cây được phân loại thành nhiều loại khác nhau. Một trong những loại phổ biến nhất là cây nhị phân (binary tree), nơi mỗi nút có tối đa hai con. Theo tài liệu của Bùi Tiến Lên, cây còn có thể là cây tuyến tính (bậc 1), cây tam phân (bậc 3) hay cây n-nhánh (bậc n). Việc lựa chọn cấu trúc và cách biểu diễn phù hợp phụ thuộc vào bài toán cụ thể để tối ưu hóa cả về không gian lưu trữ và thời gian thực thi.

3.1. Các kỹ thuật biểu diễn cây Mảng so với Con trỏ

Biểu diễn cấu trúc cây bằng mảng là một kỹ thuật trực quan, đặc biệt hiệu quả với cây nhị phân. Trong phương pháp này, nếu một nút được lưu ở chỉ số i, thì con trái của nó có thể được lưu ở 2*i + 1 và con phải ở 2*i + 2. Nút gốc (root) được lưu ở chỉ số 0. Cách này cho phép truy cập nhanh đến các nút con và cha mà không cần con trỏ, nhưng nó yêu cầu một khối bộ nhớ liên tục và có thể lãng phí không gian nếu cây bị khuyết nhiều nút. Ngược lại, biểu diễn bằng con trỏ linh hoạt hơn rất nhiều. Mỗi nút là một đối tượng struct hoặc class, chứa dữ liệu và một hoặc nhiều con trỏ đến các nút con. Cách này chỉ cấp phát bộ nhớ khi cần thiết, phù hợp với các cây có cấu trúc động và không đều. Tuy nhiên, nó yêu cầu chi phí bộ nhớ cho các con trỏ và có thể làm giảm hiệu suất do truy cập bộ nhớ không liên tục (cache miss).

3.2. Phân loại cây dựa trên bậc Cây nhị phân và Cây N nhánh

Bậc của một nút là số lượng cây con của nó, và bậc của cây là bậc lớn nhất của các nút trong cây. Dựa trên tiêu chí này, cây được phân loại thành nhiều dạng. Cây nhị phân (Binary Tree) là loại cây có bậc bằng 2, nghĩa là mỗi nút có tối đa hai con: con trái và con phải. Đây là loại cây được nghiên cứu và ứng dụng rộng rãi nhất. Các biến thể đặc biệt của nó bao gồm cây nhị phân đầy đủ (mỗi nút có 0 hoặc 2 con) và cây nhị phân hoàn chỉnh (các mức được lấp đầy từ trái sang phải). Ngoài ra, còn có Cây N-nhánh (N-ary Tree), nơi mỗi nút có thể có tới N con. Cấu trúc này thường được dùng để biểu diễn hệ thống file (mỗi thư mục có thể chứa nhiều file/thư mục con) hoặc các cây phân cấp trong cơ sở dữ liệu như B-Tree.

IV. Hướng dẫn các thuật toán duyệt cây nhị phân phổ biến

Để xử lý thông tin lưu trữ trong cấu trúc cây, việc duyệt qua tất cả các nút theo một thứ tự xác định là một thao tác cơ bản. Với cây nhị phân, có ba phương pháp duyệt theo chiều sâu (Depth-First Traversal) kinh điển, thường được cài đặt bằng thuật toán đệ quy. Các phương pháp này khác nhau ở thứ tự tương đối giữa việc xử lý nút hiện tại (N), duyệt cây con trái (L) và duyệt cây con phải (R). Duyệt tiền thứ tự (Pre-order) tuân theo trình tự N-L-R, tức là xử lý nút gốc trước, sau đó duyệt đệ quy sang cây con trái, và cuối cùng là cây con phải. Phương pháp này hữu ích để tạo ra một bản sao của cây. Duyệt trung thứ tự (In-order) theo trình tự L-N-R, duyệt cây con trái, xử lý nút gốc, rồi đến cây con phải. Đối với một cây tìm kiếm nhị phân (BST), duyệt trung thứ tự sẽ trả về các phần tử theo thứ tự tăng dần. Cuối cùng, Duyệt hậu thứ tự (Post-order) theo trình tự L-R-N, duyệt cây con trái, cây con phải, rồi mới xử lý nút gốc. Phương pháp này thường được dùng để xóa một cây, vì nó đảm bảo các nút con được xử lý trước nút cha (parent node).

4.1. Phương pháp duyệt tiền thứ tự Pre order Traversal NLR

Duyệt tiền thứ tự là một trong ba phương pháp duyệt cây theo chiều sâu. Tên gọi "tiền thứ tự" (pre-order) ám chỉ rằng nút gốc (root) được xử lý trước khi các cây con của nó được duyệt. Quy trình của thuật toán như sau: 1. Thăm (xử lý) nút hiện tại. 2. Gọi đệ quy thủ tục duyệt tiền thứ tự cho cây con trái. 3. Gọi đệ quy thủ tục duyệt tiền thứ tự cho cây con phải. Ví dụ, với cây biểu thức * (+ a b) (- c d), duyệt tiền thứ tự sẽ cho kết quả * + a b - c d, đây chính là dạng biểu diễn tiền tố (ký pháp Ba Lan). Ứng dụng phổ biến của duyệt tiền thứ tự là để sao chép một cây, vì nó tạo ra các nút theo đúng thứ tự cha trước con sau, cho phép xây dựng lại cây một cách chính xác.

4.2. Phương pháp duyệt trung thứ tự In order Traversal LNR

Duyệt trung thứ tự có quy trình xử lý nút gốc ở giữa hai lần duyệt cây con trái và phải. Các bước của thuật toán là: 1. Gọi đệ quy thủ tục duyệt trung thứ tự cho cây con trái. 2. Thăm (xử lý) nút hiện tại. 3. Gọi đệ quy thủ tục duyệt trung thứ tự cho cây con phải. Điểm đặc biệt nhất của phương pháp này là khi áp dụng trên một cây tìm kiếm nhị phân (Binary Search Tree - BST), nó sẽ trả về một danh sách các khóa (key) đã được sắp xếp theo thứ tự tăng dần. Đây là một tính chất cực kỳ hữu ích, được ứng dụng để sắp xếp dữ liệu hoặc kiểm tra tính hợp lệ của một BST. Với cây biểu thức * (+ a b) (- c d), kết quả duyệt trung thứ tự sẽ là a + b * c - d, tương ứng với dạng biểu thức trung tố quen thuộc.

4.3. Phương pháp duyệt hậu thứ tự Post order Traversal LRN

Duyệt hậu thứ tự xử lý nút gốc sau khi cả hai cây con của nó đã được duyệt xong. Quy trình của thuật toán bao gồm: 1. Gọi đệ quy thủ tục duyệt hậu thứ tự cho cây con trái. 2. Gọi đệ quy thủ tục duyệt hậu thứ tự cho cây con phải. 3. Thăm (xử lý) nút hiện tại. Ứng dụng quan trọng nhất của duyệt hậu thứ tự là để giải phóng bộ nhớ của cây. Bằng cách xử lý các nút con (child node) trước nút cha (parent node), thuật toán đảm bảo rằng không có con trỏ nào bị mất trước khi nút mà nó trỏ tới được xóa. Ngoài ra, trong cây biểu thức, duyệt hậu thứ tự sẽ cho ra biểu diễn hậu tố (ký pháp Ba Lan ngược), ví dụ a b + c d - *, rất thuận tiện cho việc tính toán giá trị biểu thức bằng cách sử dụng stack.

V. Ứng dụng Cây tìm kiếm nhị phân BST trong thực tiễn

Cây tìm kiếm nhị phân (Binary Search Tree - BST) là một ứng dụng đặc biệt và cực kỳ quan trọng của cấu trúc cây nhị phân. Nó được thiết kế để tối ưu hóa các thao tác tìm kiếm, chèn, và xóa dữ liệu. Định nghĩa của BST rất chặt chẽ: tại mỗi nút p, tất cả các khóa (key) trong cây con (subtree) bên trái của p đều nhỏ hơn khóa của p, và tất cả các khóa trong cây con bên phải của p đều lớn hơn khóa của p. Đặc tính này cho phép thực hiện thao tác tìm kiếm một cách hiệu quả. Bắt đầu từ nút gốc (root), ta so sánh khóa cần tìm với khóa của nút hiện tại. Nếu nhỏ hơn, ta đi sang cây con trái; nếu lớn hơn, ta đi sang cây con phải. Quá trình này lặp lại cho đến khi tìm thấy khóa hoặc đi đến một nút lá (leaf) mà không tìm thấy. Nếu cây là một cây cân bằng, độ phức tạp thuật toán cho các thao tác này là O(log n), nhanh hơn đáng kể so với tìm kiếm tuyến tính O(n) trên mảng hoặc danh sách. BST được ứng dụng rộng rãi trong việc xây dựng các cấu trúc chỉ mục (indexing) trong cơ sở dữ liệu, bảng ký hiệu (symbol table) trong trình biên dịch, và nhiều thuật toán khác.

5.1. Định nghĩa và đặc tính của Cây tìm kiếm nhị phân BST

Một cây tìm kiếm nhị phân là một cây nhị phân có các thuộc tính sau: 1. Cây con trái của một nút chỉ chứa các nút có khóa nhỏ hơn khóa của nút đó. 2. Cây con phải của một nút chỉ chứa các nút có khóa lớn hơn khóa của nút đó. 3. Cả cây con trái và cây con phải cũng phải là cây tìm kiếm nhị phân. 4. Không có các nút trùng khóa. Chính những quy tắc này đã tạo nên sức mạnh của BST. Chúng cho phép loại bỏ một nửa số nút cần xem xét ở mỗi bước tìm kiếm, tương tự như thuật toán tìm kiếm nhị phân trên mảng đã sắp xếp. Như đã đề cập trong tài liệu gốc, ∀q ∈ (p → left) : q → key < p → key và ∀q ∈ (p → right) : q → key > p → key. Đặc tính này cũng giúp dễ dàng tìm giá trị nhỏ nhất (nút trái nhất) và lớn nhất (nút phải nhất) trong cây.

5.2. Phân tích độ phức tạp thuật toán tìm kiếm trên BST

Độ phức tạp thuật toán tìm kiếm trên BST phụ thuộc trực tiếp vào chiều cao của cây (tree height). Ở mỗi bước so sánh, thuật toán sẽ đi sâu xuống một mức. Do đó, trong trường hợp xấu nhất, số phép so sánh bằng với chiều cao của cây. Đối với một cây cân bằng có n nút, chiều cao xấp xỉ log₂(n). Khi đó, độ phức tạp tìm kiếm là O(log n). Đây là trường hợp lý tưởng. Tuy nhiên, trong trường hợp xấu nhất, khi cây bị suy biến thành một danh sách liên kết, chiều cao của cây là n, và độ phức tạp tìm kiếm trở thành O(n). Vì vậy, để đảm bảo hiệu suất ổn định, việc giữ cho cây luôn ở trạng thái gần cân bằng là rất quan trọng. Các cấu trúc dữ liệu như cây AVL hay cây Đỏ-Đen được phát triển để tự động duy trì tính cân bằng sau mỗi thao tác chèn hoặc xóa.

VI. Kết luận và hướng phát triển của cấu trúc dữ liệu cây

Tổng kết lại, Cấu trúc dữ liệu cây (Tree Data Structure), với tư cách là một kiểu dữ liệu trừu tượng, đóng một vai trò không thể thiếu trong lĩnh vực khoa học máy tính. Từ việc biểu diễn các mối quan hệ phân cấp tự nhiên như hệ thống tập tin, đến việc tối ưu hóa các hoạt động tìm kiếm thông qua cây tìm kiếm nhị phân, cây đã chứng tỏ được tính linh hoạt và hiệu quả vượt trội so với các cấu trúc tuyến tính trong nhiều bài toán. Việc nắm vững các khái niệm từ cơ bản như nút gốc (root), nút lá (leaf), đến các kỹ thuật nâng cao như các phương pháp duyệt cây (tree traversal) và nguyên tắc hoạt động của BST là nền tảng vững chắc cho bất kỳ lập trình viên nào. Tuy nhiên, những thách thức về hiệu suất do cây không cân bằng đã thúc đẩy sự ra đời của các loại cây tự cân bằng phức tạp hơn. Hướng phát triển trong tương lai của cấu trúc cây tập trung vào việc tối ưu hóa cho các hệ thống dữ liệu lớn (Big Data), tính toán song song và các ứng dụng trong trí tuệ nhân tạo, nơi các cây quyết định (Decision Trees) và các biến thể của nó đang ngày càng trở nên quan trọng.

6.1. Tóm tắt vai trò của ADT Tree trong khoa học máy tính

ADT Tree cung cấp một mô hình mạnh mẽ để tổ chức và quản lý dữ liệu có cấu trúc phân cấp. Nó cho phép các lập trình viên trừu tượng hóa các chi tiết cài đặt phức tạp, tập trung vào các thao tác logic trên dữ liệu. Vai trò của cây trải dài trên nhiều lĩnh vực: trong hệ điều hành để quản lý cấu trúc thư mục; trong cơ sở dữ liệu với các chỉ mục B-Tree và B+ Tree để tăng tốc truy vấn; trong xử lý ngôn ngữ tự nhiên với cây cú pháp; và trong đồ họa máy tính với các cây phân vùng không gian như Quadtree hay Octree. Sự phổ biến của cấu trúc cây chứng tỏ tầm quan trọng của việc lựa chọn đúng cấu trúc dữ liệu để giải quyết hiệu quả các vấn đề trong thế giới thực.

6.2. Giới thiệu về cây cân bằng và các cấu trúc cây nâng cao

Để khắc phục nhược điểm về hiệu suất của cây tìm kiếm nhị phân trong trường hợp xấu nhất, các loại cây cân bằng (balanced tree) đã được phát triển. Đây là các BST có thêm các quy tắc để đảm bảo chiều cao của cây luôn được giữ ở mức tối thiểu, xấp xỉ O(log n). Cây AVL là một trong những cây tự cân bằng đầu tiên, nó đảm bảo chiều cao của hai cây con tại mỗi nút không chênh lệch quá 1. Cây Đỏ-Đen (Red-Black Tree) là một loại cây cân bằng khác, được sử dụng rộng rãi trong việc cài đặt các thư viện chuẩn của nhiều ngôn ngữ lập trình. Ngoài ra, các cấu trúc cây nâng cao khác như B-Tree, Tries (cây tiền tố), và Heap (cây đống) được thiết kế cho các ứng dụng chuyên biệt, từ quản lý chỉ mục trên đĩa đến các thuật toán ưu tiên và sắp xếp hiệu quả.

Nội dung chính

{
  "document_type": "textbook",
  "confidence": 0.95,
  "reasoning": "Tài liệu mang cấu trúc bài giảng/giáo trình phục vụ giảng dạy học phần Cấu trúc dữ liệu và Giải thuật ('Spring 2017 Data structure & Algorithm' của tác giả Bùi Tiến Lên), bao gồm định nghĩa lý thuyết hình thức, hệ thống thuật ngữ, định lý toán học, bảng biểu diễn dữ liệu, hình vẽ minh họa và các đoạn mã nguồn C++ mẫu."
}

CẤU TRÚC DỮ LIỆU CÂY: LÝ THUYẾT VÀ CÀI ĐẶT THUẬT TOÁN (ADT TREE)

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

Tài liệu bài giảng "Cấu trúc dữ liệu cây" do tác giả Bùi Tiến Lên biên soạn (công bố ngày 01/01/2017) là học liệu phục vụ học phần Cấu trúc Dữ liệu và Giải thuật (Data Structures & Algorithms - Spring 2017). Trong khung chương trình đào tạo bậc đại học khối ngành Công nghệ Thông tin và Khoa học Máy tính, Cấu trúc dữ liệu cây (Tree Abstract Data Type - ADT Tree) là nội dung cốt lõi thuộc nhóm cấu trúc dữ liệu phi tuyến tính, đóng vai trò bản lề giúp người học chuyển tiếp từ các cấu trúc dữ liệu tuyến tính (như mảng, danh sách liên kết, ngăn xếp, hàng đợi) sang các cấu trúc dạng đồ thị phức tạp.

Mục tiêu học tập của tài liệu tập trung vào việc trang bị cho người học:

• Khả năng hiểu và vận dụng định nghĩa đệ quy của kiểu dữ liệu cây;
• Nắm vững hệ thống thuật ngữ hình thức mô tả các thành phần và thuộc tính định lượng của cây;
• Hiểu rõ các định lý nền tảng về giới hạn số nút và chiều cao của cây nhị phân;
• Làm chủ kỹ thuật biểu diễn dữ liệu cây trong bộ nhớ máy tính bằng mảng và cấu trúc liên kết động (con trỏ template C++);
• Cài đặt thành thạo các thuật toán duyệt cây nhị phân (NLR, LNR, LRN) và các thao tác cơ bản trên Cây nhị phân tìm kiếm (Binary Search Tree - BST).

Về mặt cấu trúc, tài liệu được tổ chức theo phương pháp sư phạm diễn dịch: bắt đầu từ các ví dụ mô hình hóa hiện tượng thực tế, đi vào định nghĩa toán học hình thức, phân tích các trường hợp đặc biệt, chứng minh định lý và kết thúc bằng việc thiết kế cấu trúc dữ liệu cùng mã nguồn thực thi thuật toán bằng ngôn ngữ C++.

---

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 chia thành các phân khu chuyên đề logic tuần tự:

1. Ứng dụng thực tiễn của cấu trúc cây: Mô tả khả năng mô hình hóa quan hệ phân cấp và kế thừa qua các trường hợp cụ thể: cây gia phả dòng họ, cây phân cấp sinh học, cây thư mục tập tin hệ điều hành, hệ thống quản lý hành chính toàn cầu (Hình 1: Trái đất $\to$ Quốc gia $\to$ Tỉnh/Thành phố $\to$ Quận $\to$ Cá nhân), cây biểu thức toán học biểu diễn $(a + b) * (c - d)$ (Hình 2), cây phân tích cú pháp ngữ pháp ngôn ngữ tự nhiên cho câu "the cat sat on the mat" (Hình 3), cây phân cấp thẻ HTML (Hình 4) và chỉ mục B-Tree trong cơ sở dữ liệu (Hình 5).
2. Định nghĩa và thuật ngữ cây tổng quát: Thiết lập Định nghĩa 1 về cây phi tuyến tính theo dạng đệ quy: cây $T$ là tập rỗng ($T = \emptyset$) hoặc gồm một nút gốc $r$ kết hợp tập các cây con có thứ tự ${T_1, T_2, \dots, T_m}$. Hệ thống thuật ngữ bao gồm: nút (node - Hình 7), nhánh (branch - cạnh nối), quan hệ nút cha (parent) và nút con (child - Hình 8), cây con (subtree - Hình 9), nút gốc (root), nút lá (leaf), nút nội (internal node), nút anh em (sibling - Hình 10), bậc của nút (node degree - Hình 11), bậc của cây (tree degree - Hình 12), mức của nút (node level - Hình 13), chiều cao cây (tree height - Hình 14) và đường đi (path) cùng quan hệ tổ tiên (ancestor) - con cháu (descendant) (Hình 15).
3. Phân loại cây và các định lý nhị phân: Định nghĩa 2 phân loại cây theo bậc lớn nhất ($k=1$: tuyến tính; $k=2$: nhị phân; $k=3$: tam phân; $k=n$: $n$-nhánh). Định nghĩa 3 chuẩn hóa Cây nhị phân đầy đủ (Full Binary Tree - mỗi nút có 0 hoặc 2 con) và Cây nhị phân hoàn chỉnh (Complete Binary Tree - đầy đủ từ mức 0 đến $h-1$, mức $h$ điền liên tiếp từ trái qua phải). Thiết lập Định lý 1 về số lượng nút tối đa theo mức ($2^k$), số lá tối đa ($2^{h-1}$), số nút tối đa ($2^h - 1$), chiều cao nhỏ nhất ($\lceil \log_2(n + 1) \rceil$) và Định lý 2 về mối liên hệ giữa số nút lá $l$ và số nút nội $i$ ($l = i + 2$).
4. Kỹ thuật biểu diễn và duyệt cây nhị phân: Biểu diễn dạng bảng mảng tĩnh với các cột Chỉ số, Nút, Con trái, Con phải (Bảng 1); biểu diễn liên kết con trỏ bằng C++ Template qua cấu trúc struct Node<T> (Chương trình 1) và lớp class BinaryTree<T> (Chương trình 2). Cài đặt 3 giải thuật duyệt đệ quy: NLR (Pre-order: Nút $\to$ Trái $\to$ Phải), LNR (In-order: Trái $\to$ Nút $\to$ Phải), LRN (Post-order: Trái $\to$ Phải $\to$ Nút) minh họa qua Hình 19, 20 và mã nguồn Chương trình 3.
5. Biểu diễn cây $n$-nhánh: So sánh phương pháp mảng con trỏ cố định childs[n] (Slide 34) với mô hình tối ưu "anh cả - em kế tiếp" sử dụng hai con trỏ eldestChild và nextSibling (Slide 36, Hình 22, Hình 23).
6. Cây nhị phân tìm kiếm (BST): Thiết lập Định nghĩa 4 về ràng buộc khóa: $\forall q \in (p \to \text{left}): \text{key}(q) < \text{key}(p)$ và $\forall q \in (p \to \text{right}): \text{key}(q) > \text{key}(p)$. Cài đặt cấu trúc BSTNode<T> có/không có con trỏ parent (Chương trình 4, 5), cấu trúc lớp BSTTree<T> với các hàm search, insert, remove (Chương trình 6), cùng thuật toán tìm kiếm lặp search(int key) (Chương trình 7) và sơ đồ minh họa truy vết tìm khóa 20 (Hình 25).

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

Tài liệu cung cấp các nguyên lý nền tảng:

• Nguyên lý cấu trúc dữ liệu đệ quy: Tiếp cận định nghĩa dữ liệu qua việc lồng ghép các cấu trúc con cùng loại, làm cơ sở để thiết kế các giải thuật phân rã đệ quy.
• Hệ thống đánh giá định lượng toán học: Định lượng cấu trúc cây qua các công thức giải tích: $$\text{deg}(T) = \max(\text{deg}(p_i), p_i \in T)$$ $$\text{level}(p) = \begin{cases} 0 & \text{nếu } p = \text{root} \ \text{level}(\text{parent}(p)) + 1 & \text{nếu } p \neq \text{root} \end{cases}$$ $$\text{height}(T) = \max(\text{level}(p_i) + 1, p_i \in T)$$
• Mô hình hóa bộ nhớ động: Khái niệm hóa việc chuyển đổi liên kết logic sang cấp phát bộ nhớ vật lý thông qua các con trỏ định kiểu trong C++.

Kỹ năng phát triển

• Kỹ năng phân tích và mô hình hóa: Khả năng trừu tượng hóa các cấu trúc phân tầng trong đời sống (dữ liệu tổ chức, cú pháp ngôn ngữ, toán tử biểu thức) thành cấu trúc dữ liệu cây.
• Kỹ năng thiết kế và lập trình cấu trúc dữ liệu: Vận dụng kỹ thuật lập trình C++ Template để định nghĩa các cấu trúc dữ liệu tổng quát tái sử dụng (Node<T>, BSTNode<T>, BinaryTree<T>, BSTTree<T>).
• Kỹ năng thực thi thuật toán: Cài đặt và tính toán đường đi của các thuật toán duyệt cây đệ quy và thuật toán tìm kiếm trên cây nhị phân tìm kiếm có độ phức tạp phụ thuộc vào chiều cao của cây.

---

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

Tài liệu được thiết kế bám sát phương pháp tiếp cận trực quan hóa (visualization) kết hợp với chứng minh toán học và mã nguồn mẫu:

• Phương pháp sư phạm trực quan: Hệ thống bài giảng sử dụng 25 hình vẽ kỹ thuật (từ Hình 1 đến Hình 25) để mô tả cụ thể từng khái niệm trừu tượng. Ví dụ, sự khác biệt giữa nút lá, nút nội và nút gốc được chỉ rõ bằng sơ đồ trực quan (Hình 10); cơ chế biểu diễn "anh cả - em kế tiếp" được làm sáng tỏ bằng cách xoay trực tiếp sơ đồ cây một góc 45 độ (Hình 23).
• Tích hợp bài tập dạng Case Study: Bài giảng đưa ra các tình huống ứng dụng thực tế để sinh viên phân tích tại chỗ:
  • Phân tích cấu trúc cây biểu thức $(a + b) * (c - d)$ nhằm liên hệ với quá trình tính toán thứ tự toán tử;
  • Khảo sát cây ngữ pháp của câu "the cat sat on the mat" để hiểu quá trình xử lý cú pháp trong trình biên dịch hoặc ngôn ngữ học máy tính;
  • Phân tích cây quản lý hành chính để hiểu tính phân cấp dữ liệu thực tế.
• Thực hành lập trình từng bước: Cung cấp mã nguồn hoàn chỉnh dạng khung (skeleton code) sử dụng C++ Template, yêu cầu sinh viên hoàn thiện các thao tác còn thiếu (search, insert, remove trong BSTTree).
• Phương pháp tự học và tự đánh giá: Tài liệu cung cấp các câu hỏi kiểm tra trực tiếp trên sơ đồ (ví dụ tại Slide 41: yêu cầu xác định nút có khóa nhỏ nhất, khóa lớn nhất, nút đứng ngay trước và ngay sau nút 15 trên cây BST ở Hình 24), kèm theo sơ đồ truy vết từng bước của thuật toán tìm kiếm khóa 20 (Hình 25).

---

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

• Cấu trúc nội dung chuẩn mực học thuật: Tài liệu trình bày hệ thống các định nghĩa và định lý cơ sở của Cấu trúc Dữ liệu và Giải thuật, đảm bảo tính chuẩn xác và chặt chẽ về mặt toán học.
• Giải pháp chuyển đổi cây $n$-nhánh tối ưu: Thay vì dừng lại ở cách biểu diễn cây $n$-nhánh bằng mảng con trỏ cố định childs[n] gây lãng phí bộ nhớ khi các nút có bậc không đồng đều, tài liệu giới thiệu mô hình "anh cả - em kế tiếp" (eldestChild, nextSibling), giải quyết bài toán biểu diễn cây đa phân bất kỳ bằng cấu trúc nút nhị phân 2 con trỏ.
• Liên kết đa ngành: Minh họa cấu trúc dữ liệu không chỉ bằng các bài toán tính toán thuần túy mà mở rộng sang các hệ thống thực tế như cấu trúc DOM của tài liệu HTML, cấu trúc chỉ mục B-Tree trong hệ quản trị cơ sở dữ liệu và phân tích ngữ pháp trong xử lý ngôn ngữ.
• Minh họa giải thuật chi tiết: Quá trình tìm kiếm phần tử trên BST được trực quan hóa từng bước theo đường đi từ gốc qua các phép so sánh điều kiện (key == p->key, key < p->key, key > p->key), giúp sinh viên nắm vững nguyên lý vận hành của thuật toán tìm kiếm dạng nhánh.

---

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

• 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 Phần mềm, Hệ thống Thông tin, Khoa học Dữ liệu và Kỹ thuật Máy tính đang học môn Cấu trúc Dữ liệu và Giải thuật.
• Yêu cầu kiến thức tiên quyết (Prerequisites):
  • Kỹ thuật lập trình cơ bản bằng ngôn ngữ C/C++;
  • Hiểu biết về quản lý bộ nhớ, con trỏ (pointers) và cấp phát động;
  • Nắm vững lập trình hướng đối tượng cơ bản (struct, class) và kỹ thuật lập trình tổng quát (Template);
  • Kiến thức về giải thuật đệ quy và cấu trúc dữ liệu tuyến tính (Mảng, Danh sách liên kết).
• Giảng viên: Sử dụng làm đề cương và slide bài giảng lý thuyết trên lớp, dùng hệ thống ví dụ và hình vẽ mẫu để xây dựng bài tập thực hành, đề thi và câu hỏi vấn đáp.
• Người tự học và kỹ sư phần mềm: Dùng làm tài liệu hệ thống hóa kiến thức nền tảng về cây dữ liệu và giải thuật tìm kiếm, phục vụ chuẩn bị cho các kỳ đánh giá năng lực lập trình hoặc phỏng vấn kỹ thuật.

---

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

1. Tài liệu này phù hợp với ai?

Tài liệu được biên soạn phục vụ trực tiếp cho sinh viên đại học đang theo học học phần Cấu trúc Dữ liệu và Giải thuật, cùng các lập trình viên cần ôn tập lại nền tảng lý thuyết và cài đặt C++ của kiểu dữ liệu cây.

2. Cần chuẩn bị kiến thức nền nào trước khi tiếp cận tài liệu?

Người học cần nắm chắc ngôn ngữ C++ (đặc biệt là con trỏ, cấu trúc struct, lớp class, template), kỹ thuật đệ quy và các cấu trúc dữ liệu tuyến tính cơ bản.

3. Điểm khác biệt trong cách trình bày của tài liệu này là gì?

Tài liệu kết hợp song song giữa định nghĩa giải tích toán học hình thức, bảng biểu diễn mảng tĩnh (Bảng 1), mô hình chuyển đổi cây đa phân sang cây nhị phân (mô hình anh cả - em kế tiếp xoay 45 độ) và mã nguồn C++ Template có thể biên dịch trực tiếp.

4. Làm thế nào để tự học và nắm vững kiến thức trong tài liệu?

Người học nên kết hợp đọc lý thuyết, tự vẽ lại các cây minh họa (Hình 7 đến Hình 15) để tính toán thủ công các thông số bậc, mức, chiều cao; sau đó tự viết lại mã nguồn C++ cho các phép duyệt cây (NLR, LNR, LRN) và cài đặt lớp BSTTree theo các Chương trình 1–7.

5. Tài liệu có cung cấp mã nguồn mẫu không?

Có. Bài giảng cung cấp đầy đủ các đoạn mã mẫu bằng C++ Template từ Chương trình 1 đến Chương trình 7, bao gồm định nghĩa cấu trúc nút Node<T>, BSTNode<T>, cấu trúc lớp BinaryTree<T>, BSTTree<T>, hàm duyệt cây đệ quy NLR và thuật toán tìm kiếm lặp search trên cây nhị phân tìm kiếm.

---

Kết luận

Tài liệu bài giảng "Cấu trúc dữ liệu cây" của tác giả Bùi Tiến Lên (Học kỳ Spring 2017) cung cấp hệ thống kiến thức toàn diện, chuẩn xác về Kiểu dữ liệu trừu tượng Cây (ADT Tree). Nội dung bao quát từ định nghĩa toán học đệ quy, hệ thống thuật ngữ, các định lý cây nhị phân đến kỹ thuật cài đặt bộ nhớ và thuật toán xử lý dữ liệu trên C++ Template.

Lộ trình học tập đề xuất:

1. Nắm vững định nghĩa đệ quy và hệ thống thuật ngữ đo lường cấu trúc cây (bậc, mức, chiều cao, đường đi).
2. Học các định lý về cây nhị phân và phân biệt cây nhị phân đầy đủ với cây nhị phân hoàn chỉnh.
3. Thực hành cài đặt cấu trúc dữ liệu biểu diễn cây (mảng và con trỏ template C++) cùng 3 thuật toán duyệt cây đệ quy.
4. Làm chủ cấu trúc Cây nhị phân tìm kiếm (BST), cài đặt và kiểm thử các thao tác tìm kiếm, chèn và xóa nút.

Tài liệu tham khảo mở rộng: Sau khi hoàn thành nội dung tài liệu, người học có thể tiếp tục nghiên cứu các cấu trúc dữ liệu cây cân bằng tự động (Cây AVL, Cây Đỏ-Đen) và các cấu trúc cây đa phân nâng cao phục vụ hệ thống lưu trữ (B-Tree, B+Tree).