Cấu trúc dữ liệu Tree (Cây): Định nghĩa, Phân loại & Ứng dụng

Trong lập trình, cấu trúc dữ liệu Tree (cây) là một trong những nền tảng quan trọng giúp xử lý dữ liệu một cách có tổ chức và hiệu quả. Bài viết này sẽ giúp bạn hiểu rõ: Tree là gì, tại sao nó quan trọng, các khái niệm cơ bản như Node, Root, Leaf, và đi sâu vào phân loại, thao tác, ví dụ cài đặt, cho đến những ứng dụng thực tế trong AI, cơ sở dữ liệu, hệ thống tệp tin.

Tree (cây) là gì?

Tree (cây) là một cấu trúc dữ liệu (data structure) cơ bản và quan trọng, thuộc loại phi tuyến tính (non-linear). Nó được dùng để biểu diễn mối quan hệ phân cấp (hierarchical relationship) giữa các phần tử dữ liệu. Hãy nghĩ về nó như một tập hợp các nút (nodes) được kết nối với nhau bởi các cạnh (edges).

Để dễ hình dung hơn, bạn có thể liên tưởng cấu trúc cây với một cây gia phả quen thuộc. Có một nút gốc (root) duy nhất đại diện cho tổ tiên cao nhất. Từ nút gốc này, các nhánh (cạnh) tỏa ra, nối đến các nút con (child nodes) – tương tự như con cháu trong gia đình. Mỗi nút con lại có thể tiếp tục có các nút con khác.

Điểm khác biệt cốt lõi của cây so với các cấu trúc dữ liệu tuyến tính như mảng (array) hay danh sách liên kết (linked list) nằm ở chỗ dữ liệu không được sắp xếp thành một hàng duy nhất. Thay vào đó, dữ liệu trong cây được tổ chức theo nhiều cấp độ, nhiều nhánh, cho phép mô hình hóa các mối quan hệ phức tạp một cách trực quan và tự nhiên.

Mỗi cây (trừ cây rỗng) sẽ có một nút đặc biệt gọi là nút gốc (root) – điểm khởi đầu của mọi nhánh. Các nút không có nút con được gọi là nút lá (leaf nodes), đánh dấu điểm kết thúc của một nhánh. Mối liên kết giữa các nút được thể hiện qua các cạnh (edges).

Tại sao cấu trúc dữ liệu Cây lại quan trọng?

Cấu trúc dữ liệu cây không chỉ là một khái niệm lý thuyết trong sách vở. Nó thực sự là nền tảng cho rất nhiều ứng dụng và hệ thống mà chúng ta sử dụng hàng ngày. Vậy tại sao cây lại quan trọng đến vậy trong khoa học máy tính (computer science) và lập trình (programming)?

Lý do chính đầu tiên là khả năng biểu diễn dữ liệu phân cấp một cách tự nhiên. Nhiều dữ liệu trong thế giới thực có cấu trúc thứ bậc rõ ràng, ví dụ như sơ đồ tổ chức công ty, cấu trúc thư mục tệp tin, hay thậm chí là cây phân loại sinh học. Cây cung cấp một mô hình hoàn hảo để thể hiện các mối quan hệ cha-con này.

