Khóa học CTDL và GT

Bài 32.2: Cây nhị phân và cây nhị phân tìm kiếm

Sau khi khám phá các cấu trúc dữ liệu tuyến tính quen thuộc như mảng, danh sách liên kết hay stack/queue, giờ là lúc chúng ta bước vào thế giới của các cấu trúc phi tuyến tính (non-linear). Các cấu trúc này cho phép lưu trữ và tổ chức dữ liệu theo mối quan hệ phức tạp hơn, không chỉ đơn thuần là "phần tử đứng trước, phần tử đứng sau".

Một trong những cấu trúc phi tuyến tính phổ biến và cực kỳ mạnh mẽ mà bạn sẽ gặp là Cây (Tree). Và hạt nhân của thế giới cây chính là Cây nhị phân (Binary Tree) cùng với "biến thể" hiệu quả cho việc tìm kiếm: Cây nhị phân tìm kiếm (Binary Search Tree - BST).

Hãy cùng đi sâu vào khám phá hai cấu trúc dữ liệu tuyệt vời này nhé!

Phần 1: Cây nhị phân (Binary Tree) - Nền Tảng

Cây nhị phân là một cấu trúc dữ liệu dạng cây trong đó mỗi nút (node) có tối đa hai nút con (child nodes). Hai nút con này thường được gọi là nút con trái và nút con phải.

Các Thuật Ngữ Quan Trọng

Trước khi đi sâu, chúng ta cần nắm vững một số thuật ngữ cơ bản khi làm việc với cây:

• Nút (Node): Đơn vị cơ bản trong cây, chứa dữ liệu và các liên kết đến các nút khác.
• Nút gốc (Root): Nút trên cùng của cây. Một cây chỉ có duy nhất một nút gốc.
• Nút cha (Parent): Một nút có ít nhất một nút con.
• Nút con (Child): Nút được liên kết trực tiếp từ một nút khác (nút cha).
• Nút lá (Leaf): Nút không có nút con nào.
• Cây con (Subtree): Một phần của cây, coi một nút bất kỳ làm gốc của cây con đó. Mỗi nút có thể là gốc của một cây con trái và một cây con phải.
• Độ sâu (Depth): Khoảng cách từ nút gốc đến một nút cụ thể (số cạnh đi qua). Nút gốc có độ sâu 0.
• Chiều cao (Height): Chiều dài của đường đi dài nhất từ nút gốc đến một nút lá. Chiều cao của một cây rỗng là -1 (hoặc 0 tùy quy ước), cây chỉ có nút gốc là 0.
• Mức (Level): Tập hợp các nút có cùng độ sâu.

Biểu diễn Cây nhị phân trong C++

Chúng ta có thể biểu diễn một nút trong cây nhị phân bằng một struct hoặc class chứa dữ liệu và con trỏ tới nút con trái và nút con phải:

#include <iostream> // Để dùng cout
#include <queue>    // Có thể dùng cho duyệt theo chiều rộng (BFS), nhưng không bắt buộc trong bài này
#include <stack>    // Có thể dùng cho duyệt không đệ quy

// Khai báo cấu trúc một nút trong cây
struct Node {
    int data;      // Dữ liệu của nút
    Node* left;    // Con trỏ tới nút con trái
    Node* right;   // Con trỏ tới nút con phải

