Giáo trình Cấu trúc dữ liệu và Thuật toán (Phần 2): Cây và các thuật ngữ chính

Giáo trình toán học về cấu trúc dữ liệu và thuật toán phần 2, biên soạn theo chương trình đào tạo chuẩn, hệ thống hóa kiến thức từ cơ bản đến nâng cao.

• Trường học: Trường Đại Học Công Nghệ Thông Tin
• Chuyên ngành: Cấu Trúc Dữ Liệu Và Thuật Toán
• Đề tài: Giáo Trình Cấu Trúc Dữ Liệu Và Thuật Toán Phần 2
• Loại tài liệu: Giáo Trình
• Năm xuất bản: 2023
• Địa điểm: Hồ Chí Minh

Mục lục chi tiết

• 1. ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM
• 1.1. Định nghĩa cây
• 1.1.1. Cấu trúc đệ quy của cây
• 1.1.2. Cây trong thực tế ứng dụng
• 1.1.2.1. Cây lịch thi đấu
• 1.1.2.2. Cây gia phả
• 1.1.2.3. Cây phân cấp quản lý hành chính
• 1.1.2.4. Cây thư mục
• 1.1.2.5. Cấu trúc của sách
• 1.1.2.6. Cây gia phả ngược (Ancestor Tree)
• 1.1.2.7. Cây phân hoạch tập hợp
• 1.2. Các thuật ngữ chính
• 1.2.1. Đường đi trên cây
• 1.2.2. Độ cao và độ sâu/mức
• 1.2.3. Bậc (Degree)
• 1.3. Cây có thứ tự (Ordered Tree)
• 1.3.1. Thứ tự của các nút
• 1.3.2. Xếp thứ tự các nút
• 1.3.3. Duyệt theo thứ tự trước (Preorder Traversal)
• 1.3.4. Duyệt theo thứ tự sau (Postorder Traversal)
• 1.3.5. Duyệt theo thứ tự giữa (Inorder Traversal)
• 1.4. Cây có nhãn (Labeled Tree)
• 1.4.1. Cây biểu thức (Expression Tree)
• 1.4.2. Xác định quan hệ hậu duệ
• 1.5. ADT Cây
• 1.5.1. Các phép toán cơ bản
• 1.5.2. Biểu diễn cây
• 1.5.2.1. Biểu diễn cây dùng mảng
• 1.5.2.2. Danh sách các con (Lists of Children)
• 1.5.2.3. Dùng con trái và em kế cận phải
• 2. CÂY NHỊ PHÂN
• 2.1. Định nghĩa và tính chất
• 2.1.1. Định nghĩa cây nhị phân
• 2.1.2. Tính chất của cây nhị phân
• 2.1.3. Cây nhị phân đầy đủ (Full binary tree)
• 2.1.4. Cây nhị phân hoàn chỉnh (Complete Binary Trees)
• 2.1.5. Cây nhị phân cân đối (Balanced binary tree)
• 2.2. Biểu diễn cây nhị phân
• 2.2.1. Biểu diễn sử dụng mảng
• 2.2.2. Biểu diễn cây nhị phân dùng con trỏ
• 2.3. Các phép toán cơ bản
• 2.3.1. Tạo một nút (MakeTreeNode)
• 2.3.2. Cài đặt hàm tính số nút và độ sâu của cây
• 2.3.3. Loại bỏ cây (freeTree)
• 2.3.4. Duyệt cây nhị phân

Tóm tắt

I. Tổng quan cấu trúc dữ liệu cây Nền tảng thuật toán phi tuyến

Trong lĩnh vực khoa học máy tính, cấu trúc dữ liệu và thuật toán là hai trụ cột không thể tách rời. Nếu các cấu trúc tuyến tính như danh sách liên kết hay mảng giúp tổ chức dữ liệu theo một trình tự, thì cấu trúc dữ liệu cây mở ra một chiều không gian mới cho việc lưu trữ và truy xuất thông tin phân cấp. Cây là một cấu trúc dữ liệu phi tuyến, bao gồm các nút (node) được kết nối bởi các cạnh. Một nút đặc biệt được gọi là gốc (root), và từ đó, các nút khác được phân nhánh tạo thành một hệ thống thứ bậc. Mỗi nút có thể có một hoặc nhiều nút con, nhưng mỗi nút (trừ gốc) chỉ có duy nhất một nút cha (parent). Các nút không có con được gọi là lá (leaf). Định nghĩa đệ quy của cây là một trong những khái niệm cốt lõi: một nút đơn lẻ là một cây, và một cây mới có thể được xây dựng bằng cách kết nối một nút gốc với các cây con. Cấu trúc này mô phỏng hoàn hảo nhiều hệ thống trong thế giới thực, từ cây gia phả, sơ đồ tổ chức của một công ty, hệ thống tệp trong máy tính, cho đến cây lịch thi đấu thể thao. Việc hiểu rõ bản chất, thuật ngữ và các phép toán cơ bản trên cây là bước đệm quan trọng để tiếp cận các thuật toán phức tạp hơn, đặc biệt là trong các bài toán tìm kiếm, sắp xếp và tối ưu hóa.

