DSA Từ A-Z: Day 4 – Cấu Trúc Cây (Phần 1: Cây Nhị Phân)

Học AI cùng Losers – Nơi kẻ thất bại không bao giờ bỏ cuộc!

Hôm nay chúng ta sẽ cùng “đối mặt” với một trong những cấu trúc dữ liệu KHỦNG nhất: CÂY. Đừng lo nếu bạn cảm thấy choáng ngợp – hãy coi mỗi nút cây như một bài toán nhỏ, và Loser1 sẽ cùng bạn “chặt” từng nhánh một!

1. Giới Thiệu về Cây

Cây là một cấu trúc dữ liệu phi tuyến tính, hierarchical (có cấp bậc) được sử dụng để biểu diễn và tổ chức dữ liệu theo cách phân cấp. Trong thực tế, chúng ta có thể thấy cấu trúc cây ở khắp mọi nơi: cây gia phả, cấu trúc thư mục trong máy tính, hay thậm chí là cấu trúc tổ chức của một công ty.

1.1. Định Nghĩa và Thuật Ngữ Cơ Bản

Một cây bao gồm các thành phần sau:

• Node (Nút): Đơn vị cơ bản của cây, chứa dữ liệu và các liên kết đến node khác
• Root (Gốc): Node đầu tiên của cây
• Edge (Cạnh): Liên kết giữa hai node
• Parent (Cha): Node trực tiếp ở trên node hiện tại
• Child (Con): Node trực tiếp ở dưới node hiện tại
• Leaf (Lá): Node không có con
• Height (Chiều cao): Đường đi dài nhất từ root đến leaf
• Depth (Độ sâu): Khoảng cách từ root đến node hiện tại

1.2. Cài Đặt Cơ Bản của Node trong Cây

struct TreeNode {
    int val;                // Data stored in the node
    TreeNode* left;         // Pointer to left child
    TreeNode* right;        // Pointer to right child

    // Constructor
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

1.3. Các Loại Cây Phổ Biến

1. Cây Nhị Phân (Binary Tree): Mỗi node có tối đa 2 con
2. Cây Nhị Phân Tìm Kiếm (BST): Cây nhị phân với tính chất: node trái < node hiện tại < node phải
3. Cây Cân Bằng (AVL, Red-Black): Cây tự cân bằng để đảm bảo hiệu suất
4. Heap: Cây nhị phân hoàn chỉnh thỏa mãn tính chất heap

---

1. Binary Trees: Trái Tim Của Mọi Thuật Toán

1.1 Tree Traversals – “Bản Đồ” Duyệt Cây

Visualization:

        A
       / \
      B   C
     / \   \
    D   E   F

Cùng “đi lạc” trong khu rừng cây nhị phân với 4 cách duyệt cơ bản!

a. Pre-order Traversal (Tiền Thứ Tự)

Code:

// Pre-order traversal: Root -> Left -> Right
void preOrder(Node* root) {
    if (root == nullptr) return;
    cout << root->data << " "; // Visit root
    preOrder(root->left);       // Traverse left
    preOrder(root->right);      // Traverse right
}

Giải thích:

1. “Đập mặt” nút gốc đầu tiên
2. “Xâm nhập” sang nhánh trái, lặp lại quy trình
3. Khi nhánh trái “cạn kiệt”, quay sang nhánh phải
   Kết quả ví dụ: A → B → D → E → C → F

b. In-order Traversal (Trung Thứ Tự)

Code:

// In-order traversal: Left -> Root -> Right
void inOrder(Node* root) {
    if (root == nullptr) return;
    inOrder(root->left);        // Traverse left
    cout << root->data << " ";  // Visit root
    inOrder(root->right);       // Traverse right
}

Giải thích:

1. “Lén lút” đi đến nút trái cùng
2. “Khai hoá” nút đó
3. Quay lại cha của nó, rồi sang nhánh phải
   Kết quả ví dụ: D → B → E → A → C → F

c. Post-order Traversal (Hậu Thứ Tự)

Code:

// Post-order traversal: Left -> Right -> Root
void postOrder(Node* root) {
    if (root == nullptr) return;
    postOrder(root->left);      // Traverse left
    postOrder(root->right);     // Traverse right
    cout << root->data << " ";  // Visit root
}

Giải thích:

1. “Quét sạch” toàn bộ nhánh trái
2. “Thanh toán” nhánh phải
3. Cuối cùng mới xử lý nút gốc
   Kết quả ví dụ: D → E → B → F → C → A

d. Level-order Traversal (Duyệt Theo Tầng)

Code sử dụng Queue:

// Level-order traversal using BFS
void levelOrder(Node* root) {
    if (root == nullptr) return;

    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* current = q.front();
        q.pop();
        cout << current->data << " ";

        if (current->left) q.push(current->left);
        if (current->right) q.push(current->right);
    }
}

Giải thích:

1. “Tung” root vào queue
2. Lặp: Lấy node đầu queue → in → “ném” con vào queue
3. Giống thuật toán BFS trong đồ thị
   Kết quả ví dụ: A → B → C → D → E → F

Để minh họa các phương pháp duyệt cây này, hãy xem ví dụ sau:

Tiếp theo, tôi sẽ tiếp tục với phần Cây Nhị Phân Tìm Kiếm (BST) và các hoạt động cơ bản trên BST. Bạn có muốn tôi tiếp tục không?

---

1.2 Binary Search Trees (BST) – “Kho Tàng” Sắp Xếp

