Cây (Tree)

Cấu trúc dữ liệu dạng cây (Tree Data Structure) là một dạng đồ thị không có chu trình, trong đó có một nút gốc và các nút con được sắp xếp theo một cấu trúc phân cấp. Cây thường được sử dụng để biểu diễn các quan hệ phân cấp, chẳng hạn như cây phân loại, cây thư mục, hoặc cây tìm kiếm.

Các thành phần chính của cây:

Nút (Node): Một phần tử của cây, chứa một giá trị hoặc thông tin.
Cạnh (Edge): Liên kết giữa hai nút, đại diện cho mối quan hệ cha-con giữa các nút.
Nút gốc (Root): Nút nằm ở đỉnh của cây, không có nút cha.
Nút lá (Leaf): Nút không có nút con.
Nút cha (Parent Node): Nút có một hoặc nhiều nút con.
Nút con (Child Node): Nút có một nút cha.

Các loại cây phổ biến:

Cây nhị phân (Binary Tree): Mỗi nút có tối đa hai nút con.
Cây tìm kiếm nhị phân (Binary Search Tree - BST): Một cây nhị phân với điều kiện mỗi nút, giá trị của tất cả các nút con bên trái nhỏ hơn giá trị của nút đó và giá trị của tất cả các nút con bên phải lớn hơn giá trị của nút đó.
Cây cân bằng (Balanced Tree): Một loại cây mà độ sâu của các nhánh khác nhau không chênh lệch quá nhiều, ví dụ như AVL tree, Red-Black tree.
Cây B (B-tree): Một cấu trúc cây cân bằng đa nhánh, thường được sử dụng trong các hệ thống cơ sở dữ liệu và hệ thống tập tin.

Cách biểu diễn cây:

Liên kết (Linked Representation): Mỗi nút là một đối tượng có thể chứa con trỏ hoặc tham chiếu đến các nút con của nó.

Ví dụ cây nhị phân:
C++:
#include <iostream>

class Node {
public:
int val;
Node* left;
Node* right;

// Constructor
Node(int key) {
val = key;
left = nullptr;
right = nullptr;
}
};

int main() {
// Creating a node with value 10
Node* root = new Node(10);
std::cout << "Node created with value: " << root->val << std::endl;

// Clean up the allocated memory
delete root;

return 0;
}
Mảng (Array Representation): Đối với cây nhị phân đầy đủ, cây có thể được biểu diễn bằng một mảng, trong đó nút tại vị trí i có các nút con tại vị trí 2i+1 (con trái) và 2i+2 (con phải).

Các thao tác cơ bản trên cây:

Duyệt cây (Tree Traversal): Các thuật toán duyệt cây như duyệt trước (preorder), duyệt giữa (inorder), duyệt sau (postorder), và duyệt theo mức (level order).

Ví dụ:
- Duyệt trước (Preorder): Thăm nút gốc, sau đó thăm cây con bên trái, rồi thăm cây con bên phải.
- Duyệt giữa (Inorder): Thăm cây con bên trái, sau đó thăm nút gốc, rồi thăm cây con bên phải.
- Duyệt sau (Postorder): Thăm cây con bên trái, sau đó thăm cây con bên phải, rồi thăm nút gốc.
Thêm nút (Insertion): Thêm một nút vào cây tuân theo các quy tắc của loại cây đó (ví dụ: thêm vào cây tìm kiếm nhị phân).
Xóa nút (Deletion): Xóa một nút khỏi cây và điều chỉnh cây để duy trì cấu trúc hợp lệ.
Tìm kiếm (Search): Tìm một nút với giá trị cụ thể trong cây.

Các ứng dụng của cây:

Cây thư mục (File System): Quản lý cấu trúc thư mục và tập tin trong hệ điều hành.
Cây biểu thức (Expression Tree): Biểu diễn các biểu thức toán học trong các trình biên dịch.
Cây tìm kiếm (Search Trees): Sử dụng trong các cấu trúc dữ liệu và thuật toán tìm kiếm, như trong cơ sở dữ liệu và hệ thống tệp.
Cây trò chơi (Game Trees): Biểu diễn các trạng thái và nước đi trong trò chơi.

Cấu trúc dữ liệu cây là một phần quan trọng trong khoa học máy tính và được sử dụng rộng rãi trong nhiều lĩnh vực khác nhau để tổ chức và quản lý dữ liệu hiệu quả.

Định nghĩa cấu trúc nút

Nhìn vào hình, ta có thể dễ dàng phân tích được rằng, mỗi nút trong cây nhị phân sẽ gồm 3 thành phần như sau:

Thành phần dữ liệu: có thể là bất kỳ kiểu dữ liệu nào.
Thành phần liên kết trái: lưu trữ địa chỉ của nút gốc của cây con bên trái. Kiểu dữ liệu là con trỏ trỏ vào node.
Thành phân liên kết phải: lưu trữ địa chỉ của nút gốc của cây con bên phải. Kiểu dữ liệu là con trỏ trỏ vào node.

Chúng ta sẽ có struct lưu trữ một node như sau – ở đây để đơn giản mình sử dụng kiểu dữ liệu int cho thành phần dữ liệu của node:

struct Node
{
    int data;
    Node *left;
    Node *right;
};

Khi tạo một nút node mới, chúng ta cần phải gán lại các thành phần của node để nó không nhận giá trị rác, tránh lỗi không mong muốn. Chúng ta sẽ tạo một biến động cho node và trả về địa chỉ của node đó, mình sẽ có đoạn code tạo node như sau:

Node *CreateNode(int init)
{
    Node *p = new Node;
    p->data = init;
    p->left = NULL;
    p->right = NULL;
    return p;
}

Định nghĩa cấu trúc cây

Để quản lý một cái cây, bạn chỉ cần quản lý được nút gốc, bạn có thể đi được đến các nhánh và lá của nó từ đó. Trên thực tế bạn không cần phải định nghĩa một kiểu dữ liệu nào để quản lý cả, tuy nhiên, để cho code rõ ràng hơn, bạn nên định nghĩa một kiểu dữ liệu cây nữa.

typedef Node* Tree;

Lúc này, khi tạo một cây, bản chất là nó sẽ tạo cho bạn một con trỏ có thể trỏ vào một node.

Tree myTree;

Vì nó là con trỏ nên các bạn gán nó bằng NULL để tránh lỗi, nhưng để mọi thứ rõ ràng hơn, mình sẽ dùng hàm tạo cây đơn giản gán nó bằng NULL.

void CreateTree(Tree &root)
{
    root = NULL;
}

// Khi tạo cây
CreateTree(myTree);

Duyệt cây nhị phân

Có 3 cách duyệt cây nhị phân:

Duyệt tiền tự (NLR): duyệt nút gốc, duyệt tiền tự cây con trái, duyệt tiền tự cây con phải.
Duyệt trung tự (LNR): duyệt trung tự cây con trái, duyệt nút gốc, duyệt trung tự cây con phải.
Duyệt hậu tự (LRN): duyệt hậu tự cây con trái, duyệt hậu tự cây con phải, duyệt nút gốc.

Để bạn hiểu rõ hơn ba cách duyệt này, chúng ta sẽ sử dụng lại hình ảnh cây nhị phân trên:

Duyệt tiền tự: A B D H I E K L C F M N G O P
Duyệt trung tự: H D I B K E L A M F N C O G P
Duyệt hậu tự: H I D K L E B M N F O P G C A

Ứng với từng cách duyệt đó, chúng ta sẽ có các hàm duyệt cây như sau:

Duyệt tiền tự

void NLR(Tree root)
{
    if (root)
    {
        // Xử lý nút gốc (root)
        NLR(root->left);
        NLR(root->right);
    }
}

Duyệt trung tự

void LNR(Tree root)
{
    if (root)
    {
        LNR(root->left);
        // Xử lý nút gốc (root)
        LNR(root->right);
    }
}

Duyệt hậu tự

void LRN(Tree root)
{
    if (root)
    {
        LRN(root->left);
        LRN(root->right);
        // Xử lý nút gốc (root)
    }
}

Hủy cây nhị phân

Để hủy đi cây nhị phân, các bạn cũng thực hiện duyệt và xóa đi các nút của cây, tuy nhiên, các bạn dễ thấy rằng, nếu ta duyệt tiền tự và trung tự, khi xóa nút nhánh thì sẽ bị mất luôn địa chỉ của các nút con. Do đó, việc hủy cây nhị phân bắt buộc phải duyệt hậu tự. Hay nói cách khác, bạn phải xóa các phần tử là nút lá xóa dần lên đến nút gốc.

Chúng ta sẽ có hàm hủy như sau:

void DestroyTree(Tree &root)
{
    if (root)
    {
        DestroyTree(root->left);
        DestroyTree(root->right);
        delete root;
    }
}

Cây nhị phân tìm kiếm

Cây nhị phân tìm kiếm là cây nhị phân mà trong đó, các phần tử của cây con bên trái đều nhỏ hơn phần tử hiện hành và các phần tử của cây con bên phải đều lớn hơn phần tử hiện hành. Do tính chất này, cây nhị phân tìm kiếm không được có phần tử cùng giá trị.