1.1. Định nghĩa và các khái niệm cơ bản về cấu trúc cây

Một cấu trúc dữ liệu cây được định nghĩa một cách đệ quy. Bước cơ sở xác định rằng một nút đơn lẻ r là một cây, và r được gọi là gốc của cây đó. Bước quy nạp cho phép xây dựng một cây mới bằng cách đặt một nút r làm cha của các gốc r1, r2, ..., rk của các cây có sẵn T1, T2, ..., Tk. Trong cây mới này, r là gốc, và T1, T2, ..., Tk trở thành các cây con (subtree). Ngoài ra, các thuật ngữ quan trọng khác bao gồm: lá (leaf) là nút không có con; nút trong (internal node) là nút không phải lá; tổ tiên (ancestors) và hậu duệ (descendants) mô tả mối quan hệ phân cấp. Chiều cao (height) của một nút là đường đi dài nhất từ nút đó đến một lá, trong khi độ sâu (depth) là độ dài đường đi từ gốc đến nút đó. Bậc (degree) của một nút là số lượng con của nó. Những khái niệm này là nền tảng để phân tích và triển khai các thuật toán liên quan đến cây.

1.2. Các ứng dụng thực tế của cây trong khoa học máy tính

Cấu trúc cây không chỉ là một khái niệm lý thuyết mà còn có vô số ứng dụng thực tiễn. Cây thư mục trong hệ điều hành là một ví dụ điển hình, nơi mỗi thư mục là một nút và có thể chứa các tệp (lá) hoặc các thư mục con. Cây gia phả thể hiện mối quan hệ huyết thống một cách trực quan. Trong lĩnh vực thể thao, cây lịch thi đấu được dùng để theo dõi các trận đấu loại trực tiếp. Một ứng dụng quan trọng khác là cây biểu thức (expression tree), dùng để biểu diễn các biểu thức số học, nơi các toán hạng là lá và các phép toán là nút trong. Ngoài ra, cây quyết định (decision tree) là một công cụ mạnh mẽ trong học máy và trí tuệ nhân tạo để phân loại dữ liệu. Việc hiểu các ứng dụng này giúp nhận thức rõ hơn về sức mạnh và tính linh hoạt của cấu trúc dữ liệu cây trong việc giải quyết các bài toán phức tạp.

II. Thách thức duyệt cây Hướng dẫn 3 phương pháp duyệt hiệu quả

Duyệt cây (tree traversal) là quá trình truy cập (thăm) tất cả các nút trong cây một cách có hệ thống, mỗi nút đúng một lần. Do cấu trúc phi tuyến của cây, việc duyệt không đơn giản như duyệt một mảng từ đầu đến cuối. Các thuật toán duyệt cây cung cấp một trình tự xác định để xử lý thông tin tại mỗi nút, là cơ sở cho nhiều thao tác phức tạp khác như tìm kiếm, sao chép, hoặc xóa cây. Có ba phương pháp duyệt đệ quy phổ biến và quan trọng nhất, được định nghĩa dựa trên thứ tự thăm nút gốc so với các cây con của nó: Thứ tự trước (Preorder), Thứ tự sau (Postorder), và Thứ tự giữa (Inorder). Mỗi phương pháp duyệt này tạo ra một chuỗi các nút khác nhau và phục vụ cho những mục đích riêng biệt. Ví dụ, duyệt theo thứ tự trước thường được dùng để tạo bản sao của cây, trong khi duyệt theo thứ tự sau hữu ích trong việc giải phóng bộ nhớ của cây. Việc lựa chọn phương pháp duyệt phù hợp phụ thuộc hoàn toàn vào yêu cầu của bài toán cụ thể, và nắm vững cả ba phương pháp là kỹ năng thiết yếu khi làm việc với cấu trúc dữ liệu và thuật toán liên quan đến cây.

2.1. Phân tích thuật toán duyệt cây theo thứ tự trước Preorder

Duyệt theo thứ tự trước (Preorder Traversal) tuân theo quy tắc "Gốc - Trái - Phải". Thuật toán được định nghĩa đệ quy như sau: đầu tiên, thăm nút gốc; tiếp theo, duyệt cây con trái nhất theo thứ tự trước; sau đó, lần lượt duyệt các cây con còn lại từ trái sang phải theo thứ tự trước. Theo tài liệu, thuật toán PREORDER(nodeT r) được mô tả: "(1) Đưa ra r; (2) for (mỗi con c của r) do PREORDER(c);". Cách duyệt này đảm bảo rằng một nút cha luôn được xử lý trước các nút con của nó. Ứng dụng tiêu biểu của Preorder là khi cần sao chép một cây, vì nó tạo ra một bản sao có cấu trúc giống hệt cây gốc. Trong cây biểu thức, duyệt theo thứ tự trước sẽ cho ra biểu thức ở dạng tiền tố (ký pháp Ba Lan).