Visualization:

        8
       / \
      3   10
     / \   \
    1   6   14

BST – Nơi mọi nút trái đều nhỏ hơn cha, nút phải đều lớn hơn cha!

a. Tìm Kiếm Trong BST

Code:

// BST Search: O(h) time complexity
Node* search(Node* root, int key) {
    if (root == nullptr || root->data == key)
        return root;

    if (key < root->data)
        return search(root->left, key);
    else
        return search(root->right, key);
}

Giải thích:

1. So sánh key với nút hiện tại
2. Nhỏ hơn → rẽ trái, lớn hơn → rẽ phải
3. Đệ quy đến khi tìm thấy hoặc gặp nullptr

b. Thêm Node Mới

Code:

// BST Insertion: Maintain BST property
Node* insert(Node* root, int value) {
    if (root == nullptr) 
        return new Node(value);

    if (value < root->data)
        root->left = insert(root->left, value);
    else if (value > root->data)
        root->right = insert(root->right, value);

    return root;
}

Giải thích:

1. Tìm vị trí “hợp lệ” theo BST property
2. Khi gặp nullptr → tạo node mới
3. “Lắp ráp” lại cây qua các lần return

c. Xóa Node – “Ác Mộng” Của Mọi Newbie

Code:

// BST Deletion: 3 cases
Node* deleteNode(Node* root, int key) {
    if (root == nullptr) return root;

    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        // Case 1: No child
        if (root->left == nullptr && root->right == nullptr) {
            delete root;
            root = nullptr;
        }
        // Case 2: One child
        else if (root->left == nullptr) {
            Node* temp = root;
            root = root->right;
            delete temp;
        }
        else if (root->right == nullptr) {
            Node* temp = root;
            root = root->left;
            delete temp;
        }
        // Case 3: Two children
        else {
            Node* successor = findMin(root->right);
            root->data = successor->data;
            root->right = deleteNode(root->right, successor->data);
        }
    }
    return root;
}

Giải thích 3 Trường Hợp:

1. Node lá: Xóa thẳng, không ảnh hưởng cấu trúc
2. Một con: “Cắt” node, nối cha với con duy nhất
3. Hai con: Tìm successor (node nhỏ nhất bên phải), thay thế và xóa successor

---

1.3 Các Phép Toán Cơ Bản

a. Tính Chiều Cao Cây

Code:

// Tree Height: Max depth from root to leaf
int height(Node* root) {
    if (root == nullptr)
        return -1; // or 0 depending on definition
    return 1 + max(height(root->left), height(root->right));
}

Giải thích:

• Chiều cao = 1 + max(chiều cao nhánh trái, phải)
• Node lá có chiều cao 0 (nếu định nghĩa base case là -1)

b. Kiểm Tra BST

Code:

// Check BST using range
bool isBST(Node* root, Node* min = nullptr, Node* max = nullptr) {
    if (root == nullptr) return true;

    if ((min && root->data <= min->data) || 
        (max && root->data >= max->data))
        return false;

    return isBST(root->left, min, root) && 
           isBST(root->right, root, max);
}

Giải thích:

• Mỗi node phải nằm trong khoảng (min, max)
• Khi rẽ trái: cập nhật max = current node
• Khi rẽ phải: cập nhật min = current node

---

2. Visualizations Sinh Động

2.1 BST Insertion Animation

Trước khi thêm 7:

        5
       / \
      3   8
     / \
    2   4

Sau khi thêm 7:

        5
       / \
      3   8
     / \  /
    2   4 7

Node 7 “chui” vào vị trí hợp lệ bên trái 8

2.2 BST Deletion Visualization

Xóa node 3 (có 2 con):

        5                      5
       / \                    / \
      3   8    ==>           4   8
     / \                    /
    2   4                  2

Successor (4) thế chỗ 3, cây vẫn giữ nguyên tính chất BST

---

3. Bài Tập Thực Hành

3.1 Easy: Đếm Số Node Trong Cây

int countNodes(Node* root) {
    if (root == nullptr) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

Gợi ý: Tổng = 1 (node hiện tại) + tổng nhánh trái + tổng nhánh phải

3.2 Medium: Kiểm Tra Cây Đối Xứng

bool isSymmetric(Node* root) {
    return isMirror(root, root);
}

bool isMirror(Node* t1, Node* t2) {
    if (t1 == nullptr && t2 == nullptr) return true;
    if (t1 == nullptr || t2 == nullptr) return false;
    return (t1->data == t2->data) &&
           isMirror(t1->right, t2->left) &&
           isMirror(t1->left, t2->right);
}

Mẹo: Coi cây như 2 cây con và kiểm tra mirror từng cặp node

---

4. Kết Luận & Bài Học Cuộc Sống

Cây nhị phân giống như cuộc đời mỗi người:

• Pre-order: Hành động trước khi suy nghĩ
• In-order: Cân bằng giữa suy nghĩ và hành động
• Post-order: Học từ sai lầm sau khi hành động

Hãy là một BST – Luôn biết vị trí của mình trong vũ trụ!

Hẹn gặp lại ở Phần 2: Balanced Trees – Khi cây học cách “giữ thăng bằng” trong cuộc sống!

Loser1 tip: Bạn thấy bài viết có ích? Hãy chia sẻ để 10 người bạn cùng đọc - vì chúng ta là những kẻ thất bại BIẾT CÁCH ĐỨNG LÊN!