Rate this post

Binary Search Trees, viết tắt là BST, là một cấu trúc dữ liệu cây được sử dụng phổ biến trong lĩnh vực khoa học máy tính và công nghệ thông tin. BST được thiết kế để lưu trữ dữ liệu theo cách có thể tìm kiếm hiệu quả và dễ dàng. Mỗi phần tử trong BST được gọi là một “node”, mỗi node chứa một giá trị và có thể có tối đa hai node con: một node con trái và một node con phải.

Tóm tắt nội dung

Ý nghĩa và ứng dụng của BST

BST đóng vai trò quan trọng trong việc cải thiện hiệu suất của các thuật toán tìm kiếm, thêm, xóa và sắp xếp dữ liệu. Một số ứng dụng chính của BST bao gồm:

Tìm kiếm nhanh chóng: BST cho phép tìm kiếm một phần tử trong tập dữ liệu với độ phức tạp thời gian là O(log n), trong đó n là số lượng phần tử trong BST. Điều này làm cho BST trở thành một cấu trúc dữ liệu hữu ích khi cần thực hiện các thao tác tìm kiếm nhanh chóng trên dữ liệu lớn.
Sắp xếp dữ liệu: BST cũng có thể được sử dụng để sắp xếp dữ liệu. Khi các phần tử được thêm vào BST theo thứ tự tăng dần hoặc giảm dần, BST sẽ tự động sắp xếp chúng thành một dãy tăng dần hoặc giảm dần.
Cấu trúc dữ liệu linh hoạt: BST có thể được áp dụng trong nhiều ngữ cảnh khác nhau và có thể điều chỉnh để phản ánh yêu cầu cụ thể của vấn đề. Điều này làm cho BST trở thành một công cụ mạnh mẽ và linh hoạt cho việc lưu trữ và quản lý dữ liệu trong các ứng dụng thực tế.

BST không chỉ là một cấu trúc dữ liệu quan trọng mà còn là một khái niệm cơ bản trong việc nắm vững các thuật toán tìm kiếm và sắp xếp dữ liệu. Điều này giúp sinh viên và những người mới bắt đầu trong lĩnh vực khoa học máy tính hiểu rõ hơn về cách hoạt động của các thuật toán và cách áp dụng chúng vào các vấn đề thực tế.

Cấu trúc cơ bản của BST

Node trong BST

Trong Binary Search Tree (BST), mỗi phần tử được biểu diễn bởi một node. Mỗi node chứa một giá trị dữ liệu và có thể có tối đa hai node con: một node con trái và một node con phải. Cấu trúc của một node trong BST bao gồm hai thành phần chính:

Dữ liệu (Data): Đây là giá trị mà node chứa. Dữ liệu có thể là bất kỳ loại dữ liệu nào, ví dụ như số nguyên, số thực, chuỗi, hoặc các kiểu dữ liệu phức tạp khác.
Con trỏ (Pointer): Con trỏ được sử dụng để chỉ đến các node con của node hiện tại. Cụ thể, một node có hai con trỏ: một con trỏ trỏ đến node con trái và một con trỏ trỏ đến node con phải. Nếu một node không có node con tương ứng, con trỏ tương ứng sẽ được gán giá trị null.

Quy tắc của BST

BST tuân theo một số quy tắc cơ bản sau:

Quy tắc sắp xếp: Tại mỗi node, giá trị của node con trái phải nhỏ hơn giá trị của node hiện tại và giá trị của node con phải phải lớn hơn giá trị của node hiện tại. Điều này đảm bảo rằng tất cả các phần tử bên trái của một node có giá trị nhỏ hơn node đó, trong khi tất cả các phần tử bên phải có giá trị lớn hơn node đó, tạo thành một cấu trúc dữ liệu có thứ tự.
Dữ liệu không trùng lặp: Mỗi giá trị dữ liệu trong BST là duy nhất. Trong trường hợp có sự trùng lặp, BST có thể được điều chỉnh để xử lý trường hợp này theo yêu cầu cụ thể của ứng dụng.
Cấu trúc cây: BST là một cấu trúc dữ liệu cây nhị phân, có nghĩa là mỗi node chỉ có tối đa hai node con: một node con trái và một node con phải. Cấu trúc này giúp giảm thiểu độ phức tạp của các thao tác tìm kiếm và thêm/xóa phần tử trong BST.