Nhờ vào tính chất đặc biệt này, cây nhị phân tìm kiếm được sử dụng để tìm kiếm phần tử nhanh hơn (tương tự với tìm kiếm nhị phân). Khi duyệt cây nhị phân theo cách duyệt trung tự, bạn sẽ thu được một mảng có thứ tự. Chúng ta sẽ lần lượt tìm hiểu qua chúng.

Thêm phần tử vào cây nhị phân tìm kiếm

Để thêm phần tử vào cây nhị phân tìm kiếm, ta phải thêm vào cây nhưng vẫn đảm bảo được cây đó vẫn là cây nhị phân tìm kiếm. Ví dụ thêm phần tử 12 vào cây trong hình trên, mình sẽ cần chèn vào vị trí bên trái 13. Hàm duyệt tìm vị trí thích hợp và chèn của mình như sau:

void AddNode(Tree &root, Node *node)
{
    if (root)
    {
        if (root->data == node->data) // Nếu bị trùng giá trị thì không thêm
            return;
        if (node->data < root->data) // Thêm vào cây con bên trái (nhỏ hơn nút hiện tại)
            AddNode(root->left, node);
        else
            AddNode(root->right, node); // Thêm vào cây con bên phải (lớn hơn nút hiện tại)
    }
    else
    {
        root = node; // Đã tìm thấy vị trí thích hợp, thêm node vào
    }
}

Tìm một phần tử trong cây nhị phân tìm kiếm

Như đã giới thiệu ở trên, để tìm một phần tử trong cây nhị phân tìm kiếm, chúng ta sẽ thực hiện tương tự việc tìm kiếm nhị phân. Nếu như nút cần tìm nhỏ hơn nút đang xét, chúng ta sẽ tìm cây con bên trái, ngược lại chúng ta sẽ tìm trong cây con bên phải, nếu đúng nút cần tìm thì mình sẽ trả về địa chỉ của nút đó. Mình sẽ có thuật toán sau:

Node *FindNode(Tree root, int x)
{
    if (root)
    {
        if (root->data == x) // Tìm thấy
            return root;
        if (x < root->data)
            return FindNode(root->left, x); // Tìm cây con bên trái
        return FindNode(root->right, x); // Tìm cây con bên phải
    }
    return NULL; // Không tìm thấy
}

Hủy nút trên cây nhị phân tìm kiếm

Để hủy một nút có khóa X trong cây nhị phân tìm kiếm, chúng ta cần giải quyết ba trường hợp sau:

Nút X là nút lá, ta xóa đi mà không làm ảnh hưởng đến các nút khác. Ví dụ xóa nút 15 đi không ảnh hưởng gì đến các nút khác.
Nút X có 1 cây con, chúng ta chỉ cần nối nút cha của X với nút con của X. Ví dụ xóa nút 13 đi, ta chỉ cần nối nút 18 và 15 lại, sau đó xóa nút 13 đi.
Nút X có đầy đủ 2 cây con: vì X có đầy đủ 2 nút nên nếu ta xóa đi, ta sẽ bị mất toàn bộ cây con. Do đó chúng ta cần tìm phần tử thế mạng cho X mà vẫn đảm bảo được cây nhị phân tìm kiếm, sau đó mới xóa X đi.

Đối với hai trường hợp đầu thì dễ, tuy nhiên, với trường hợp thứ 3, chúng ta cần phải giải quyết vấn đề tìm phần tử thế mạng cho x, chúng ta sẽ có hai cách thực hiện như sau:

Nút thế mạng là nút có khóa nhỏ nhất (trái nhất) của cây con bên phải x.
Nút thế mạng là nút có khóa lớn nhất (phải nhất) của cây con bên trái x.

Lấy ví dụ cho các bạn dễ hiểu hơn, hình phía trên, xóa đi phần tử 18 theo cách 1, phần tử lớn nhất của cây con bên trái là 15, vậy thì thay 18 bằng 15 rồi xóa đi nút 15 cuối. Cách 2, phần tử nhỏ nhất của cây con bên phải là 23, vậy 18 sẽ thay bằng 23 và xóa nút 23 đó đi.

Đối với hai trường hợp đầu tiên khá đơn giản, nên mình sẽ lồng nó vào code luôn ở phần dưới, mình sẽ giải quyết cách tìm phần tử thế mạng ở trường hợp 3 trước và theo cả hai cách. Theo cách 1, mình sẽ làm như sau:

Trường hợp 1

// nút p là nút cần thay thế, tree là cây đang xét (cây bên phải)
void FindAndReplace1(Tree &p, Tree &tree)
{
    if (tree->left) // chưa phải nhỏ nhất (trái nhất)
        FindAndReplace1(p, tree->left); // tiếp tục tìm
    else // tree là nút trái nhất
    {
        p->data = tree->data; // copy data
        p = tree; // trỏ nút p vào nút tree sẽ làm thế mạng bị xóa
        tree = tree->right; // nút trái không còn tuy nhiên nút phải có thể còn nên ta phải nối chúng lại
    }
}

