Dẫn nhập

Trong lĩnh vực khoa học máy tính và cấu trúc dữ liệu, cây nhị phân (binary tree) là một trong những cấu trúc dữ liệu quan trọng. Nó cung cấp một phương pháp hiệu quả để tổ chức và lưu trữ dữ liệu có tính cấu trúc. Trên thực tế, cây nhị phân tìm kiếm (binary search tree) được sử dụng rộng rãi trong nhiều ứng dụng khác nhau, từ các thuật toán tìm kiếm đến quản lý cơ sở dữ liệu.

Binary tree là gì?

Cây nhị phân là một loại cấu trúc dữ liệu được hình thành bởi các nút (node) liên kết thông qua các mối quan hệ cha-con. Mỗi nút trong cây nhị phân có thể có tối đa hai nút con, được gọi là nút con trái và nút con phải. Nút cha được liên kết trực tiếp đến các nút con của nó.

Cây nhị phân tìm kiếm là một cây nhị phân đảm bảo tính chất sau: Các nút con bên trái luôn nhỏ hơn nút cha, và các nút con bên phải thì luôn lớn hơn nút cha.

Ví dụ

Ví dụ dưới đây minh họa một cây nhị phân đơn giản:

        C
       / \
      B   E
     /   / \
    A   D   F

Trong ví dụ này, nút gốc là nút C. Nút C có hai nút con là B và E. Nút B có một nút con là A. Nút E có hai nút con là D và F.

Ứng dụng của Binary Tree

Cây nhị phân có nhiều ứng dụng quan trọng trong lĩnh vực khoa học máy tính và lập trình. Một số ứng dụng phổ biến của cây nhị phân bao gồm:

• Binary Search Tree (Cây tìm kiếm nhị phân): Dùng để tìm kiếm và sắp xếp dữ liệu một cách hiệu quả.
• Cây cấu trúc dữ liệu (Parse Tree): Được sử dụng để phân tích và biểu diễn cú pháp trong ngôn ngữ lập trình.
• Cây Huffman: Sử dụng trong nén dữ liệu để giảm kích thước của dữ liệu.

Ưu điểm của Binary Tree so với các kiểu cấu trúc dữ liệu khác

Cây nhị phân có một số ưu điểm so với các kiểu cấu trúc dữ liệu khác như danh sách liên kết hoặc mảng. Dưới đây là một số ưu điểm chính của cây nhị phân:

1. Tìm kiếm hiệu quả: Trong cây nhị phân cân bằng, thao tác tìm kiếm có độ phức tạp O(log n), cho phép tìm kiếm nhanh chóng trong dữ liệu lớn.
2. Sắp xếp dữ liệu: Cây nhị phân cân bằng có thể được sử dụng để sắp xếp dữ liệu một cách hiệu quả với độ phức tạp O(n log n).
3. Dễ dàng thêm, xóa dữ liệu: Cây nhị phân cho phép thêm, xóa dữ liệu một cách dễ dàng và hiệu quả.
4. Dễ dàng duyệt: Cây nhị phân cung cấp các phương pháp duyệt dữ liệu như duyệt tiền thứ tự (pre-order), duyệt trung thứ tự (in-order) và duyệt hậu thứ tự (post-order).

Các thao tác cơ bản

Cây nhị phân hỗ trợ một số thao tác quan trọng như:

• Thêm một nút vào cây: Thêm một nút mới vào cây nhị phân.
• Xóa một nút khỏi cây: Xóa một nút khỏi cây nhị phân.
• Tìm kiếm: Tìm kiếm một giá trị trong cây nhị phân.
• Duyệt cây: Duyệt qua các nút của cây nhị phân theo các phương pháp duyệt khác nhau.

Triển khai cây nhị phân tìm kiếm bằng C++

Dưới đây là một ví dụ về triển khai cây nhị phân tìm kiếm và các thao tác sử dụng ngôn ngữ C++:

#include <iostream>
using namespace std;

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

    Node(int value) {
        data = value;
        left = NULL;
        right = NULL;
    }
};

void insert(Node*& root, int value) {
    if (root == NULL) {
        root = new Node(value);
        return;
    }

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

// Phương pháp duyệt trung tự LNR
void traverseInOrder(Node* root) {
    if (root == NULL) {
        return;
    }

    traverseInOrder(root->left);
    cout << root->data << " ";
    traverseInOrder(root->right);
}

int main() {
    Node* root = NULL;

    insert(root, 50);
    insert(root, 30);
    insert(root, 20);
    insert(root, 40);
    insert(root, 70);
    insert(root, 60);
    insert(root, 80);

    cout << "Duyệt cây theo thứ tự tăng dần: ";
    traverseInOrder(root);
    cout << endl;

    return 0;
}

Bạn có thể tham khảo đầy đủ các thao tác trên cây nhị phân tìm kiếm tại đây

Tổng kết

Một bài toán phổ biến có thể được giải quyết bằng cây nhị phân là tìm kiếm phần tử trong một danh sách không đổi. Thay vì tìm kiếm tuần tự qua từng phần tử, ta có thể xây dựng một cây nhị phân từ danh sách và thực hiện tìm kiếm một cách hiệu quả với độ phức tạp O(log n).

Ví dụ, giả sử chúng ta có một danh sách số nguyên và muốn tìm kiếm một số cụ thể trong danh sách đó. Ta có thể sử dụng cây nhị phân để xây dựng cấu trúc dữ liệu và thực hiện tìm kiếm nhanh chóng.

Trong bài viết này, chúng ta đã tìm hiểu về cây nhị phân và các khía cạnh quan trọng của nó. Cây nhị phân là một công cụ mạnh mẽ trong lĩnh vực cấu trúc dữ liệu và có nhiều ứng dụng trong lập trình.