2.2. Khám phá thuật toán duyệt cây theo thứ tự sau Postorder

Trái ngược với Preorder, duyệt theo thứ tự sau (Postorder Traversal) tuân theo quy tắc "Trái - Phải - Gốc". Thuật toán này duyệt tất cả các cây con từ trái sang phải theo thứ tự sau trước, và cuối cùng mới thăm nút gốc. Tài liệu mô tả thuật toán POSTORDER(nodeT r) bằng cách "đảo ngược hai thao tác (1) và (2) trong PREORDER". Cụ thể là: "for (mỗi con c của r) do POSTORDER(c); (2) Đưa ra r;". Vì nút gốc luôn được thăm sau cùng, phương pháp này rất hữu ích trong các tác vụ cần xử lý các nút con trước khi xử lý nút cha. Một ứng dụng điển hình là việc xóa một cây và giải phóng bộ nhớ, vì không thể xóa một nút cha trước khi các con của nó đã được xóa. Đối với cây biểu thức, duyệt theo thứ tự sau sẽ cho ra biểu thức ở dạng hậu tố (ký pháp Ba Lan ngược), rất thuận tiện cho việc tính toán bằng stack.

2.3. Tìm hiểu thuật toán duyệt theo thứ tự giữa Inorder

Duyệt theo thứ tự giữa (Inorder Traversal) chủ yếu được áp dụng cho cây nhị phân và tuân theo quy tắc "Trái - Gốc - Phải". Định nghĩa đệ quy của nó là: đầu tiên, duyệt cây con trái theo thứ tự giữa; tiếp theo, thăm nút gốc; và cuối cùng, duyệt cây con phải theo thứ tự giữa. Đối với cây tổng quát có nhiều hơn hai con, khái niệm này được mở rộng: duyệt cây con trái nhất, sau đó thăm gốc, và cuối cùng duyệt các cây con còn lại. Một trong những ứng dụng quan trọng nhất của Inorder traversal là trên cây tìm kiếm nhị phân. Khi duyệt một cây tìm kiếm nhị phân theo thứ tự giữa, các giá trị tại các nút sẽ được liệt kê theo thứ tự tăng dần. Điều này làm cho Inorder trở thành một phương pháp sắp xếp tự nhiên khi dữ liệu được tổ chức trong cấu trúc này.

III. Cây nhị phân Cấu trúc dữ liệu và các tính chất cơ bản nhất

Cây nhị phân (Binary Tree) là một dạng cây đặc biệt và được sử dụng rộng rãi nhất trong cấu trúc dữ liệu và thuật toán. Theo định nghĩa, cây nhị phân là cây mà mỗi nút có nhiều nhất hai con. Hai con này được phân biệt rõ ràng là con trái (left child) và con phải (right child). Điều này tạo ra một sự khác biệt quan trọng so với cây tổng quát, ngay cả khi một nút chỉ có một con, việc nó là con trái hay con phải cũng mang ý nghĩa cấu trúc. Cây nhị phân là nền tảng cho nhiều cấu trúc dữ liệu hiệu quả khác như cây tìm kiếm nhị phân, cây heap, và cây Huffman. Việc nghiên cứu các tính chất của nó, chẳng hạn như mối quan hệ giữa chiều cao và số lượng nút, là rất quan trọng. Ví dụ, một cây nhị phân có chiều cao k có không quá 2^k - 1 nút. Hiểu rõ các biến thể của cây nhị phân như cây nhị phân đầy đủ, cây nhị phân hoàn chỉnh, và cây nhị phân cân bằng giúp lựa chọn cấu trúc phù hợp để tối ưu hóa hiệu suất của các thuật toán.

3.1. Tính chất và đặc điểm của một cây nhị phân tiêu chuẩn

Một cây nhị phân sở hữu nhiều tính chất toán học quan trọng. Bổ đề 1 trong tài liệu chỉ ra rằng: (i) số nút lớn nhất ở mức i là 2^(i-1); (ii) một cây nhị phân với chiều cao k có tối đa 2^k - 1 nút; và (iii) một cây nhị phân n nút có chiều cao tối thiểu là ceil(log2(n+1)). Những tính chất này cung cấp giới hạn trên và dưới cho hiệu suất của các thuật toán hoạt động trên cây. Chẳng hạn, trong một cây nhị phân cân bằng, thời gian tìm kiếm một phần tử là O(log n) vì chiều cao của nó được giữ ở mức tối thiểu. Việc phân biệt con trái và con phải cũng là đặc điểm cốt lõi, làm cho hai cây có cùng các nút nhưng thứ tự con khác nhau được coi là hai cây nhị phân khác nhau.

3.2. Phân biệt cây nhị phân đầy đủ hoàn chỉnh và cân bằng