Quy tắc cơ bản này cung cấp một cơ sở vững chắc cho việc xây dựng và duy trì một BST hiệu quả và có thứ tự.

Các phép toán cơ bản trên BST

Tìm kiếm (Search)

Phép toán tìm kiếm trên BST nhằm tìm kiếm một giá trị cụ thể trong cây. Quy trình tìm kiếm bắt đầu từ gốc của cây và di chuyển xuống dọc theo cây cho đến khi tìm thấy giá trị cần tìm hoặc đến khi đạt đến một node không có node con.

Bắt đầu từ gốc của BST.
So sánh giá trị cần tìm với giá trị của node hiện tại.
Nếu giá trị cần tìm bằng giá trị của node hiện tại, trả về node đó.
Nếu giá trị cần tìm nhỏ hơn giá trị của node hiện tại, tiếp tục tìm kiếm ở node con trái của node hiện tại.
Nếu giá trị cần tìm lớn hơn giá trị của node hiện tại, tiếp tục tìm kiếm ở node con phải của node hiện tại.
Lặp lại các bước 2-5 cho đến khi tìm thấy giá trị cần tìm hoặc đạt đến một node không có node con, trong trường hợp này, giá trị cần tìm không tồn tại trong BST.

Thêm phần tử mới (Insert)

Phép toán thêm phần tử mới vào BST nhằm chèn một giá trị mới vào cây theo quy tắc sắp xếp.

Bắt đầu từ gốc của BST.
So sánh giá trị cần chèn với giá trị của node hiện tại.
Nếu giá trị cần chèn nhỏ hơn giá trị của node hiện tại và node con trái của node hiện tại không tồn tại, chèn giá trị mới vào node con trái của node hiện tại.
Nếu giá trị cần chèn lớn hơn giá trị của node hiện tại và node con phải của node hiện tại không tồn tại, chèn giá trị mới vào node con phải của node hiện tại.
Nếu giá trị cần chèn nhỏ hơn giá trị của node hiện tại và node con trái của node hiện tại tồn tại, tiếp tục quá trình chèn ở node con trái.
Nếu giá trị cần chèn lớn hơn giá trị của node hiện tại và node con phải của node hiện tại tồn tại, tiếp tục quá trình chèn ở node con phải.
Lặp lại các bước 2-6 cho đến khi chèn thành công giá trị mới vào BST.

Xóa phần tử (Delete)

Phép toán xóa phần tử khỏi BST nhằm loại bỏ một giá trị cụ thể khỏi cây trong BST.

Nếu cây rỗng, không cần phải thực hiện bất kỳ thao tác nào.
Nếu giá trị cần xóa nhỏ hơn giá trị của node hiện tại, tiếp tục tìm kiếm ở node con trái của node hiện tại.
Nếu giá trị cần xóa lớn hơn giá trị của node hiện tại, tiếp tục tìm kiếm ở node con phải của node hiện tại.
Nếu giá trị cần xóa bằng giá trị của node hiện tại, có các trường hợp sau:
a. Node cần xóa không có node con: Xóa node đó khỏi cây.
b. Node cần xóa chỉ có một node con: Thay thế node cần xóa bằng node con của nó.
c. Node cần xóa có hai node con: Tìm node kế tiếp lớn nhất của node cần xóa (node phải nhất của cây con trái) hoặc node trước đó nhỏ nhất của node cần xóa (node trái nhất của cây con phải), sao chép giá trị của node đó vào node cần xóa, sau đó xóa node kế tiếp đó.
Lặp lại các bước 2-4 cho đến khi xóa thành công giá trị khỏi BST.

Độ phức tạp thời gian của các phép toán

Tìm kiếm

Thời gian tìm kiếm trên một Binary Search Tree (BST) có độ phức tạp thời gian trung bình và tốt nhất là O(log n), trong đó n là số lượng phần tử trong cây. Điều này là do BST được cấu trúc sao cho mỗi lần tìm kiếm, cây sẽ bị cắt giảm đi khoảng một nửa, giảm bớt số lượng node cần xem xét. Tuy nhiên, trong trường hợp xấu nhất, thời gian tìm kiếm trên BST có thể là O(n), nếu cây được cấu trúc thành một danh sách liên kết không cân đối.

