Discrete Mathematics

Binary Search Trees

Posted on by Dục Đoàn Trình
Rate this post

Binary Search Trees có thuộc tính là nút bên trái chứa giá trị nhỏ hơn nút trỏ tới nó và nút bên phải chứa giá trị lớn hơn nút trỏ tới nó.

Các bài viết liên quan:

Không nhất thiết một nút trong ‘Binary Search Trees’ phải trỏ đến các nút có giá trị ngay trước đó và theo sau nó.

Giới thiệu về Binary Search Trees

Trong khoa học máy tính, Binary Search Tree (BST) là một loại cấu trúc dữ liệu cây nhị phân có thứ tự. Nó được sử dụng rộng rãi để lưu trữ và tìm kiếm dữ liệu hiệu quả. BST có các tính chất đặc biệt mà làm cho nó phù hợp cho việc thực hiện các thao tác như tìm kiếm, thêm, xóa và sắp xếp dữ liệu một cách nhanh chóng.

Một BST được xây dựng từ các nút, trong đó mỗi nút có giá trị và có tối đa hai con, được gọi là con trái và con phải. Giá trị của mỗi nút trong cây phải lớn hơn giá trị của tất cả các nút trong cây con trái của nó và nhỏ hơn giá trị của tất cả các nút trong cây con phải của nó. Điều này tạo ra một sự sắp xếp tự nhiên trong cây, giúp tối ưu hóa các thao tác tìm kiếm.

BST cung cấp các phương pháp cơ bản như:

  1. Tìm kiếm: BST cho phép tìm kiếm một giá trị cụ thể trong cây một cách hiệu quả. Bằng cách so sánh giá trị tìm kiếm với giá trị của nút hiện tại, cây có thể được duyệt theo chiều dọc từ gốc đến lá để tìm ra giá trị mong muốn.
  2. Thêm: BST cho phép thêm một giá trị mới vào cây một cách chính xác, duy trì tính chất của cây nhị phân tìm kiếm. Quá trình này đòi hỏi so sánh giá trị của nút mới với giá trị của các nút hiện có và thêm nút mới vào đúng vị trí.
  3. Xóa: BST cho phép xóa một giá trị khỏi cây một cách chính xác, duy trì tính chất của cây nhị phân tìm kiếm. Quá trình này yêu cầu tìm kiếm giá trị cần xóa và thực hiện việc xóa nút tương ứng.

BST có hiệu suất tốt trong các tác vụ tìm kiếm và sắp xếp. Tuy nhiên, nếu cây không cân bằng, nó có thể dẫn đến hiệu suất tồi và tác động đến thời gian thực thi các thao tác.

Các thao tác trên Binary Search Trees

Binary Search Trees (BST) cung cấp một số thao tác cơ bản để thực hiện các hoạt động liên quan đến dữ liệu. Dưới đây là một số thao tác quan trọng trên BST:

  1. Tìm kiếm: Thao tác tìm kiếm cho phép tìm kiếm một giá trị cụ thể trong BST. Quá trình tìm kiếm bắt đầu từ gốc của cây và so sánh giá trị tìm kiếm với giá trị của nút hiện tại. Nếu giá trị tìm kiếm nhỏ hơn giá trị của nút hiện tại, ta di chuyển sang cây con trái. Ngược lại, nếu giá trị tìm kiếm lớn hơn giá trị của nút hiện tại, ta di chuyển sang cây con phải. Quá trình này được lặp lại cho đến khi tìm thấy giá trị cần tìm kiếm hoặc cây đã được duyệt hết.
  2. Thêm: Thao tác thêm cho phép thêm một giá trị mới vào BST. Khi thêm giá trị mới, ta tạo một nút mới và tìm vị trí phù hợp để chèn nút mới vào cây. Quá trình này tương tự như thao tác tìm kiếm. Ta di chuyển qua các nút từ gốc đến lá, so sánh giá trị mới với giá trị của nút hiện tại. Dựa vào kết quả so sánh, ta di chuyển sang cây con trái hoặc cây con phải để chèn nút mới. Sau khi tìm được vị trí phù hợp, ta thêm nút mới vào đó.
  3. Xóa: Thao tác xóa cho phép loại bỏ một giá trị khỏi BST. Khi xóa giá trị, ta tìm vị trí của giá trị cần xóa trong cây. Quá trình này tương tự như thao tác tìm kiếm. Nếu giá trị cần xóa nhỏ hơn giá trị của nút hiện tại, ta di chuyển sang cây con trái. Ngược lại, nếu giá trị cần xóa lớn hơn giá trị của nút hiện tại, ta di chuyển sang cây con phải. Khi tìm thấy giá trị cần xóa, ta thực hiện việc xóa nút tương ứng.
  4. Duyệt: BST cung cấp các phương pháp duyệt để truy cập các giá trị trong cây theo một thứ tự nhất định. Có ba
  5. Duyệt: BST cung cấp các phương pháp duyệt để truy cập các giá trị trong cây theo một thứ tự nhất định. Có ba phương pháp duyệt chính trong BST:
    • Duyệt tiền thứ tự (Pre-order traversal): Quá trình duyệt bắt đầu từ gốc, sau đó duyệt cây con trái, và cuối cùng duyệt cây con phải. Trong quá trình duyệt, giá trị của nút hiện tại được truy cập trước khi duyệt các nút con.
    • Duyệt giữa thứ tự (In-order traversal): Quá trình duyệt bắt đầu từ cây con trái, sau đó truy cập giá trị của nút hiện tại, và cuối cùng duyệt cây con phải. Duyệt giữa thứ tự cho phép truy cập các giá trị trong BST theo thứ tự tăng dần.
    • Duyệt hậu thứ tự (Post-order traversal): Quá trình duyệt bắt đầu từ cây con trái, sau đó duyệt cây con phải, và cuối cùng truy cập giá trị của nút hiện tại. Duyệt hậu thứ tự cho phép truy cập các giá trị trong BST theo thứ tự từ cây con trái đến cây con phải, và sau đó là giá trị của nút hiện tại.
  6. Sắp xếp: BST có khả năng tự sắp xếp dữ liệu theo thứ tự tăng dần. Khi các giá trị được chèn vào cây, BST sẽ tự động định vị chúng vào vị trí thích hợp để duy trì tính chất của BST. Do đó, BST có thể được sử dụng để sắp xếp một danh sách các giá trị một cách nhanh chóng và hiệu quả.