Có ba loại cây nhị phân đặc biệt thường được đề cập. Cây nhị phân đầy đủ (Full Binary Tree) là cây mà mọi nút trong đều có đúng hai con và tất cả các lá đều có cùng độ sâu. Cây nhị phân hoàn chỉnh (Complete Binary Tree) là cây nhị phân mà tất cả các mức, trừ mức cuối cùng, đều được lấp đầy, và các nút ở mức cuối cùng được lấp đầy từ trái sang phải. Cấu trúc này rất lý tưởng cho việc biểu diễn bằng mảng. Cuối cùng, cây nhị phân cân bằng (Balanced Binary Tree) là cây mà tại mọi nút, chênh lệch chiều cao giữa cây con trái và cây con phải không quá 1. Cây đầy đủ là cây hoàn chỉnh, và cây hoàn chỉnh cũng là cây cân bằng, nhưng điều ngược lại không phải lúc nào cũng đúng. Việc duy trì tính cân bằng là chìa khóa để đảm bảo hiệu suất O(log n) cho các thao tác tìm kiếm, chèn, xóa.

IV. Cách biểu diễn cây Từ mảng đến con trỏ trong lập trình

Để triển khai cấu trúc dữ liệu cây trong một chương trình máy tính, cần có một phương pháp biểu diễn hiệu quả. Việc lựa chọn cách biểu diễn ảnh hưởng trực tiếp đến hiệu suất của các thuật toán thao tác trên cây. Có hai phương pháp chính: sử dụng mảng và sử dụng con trỏ. Biểu diễn cây dùng mảng đặc biệt hiệu quả đối với cây nhị phân hoàn chỉnh. Trong phương pháp này, mối quan hệ cha-con có thể được suy ra trực tiếp từ chỉ số của mảng. Ví dụ, với nút tại chỉ số i, con trái của nó sẽ ở 2*i và con phải ở 2*i+1. Tuy nhiên, phương pháp này rất lãng phí bộ nhớ đối với các cây không hoàn chỉnh. Ngược lại, biểu diễn cây dùng con trỏ linh hoạt hơn rất nhiều. Mỗi nút được biểu diễn bằng một cấu trúc (struct) chứa dữ liệu và các con trỏ đến các nút con của nó. Đối với cây tổng quát, có thể dùng danh sách các con hoặc biểu diễn "con trái nhất, em kế cận phải". Đối với cây nhị phân, mỗi nút chỉ cần hai con trỏ: một cho con trái và một cho con phải, đây là cách tiếp cận phổ biến và trực quan nhất.

4.1. Phương pháp biểu diễn cây bằng mảng và các ưu nhược điểm

Biểu diễn cây nhị phân hoàn chỉnh bằng mảng là một kỹ thuật rất hiệu quả. Các nút được đánh số từ trên xuống dưới và từ trái qua phải, bắt đầu từ 1. Nút i sẽ được lưu tại phần tử A[i] của mảng. Từ đó, ta có thể tìm nút cha của A[i] tại A[floor(i/2)], con trái tại A[2*i], và con phải tại A[2*i+1]. Ưu điểm của phương pháp này là tiết kiệm không gian bộ nhớ do không cần lưu các con trỏ và cho phép truy cập cha-con nhanh chóng. Tuy nhiên, nhược điểm lớn là sự lãng phí bộ nhớ khi cây thưa hoặc không cân bằng. Nếu một cây có chiều cao lớn nhưng ít nút, mảng biểu diễn sẽ có rất nhiều ô trống, làm cho phương pháp này không thực tế trong nhiều trường hợp.

4.2. Kỹ thuật biểu diễn cây bằng cấu trúc con trỏ linh hoạt

Phương pháp biểu diễn cây dùng con trỏ là cách tiếp cận phổ biến và linh hoạt nhất. Mỗi nút được định nghĩa là một cấu trúc dữ liệu, ví dụ trong ngôn ngữ C: struct Tnode { DataType Item; struct Tnode *left; struct Tnode *right; };. Cấu trúc này chứa dữ liệu (Item) và hai con trỏ, một đến con trái (left) và một đến con phải (right). Nếu một nút không có con trái hoặc con phải, con trỏ tương ứng sẽ được gán giá trị NULL. Ưu điểm của phương pháp này là chỉ cấp phát bộ nhớ cho các nút thực sự tồn tại, do đó rất hiệu quả về không gian cho mọi loại cây. Nó cũng cho phép các thao tác chèn và xóa nút một cách linh hoạt mà không cần phải di chuyển một lượng lớn dữ liệu như trong biểu diễn mảng.

V. Top ứng dụng của cấu trúc dữ liệu cây trong các bài toán thực tế

