1. Mở đầu

Bạn đã từng tổ chức thư mục trên máy tính chưa? Như có thư mục Projects chứa Web, Mobile, rồi trong Web lại có HTML, CSS, vân vân…? Cấu trúc đó chính là một cây, một cách tự nhiên và thông minh để sắp xếp dữ liệu không theo hàng ngang (line), mà theo dạng phân cấp (hierarchy). Trong lập trình, cây không chỉ giúp bạn “nhìn thấy” cấu trúc dữ liệu rõ ràng mà còn tối ưu hiệu suất thao tác nữa. Vậy, cây là gì, cấu thành ra sao, và vì sao nó quan trọng như thế?

2. Nội dung chính

2.1 Cây là gì?

Khái niệm đơn giản: Cây là cấu trúc dữ liệu dạng phân nhánh, nơi có một nút gốc (root), từ đó tỏa ra các nút con (child nodes) theo kiểu đệ quy, tạo nên một mạng lưới “lưới tổ ong” không lặp lại đường đi (GeeksforGeeks).
Tại sao gọi là “non-linear” (không tuyến tính)? Vì các phần tử không nằm nối tiếp như trong mảng hay danh sách liên kết mà phân bố trên nhiều cấp, theo kiểu “cây cổ thụ” (cấp trên – cấp dưới) (GeeksforGeeks).
Các thuật ngữ cơ bản:
- Root: nút đầu tiên, không có cha.
- Node: chứa dữ liệu, là thành phần cơ bản.
- Parent – Child, Subtree, Leaf (nút lá),… (GeeksforGeeks).

2.2 Các loại cây phổ biến (bottom-up approach)

Cây tổng quát (General Tree / N-ary Tree) Mỗi nút có thể có nhiều con (không giới hạn). Ví dụ 1 (trong lập trình): Cấu trúc thư mục máy tính—thư mục mẹ có nhiều thư mục con. Ví dụ 2 (đời sống): Sơ đồ tổ chức: Giám đốc → các trưởng phòng → nhân viên.
Cây nhị phân (Binary Tree) Mỗi nút tối đa có 2 con (trái và phải) (GeeksforGeeks, Wikipedia). Ví dụ 1: Trong lập trình, cây quyết định game (Decision Tree) đơn giản, tại mỗi nút hỏi “có hay không”. Ví dụ 2 (đời thường): Trò chơi "đi/bên trái hay bên phải" — tại mỗi ngã, chọn một trong hai.
Binary Search Tree (BST) Cây nhị phân mà bên trái chỉ nút nhỏ hơn, bên phải nút lớn hơn — giúp tìm nhanh (Search), thêm (Insert), xóa (Delete) thật sướng (GeeksforGeeks, Wikipedia). Ví dụ 1 (lập trình): Bạn lưu điểm số học sinh; tìm nhanh ai cao hơn, ai thấp hơn. Ví dụ 2 (đời sống): Tự sắp xếp sách theo chiều cao: bên trái thấp hơn, bên phải cao hơn.
Các dạng khác: AVL, Red-Black, B-Tree, Trie…
- AVL, Red-Black: Tự cân bằng để tránh đổ về dạng “một vạch” (chậm) như danh sách liên kết (GeeksforGeeks, Wikipedia).
- B-Tree / B+ Tree: Cho phép nhiều con, thường dùng trong lưu trữ cơ sở dữ liệu (database) (GeeksforGeeks, Wikipedia).
- Trie (cây tiền tố): Tìm từ theo từng chữ cái rất nhanh, thường dùng trong từ điển, auto-complete (GeeksforGeeks).

2.3 Tại sao dùng Cây? Ứng dụng thực tế

File system (hệ thống tập tin) — thư mục/phần mềm (GeeksforGeeks).
Trình biên dịch (compiler) — dùng cây cú pháp (syntax tree) để phân tích code (GeeksforGeeks).
URI/XML/HTML — cây DOM (cấu trúc dữ liệu trình duyệt) (GeeksforGeeks).
Trie — gợi từ, từ điển tự động hoàn thành (GeeksforGeeks).
AI / game (Decision Tree) — quyết định logic chơi (GeeksforGeeks). … và nhiều hơn nữa như DNS, mạng, đồ họa, AI, indexing trong DB (GeeksforGeeks).

2.4 Đoạn code minh hoạ (C++, đơn giản)

#include <iostream>
using namespace std;

// Khai báo nút của Binary Tree
struct Node {
    int data;       // Dữ liệu
    Node* left;     // Con trái
    Node* right;    // Con phải
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

int main() {
    // Tạo cây đơn giản:
    //     10
    //    /  \
    //   5    15
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);

    cout << "Goc: " << root->data << "\n";
    cout << "Con trai cua goc: " << root->left->data << "\n";
    cout << "Con phai cua goc: " << root->right->data << "\n";

    // Dọn bộ nhớ (simplified)
    delete root->left;
    delete root->right;
    delete root;
    return 0;
}

Mỗi nút gồm dữ liệu data và hai con left, right. Bạn có thể mở rộng thành cây nhiều nhánh nếu muốn.

2.5 Minh hoạ ASCII nhỏ

      [ROOT]
       /  \
   [A]     [B]
   /
[C]

ROOT là gốc, A và B là con. C là con của A.
Cấu trúc rõ ràng, dễ hình dung và truy cập theo thứ tự riêng (traversal).

2.6 Tương tác nhẹ

Bạn thử suy nghĩ nhé:

Thử thách: Hãy tưởng tượng bạn có BST chứa số 20, 10, 30, 5, 15. Hãy vẽ nó bằng tay và thử tìm xem số 15 nằm ở đâu? (Gợi ý: so sánh từ gốc, đi trái hay phải?)
Tự hỏi: Nếu tôi thêm số 25 và 35, cây có cân bằng không? Nếu không, có cách nào tự cân bằng BST?

3. Kết luận

Cây là cấu trúc dữ liệu phân cấp, giúp sắp xếp và truy xuất dữ liệu hiệu quả và trực quan.
Các dạng quan trọng: General Tree, Binary Tree, BST, Self-balancing Tree (AVL, Red-Black), B-Tree, Trie…
Ứng dụng: Từ thư mục máy tính đến trình biên dịch, từ game AI đến autocompletion, và rất nhiều nữa!
Lời khuyên: Bắt đầu bằng cây nhị phân (binary tree), vẽ vời và viết code thật nhiều. Khi thấy chán vì BST đôi khi chậm (do lệch), hãy tìm hiểu AVL/Red-Black nhé.

4. Tài liệu tham khảo thêm

GeeksforGeeks – Introduction to Tree Data Structure (cập nhật 27 Jul 2025) (GeeksforGeeks)
GeeksforGeeks – Types of Trees in Data Structures (23 Jul 2025) (GeeksforGeeks)
GeeksforGeeks – Binary Tree Data Structure (2 Aug 2025) (GeeksforGeeks)
GeeksforGeeks – Applications of tree data structure (2 weeks ago) (GeeksforGeeks)

Chúc bạn có một hành trình học cây thật thú vị và dễ hiểu! Nếu cần giải thích thêm hay giúp code, cứ nhắn nhé!

Cấu trúc dữ liệu cây (tree)