Thêm phần tử mới

Độ phức tạp thời gian cho phép toán thêm phần tử mới vào một BST phụ thuộc vào cấu trúc hiện tại của cây. Trong trường hợp tốt nhất và trung bình, thời gian thêm một phần tử mới vào BST là O(log n), vì các phần tử được thêm vào một BST thường sẽ làm cây cân đối hơn. Tuy nhiên, trong trường hợp xấu nhất, thời gian thêm một phần tử mới có thể là O(n) nếu cây trở thành một danh sách liên kết không cân đối.

Xóa phần tử

Độ phức tạp thời gian cho phép toán xóa một phần tử khỏi BST cũng phụ thuộc vào cấu trúc hiện tại của cây. Trong trường hợp tốt nhất và trung bình, thời gian xóa một phần tử khỏi BST là O(log n), vì các phần tử thường được xóa từ cây cân đối. Tuy nhiên, trong trường hợp xấu nhất, thời gian xóa một phần tử có thể là O(n) nếu cây trở thành một danh sách liên kết không cân đối.

Tóm lại, BST cung cấp hiệu suất tốt cho các phép toán tìm kiếm, thêm và xóa phần tử với độ phức tạp thời gian trung bình là O(log n). Tuy nhiên, để đảm bảo hiệu suất tốt nhất, việc duy trì cân đối của cây là rất quan trọng.

Cải tiến và ứng dụng của BST

Self-balancing BST

Một trong những cải tiến quan trọng của BST là Self-balancing BST, hay còn gọi là AVL trees, Red-Black trees, và Splay trees. Mục tiêu của các cây tự cân bằng là giữ cho cây luôn cân đối sau mỗi thao tác thêm, xóa, hoặc sửa đổi để đảm bảo rằng thời gian tìm kiếm, thêm và xóa là tối ưu. Các thuật toán tự cân bằng cố gắng duy trì chiều cao của cây ở mức tối thiểu, thường là O(log n), kể cả trong trường hợp xấu nhất. Điều này giúp giảm độ phức tạp thời gian của các phép toán và đảm bảo hiệu suất của cây trong các ứng dụng thực tế.

Sử dụng BST trong các thuật toán tìm kiếm và sắp xếp

BST không chỉ được sử dụng cho các thao tác cơ bản như tìm kiếm, thêm và xóa, mà còn là một phần quan trọng của nhiều thuật toán tìm kiếm và sắp xếp khác nhau. Ví dụ, thuật toán tìm kiếm nhị phân sử dụng một BST để tìm kiếm phần tử trong một dãy dữ liệu đã được sắp xếp. BST cũng có thể được sử dụng để sắp xếp dữ liệu, nơi các phần tử được chèn vào cây theo thứ tự và sau đó được trích xuất ra theo thứ tự tăng dần hoặc giảm dần. BST là một công cụ mạnh mẽ cho việc giải quyết nhiều vấn đề trong lĩnh vực khoa học máy tính, từ tìm kiếm dữ liệu đến sắp xếp và thậm chí là các vấn đề phức tạp hơn như xử lý cây phân cấp và cấu trúc dữ liệu dạng cây khác.

Ví dụ

Ví dụ: Cây được hiển thị trong hình là Binary Search Trees.

Chèn vào Binary Search Trees: Hãy xem xét cây nhị phân T. Giả sử chúng ta đã đưa ra một ITEM thông tin để chèn vào T. ITEM được chèn như một chiếc lá trong cây. Các bước sau giải thích quy trình chèn một ITEM trong Binary Search Trees T.

So sánh ITEM với nút gốc.
Nếu ITEM> ROOT NODE, hãy chuyển đến nút con bên phải và nó trở thành nút gốc cho cây con bên phải.
Nếu ITEM <ROOT NODE, hãy chuyển sang con bên trái.
Lặp lại các bước trên cho đến khi chúng ta gặp một nút không có cây con bên trái và bên phải.
Bây giờ nếu ITEM lớn hơn nút, thì ITEM được chèn vào như nút con bên phải và nếu ITEM nhỏ hơn nút, thì ITEM được chèn vào làm nút con bên trái.