    // Constructor để tạo nút mới dễ dàng hơn
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// Lưu ý: 'nullptr' trong C++11 trở lên tương đương với NULL
// Nó rõ ràng hơn về mặt kiểu dữ liệu (pointer type)

Giải thích code:

• Chúng ta định nghĩa một struct tên là Node.
• Mỗi Node có một biến data (ở đây là int, có thể là kiểu dữ liệu khác tùy ý).
• left và right là các con trỏ kiểu Node*, trỏ đến nút con trái và nút con phải tương ứng. Nếu một nút không có con trái hoặc con phải, con trỏ đó sẽ là nullptr.
• Constructor Node(int value) giúp chúng ta tạo một nút mới và khởi tạo dữ liệu của nó, đồng thời đặt cả hai con trỏ con thành nullptr ban đầu.

Các Kiểu Cây Nhị Phân Đặc Biệt

Mặc dù định nghĩa cơ bản là mỗi nút có tối đa 2 con, nhưng có một số dạng cây nhị phân đặc trưng:

• Full Binary Tree (Cây nhị phân đầy đủ): Mỗi nút không phải nút lá đều có đúng hai nút con.
• Complete Binary Tree (Cây nhị phân hoàn chỉnh): Tất cả các mức, trừ mức cuối cùng, đều được lấp đầy hoàn toàn. Ở mức cuối cùng, các nút được lấp đầy từ trái sang phải. Mảng có thể được dùng để biểu diễn cây nhị phân hoàn chỉnh một cách hiệu quả.
• Perfect Binary Tree (Cây nhị phân hoàn hảo): Là một cây nhị phân đầy đủ và hoàn chỉnh. Tất cả các nút lá đều ở cùng một mức, và mỗi nút không phải lá đều có đúng hai con. Số nút ở mức k là 2^k. Tổng số nút là 2^(h+1) - 1 (với h là chiều cao).
• Skewed Binary Tree (Cây nhị phân xiên): Là cây mà mỗi nút chỉ có tối đa một nút con. Nó có thể là xiên trái (chỉ có con trái) hoặc xiên phải (chỉ có con phải). Dạng này giống hệt như một danh sách liên kết.

Duyệt Cây Nhị Phân (Tree Traversal)

Duyệt cây là quá trình thăm tất cả các nút trong cây một cách có hệ thống. Có ba phương pháp duyệt theo chiều sâu (Depth-First Search - DFS) phổ biến đối với cây nhị phân:

1. Duyệt theo thứ tự giữa (Inorder Traversal): Thăm cây con trái, sau đó thăm nút gốc, rồi thăm cây con phải. Thứ tự: Trái -> Gốc -> Phải.
2. Duyệt theo thứ tự trước (Preorder Traversal): Thăm nút gốc, sau đó thăm cây con trái, rồi thăm cây con phải. Thứ tự: Gốc -> Trái -> Phải.
3. Duyệt theo thứ tự sau (Postorder Traversal): Thăm cây con trái, sau đó thăm cây con phải, rồi thăm nút gốc. Thứ tự: Trái -> Phải -> Gốc.

Hãy xem cách triển khai chúng bằng đệ quy trong C++:

#include <iostream>

// (Sử dụng lại struct Node đã định nghĩa ở trên)
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// Duyệt theo thứ tự giữa (Inorder)
void inorderTraversal(Node* root) {
    if (root == nullptr) {
        return; // Trường hợp cơ sở: cây rỗng
    }
    inorderTraversal(root->left);  // 1. Duyệt cây con trái
    std::cout << root->data << " "; // 2. Thăm nút gốc (in dữ liệu)
    inorderTraversal(root->right); // 3. Duyệt cây con phải
}

// Duyệt theo thứ tự trước (Preorder)
void preorderTraversal(Node* root) {
    if (root == nullptr) {
        return; // Trường hợp cơ sở: cây rỗng
    }
    std::cout << root->data << " "; // 1. Thăm nút gốc (in dữ liệu)
    preorderTraversal(root->left);  // 2. Duyệt cây con trái
    preorderTraversal(root->right); // 3. Duyệt cây con phải
}

// Duyệt theo thứ tự sau (Postorder)
void postorderTraversal(Node* root) {
    if (root == nullptr) {
        return; // Trường hợp cơ sở: cây rỗng
    }
    postorderTraversal(root->left);  // 1. Duyệt cây con trái
    postorderTraversal(root->right); // 2. Duyệt cây con phải
    std::cout << root->data << " "; // 3. Thăm nút gốc (in dữ liệu)
}

// Ví dụ minh họa cách sử dụng
int main() {
    /* Xây dựng cây nhị phân sau:
            1
           / \
          2   3
         / \
        4   5
    */
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);

    std::cout << "Inorder traversal: ";
    inorderTraversal(root); // Output: 4 2 5 1 3
    std::cout << std::endl;

    std::cout << "Preorder traversal: ";
    preorderTraversal(root); // Output: 1 2 4 5 3
    std::cout << std::endl;

    std::cout << "Postorder traversal: ";
    postorderTraversal(root); // Output: 4 5 2 3 1
    std::cout << std::endl;

    // Lưu ý: Để hoàn chỉnh, bạn nên thêm code để giải phóng bộ nhớ (delete nodes)

    return 0;
}

Giải thích code:

• Mỗi hàm duyệt nhận con trỏ root của cây (hoặc cây con) cần duyệt.
• Trường hợp cơ sở (Base Case): Nếu root là nullptr (tức là cây rỗng hoặc đã đi qua hết nhánh), hàm sẽ dừng lại (return). Đây là điểm dừng của đệ quy.
• Bước đệ quy:
  • inorderTraversal: Gọi đệ quy cho nhánh trái, sau đó xử lý nút hiện tại (cout << root->data << " "), rồi gọi đệ quy cho nhánh phải.
  • preorderTraversal: Xử lý nút hiện tại trước, sau đó gọi đệ quy cho nhánh trái, rồi nhánh phải.
  • postorderTraversal: Gọi đệ quy cho nhánh trái, rồi nhánh phải, sau đó mới xử lý nút hiện tại.
• Hàm main minh họa cách tạo một cây đơn giản và gọi các hàm duyệt để xem kết quả.

Ba phương pháp duyệt này là nền tảng quan trọng để xử lý dữ liệu trong cây.

Phần 2: Cây nhị phân tìm kiếm (Binary Search Tree - BST) - Sức Mạnh Của Thứ Tự

Bây giờ, hãy nâng cấp cây nhị phân lên một tầm cao mới với Cây nhị phân tìm kiếm (Binary Search Tree - BST). BST là một loại cây nhị phân có trật tự, được thiết kế đặc biệt để tối ưu hóa các thao tác tìm kiếm, chèn và xóa dữ liệu.

Tính Chất Quan Trọng Của BST

Một cây nhị phân được gọi là Cây nhị phân tìm kiếm nếu nó tuân thủ quy tắc sau đối với mọi nút trong cây:

• Tất cả các giá trị trong cây con bên trái của nút đó đều nhỏ hơn giá trị của nút đó.
• Tất cả các giá trị trong cây con bên phải của nút đó đều lớn hơn giá trị của nút đó. (Hoặc lớn hơn hoặc bằng, tùy thuộc vào cách bạn xử lý các giá trị trùng lặp). Trong ví dụ này, chúng ta giả định các giá trị là khác nhau.
• Các cây con bên trái và bên phải cũng phải là các BST.

Quy tắc đơn giản này mang lại sức mạnh to lớn cho BST. Khi dữ liệu được tổ chức theo cách này, việc tìm kiếm một giá trị trở nên cực kỳ hiệu quả, tương tự như tìm kiếm nhị phân trên mảng đã sắp xếp.

Các Thao Tác Cơ Bản Trên BST

Chúng ta sẽ xem xét cách triển khai các thao tác chèn (insertion), tìm kiếm (search) và xóa (deletion) trên BST bằng C++. Cấu trúc Node vẫn giống như trước.

#include <iostream>

// (Sử dụng lại struct Node đã định nghĩa ở trên)
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

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

    // 2. Nếu giá trị cần chèn nhỏ hơn dữ liệu của nút hiện tại, đi sang cây con trái
    if (value < root->data) {
        root->left = insert(root->left, value); // Gán kết quả vào con trỏ left
    }
    // 3. Nếu giá trị cần chèn lớn hơn dữ liệu của nút hiện tại, đi sang cây con phải
    else if (value > root->data) { // Xử lý trường hợp giá trị bằng: ở đây bỏ qua hoặc bạn có thể cho sang phải
        root->right = insert(root->right, value); // Gán kết quả vào con trỏ right
    }
    // else { // Giá trị đã tồn tại, không làm gì cả (nếu không cho phép trùng lặp) }

    // 4. Trả về con trỏ gốc (hoặc gốc của cây con)
    return root;
}

// Hàm tìm kiếm một giá trị trong BST
Node* search(Node* root, int value) {
    // 1. Trường hợp cơ sở: Cây rỗng hoặc tìm thấy giá trị
    if (root == nullptr || root->data == value) {
        return root; // Trả về con trỏ tới nút nếu tìm thấy, nullptr nếu không
    }

    // 2. Nếu giá trị cần tìm nhỏ hơn dữ liệu của nút hiện tại, tìm kiếm trong cây con trái
    if (value < root->data) {
        return search(root->left, value);
    }
    // 3. Nếu giá trị cần tìm lớn hơn dữ liệu của nút hiện tại, tìm kiếm trong cây con phải
    else { // value > root->data
        return search(root->right, value);
    }
}

// Hàm hỗ trợ tìm nút có giá trị nhỏ nhất trong một cây con
Node* findMin(Node* node) {
    Node* current = node;
    // Duyệt xuống nhánh trái nhất có thể để tìm giá trị nhỏ nhất
    while (current && current->left != nullptr) {
        current = current->left;
    }
    return current;
}