Thứ hai, một số loại cây đặc biệt như Cây Nhị phân Tìm kiếm (Binary Search Tree – BST) hay các biến thể cân bằng của nó (AVL, Red-Black Tree) cho phép thực hiện các thao tác tìm kiếm, thêm, xóa dữ liệu cực kỳ hiệu quả. Với một cây cân bằng, các thao tác này thường chỉ mất thời gian logarith (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 không sắp xếp.

Thứ ba, cây là cấu trúc dữ liệu động (dynamic), nghĩa là kích thước của nó có thể thay đổi dễ dàng trong quá trình chạy chương trình. Bạn có thể thêm hoặc xóa các nút mà không cần phải định trước kích thước tối đa như mảng, mang lại sự linh hoạt cao trong quản lý bộ nhớ và dữ liệu.

Cuối cùng, cây là nền tảng cho nhiều thuật toán (algorithms) quan trọng khác. Ví dụ, thuật toán sắp xếp Heap Sort sử dụng cấu trúc dữ liệu Heap (một loại cây đặc biệt). Các thuật toán trong trí tuệ nhân tạo như Cây Quyết định (Decision Tree) cũng dựa trên cấu trúc này. Hiểu về cây mở ra cánh cửa để tiếp cận các khái niệm thuật toán phức tạp hơn.

Các thuật ngữ cơ bản cần nắm vững về Cây

Để làm việc hiệu quả với cấu trúc dữ liệu cây, việc nắm vững các thuật ngữ liên quan là điều cần thiết. Giống như học một ngôn ngữ mới, biết các “từ vựng” cơ bản sẽ giúp bạn hiểu và diễn đạt các khái niệm một cách chính xác.

Nút (Node): Nút Gốc (Root), Nút Lá (Leaf), Nút Trong (Internal Node)

• Nút (Node): Là thành phần cơ bản nhất của cây, chứa dữ liệu (key hoặc value) và các con trỏ (pointers) hoặc tham chiếu đến các nút con của nó. Mỗi vòng tròn bạn thấy trong sơ đồ cây thường biểu diễn một nút.
• Nút Gốc (Root Node): Là nút đặc biệt nằm ở vị trí cao nhất trong cây (mức 0). Nó là nút duy nhất không có nút cha (parent node). Mọi cây không rỗng đều có chính xác một nút gốc. Đây là điểm xuất phát để truy cập vào các nút khác trong cây.
• Nút Lá (Leaf Node): Là các nút nằm ở tận cùng của các nhánh, tức là chúng không có bất kỳ nút con nào (null children). Chúng đại diện cho điểm kết thúc của một đường đi trên cây.
• Nút Trong (Internal Node): Là bất kỳ nút nào không phải là nút gốc và cũng không phải là nút lá. Nói cách khác, đây là những nút có ít nhất một nút con và cũng có một nút cha.

Quan hệ giữa các Nút: Nút Cha (Parent), Nút Con (Child), Nút Anh Em (Sibling)

Mối quan hệ phân cấp trong cây được mô tả qua các thuật ngữ sau:

• Nút Cha (Parent Node): Một nút A được gọi là nút cha của nút B nếu có một cạnh nối trực tiếp từ A xuống B. Mỗi nút (trừ nút gốc) chỉ có duy nhất một nút cha.
• Nút Con (Child Node): Ngược lại với nút cha, nút B được gọi là nút con của nút A nếu có cạnh nối từ A xuống B. Một nút cha có thể có một hoặc nhiều nút con.
• Nút Anh Em (Sibling Nodes): Là các nút có cùng một nút cha. Chúng nằm cùng một cấp (level) trong cây và là con của cùng một nút.

Cạnh (Edge)

Cạnh (Edge) đơn giản là đường nối trực tiếp giữa hai nút, cụ thể là giữa một nút cha và một nút con của nó. Cạnh biểu diễn mối quan hệ trực thuộc giữa hai nút này. Số cạnh trong một cây luôn bằng số nút trừ đi 1 (Edges = Nodes – 1).

Đường đi (Path), Chiều dài đường đi (Path Length)

• Đường đi (Path): Là một chuỗi các nút liên tiếp được nối với nhau bằng các cạnh, bắt đầu từ một nút gốc (thường là nút gốc của cây hoặc cây con) đến một nút đích. Ví dụ: đường đi từ nút gốc A đến nút lá E có thể là A -> B -> D -> E.
• Chiều dài đường đi (Path Length): Là số lượng cạnh trên đường đi đó. Trong ví dụ trên (A -> B -> D -> E), có 3 cạnh, vậy chiều dài đường đi là 3.

Chiều cao (Height) của Nút và Cây

• Chiều cao của Nút (Height of a Node): Là chiều dài đường đi dài nhất từ nút đó đến một nút lá thuộc cây con gốc tại nút đó. Chiều cao của một nút lá luôn bằng 0.
• Chiều cao của Cây (Height of a Tree): Bằng chiều cao của nút gốc. Nó đại diện cho chiều dài đường đi dài nhất từ gốc đến bất kỳ nút lá nào trong cây. Chiều cao của cây rỗng thường được định nghĩa là -1.

Độ sâu (Depth) của Nút

Độ sâu (Depth) của Nút (còn gọi là Mức – Level): Là chiều dài đường đi từ nút gốc của cây đến nút đó. Độ sâu của nút gốc luôn bằng 0. Các nút con trực tiếp của gốc có độ sâu là 1, và cứ thế tăng dần xuống các cấp dưới.

Bậc (Degree) của Nút

Bậc (Degree) của Nút: Là số lượng cây con (hoặc số lượng nút con trực tiếp) của nút đó. Bậc của một nút lá luôn bằng 0. Trong cây nhị phân, bậc của mọi nút không thể vượt quá 2.

Cây con (Subtree)

Cây con (Subtree): Là một phần của cây lớn, bao gồm một nút và tất cả các hậu duệ (descendants) của nó. Mỗi nút trong cây (trừ nút lá) đều có thể coi là gốc của một hoặc nhiều cây con. Ví dụ, nếu nút B là con của nút gốc A, thì B và tất cả các nút bên dưới B tạo thành một cây con của cây gốc A.

Phân loại các cấu trúc dữ liệu Cây phổ biến

Thế giới của cấu trúc dữ liệu cây rất đa dạng, với nhiều loại cây khác nhau được thiết kế để giải quyết các vấn đề cụ thể hoặc tối ưu hóa cho các hoạt động nhất định. Dưới đây là một số loại cây phổ biến nhất mà bạn nên biết:

Cây Nhị phân (Binary Tree – BT)

Đây là loại cây cơ bản và phổ biến nhất. Cây Nhị phân (Binary Tree – BT) là một cây mà mỗi nút có tối đa hai nút con, thường được gọi là con trái (left child) và con phải (right child). Một nút có thể không có con nào, chỉ có con trái, chỉ có con phải, hoặc có cả hai.

Cây nhị phân có một số dạng đặc biệt:

• Cây nhị phân đầy đủ (Full Binary Tree): Mỗi nút trong cây đều có 0 hoặc 2 nút con.
• Cây nhị phân hoàn chỉnh (Complete Binary Tree): Tất cả các mức, trừ mức cuối cùng có thể, đều được lấp đầy hoàn toàn, và các nút ở mức cuối cùng được xếp từ trái sang phải. Cấu trúc này quan trọng cho Cây Heap.
• Cây nhị phân hoàn hảo (Perfect Binary Tree): Là cây nhị phân đầy đủ mà tất cả các nút lá đều ở cùng một mức (độ sâu).

Cây Nhị phân Tìm kiếm (Binary Search Tree – BST)

Cây Nhị phân Tìm kiếm (Binary Search Tree – BST) là một loại cây nhị phân đặc biệt với một thuộc tính thứ tự quan trọng:

• Với mọi nút trong cây, tất cả các khóa (keys) trong cây con trái của nó đều nhỏ hơn khóa của nút đó.
• Tất cả các khóa trong cây con phải của nó đều lớn hơn (hoặc bằng, tùy quy ước) khóa của nút đó.
• Cả cây con trái và cây con phải cũng đều phải là các cây nhị phân tìm kiếm.

Thuộc tính này giúp việc tìm kiếm (searching) một phần tử trong BST trở nên rất hiệu quả. Bắt đầu từ gốc, 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 trái; nếu lớn hơn, ta đi sang phải. Quá trình này lặp lại cho đến khi tìm thấy nút hoặc đi đến một vị trí null (không tìm thấy).

Tuy nhiên, hiệu quả của BST phụ thuộc vào hình dạng của cây. Trong trường hợp xấu nhất (ví dụ: thêm các phần tử đã sắp xếp tăng dần), cây có thể bị suy biến (degenerate) thành một danh sách liên kết, khiến thao tác tìm kiếm mất thời gian O(n).

Cây Nhị phân Tìm kiếm Cân bằng (Balanced BST)

Để khắc phục nhược điểm của BST thông thường (nguy cơ suy biến), người ta đã phát triển các loại Cây Nhị phân Tìm kiếm Cân bằng (Balanced BST). Mục tiêu của chúng là duy trì chiều cao của cây ở mức thấp nhất có thể (gần với log n) ngay cả khi thêm hoặc xóa các nút, đảm bảo hiệu suất O(log n) cho các thao tác chính.

Cây AVL (AVL Tree)

Cây AVL (AVL Tree), đặt tên theo hai nhà phát minh Adelson-Velsky và Landis, là cây BST tự cân bằng đầu tiên. Nó duy trì tính cân bằng bằng cách đảm bảo rằng tại mọi nút, chiều cao của cây con trái và cây con phải chênh lệch nhau không quá 1. Giá trị chênh lệch này gọi là hệ số cân bằng (balance factor).

Khi thêm hoặc xóa một nút có thể làm mất cân bằng (hệ số cân bằng > 1 hoặc < -1 tại một nút nào đó), cây AVL sẽ tự động thực hiện các phép xoay (rotations) – các thao tác sắp xếp lại cấu trúc cây cục bộ – để khôi phục lại tính cân bằng mà vẫn giữ nguyên thuộc tính BST. Có 4 loại phép xoay cơ bản: Xoay trái đơn, Xoay phải đơn, Xoay kép Trái-Phải, và Xoay kép Phải-Trái.

Cây Đỏ Đen (Red-Black Tree)

Cây Đỏ Đen (Red-Black Tree) là một loại cây BST tự cân bằng khác, được sử dụng rộng rãi trong thực tế (ví dụ: trong std::map và std::set của C++, TreeMap và TreeSet của Java). Nó đảm bảo cân bằng bằng cách tuân thủ một bộ quy tắc phức tạp hơn liên quan đến việc tô màu cho mỗi nút là Đỏ (Red) hoặc Đen (Black):

1. Mỗi nút là Đỏ hoặc Đen.
2. Nút gốc luôn là Đen.
3. Mọi nút lá (thường là các nút null tượng trưng) đều là Đen.
4. Nếu một nút là Đỏ, thì cả hai con của nó phải là Đen. (Không có hai nút Đỏ liên tiếp trên một đường đi từ gốc đến lá).
5. Mọi đường đi đơn giản từ một nút bất kỳ đến các nút lá hậu duệ của nó đều chứa cùng một số lượng nút Đen (Black-Height).

Các quy tắc này đảm bảo rằng đường đi dài nhất từ gốc đến lá không bao giờ dài hơn gấp đôi đường đi ngắn nhất, giữ cho cây tương đối cân bằng và đảm bảo hiệu suất O(log n) cho các thao tác. Việc cân bằng cũng được thực hiện thông qua các phép xoay và tô màu lại (recoloring).

Cây Heap (Heap)

Cây Heap (Heap) là một cấu trúc dữ liệu dựa trên cây nhị phân hoàn chỉnh (complete binary tree) đặc biệt, thỏa mãn tính chất Heap (Heap Property):

• Max Heap: Khóa của mỗi nút cha luôn lớn hơn hoặc bằng khóa của các nút con của nó. Do đó, nút gốc luôn chứa giá trị lớn nhất.
• Min Heap: Khóa của mỗi nút cha luôn nhỏ hơn hoặc bằng khóa của các nút con của nó. Nút gốc chứa giá trị nhỏ nhất.

Heap thường được cài đặt hiệu quả bằng mảng thay vì dùng con trỏ. Do tính chất cây nhị phân hoàn chỉnh, vị trí của nút cha và các nút con có thể dễ dàng tính toán qua chỉ số mảng. Heap là nền tảng của thuật toán sắp xếp Heap Sort và cấu trúc dữ liệu Hàng đợi Ưu tiên (Priority Queue), nơi cần lấy ra phần tử có độ ưu tiên cao nhất (lớn nhất hoặc nhỏ nhất) một cách nhanh chóng.

Cây B và B+ (B-Tree & B+ Tree)

Khác với các cây nhị phân, Cây B (B-Tree) và Cây B+ (B+ Tree) là các cây tìm kiếm đa phân (multi-way search trees) tự cân bằng. Điều này có nghĩa là mỗi nút có thể có nhiều hơn hai nút con và chứa nhiều khóa trong cùng một nút.

Đặc điểm này làm cho B-Tree và B+ Tree rất phù hợp cho các hệ thống lưu trữ dữ liệu trên đĩa cứng (disk-based storage) như cơ sở dữ liệu (databases) và hệ thống tệp (file systems). Việc đọc dữ liệu từ đĩa rất chậm so với từ bộ nhớ chính (RAM). B-Tree và B+ Tree giảm thiểu số lần truy cập đĩa bằng cách lưu trữ nhiều khóa trong một nút (tương ứng với một khối đĩa – disk block), làm cho cây “rộng” và “nông” hơn (chiều cao thấp).

Điểm khác biệt chính giữa B-Tree và B+ Tree là:

• B-Tree: Lưu cả khóa và dữ liệu (hoặc con trỏ tới dữ liệu) ở cả nút trong và nút lá.
• B+ Tree: Chỉ lưu khóa ở các nút trong (để điều hướng), còn tất cả các khóa và dữ liệu (hoặc con trỏ dữ liệu) đều nằm ở các nút lá. Các nút lá thường được liên kết với nhau bằng danh sách liên kết để hỗ trợ duyệt tuần tự (range queries) hiệu quả. Do đó, B+ Tree thường được ưu tiên sử dụng trong các hệ quản trị cơ sở dữ liệu.

Cây Trie (Prefix Tree / Radix Tree)

Cây Trie (phát âm là “try”), còn gọi là Cây Tiền tố (Prefix Tree) hoặc Cây Cơ số (Radix Tree), là một cấu trúc cây đặc biệt dùng để lưu trữ và tìm kiếm hiệu quả một tập hợp các chuỗi (strings). Mỗi nút trong Trie đại diện cho một tiền tố chung của các chuỗi. Các cạnh thường được gán nhãn bằng các ký tự.

Đường đi từ gốc đến một nút nào đó sẽ tạo thành một tiền tố. Nếu nút đó được đánh dấu là kết thúc của một từ, thì tiền tố đó chính là một từ trong tập hợp. Trie rất hiệu quả cho các bài toán liên quan đến tiền tố, ví dụ như:

• Kiểm tra xem một chuỗi có tồn tại trong từ điển không.
• Tìm tất cả các từ có cùng một tiền tố (ứng dụng trong gợi ý từ khóa – autocomplete hoặc tự động hoàn thành – auto-suggestion).
• Sắp xếp từ điển.

Các thao tác (phép toán) cơ bản trên Cây

Sau khi hiểu về cấu trúc và các loại cây, bước tiếp theo là tìm hiểu các thao tác cơ bản mà chúng ta có thể thực hiện trên chúng. Các thao tác này là nền tảng để xây dựng các thuật toán phức tạp hơn.

Duyệt cây (Tree Traversal) – Cách “thăm” các nút

Duyệt cây (Tree Traversal) là quá trình “thăm” (visit) tất cả các nút trong cây đúng một lần theo một thứ tự có hệ thống. Việc “thăm” có thể là in giá trị của nút, thực hiện một phép toán nào đó trên nút, hoặc đơn giản là đánh dấu nút đã được ghé qua. Có hai chiến lược duyệt cây chính:

Duyệt theo chiều sâu (Depth-First Search – DFS)

DFS ưu tiên đi sâu xuống một nhánh con trước khi quay lại và đi sang nhánh khác. Có ba cách duyệt DFS phổ biến trên cây nhị phân, thường được cài đặt bằng đệ quy (recursion) hoặc sử dụng ngăn xếp (stack):

1. Preorder (NLR – Node Left Right): Thăm nút gốc (N) -> Duyệt cây con trái (L) -> Duyệt cây con phải (R). Thứ tự này hữu ích khi cần sao chép cây hoặc lấy biểu thức tiền tố.
   • Ví dụ: Với cây gốc A, con trái B, con phải C. Thứ tự duyệt: A, B, C.
2. Inorder (LNR – Left Node Right): Duyệt cây con trái (L) -> Thăm nút gốc (N) -> Duyệt cây con phải (R). Trên cây BST, duyệt Inorder sẽ cho ra các khóa theo thứ tự tăng dần.
   • Ví dụ: Với cây gốc A, con trái B, con phải C. Thứ tự duyệt: B, A, C.
3. Postorder (LRN – Left Right Node): Duyệt cây con trái (L) -> Duyệt cây con phải (R) -> Thăm nút gốc (N). Thứ tự này hữu ích khi cần xóa cây (xóa con trước khi xóa cha) hoặc lấy biểu thức hậu tố.
   • Ví dụ: Với cây gốc A, con trái B, con phải C. Thứ tự duyệt: B, C, A.

Duyệt theo chiều rộng (Breadth-First Search – BFS)

Duyệt theo chiều rộng (BFS), còn gọi là duyệt theo mức (Level Order Traversal), thăm tất cả các nút ở cùng một mức (độ sâu) trước khi chuyển xuống mức tiếp theo. BFS thường được cài đặt sử dụng hàng đợi (queue).

• Quy tắc: Bắt đầu từ nút gốc, đưa gốc vào hàng đợi. Chừng nào hàng đợi còn phần tử, lấy một nút ra, “thăm” nút đó, sau đó lần lượt đưa các nút con (nếu có) của nó vào cuối hàng đợi (thường là từ trái sang phải).

BFS hữu ích khi cần tìm đường đi ngắn nhất từ gốc đến một nút nào đó (tính theo số cạnh) hoặc khi cần xử lý các nút theo từng cấp độ.

Tìm kiếm (Searching) trên Cây

Thao tác tìm kiếm là xác định xem một giá trị (khóa) cụ thể có tồn tại trong cây hay không, và nếu có thì nó nằm ở đâu. Cách tìm kiếm phụ thuộc vào loại cây:

• Trên cây thông thường (không có thứ tự): Thường phải duyệt cây (DFS hoặc BFS) và so sánh giá trị tại mỗi nút được thăm. Độ phức tạp là O(n).
• Trên Cây Nhị phân Tìm kiếm (BST): Tận dụng thuộc tính thứ tự để tìm kiếm hiệu quả hơn (O(h), với h là chiều cao cây, lý tưởng là O(log n) cho cây cân bằng).
  1. Bắt đầu từ gốc.
  2. So sánh giá trị cần tìm (target) với giá trị nút hiện tại (current).
  3. Nếu target == current: Tìm thấy.
  4. Nếu target < current: Đi sang cây con trái, lặp lại bước 2.
  5. Nếu target > current: Đi sang cây con phải, lặp lại bước 2.
  6. Nếu gặp nút null: Không tìm thấy.

Thêm nút (Insertion) vào Cây

Thao tác thêm một nút mới vào cây cũng phụ thuộc vào loại cây:

• Trên Cây Nhị phân Tìm kiếm (BST):
  1. Tìm vị trí thích hợp để chèn nút mới sao cho vẫn duy trì thuộc tính BST. Quá trình này tương tự như tìm kiếm.
  2. Đi từ gốc, so sánh giá trị cần chèn với nút hiện tại. Nếu nhỏ hơn đi sang trái, lớn hơn đi sang phải, cho đến khi gặp một vị trí con trỏ null.
  3. Tạo nút mới và gắn nó vào vị trí con trỏ null đó.
• Trên Cây cân bằng (AVL, Red-Black):
  1. Thực hiện chèn như BST thông thường.
  2. Sau khi chèn, kiểm tra xem có nút nào bị mất cân bằng không (dựa trên hệ số cân bằng hoặc quy tắc màu).
  3. Nếu có, thực hiện các phép xoay và/hoặc tô màu lại cần thiết để khôi phục tính cân bằng, bắt đầu từ nút mới chèn đi ngược lên gốc.

Xóa nút (Deletion) khỏi Cây

Xóa một nút khỏi cây, đặc biệt là BST, là thao tác phức tạp nhất vì cần đảm bảo cấu trúc cây (và thuộc tính BST) vẫn được duy trì sau khi xóa. Có ba trường hợp chính khi xóa nút X khỏi BST:

1. Nút X là nút lá (không có con): Đơn giản chỉ cần xóa nút X và cập nhật con trỏ của nút cha trỏ đến X thành null.
2. Nút X có một con: Thay thế nút X bằng nút con duy nhất của nó. Cập nhật con trỏ của nút cha của X trỏ trực tiếp đến nút con đó.
3. Nút X có hai con: Đây là trường hợp phức tạp nhất.
   • Tìm nút thay thế phù hợp cho X. Có hai lựa chọn phổ biến:
     • Nút lớn nhất trong cây con trái (Inorder Predecessor): Đi sang trái một bước, sau đó đi hết sang phải.
     • Nút nhỏ nhất trong cây con phải (Inorder Successor): Đi sang phải một bước, sau đó đi hết sang trái.
   • Sao chép giá trị của nút thay thế vào nút X.
   • Xóa nút thay thế khỏi vị trí gốc của nó (lúc này bài toán xóa quay về trường hợp 1 hoặc 2 vì nút thay thế chỉ có tối đa 1 con).

• Trên Cây cân bằng (AVL, Red-Black): Tương tự như khi thêm, sau khi thực hiện xóa theo logic BST, cần kiểm tra và thực hiện các phép xoay/tô màu lại để khôi phục tính cân bằng.

Ví dụ cài đặt cấu trúc dữ liệu cây

Lý thuyết là quan trọng, nhưng việc thấy code chạy thực tế sẽ giúp củng cố hiểu biết. Dưới đây là một số ví dụ cài đặt đơn giản bằng ngôn ngữ Python, tập trung vào Cây Nhị phân Tìm kiếm cơ bản.

Cài đặt Lớp Nút (Node Class)

Đầu tiên, chúng ta cần định nghĩa cấu trúc của một nút trong cây nhị phân. Mỗi nút sẽ chứa dữ liệu (ví dụ: key) và hai con trỏ tới nút con trái và con phải.

Python

class Node:
    """Đại diện cho một nút trong Cây Nhị phân Tìm kiếm."""
    def __init__(self, key):
        self.key = key  # Giá trị (khóa) của nút
        self.left = None  # Con trỏ tới nút con trái
        self.right = None # Con trỏ tới nút con phải

    def __str__(self):
        # Hàm tiện ích để in giá trị nút (cho dễ debug)
        return str(self.key)

Đoạn code trên định nghĩa lớp Node rất đơn giản. Hàm __init__ khởi tạo một nút mới với key cho trước, con trái và con phải ban đầu là None (rỗng).

Cài đặt cây nhị phân tìm kiếm (BST Class) cơ bản (Thêm, Tìm kiếm)

Bây giờ, chúng ta xây dựng lớp BinarySearchTree sử dụng lớp Node. Chúng ta sẽ cài đặt phương thức thêm (insert) và tìm kiếm (search) cơ bản.

Python

class BinarySearchTree:
    """Đại diện cho một Cây Nhị phân Tìm kiếm."""
    def __init__(self):
        self.root = None # Ban đầu cây rỗng, gốc là None

    # --- Thêm nút (Insert) ---
    def insert(self, key):
        """Thêm một khóa mới vào cây BST."""
        if self.root is None:
            # Nếu cây rỗng, nút mới trở thành gốc
            self.root = Node(key)
        else:
            # Gọi hàm đệ quy hỗ trợ để tìm vị trí chèn
            self._insert_recursive(self.root, key)

    def _insert_recursive(self, current_node, key):
        """Hàm đệ quy để chèn khóa vào cây con gốc tại current_node."""
        if key < current_node.key:
            # Đi sang trái
            if current_node.left is None:
                current_node.left = Node(key)
            else:
                self._insert_recursive(current_node.left, key)
        elif key > current_node.key:
            # Đi sang phải
            if current_node.right is None:
                current_node.right = Node(key)
            else:
                self._insert_recursive(current_node.right, key)
        # else: key == current_node.key -> Khóa đã tồn tại, không làm gì cả (hoặc cập nhật tùy yêu cầu)

    # --- Tìm kiếm (Search) ---
    def search(self, key):
        """Tìm kiếm một khóa trong cây BST."""
        return self._search_recursive(self.root, key)

    def _search_recursive(self, current_node, key):
        """Hàm đệ quy để tìm kiếm khóa trong cây con gốc tại current_node."""
        if current_node is None:
            # Đi hết nhánh mà không thấy -> không tồn tại
            return None
        elif key == current_node.key:
            # Tìm thấy khóa tại nút hiện tại
            return current_node
        elif key < current_node.key:
            # Tìm kiếm tiếp ở cây con trái
            return self._search_recursive(current_node.left, key)
        else: # key > current_node.key
            # Tìm kiếm tiếp ở cây con phải
            return self._search_recursive(current_node.right, key)

Lớp BinarySearchTree có thuộc tính root trỏ đến nút gốc. Các phương thức insert và search sử dụng hàm đệ quy (_insert_recursive, _search_recursive) để duyệt cây và thực hiện thao tác tương ứng theo logic của BST.

Ví dụ code duyệt cây Inorder (LNR) bằng đệ quy

Duyệt cây Inorder là một thao tác phổ biến, đặc biệt hữu ích trên BST vì nó trả về các khóa theo thứ tự tăng dần.

Python

# (Thêm phương thức này vào lớp BinarySearchTree)
    def inorder_traversal(self):
        """Thực hiện duyệt Inorder và trả về danh sách các khóa."""
        result = []
        self._inorder_recursive(self.root, result)
        return result

    def _inorder_recursive(self, current_node, result_list):
        """Hàm đệ quy duyệt Inorder."""
        if current_node is not None:
            # 1. Duyệt cây con trái (L)
            self._inorder_recursive(current_node.left, result_list)
            # 2. Thăm nút hiện tại (N) - ở đây là thêm vào danh sách kết quả
            result_list.append(current_node.key)
            # 3. Duyệt cây con phải (R)
            self._inorder_recursive(current_node.right, result_list)

# --- Ví dụ sử dụng ---
bst = BinarySearchTree()
nodes_to_insert = [50, 30, 70, 20, 40, 60, 80]
for node_key in nodes_to_insert:
    bst.insert(node_key)

print("Duyệt Inorder:", bst.inorder_traversal()) # Output: [20, 30, 40, 50, 60, 70, 80]

found_node = bst.search(40)
if found_node:
    print(f"Tìm thấy nút có khóa: {found_node.key}")
else:
    print("Không tìm thấy nút.")

not_found_node = bst.search(90)
if not_found_node:
     print(f"Tìm thấy nút có khóa: {not_found_node.key}")
else:
    print("Không tìm thấy nút có khóa 90.")

Ví dụ trên cho thấy cách thêm phương thức inorder_traversal vào lớp BinarySearchTree. Hàm đệ quy _inorder_recursive tuân thủ đúng quy tắc LNR. Kết quả khi chạy cho thấy danh sách các khóa được trả về theo đúng thứ tự tăng dần.

Lưu ý: Các ví dụ code trên chỉ mang tính minh họa cơ bản. Việc cài đặt đầy đủ các loại cây (đặc biệt là cây tự cân bằng như AVL, RBT hay B-Tree) phức tạp hơn đáng kể và thường người ta sẽ sử dụng các thư viện chuẩn có sẵn đã được tối ưu và kiểm thử kỹ lưỡng.

Phân tích độ phức tạp thuật toán (Complexity Analysis)

Hiểu về độ phức tạp thuật toán (algorithmic complexity), thường được biểu diễn bằng ký pháp Big O (Big O notation), giúp chúng ta đánh giá hiệu suất của các thao tác trên cây trong các trường hợp khác nhau (trung bình và xấu nhất). Điều này rất quan trọng để chọn đúng loại cây cho ứng dụng cụ thể.

Thao tác	BST (Trung bình)	BST (Xấu nhất)	AVL / Red-Black	Heap	B/B+ Tree (b là bậc)
Tìm kiếm	O(logn)	O(n)	O(logn)	O(n)	O(logb​n)
Thêm	O(logn)	O(n)	O(logn)	O(logn)	O(logb​n)
Xóa	O(logn)	O(n)	O(logn)	O(logn)	O(logb​n)
Lấy Min/Max	O(logn)	O(n)	O(logn)	O(1)	O(logb​n)
Duyệt (All)	O(n)	O(n)	O(n)	O(n)	O(n)

Giải thích:

• O(logn) (Logarithmic Time): Rất hiệu quả. Thời gian thực hiện tăng rất chậm khi số lượng phần tử (n) tăng lên. Đây là hiệu suất mong muốn của các cây cân bằng (AVL, RBT) và BST trong trường hợp trung bình. Đối với B/B+ Tree, cơ số logarit là bậc b của cây, nên hiệu suất càng tốt khi b lớn (tương ứng với chiều cao cây thấp).
• O(n) (Linear Time): Thời gian thực hiện tăng tuyến tính với số lượng phần tử. Đây là trường hợp xấu nhất của BST khi cây bị suy biến thành danh sách liên kết. Duyệt toàn bộ cây hoặc tìm kiếm trên Heap cũng mất O(n).
• O(1) (Constant Time): Cực kỳ hiệu quả. Thời gian thực hiện không đổi dù số lượng phần tử là bao nhiêu. Ví dụ điển hình là lấy phần tử nhỏ nhất (Min Heap) hoặc lớn nhất (Max Heap) từ gốc của Heap.

Bảng phân tích trên cho thấy rõ lợi ích của việc sử dụng cây cân bằng (AVL, Red-Black) hoặc B/B+ Tree khi cần đảm bảo hiệu suất ổn định O(logn) cho các thao tác tìm kiếm, thêm, xóa, tránh được trường hợp xấu O(n) của BST thông thường. Heap lại tỏa sáng khi cần truy cập nhanh phần tử nhỏ nhất/lớn nhất.

Ứng dụng thực tế của cấu trúc dữ liệu cây

Cấu trúc dữ liệu cây không chỉ tồn tại trong lý thuyết hay các bài tập lập trình. Chúng là xương sống của rất nhiều công nghệ và ứng dụng mà chúng ta tương tác hàng ngày:

Tổ chức hệ thống tệp tin (File Systems)

Hầu hết các hệ điều hành (Windows, macOS, Linux) sử dụng cấu trúc giống cây để quản lý tệp và thư mục. Mỗi thư mục là một nút, có thể chứa các tệp (nút lá) hoặc các thư mục con khác (nút trong). Cấu trúc phân cấp này giúp người dùng và hệ thống dễ dàng điều hướng và quản lý dữ liệu.

Lập chỉ mục cơ sở dữ liệu (Database Indexing – B/B+ Trees)

Như đã đề cập, B-Tree và đặc biệt là B+ Tree được sử dụng rộng rãi để tạo chỉ mục (index) trong các hệ quản trị cơ sở dữ liệu quan hệ (như MySQL, PostgreSQL, Oracle). Chỉ mục giúp tăng tốc độ truy vấn dữ liệu đáng kể bằng cách cho phép hệ thống nhanh chóng xác định vị trí của các bản ghi cần thiết trên đĩa mà không cần quét toàn bộ bảng.

Phân tích cú pháp HTML/XML (DOM Structure)

Khi trình duyệt web tải một trang HTML, nó sẽ xây dựng một cấu trúc cây gọi là Document Object Model (DOM). Mỗi thẻ HTML (như <html>, <body>, <div>, <p>) trở thành một nút trong cây DOM, phản ánh cấu trúc lồng nhau của tài liệu. Javascript sử dụng cây DOM này để truy cập và thay đổi nội dung, cấu trúc, kiểu dáng của trang web một cách động.

Thuật toán định tuyến mạng (Network Routing)

Một số thuật toán định tuyến trong mạng máy tính sử dụng cấu trúc cây (ví dụ: Spanning Tree Protocol – STP) để xác định đường đi tốt nhất và tránh các vòng lặp (loops) trong mạng. Các bộ định tuyến (routers) xây dựng bảng định tuyến dựa trên cấu trúc mạng, tương tự như một dạng cây phân cấp.

Sắp xếp dữ liệu (Heapsort)

Thuật toán sắp xếp Heap Sort sử dụng cấu trúc dữ liệu Max Heap (hoặc Min Heap) để sắp xếp một mảng dữ liệu với độ phức tạp thời gian ổn định O(nlogn). Nó xây dựng một Heap từ dữ liệu đầu vào, sau đó liên tục lấy phần tử lớn nhất (từ gốc Max Heap) đặt vào cuối mảng đã sắp xếp.

Cây quyết định trong AI/ML (Decision Trees)

Trong lĩnh vực Trí tuệ Nhân tạo (AI) và Học máy (Machine Learning), Cây Quyết định (Decision Tree) là một mô hình học có giám sát phổ biến. Nó sử dụng cấu trúc cây để đưa ra quyết định dựa trên các đặc trưng (features) của dữ liệu. Mỗi nút trong biểu diễn một bài kiểm tra trên một đặc trưng, mỗi nhánh biểu diễn kết quả của bài kiểm tra, và mỗi nút lá biểu diễn một nhãn lớp hoặc giá trị dự đoán.

Gợi ý từ khóa/Tự động hoàn thành (Autocomplete – Trie)

Cấu trúc cây Trie là lựa chọn lý tưởng cho các chức năng tự động hoàn thành hoặc gợi ý từ khóa mà bạn thấy trong các công cụ tìm kiếm, trình soạn thảo code, hoặc ứng dụng nhắn tin. Khi bạn gõ, hệ thống sử dụng Trie để nhanh chóng tìm tất cả các từ hoặc cụm từ có tiền tố trùng khớp với những gì bạn đã nhập.

Ngoài ra, cây còn có nhiều ứng dụng khác như trong thuật toán nén dữ liệu (Huffman Coding), xử lý biểu thức toán học, các thuật toán đồ thị, và nhiều lĩnh vực khác của khoa học máy tính.

---

Qua bài viết này, chúng ta đã cùng nhau khám phá thế giới phong phú của cấu trúc dữ liệu Tree (Cây). Từ định nghĩa cơ bản, các thuật ngữ quan trọng, đến việc phân loại các loại cây phổ biến như Cây Nhị phân, BST, AVL, Red-Black, Heap, B-Tree, B+ Tree, Trie, chúng ta đã thấy được sự đa dạng và vai trò không thể thiếu của chúng.

Chúng ta cũng đã tìm hiểu các thao tác cốt lõi như duyệt cây (DFS, BFS), tìm kiếm, thêm, xóa nút, cùng với việc phân tích độ phức tạp để đánh giá hiệu suất. Quan trọng hơn, việc nhận ra các ứng dụng thực tế của cây trong hệ thống tệp, cơ sở dữ liệu, web, AI… giúp chúng ta thấy rõ giá trị và tầm quan trọng của việc nắm vững cấu trúc dữ liệu này.

Hi vọng rằng, bài viết đã cung cấp cho bạn, dù là sinh viên đang học hay lập trình viên muốn củng cố kiến thức, một nền tảng vững chắc về cấu trúc dữ liệu cây. Đây là một chủ đề rộng lớn và luôn có những khía cạnh sâu hơn để khám phá.