Cấu trúc dữ liệu cây và các thuật toán liên quan không chỉ là những khái niệm trừu tượng mà còn là công cụ giải quyết vô số bài toán trong thế giới thực. Sức mạnh của cây nằm ở khả năng mô hình hóa các mối quan hệ phân cấp và cho phép các thao tác tìm kiếm, truy vấn hiệu quả. Một trong những ứng dụng phổ biến nhất là cây biểu thức nhị phân, được sử dụng bởi các trình biên dịch để phân tích và tính toán giá trị của các biểu thức toán học. Một lĩnh vực khác là học máy, nơi cây quyết định được dùng làm mô hình dự đoán để phân loại dữ liệu dựa trên một chuỗi các câu hỏi. Ngoài ra, trong lĩnh vực nén dữ liệu, Mã Huffman (Huffman Code) sử dụng cây nhị phân để xây dựng một bộ mã có độ dài thay đổi, giúp giảm đáng kể kích thước của tệp tin mà không làm mất thông tin. Những ví dụ này chỉ là một phần nhỏ, cho thấy tầm quan trọng và tính ứng dụng rộng rãi của cây trong công nghệ hiện đại.

5.1. Cây biểu thức nhị phân và việc tính toán biểu thức

Cây biểu thức nhị phân (Binary Expression Tree) là một ứng dụng trực tiếp của cây nhị phân để biểu diễn các biểu thức số học. Trong cây này, mỗi nút lá chứa một toán hạng (số hoặc biến), và mỗi nút trong chứa một phép toán hai ngôi. Cây con trái và phải của một nút phép toán biểu diễn các biểu thức con. Ưu điểm của cấu trúc này là thứ tự ưu tiên của các phép toán được xác định rõ ràng bởi cấu trúc của cây mà không cần dùng đến dấu ngoặc. Bằng cách áp dụng các phương pháp duyệt cây, ta có thể dễ dàng thu được các dạng biểu diễn khác nhau: duyệt theo thứ tự giữa (Inorder) cho ra dạng trung tố (dạng viết thông thường), duyệt theo thứ tự trước (Preorder) cho ra dạng tiền tố, và duyệt theo thứ tự sau (Postorder) cho ra dạng hậu tố. Dạng hậu tố đặc biệt hữu ích cho việc tính toán hiệu quả bằng cấu trúc dữ liệu stack.

5.2. Mã Huffman Ứng dụng cây nhị phân trong nén dữ liệu

Mã Huffman là một thuật toán nén dữ liệu không mất mát, dựa trên tần suất xuất hiện của các ký tự. Ý tưởng cốt lõi là sử dụng các mã nhị phân có độ dài thay đổi: các ký tự xuất hiện thường xuyên được gán mã ngắn hơn, còn các ký tự ít xuất hiện được gán mã dài hơn. Để xây dựng bộ mã này, thuật toán Huffman sử dụng một cây nhị phân. Ban đầu, mỗi ký tự được xem là một nút lá với trọng số là tần suất của nó. Thuật toán lặp đi lặp lại việc kết hợp hai nút có tần suất thấp nhất để tạo thành một nút cha mới, có tần suất bằng tổng tần suất của hai con. Quá trình này tiếp tục cho đến khi chỉ còn lại một cây duy nhất. Mã của mỗi ký tự được xác định bằng đường đi từ gốc đến lá tương ứng (ví dụ: rẽ trái là 0, rẽ phải là 1). Kết quả là một bộ mã tiền tố (prefix code), đảm bảo việc giải mã là duy nhất và hiệu quả.

VI. Kết luận Tầm quan trọng của cây trong khoa học máy tính

Qua các phân tích về định nghĩa, thuộc tính, các phương pháp duyệt và ứng dụng, có thể khẳng định rằng cấu trúc dữ liệu cây là một trong những khái niệm nền tảng và mạnh mẽ nhất trong khoa học máy tính. Khả năng biểu diễn dữ liệu phân cấp một cách tự nhiên giúp nó trở thành lựa chọn tối ưu cho nhiều bài toán, từ quản lý hệ thống tệp đến phân tích cú pháp trong trình biên dịch và các mô hình học máy. Đặc biệt, cây nhị phân và các biến thể của nó như cây tìm kiếm nhị phân hay cây heap đã tạo ra những thuật toán có hiệu suất vượt trội, cho phép xử lý các tập dữ liệu lớn với thời gian tiệm cận logarit. Việc nắm vững các khái niệm từ cơ bản như nút, gốc, lá đến các kỹ thuật phức tạp như duyệt cây hay cân bằng cây là kỹ năng không thể thiếu đối với bất kỳ lập trình viên hay kỹ sư phần mềm nào. Cấu trúc cây không chỉ là một công cụ, mà còn là một lối tư duy để mô hình hóa và giải quyết vấn đề một cách hiệu quả và có hệ thống.

6.1. Tóm tắt vai trò của cấu trúc dữ liệu cây và thuật toán