// Hàm xóa một nút có giá trị key khỏi BST
Node* deleteNode(Node* root, int key) {
    // 1. Trường hợp cơ sở: Cây rỗng
    if (root == nullptr) {
        return root;
    }

    // 2. Nếu giá trị cần xóa nhỏ hơn dữ liệu của nút hiện tại, đệ quy sang trái
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    }
    // 3. Nếu giá trị cần xóa lớn hơn dữ liệu của nút hiện tại, đệ quy sang phải
    else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    }
    // 4. Nếu nút hiện tại chứa giá trị cần xóa (key == root->data)
    else {
        // Case 1: Nút cần xóa không có con hoặc chỉ có một con
        // Nếu không có con trái
        if (root->left == nullptr) {
            Node* temp = root->right; // Lưu con trỏ con phải (có thể là nullptr)
            delete root;              // Giải phóng bộ nhớ của nút hiện tại
            return temp;              // Trả về con trỏ con phải (hoặc nullptr)
        }
        // Nếu không có con phải
        else if (root->right == nullptr) {
            Node* temp = root->left;  // Lưu con trỏ con trái
            delete root;              // Giải phóng bộ nhớ
            return temp;              // Trả về con trỏ con trái
        }

        // Case 2: Nút cần xóa có cả hai con
        // Tìm nút kế nhiệm theo thứ tự giữa (inorder successor):
        // Nút nhỏ nhất trong cây con bên phải
        Node* temp = findMin(root->right);

        // Sao chép dữ liệu của nút kế nhiệm vào nút hiện tại
        root->data = temp->data;

        // Xóa nút kế nhiệm (đã sao chép dữ liệu, giờ cần loại bỏ nút gốc)
        // Việc xóa nút kế nhiệm này sẽ rơi vào Case 1 (vì nút kế nhiệm luôn không có con trái)
        root->right = deleteNode(root->right, temp->data);
    }
    return root; // Trả về con trỏ gốc (hoặc gốc của cây con sau khi xóa)
}

// (Sử dụng lại hàm inorderTraversal từ phần trước để kiểm tra BST đã sắp xếp)
void inorderTraversal(Node* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    std::cout << root->data << " ";
    inorderTraversal(root->right);
}


// Ví dụ minh họa các thao tác trên BST
int main() {
    Node* bstRoot = nullptr; // Bắt đầu với BST rỗng

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

    /* Cây BST sau khi chèn các giá trị trên sẽ có dạng (gần đúng):
              50
             /  \
            30   70
           / \  / \
          20 40 60 80
    */

    std::cout << "Inorder traversal of the BST: ";
    inorderTraversal(bstRoot); // Output: 20 30 40 50 60 70 80 (dữ liệu đã sắp xếp!)
    std::cout << std::endl;

    // Tìm kiếm giá trị
    int searchKey = 40;
    if (search(bstRoot, searchKey) != nullptr) {
        std::cout << "Found " << searchKey << " in the BST." << std::endl;
    } else {
        std::cout << searchKey << " not found in the BST." << std::endl;
    }

    searchKey = 90;
     if (search(bstRoot, searchKey) != nullptr) {
        std::cout << "Found " << searchKey << " in the BST." << std::endl;
    } else {
        std::cout << searchKey << " not found in the BST." << std::endl;
    }

    // Xóa giá trị
    int deleteKey = 20; // Xóa nút lá
    std::cout << "Deleting " << deleteKey << "..." << std::endl;
    bstRoot = deleteNode(bstRoot, deleteKey);
    std::cout << "Inorder traversal after deleting " << deleteKey << ": ";
    inorderTraversal(bstRoot);
    std::cout << std::endl;

    deleteKey = 70; // Xóa nút có hai con
    std::cout << "Deleting " << deleteKey << "..." << std::endl;
    bstRoot = deleteNode(bstRoot, deleteKey);
    std::cout << "Inorder traversal after deleting " << deleteKey << ": ";
    inorderTraversal(bstRoot);
    std::cout << std::endl;

    deleteKey = 50; // Xóa nút gốc (có hai con)
    std::cout << "Deleting " << deleteKey << " (root)..." << std::endl;
    bstRoot = deleteNode(bstRoot, deleteKey);
    std::cout << "Inorder traversal after deleting " << deleteKey << ": ";
    inorderTraversal(bstRoot);
    std::cout << std::endl;

    // Lưu ý: Để hoàn chỉnh, bạn nên thêm code để giải phóng bộ nhớ còn lại sau khi dùng cây

    return 0;
}