Ví dụ: Hiển thị Binary Search Trees sau khi chèn 3, 1,4,6,9,2,5,7 vào Binary Search Trees trống ban đầu.

Giải pháp: Việc chèn các nút trên vào Binary Search Trees trống được hiển thị trong hình:

Xóa trong Binary Search Trees: Hãy xem xét cây nhị phân T. Giả sử chúng ta muốn xóa một ITEM đã cho khỏi Binary Search Trees. Để xóa một ITEM khỏi Binary Search Trees, chúng ta có ba trường hợp, tùy thuộc vào số lượng nút con của nút bị xóa.

Nút đã xóa không có nút con: Việc xóa một nút không có nút con rất đơn giản, vì thay thế nút đó bằng null.
Nút đã xóa chỉ có một nút con: Thay thế giá trị của nút bị xóa bằng nút con duy nhất.
Nút xóa chỉ có hai nút con: Trong trường hợp này, hãy thay thế nút đã xóa bằng nút có giá trị gần nhất với nút bị xóa. Để tìm giá trị gần nhất, chúng ta di chuyển một lần sang trái và sau đó sang phải càng xa càng tốt. Nút này được gọi là nút tiền nhiệm ngay lập tức. Bây giờ thay thế giá trị của nút đã xóa bằng nút tiền nhiệm ngay lập tức và sau đó xóa nút đã thay thế bằng cách sử dụng case1 hoặc case2.

Ví dụ: Chỉ ra rằng cây nhị phân được hiển thị trong hình (viii) sau khi xóa nút gốc.

Giải pháp: Để xóa nút gốc, trước tiên hãy thay thế nút gốc bằng các phần tử gần nhất của gốc. Đối với điều này, đầu tiên, di chuyển một bước sang trái và sau đó sang phải càng xa càng tốt đến nút, sau đó xóa nút đã thay thế. Cây sau khi xóa được hiển thị trong hình:

Demo source code của BST trong C++

Dưới đây là một ví dụ về mã nguồn C++ để triển khai Binary Search Tree (BST):

#include <iostream>

// Định nghĩa lớp Node để biểu diễn một nút trong BST
class Node {
public:
    int data;
    Node* left;
    Node* right;

    // Constructor
    Node(int value) {
        data = value;
        left = nullptr;
        right = nullptr;
    }
};

// Hàm chèn một giá trị vào BST
Node* insertNode(Node* root, int value) {
    // Nếu cây rỗng, tạo nút mới và trả về nút đó
    if (root == nullptr) {
        return new Node(value);
    }

    // Nếu giá trị chèn nhỏ hơn giá trị của nút gốc, chèn vào cây con trái
    if (value < root->data) {
        root->left = insertNode(root->left, value);
    }
    // Nếu giá trị chèn lớn hơn hoặc bằng giá trị của nút gốc, chèn vào cây con phải
    else {
        root->right = insertNode(root->right, value);
    }

    return root;
}

// Hàm duyệt cây theo thứ tự trước (preorder traversal)
void preorderTraversal(Node* root) {
    if (root == nullptr) {
        return;
    }

    std::cout << root->data << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

int main() {
    Node* root = nullptr;

    // Chèn các giá trị vào BST
    root = insertNode(root, 50);
    insertNode(root, 30);
    insertNode(root, 20);
    insertNode(root, 40);
    insertNode(root, 70);
    insertNode(root, 60);
    insertNode(root, 80);

    // Duyệt cây theo thứ tự trước và in ra các giá trị
    std::cout << "Preorder traversal of BST: ";
    preorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

Trong ví dụ trên, chúng ta triển khai một BST và chèn một số giá trị vào cây. Sau đó, chúng ta duyệt cây theo thứ tự trước (preorder) và in ra các giá trị đã chèn.

Lưu ý rằng đây chỉ là một ví dụ đơn giản để hiểu cách triển khai BST trong C++. Trong thực tế, BST có thể được triển khai với nhiều chức năng bổ sung như xóa nút, tìm kiếm, duyệt các thứ tự khác nhau, và kiểm tra tính cân bằng của cây.

Đảm bảo bạn hiểu và kiểm tra mã nguồn của BST trước khi sử dụng nó trong ứng dụng thực tế.

Xem thêm Binary Operation

Discrete Mathematics

Binary Search Trees – kiến thức cơ bản