Cấu trúc dữ liệu cây đóng vai trò trung tâm trong việc tổ chức dữ liệu theo một cấu trúc phân cấp, phản ánh nhiều hệ thống trong thực tế. Nó cung cấp một giải pháp hiệu quả hơn so với các cấu trúc tuyến tính khi giải quyết các bài toán liên quan đến tìm kiếm và sắp xếp phân cấp. Các thuật toán như duyệt cây (Preorder, Inorder, Postorder) cung cấp các phương pháp có hệ thống để xử lý mọi nút trong cây, phục vụ cho vô số ứng dụng. Các cấu trúc chuyên biệt như cây nhị phân và các biến thể của nó đã chứng tỏ hiệu quả vượt trội, đặc biệt là cây tìm kiếm nhị phân cân bằng, giúp giảm độ phức tạp thời gian của các thao tác cơ bản xuống O(log n). Tóm lại, cây là một công cụ không thể thay thế, là cầu nối giữa lý thuyết thuật toán và các ứng dụng thực tiễn.

6.2. Hướng phát triển và các cấu trúc cây nâng cao trong tương lai

Lĩnh vực cấu trúc dữ liệu và thuật toán luôn không ngừng phát triển. Dựa trên nền tảng của cây nhị phân, nhiều cấu trúc cây nâng cao đã được ra đời để giải quyết các bài toán chuyên biệt hơn. Ví dụ, B-Tree và các biến thể của nó (B+ Tree, B* Tree) là cấu trúc nền tảng của hầu hết các hệ quản trị cơ sở dữ liệu và hệ thống tệp hiện đại, được tối ưu cho việc truy xuất dữ liệu trên bộ nhớ ngoài. Cây Đỏ-Đen (Red-Black Tree) và cây AVL là các loại cây tìm kiếm nhị phân tự cân bằng, đảm bảo hiệu suất ổn định trong trường hợp xấu nhất. Trong đồ họa máy tính và tìm kiếm không gian, các cấu trúc như K-D Tree hay Quadtree được sử dụng để phân hoạch không gian một cách hiệu quả. Việc nghiên cứu và ứng dụng các cấu trúc cây nâng cao này sẽ tiếp tục là một hướng đi quan trọng, mở ra những giải pháp tối ưu hơn cho các thách thức công nghệ trong tương lai.

Trích đoạn nội dung tài liệu

ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM 4. Định nghĩa cây Cây bao gồm các nút, có một nút đặc biệt được gọi là gốc (root) và các cạnh nối các nút. Cây được định nghĩa đệ quy như sau: Định nghĩa cây Bước cơ sở: Một nút r là cây và r được gọi là gốc của cây này. Bước quy nạp: Giả sử 7¡, 7;,., 7; là các cây với gốc là rụ, ra.

Ta có thể xây dựng cây mới bang cach dat r lam cha (parent) của các nút r\, 7a,. Trong cây nay r là gôc và 7\, 7›,., 7¿ là các cây con của gôc z., r¿ được gọi là con của nút z. Chú ý: Nhiều khi để phù hợp, ta cần định nghĩa cây rỗng (null tree) là cây không có nút nào cả. Cầu trúc đệ quy của cây Cây trong thực tế ứng dụng ~ Biểu đồ lịch thí đầu.

— Cây gia phả. — Biểu đồ phân cấp quản lý hành chính. — Cây thư mục. — Cầu trúc của một quyển sách.