BST là một cấu trúc dữ liệu quan trọng trong khoa học máy tính và được áp dụng rộng rãi trong việc tìm kiếm, sắp xếp và lưu trữ dữ liệu. Tuy nhiên, để đảm bảo hiệu suất tốt và tránh trường hợp tồi nhất, cần đảm bảo rằng cây BST được cân bằng và không tồn tại các trường hợp xấu nhất định.

Hiệu suất của Binary Search Trees

Binary Search Trees (BST) có hiệu suất tốt trong các thao tác tìm kiếm, chèn và xóa nếu cây được cân bằng. Tuy nhiên, hiệu suất của BST có thể bị ảnh hưởng bởi cấu trúc cây và thứ tự chèn các giá trị.

  1. Tìm kiếm: Trong trường hợp tốt nhất, thời gian tìm kiếm trong BST là O(log n), với n là số lượng nút trong cây. Tuy nhiên, trong trường hợp xấu nhất, thời gian tìm kiếm có thể là O(n), khi BST không cân bằng và trở thành một danh sách liên kết. Do đó, việc duy trì cân bằng BST là quan trọng để đảm bảo hiệu suất tốt.
  2. Chèn và xóa: Trong trường hợp tốt nhất và trung bình, thời gian chèn và xóa trong BST cũng là O(log n). Tuy nhiên, trong trường hợp xấu nhất, thời gian chèn và xóa có thể là O(n) nếu BST không cân bằng. Để đảm bảo hiệu suất tốt, các thuật toán cân bằng cây như AVL Trees và Red-Black Trees được sử dụng để duy trì cân bằng BST.
  3. Duyệt: Thời gian duyệt BST là O(n), với n là số lượng nút trong cây. Trong mỗi trường hợp (tiền thứ tự, giữa thứ tự, hậu thứ tự), tất cả các nút trong cây được duyệt qua một lần.

Để tăng hiệu suất của BST, có một số phương pháp và cấu trúc dữ liệu tương tự như AVL Trees, Red-Black Trees và B-Trees. Các cấu trúc này đảm bảo rằng cây luôn cân bằng và đạt được hiệu suất tối ưu trong các thao tác tìm kiếm, chèn và xóa.

Tuy nhiên, cần lưu ý rằng hiệu suất của BST có thể bị ảnh hưởng bởi sự phân phối của dữ liệu và cách chèn các giá trị. Trường hợp xấu nhất xảy ra khi cây trở thành một danh sách liên kết, khiến hiệu suất của BST giảm đi đáng kể. Do đó, việc lựa chọn và cân nhắc các cấu trúc dữ liệu và thuật toán phù hợp là rất quan trọng để đảm bảo hiệu suất tốt

Ứng dụng của Binary Search Trees

Binary Search Trees (BST) có nhiều ứng dụng trong lĩnh vực khoa học máy tính và các lĩnh vực liên quan. Dưới đây là một số ứng dụng phổ biến của BST:

  1. Tìm kiếm dữ liệu: BST được sử dụng để tìm kiếm nhanh chóng một giá trị cụ thể trong một tập dữ liệu đã được sắp xếp. Do BST có tính chất cân bằng và đặc trưng của cây nhị phân, việc tìm kiếm trong BST có độ phức tạp thấp (O(log n)), làm cho nó trở thành một cấu trúc dữ liệu phù hợp cho việc tìm kiếm dữ liệu trong các ứng dụng như cơ sở dữ liệu, hệ thống tìm kiếm, v.v.
  2. Sắp xếp dữ liệu: BST có khả năng tự động sắp xếp các giá trị dữ liệu theo thứ tự tăng dần. Điều này làm cho BST hữu ích trong việc sắp xếp các tập dữ liệu và giải thuật liên quan đến việc sắp xếp. BST được sử dụng trong các thuật toán sắp xếp như Quicksort và Heapsort để tăng hiệu suất và đơn giản hóa quá trình sắp xếp.
  3. Tìm kiếm khoảng cách gần nhất: BST có thể được sử dụng để tìm kiếm giá trị gần nhất với một giá trị xác định. Bằng cách duyệt cây từ gốc đến lá và so sánh khoảng cách giữa các giá trị, BST có thể tìm ra giá trị gần nhất với giá trị cần tìm. Điều này có ứng dụng trong các thuật toán tìm kiếm, định vị và xử lý hình ảnh.
  4. Xóa và chèn dữ liệu: BST cung cấp các phương thức để chèn và xóa giá trị dữ liệu một cách hiệu quả. Khi một giá trị mới được chèn vào BST, nó được định vị vào vị trí thích hợp dựa trên tính chất cân bằng của cây. Tương tự, khi một giá trị được xóa khỏi BST, cây sẽ tự điều chỉnh để duy trì tính chất của BST. Điều này làm cho BST hữu ích trong việc thêm, xóa và quản lý dữ liệu trong các ứng dụng như cơ sở dữ liệu và hệ thống quản lý

Xem thêm binary search trong 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

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Contact Me on Zalo
Call now