Giải thích code:

• insert(Node* root, int value): Hàm này nhận gốc của cây con (root) và giá trị cần chèn. Nó hoạt động đệ quy:
  • Nếu root là nullptr, tức là đã tìm thấy vị trí thích hợp để chèn, nó tạo một nút mới và trả về con trỏ tới nút đó.
  • Nếu value nhỏ hơn dữ liệu ở nút hiện tại, nó gọi đệ quy cho cây con bên trái (root->left = insert(...)). Quan trọng là phải gán lại con trỏ left vì nút con mới có thể được tạo hoặc cây con trái có thể thay đổi cấu trúc (ví dụ: nếu chèn vào cây con rỗng).
  • Nếu value lớn hơn, nó gọi đệ quy cho cây con bên phải (root->right = insert(...)).
  • Cuối cùng, nó trả về con trỏ root ban đầu (hoặc con trỏ tới nút mới nếu chèn vào cây rỗng).
• search(Node* root, int value): Hàm này cũng đệ quy:
  • Trường hợp cơ sở: Nếu root là nullptr (không tìm thấy) hoặc root->data bằng value (tìm thấy), trả về root.
  • Nếu value nhỏ hơn root->data, tìm kiếm tiếp trong cây con trái.
  • Nếu value lớn hơn root->data, tìm kiếm tiếp trong cây con phải.
• findMin(Node* node): Hàm này là một hàm hỗ trợ, đi từ một nút cho trước xuống nhánh trái nhất để tìm nút có giá trị nhỏ nhất trong cây con đó. Nút này chính là nút kế nhiệm theo thứ tự giữa (inorder successor) nếu nút ban đầu là gốc của cây con bên phải.
• deleteNode(Node* root, int key): Đây là thao tác phức tạp nhất. Hàm này cũng đệ quy và xử lý ba trường hợp chính khi tìm thấy nút cần xóa:
  • Không có con hoặc một con: Nếu nút cần xóa không có con trái (hoặc cả hai con đều nullptr), chỉ cần trả về con trỏ con phải của nó. Nếu không có con phải, trả về con trỏ con trái. Nút gốc (root) được giải phóng bộ nhớ bằng delete. Con trỏ của nút cha (trong lần gọi đệ quy trước đó) sẽ được gán bằng con trỏ trả về này.
  • Có hai con: Đây là trường hợp phức tạp. Để duy trì tính chất BST, chúng ta không thể chỉ xóa nút đi. Thay vào đó, chúng ta tìm nút kế nhiệm theo thứ tự giữa (inorder successor), là nút có giá trị nhỏ nhất trong cây con bên phải của nút cần xóa (tìm bằng findMin(root->right)). Chúng ta sao chép dữ liệu từ nút kế nhiệm sang nút hiện tại (root->data = temp->data). Sau đó, chúng ta đệ quy gọi hàm deleteNode để xóa nút kế nhiệm gốc khỏi cây con bên phải. Việc xóa nút kế nhiệm luôn rơi vào trường hợp không có con hoặc một con, nên nó sẽ dễ dàng hơn.
• Hàm main minh họa cách sử dụng các hàm insert, search, deleteNode và inorderTraversal để xây dựng và thao tác trên một BST. Duyệt Inorder sau khi chèn cho thấy dữ liệu được sắp xếp đúng. Duyệt Inorder sau khi xóa minh họa cách BST thay đổi.

Độ Phức Tạp Của Thao Tác Trên BST

Hiệu suất của các thao tác tìm kiếm, chèn và xóa trên BST phụ thuộc vào chiều cao của cây.

• Trường hợp trung bình (Average Case): Nếu BST cân bằng tốt (chiều cao gần bằng log n, với n là số nút), thì các thao tác tìm kiếm, chèn và xóa đều có độ phức tạp thời gian là O(log n). Đây là điểm mạnh của BST, nhanh hơn nhiều so với O(n) trên danh sách liên kết hoặc mảng không sắp xếp.
• Trường hợp xấu nhất (Worst Case): Nếu dữ liệu được chèn theo thứ tự tăng dần hoặc giảm dần, BST sẽ trở thành một cây nhị phân xiên (skewed tree), giống như một danh sách liên kết. Khi đó, chiều cao của cây là O(n), và độ phức tạp của các thao tác tìm kiếm, chèn, xóa sẽ là O(n). Điều này làm mất đi lợi thế của BST.