143 ~ Cây biểu thức. ~ Cay phân hoạch tập hợp. Cây lịch thi đấu Trong đời thường, cây rất hay được sử dụng để diễn tả lịch thi đấu của các giải thé thao theo thể thức đầu loại trực tiếp, chẳng hạn vòng 2 của World Cup. Pháp @ Tây Ban Nha Brazin @ Anh Đức @ Ucraina Italia 6 Achentina Cay gia pha Nikolaus Johan I Nikolaus JacobI 1667-1748 1662-1716 1654-1705 Nikolaus II Daniel Johan It Nikolaus JN 1695-1726 1700-1782 1710-1790 1687-1759 Johan IT Jacob IE 1746-1807 1759-1789 Cây gia pha của các nhà toán hoc dong ho Bernoulli Cây phân cấp quần lý hành chính [Ban Giám đốc ị Phòng Phòng Phong Phang Phong Hành chỉnh Tổ chức Tài vụ Kinh doanh Kế hoạch [re] [vantnw] [ II 1 | lÌ | lÌ | 144 Cay thu muc H1 fe] ea) [0800] (3[0000000FlashDisk] ({00KSTNDocum] CH0Baocso] H0BookDown] | {I{0ChuongTrinhCeoDang] [0GiaoTrinh] {300] 1[000TestsProblemForSomeProh] - : Ê3{01-01-2006] kế 3[0AIgorithmic] Cl[0BlumFeraitv] 3[BCombinGeameTheorv] [0DisMotn] CH-¬1[0000DM_Far_Vd] [¬[000Stide] [9501DM_F06] ¬[abutetovị C[Baigiang].

{5[Homework Assignments, UMBC CMSC 441, Fall 2006_files} ([Alan T_ Sherman (Home Page)_files] IICMSC 203 Home Page_tiles] [Cygwin Information and Installation_files] Ciflect2_jim_files] (afLect3_files] {[Form kiem dinh 2007] £[Saoluu] C(t] Cifesct64] [DM] | Cấu trúc của sách Sách Cl 1. : 145 Cây mục lục Book Chapter 1 [Subsection 1. Cay gia pha nguge (Ancestor Tree) Cây phả hệ ngược: mỗi người đều có bố mẹ. Cây này là cây nhị phân (binary tree).

ar] Cây phân hoạch tập hợp es {1,2, 3, 4, 5, 6,7,8, 9, 10} | Tập con các số lết Tập con các số chan: {1,3, 5,7, 9} {2,4,6, 8,10}. {1, 9} Tập con các sé nguyên tb: {2, 4, 8, 10} Tập con số hoàn hảo: {3, 5,7} {6} 4. Các thuật ngữ chính Các thuật ngữ chính liên quan đến cây là: — Niit — node; - Gốc - root; — Lá ~ leaf; — Con — child; ~ Cha — parent; — Té tién —‘ancestors; — Hau dué — descendants: ~ Anh em ~ sibling; — Nut trong = internal node; ~ Chidu cao — hight, chidu sau — depth., n¿ là đấy nút trên cây sao cho n; là cha của nại với 1 < í < &, thì dãy này được gọi là đường đi (padh) từ nút m tới nút my. Độ dài (length) của đường ởi bằng số lượng nút trên đường đi trừ bớt 1.

Như vậy đường đi độ dài 0 là đường đi từ một nút đền chính nó. 147 Nếu có đường đi từ nút ø tới nút b, thì ø được gọi là đổ tiên (ancestor) của b, còn 5 duge goi la hdu dué (descendant) cha a. Trong cay, gộc là nút không có tô tiên chính thường và mọi nút khác trên cây đêu lả hậu duệ chính thường của nó. Một nút không có hậu duệ chỉnh thường được gọi là 14 (leay).

Các nút có cùng cha được gọi là anh em (sibling). Cây con (subiree) của một cây là một nút cùng với tất cả các hậu dué của nó. Chiều cao (heigbi) của nút trên cây bằng độ dài của đường đi đài nhất từ nút đó đến lá cộng 1. Chiều cao của cây (eight oƒa tre) là chiều cao của gốc.

Độ sẩu/mức (depth/level) của nút bằng 1 cộng với độ dài của đường đi duy nhất từ gốc đến nó. root, ancestor internal node parent sibling descendent aikaek ` are leaves Cây con (Subtree) Node and its decendants 148 Đường đi trên cây * Path eo 1 (c ) \, Path 2 G) Path 1: {4,867} Path 2: {d,i} Độ cao (heighO và độ sâu/mức (depth/level) Độ:cao của cây là 5 Tà quan sát cây trong tin học như thế nào? 149 Bậc (Depree) Số lượng con của nút x được gọi là bậc (degree) của x. Ou 3 % vì Saws ay a — A» © @) 4. Cây có thir tw (Ordered Tree) Thứ tự của các nút Các con của một nút thường được xếp theo thứ tự ¿ ái sang phải.

Như vậy bai cây trong hình sau đây là khác nhau, bởi vi hai con của nit a xuất hiện trong hai cây theo thứ tự khác nhau: @) @) OO © Cây với các nút được xếp thử tự được gọi là cây có thứ tự. Ta sẽ xét chủ yếu là cây có thứ tự. Vì vậy, tiếp theo đây thuật ngữ cây là để chỉ cấy có thứ tự. Khi muốn khẳng định không quan tâm đến thứ tự, ta sẽ phải nói rõ là cây không có thứ tự.

Thứ tự "từ trái sáng phải" của các anh em (các con của cùng một nút) có thể tổng quát để so sánh hai nútkhông, có quan hệ tô tiên — hậu duệ. Quy tác 80 ) sánh là: của j. 150 Ví dụ: Nút ¿ ở bên phải nút:b, ở bên trái các nút í,.ƒ ƒ, 2; ø VàẠ không ở bên trái cũng như bên phải của các nút tổ tiên của nó 4, e, e. +: ha vất Xếp thứ tự các nút na Ta có thể xếp thứ tự các nút của cây theo nhiều cách.

Gó ba thứ tự quan trọng nhất, đó là Thứ tự trước, Thú tự sau va Thứ tự gilta (Preorder, Postorđer và Tnorder). Các thứ tự này được định nghĩa một cách đệ quy nhự. sau: " l ~— Nếu cây 7 là rỗng, thì danh sách rỗng là danh sách, theo tứ tự, trước, thứ tự sau và thứ tự giữa của cây 7. — Nếu cây 7 có một nút, thì nút đó chính là danh sách theo thứ tự trước, thứ tự sau và thứ tự giữa của cây 1.

: — Trái lại, giả sử 7à cây có Bốc r với các cây con là 7Ị; Ti. Duyệt theo thứ tự trước — Preorder Traversal” ‘ Thứ tự trước (hay duyệt theo thử tự trước ~ preorder traversal) của các Trút của cây 7là: — Gốc r của T; _ Tiếp đến là các nút của 7¡ theo thứn tự trước; — Sau đó là các nút của 7; theo thứ tự trước; wey ~ Và cuối cùng là các nút của 7 theo thứ tự trước. Duyệt theo thứ tự Sau — Postorder Traversal _ /. Thứ tự sau của các nút của cây Tia: — Cac nut cha 7; theo thir ty sau; — Tiếp đến là các nút của 7; theo thứ tự sau; ~ Các nút'của 7, theo thứ ft sau; ei oe Oe — Sau cùng là nút gốc z.

151 Duyệt theo thứ tự giữa— Inorder Traversal Thứ tự giữa của các nút của cây T là: — Các nút của 7ì theo thứ tự giữa; : =+©'Tiếp đến là núĩ gốc r; -~ ˆ 12 'Tiếp theo là các nữ của Tp, | , Tị, tnỗi nhóm mút được xếp theo thứ tự giữa. Thuật toán duyệt theo thứ tự trước~Preorder Traversal ˆ vald PREORDER (øođeTr) ` f ¬ (1) Đưa rar; (2) for (mỗi con c của z, nếu có, theo thứ-tự từ trái sang) đo PREORDER(); } ` Vi dy: Thứ tự trước của các đỉnh của cây trên hình vẽ là: %bj dể - & hy Ú ƒ G 'Thuật toán duyệt theo thứ tự sau — Postorder Traversal Thuật toán đuyệt theo thứ tự sau thu được bằng cách đảo ngược hai thao tác (1) và (2) trong PREORDER: void POSTORDER ( nođeT z) { for (mỗi con c của r, nếu có, theo thứ tự từ trái sang) do POSTORDER(c) Dua rar; } Vi du: Diy cdc đỉnh được liệt kê theo #lu# tự sạu của cây trong hình vẽ là: bhi gif oda 152 'Thuật toán duyệt theo thứ tự giữa — Inorder Traversal void INORDER (nodeT r) { + jf (r là lá ) Đưa ra r; else { TNORDER(con trái nhật của r); Dua rar; for (mỗi con ơ của r, ngoại trừ con trải nhất, theo thứ tự từ trái sang) do INORDER(c); } Ví dụ: Dãy các đỉnh của cây trong hình vẽ được liệt kê theo thứ tự giữa là: b,a,h, e, Ù G ÿ ƒ 8; d Xếp thứ tự các nút, Để nhớ cách đưa ra các nút theo ba thứ ft vừa trình bày, hãy hình dung là ta đi vòng quanh bên ngoài. bắt đầu từ gốc, ngược chiều kim đồng hồ và sát theo cây nhất. Chẳng hạn, đường đi đó đối với cây trong các ví dụ đã xét ở trên như sau: Đối với thứ tự trước, ta đứa ra nút mỗi khí đi qua nó, ` 'Đối với thứ tự san, ta đưa ra nút khi qua nó ở lần cuối trước khi quay về cha của nó.

Đối với thứ tự giữa, ta đưa ra lá ngay khi đi qua nó, cònn những, nút trong được đưa rà khi lần thứ hai được đi qua. các lá được xếp theo thứ tự từ trái i sang phải như nhau trong cả ba cach sap xép.4, Cây có nhãn (Labeled Tree) Thông thường người ta gán cho mỗi nút của cây một nhãn (2e!) hoặc một giá trị, cũng tương tự như chúng ta đã gán mỗi nút của đanh sách với một phần tử. 153 Nghĩa là, nhãn của nút không phải tên gợi của nút mà là giá trị được cất giữ trong nó. Trong một số ứng dụng, ta có thể thay đổi nhãn của nút mà tên của nó vẫn được giữ nguyên.

Ví dụ: Xét cây có 7 nit m,. Ta gán nhãn cho các nút như sau: — Nút ø có nhãn *; — Nút ø¿ có nhãn +; — Nút ø có nhãn —; — Nút mạ có nhãn 4a; — Nút n; có nhãn ð; = Nút nạ có nhãn a; — Nút mị cô nhãn e. Cây biểu thức (Expression Tree) Cây trong ví dụ vừa nêu có tên gọi là cây biểu thức: (a + b)*(4~ 2) Quy tắc để cây có nhãn biểu diễn một biểu thức là: — Mỗi nút lá có nhãn là toán hạng và chỉ gồm một toán hạng đó. Ví dụ nút 4 biểu diễn biểu thức ø.

— Mỗi nút trong n được gán nhãn là phép toán. Giả sử z: có nhãn là phép toán hai ngôi q, như + hoặc *, con trái biểu điển biểu thúc Z và con phải biểu điễn biểu thức Ey, Khi đó n biểu diễn biểu thức (1) q (Ea). Ta có thể bỏ dấu ngoặc nếu như điều đó là không cân thiết.