Đối với trường hợp này, các bạn phải gọi hàm FindAndReplace1(p, root->right) trong hàm DeleteNode ở phía trên. Trường hợp thứ 2 thì ngược lại.

Trường hợp 2

// nút p là nút cần thay thế, tree là cây đang xét (cây bên trái)
void FindAndReplace2(Tree &p, Tree &tree)
{
    if (tree->right) // chưa phải lớn nhất (phải nhất)
        FindAndReplace2(p, tree->right); // tiếp tục tìm
    else // tree là nút trái nhất
    {
        p->data = tree->data; // copy data
        p = tree; // trỏ nút p vào nút tree sẽ làm thế mạng bị xóa
        tree = tree->left; // nút phải không còn tuy nhiên nút trái có thể còn nên ta phải nối chúng lại
    }
}

Và trong hàm DeleteNode, các bạn sẽ gọi hàm FindAndReplace(p, root->left). Bây giờ, tổng hợp lại, chúng ta đã có thể dể dàng xóa một nút khỏi cây nhị phân tìm kiếm, mình sẽ code như sau:

void DeleteNode(Tree &root, int x)
{
    if (root)
    {
        if (x > root->data)
            DeleteNode(root->right, x);
        else if (x < root->data)
            DeleteNode(root->left, x);
        else // nút hiện tại (root) là nút cần xóa
        {
            Node *p = root; // lưu lại nút cần xóa tránh bị ghi đè
            if (!root->left)
                root = root->right; // trường hợp 1
            else if (!root->right)
                root = root->left; // trường hợp 2
            else
                FindAndReplace1(p, root->right); // cách 1
                // FindAndReplace2(p, root->left); // cách 2
            delete p; // xóa nút
        }
    }
    else
    {
        cout << "Not found!n"; // Không tìm thấy phần tử cần xóa
    }
}

Source code

struct Node
{
    int data;
    Node *left;
    Node *right;
};

typedef Node *Tree;

Node *CreateNode(int init)
{
    Node *p = new Node;
    p->data = init;
    p->left = NULL;
    p->right = NULL;
    return p;
}

void CreateTree(Tree &root)
{
    root = NULL;
}

void DestroyTree(Tree &root)
{
    if (root)
    {
        DestroyTree(root->left);
        DestroyTree(root->right);
        delete root;
    }
}

void AddNode(Tree &root, Node *node)
{
    if (root)
    {
        if (root->data == node->data)
            return;
        if (node->data < root->data)
            AddNode(root->left, node);
        else
            AddNode(root->right, node);
    }
    else
    {
        root = node;
    }
}

Node *FindNode(Tree root, int x)
{
    if (root)
    {
        if (root->data == x)
            return root;
        if (x < root->data)
            return FindNode(root->left, x);
        return FindNode(root->right, x);
    }
    return NULL;
}

void PrintTree(Tree root)// print tree using LNR
{
    if (root)
    {
        PrintTree(root->left);
        cout << root->data << ' ';
        PrintTree(root->right);
    }
}

void NLR(Tree root)
{
    if (root)
    {
        // Xử lý nút gốc (root)
        NLR(root->left);
        NLR(root->right);
    }
}

void LNR(Tree root)
{
    if (root)
    {
        LNR(root->left);
        // Xử lý nút gốc (root)
        LNR(root->right);
    }
}

void LRN(Tree root)
{
    if (root)
    {
        LRN(root->left);
        LRN(root->right);
        // Xử lý nút gốc (root)
    }
}

void FindAndReplace1(Tree &p, Tree &tree)
{
    if (tree->left)
        FindAndReplace1(p, tree->left);
    else
    {
        p->data = tree->data;
        p = tree;
        tree = tree->right;
    }
}

void FindAndReplace2(Tree &p, Tree &tree)
{
    if (tree->right)
        FindAndReplace2(p, tree->right);
    else
    {
        p->data = tree->data;
        p = tree;
        tree = tree->left;
    }
}

void DeleteNode(Tree &root, int x)
{
    if (root)
    {
        if (x > root->data)
            DeleteNode(root->right, x);
        else if (x < root->data)
            DeleteNode(root->left, x);
        else
        {
            Node *p = root;
            if (!root->left)
                root = root->right;
            else if (!root->right)
                root = root->left;
            else
                FindAndReplace1(p, root->right);
            // FindAndReplace2(p, root->left);
            delete p;
        }
    }
    else
    {
        cout << "Not found!n";
    }
}