Cây tìm kiếm nhị phân - Tìm kiếm dữ liệu hiệu quả

Trong bài viết này, chúng ta sẽ tìm hiểu về cấu trúc dữ liệu cây, và cụ thể là cây tìm kiếm nhị phân. Cây tìm kiếm nhị phân là một cấu trúc dữ liệu được sử dụng phổ biến và có tính ứng dụng cao. Hãy cùng tìm hiểu và cài đặt cây tìm kiếm nhị phân sử dụng ngôn ngữ C/C++.

1. Lý thuyết về cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân (BST) là một cây nhị phân và có các ràng buộc sau:

1. Giá trị của tất cả các Node ở cây con bên trái phải = giá trị của Node gốc.
2. Giá trị của tất cả các Node ở cây con bên phải phải > giá trị của Node gốc.
3. Tất cả các cây con (bao gồm bên trái và phải) cũng phải đảm bảo 2 tính chất trên.

Cây tìm kiếm nhị phân là một cấu trúc dữ liệu hiệu quả cho phép chúng ta xây dựng nên một danh sách mà dữ liệu trên đó được sắp xếp. Nó được gọi là cây nhị phân vì mỗi Node của cây chỉ có tối đa hai con. Nó được gọi là cây tìm kiếm nhị phân vì nó có thể được sử dụng để tìm kiếm sự hiện diện của một phần tử trong thời gian O(log(n)).

2. Cài đặt cây BST

Sau đây, chúng ta sẽ cùng đi cài đặt cây tìm kiếm nhị phân sử dụng danh sách liên kết. Chúng ta chỉ cần lưu giữ Node gốc của cây.

Đầu tiên, chúng ta sẽ định nghĩa kiểu dữ liệu cho các Node của cây:

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

Tiếp theo, chúng ta sẽ triển khai code cho một số chức năng của cây BST.

2.1. Hàm giải phóng dữ liệu

Chúng ta sẽ sử dụng hàm này khi muốn xóa một cây con hoặc toàn bộ cây bằng cách cung cấp Node gốc của cây muốn xóa. Việc giải phóng được thực hiện theo trình tự:

1. Gọi đệ quy xóa cây con bên trái.
2. Gọi đệ quy xóa cây con bên phải.
3. Giải phóng vùng nhớ cho con trỏ hiện tại.

void Free(node_t* root) {
    if (root == NULL) return;
    Free(root->left);
    Free(root->right);
    free(root);
}

2.2. Hàm điều hướng của cây

Hai hàm dưới đây sẽ phục vụ chúng ta trong quá trình thêm phần tử và tìm kiếm trên cây tìm kiếm nhị phân.

int LeftOf(const int value, const node_t* root) {
    return value  root->data;
}

int RightOf(const int value, const node_t* root) {
    return value > root->data;
}

2.3. Thêm phần tử vào BST

Việc thêm một phần tử vào cây nhị phân tìm kiếm vẫn phải đảm bảo các ràng buộc của một BST. Đầu tiên, chúng ta cần tìm vị trí thích hợp trong BST để lưu giữ phần tử mới.

Nếu Node hiện tại là NULL, đó là vị trí cần thêm. Thêm vào BST và kết thúc.

Nếu giá trị cần thêm giá trị root hiện tại, gọi đệ quy Insert vào cây con bên trái.

Nếu giá trị cần thêm > giá trị root hiện tại, gọi đệ quy Insert vào cây con bên phải.

node_t* Insert(node_t* root, const int value) {
    if (root == NULL) {
        node_t* node = (node_t*)malloc(sizeof(node_t));
        node->left = NULL;
        node->right = NULL;
        node->data = value;
        return node;
    }
    if (LeftOf(value, root))
        root->left = Insert(root->left, value);
    else if (RightOf(value, root))
        root->right = Insert(root->right, value);
    return root;
}

2.4. Tìm kiếm trên BST

Việc tìm kiếm cũng tương tự như việc thêm phần tử vào BST. Chúng ta cần duyệt qua BST để tìm phần tử cần tìm.

Nếu Node hiện tại có giá trị = giá trị cần tìm, trả về true và kết thúc.

Nếu Node hiện tại có giá trị > giá trị cần tìm, gọi đệ quy tìm ở cây con bên trái.

Nếu Node hiện tại có giá trị giá trị cần tìm, gọi đệ quy tìm ở cây con bên phải.

Nếu tìm đến hết cây (Node đó = NULL) mà không tìm thấy, trả về false và kết thúc.

int Search(const node_t* root, int value) {
    if (root == NULL)
        return 0;
    if (root->data == value) {
        return 1;
    } else if (LeftOf(value, root)) {
        return Search(root->left, value);
    } else if (RightOf(value, root)) {
        return Search(root->right, value);
    }
}

2.5. Lấy giá trị con trái nhất

Để lấy giá trị con trái nhất, chúng ta chỉ cần duyệt theo con trỏ trỏ từ Node gốc đến cây con bên trái cho đến khi không còn con bên trái nào nữa.

int LeftMostValue(const node_t* root) {
    while (root->left != NULL)
        root = root->left;
    return root->data;
}

2.6. Xóa Node trong BST

Việc xóa Node trong BST có thể phức tạp tùy thuộc vào trường hợp. Chúng ta sẽ xóa một Node ở trung gian, và cần tìm cách xóa và nối lại cây để vẫn đảm bảo BST.

1. Node cần xóa là Node lá (không có con nào)

Trong trường hợp này, Node sẽ được giải phóng và cây con duy nhất của Node sẽ được liên kết trực tiếp với cha của Node đó.

2. Node cần xóa có 1 con

Trong trường hợp này, Node sẽ được giải phóng và cây con duy nhất của Node sẽ được liên kết trực tiếp với cha của Node đó.

3. Node cần xóa có đủ 2 con

Đây là trường hợp phức tạp nhất. Ta cần tìm Node thế thân cho Node cần xóa, đó là Node trái nhất của cây con bên phải của Node cần xóa. Sau đó, gọi đệ quy xóa Node thế thân. Khi đó, Node cần xóa sẽ quay trở về trường hợp 1 hoặc 2.

node_t* Delete(node_t* root, int value) {
    if (root == NULL)
        return root;
    if (LeftOf(value, root))
        root->left = Delete(root->left, value);
    else if (RightOf(value, root))
        root->right = Delete(root->right, value);
    else {
        // root->data == value, delete this node
        if (root->left == NULL) {
            node_t* newRoot = root->right;
            free(root);
            return newRoot;
        }
        if (root->right == NULL) {
            node_t* newRoot = root->left;
            free(root);
            return newRoot;
        }
        root->data = LeftMostValue(root->right);
        root->right = Delete(root->right, root->data);
    }
    return root;
}

3. Duyệt cây tìm kiếm nhị phân

Ở mục này, chúng ta sẽ tìm hiểu về 3 cách duyệt cây tìm kiếm nhị phân: PreOrder, InOrder và PostOrder.

3.1. Duyệt PreOrder

Quy trình duyệt PreOrder sẽ thực hiện theo thứ tự Node -> Left -> Right, cụ thể như sau:

1. Ghé thăm Node root.
2. Gọi đệ quy duyệt qua cây con bên trái.
3. Gọi đệ quy duyệt qua cây con bên phải.

void PreOrder(node_t* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

3.2. Duyệt InOrder

Quy trình duyệt InOrder sẽ thực hiện theo thứ tự Left -> Node -> Right, cụ thể như sau:

1. Gọi đệ quy duyệt qua cây con bên trái.
2. Ghé thăm Node root.
3. Gọi đệ quy duyệt qua cây con bên phải.

void InOrder(node_t* root) {
    if (root != NULL) {
        InOrder(root->left);
        printf("%d ", root->data);
        InOrder(root->right);
    }
}

3.3. Duyệt PostOrder

Quy trình duyệt PostOrder sẽ thực hiện theo thứ tự Left -> Right -> Node, cụ thể như sau:

1. Gọi đệ quy duyệt qua cây con bên trái.
2. Gọi đệ quy duyệt qua cây con bên phải.
3. Ghé thăm Node root.

void PostOrder(node_t* root) {
    if (root != NULL) {
        PostOrder(root->left);
        PostOrder(root->right);
        printf("%d ", root->data);
    }
}

4. Code đầy đủ cây tìm kiếm nhị phân

#include 
#include 

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

void Free(node_t* root) {
    if (root == NULL)
        return;
    Free(root->left);
    Free(root->right);
    free(root);
}

int LeftOf(const int value, const node_t* root) {
    return value  root->data;
}

int RightOf(const int value, const node_t* root) {
    return value > root->data;
}

node_t* Insert(node_t* root, const int value) {
    if (root == NULL) {
        node_t* node = (node_t*)malloc(sizeof(node_t));
        node->left = NULL;
        node->right = NULL;
        node->data = value;
        return node;
    }
    if (LeftOf(value, root))
        root->left = Insert(root->left, value);
    else if (RightOf(value, root))
        root->right = Insert(root->right, value);
    return root;
}

int Search(const node_t* root, int value) {
    if (root == NULL)
        return 0;
    if (root->data == value) {
        return 1;
    } else if (LeftOf(value, root)) {
        return Search(root->left, value);
    } else if (RightOf(value, root)) {
        return Search(root->right, value);
    }
}

int LeftMostValue(const node_t* root) {
    while (root->left != NULL)
        root = root->left;
    return root->data;
}

node_t* Delete(node_t* root, int value) {
    if (root == NULL)
        return root;
    if (LeftOf(value, root))
        root->left = Delete(root->left, value);
    else if (RightOf(value, root))
        root->right = Delete(root->right, value);
    else {
        // root->data == value, delete this node
        if (root->left == NULL) {
            node_t* newRoot = root->right;
            free(root);
            return newRoot;
        }
        if (root->right == NULL) {
            node_t* newRoot = root->left;
            free(root);
            return newRoot;
        }
        root->data = LeftMostValue(root->right);
        root->right = Delete(root->right, root->data);
    }
    return root;
}

void PreOrder(node_t* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        PreOrder(root->left);
        PreOrder(root->right);
    }
}

void InOrder(node_t* root) {
    if (root != NULL) {
        InOrder(root->left);
        printf("%d ", root->data);
        InOrder(root->right);
    }
}

void PostOrder(node_t* root) {
    if (root != NULL) {
        PostOrder(root->left);
        PostOrder(root->right);
        printf("%d ", root->data);
    }
}

int main() {
    node_t* root = NULL;
    root = Insert(root, 25);
    root = Insert(root, 15);
    root = Insert(root, 50);
    root = Insert(root, 10);
    root = Insert(root, 22);
    root = Insert(root, 35);
    root = Insert(root, 70);
    root = Insert(root, 4);
    root = Insert(root, 12);
    root = Insert(root, 18);
    root = Insert(root, 24);
    root = Insert(root, 31);
    root = Insert(root, 44);
    root = Insert(root, 66);
    root = Insert(root, 90);

    printf("\nDuyệt PreOrder: ");
    PreOrder(root);
    printf("\nDuyệt InOrder: ");
    InOrder(root);
    printf("\nDuyệt PostOrder: ");
    PostOrder(root);

    printf("\n\n==Thử thêm phần tử 15 vào BTS==\n");
    Insert(root, 15);
    printf("\nDuyệt PreOrder: ");
    PreOrder(root);
    printf("\nDuyệt InOrder: ");
    InOrder(root);
    printf("\nDuyệt PostOrder: ");
    PostOrder(root);

    printf("\n\n==Thử xóa phần tử 50 khỏi BTS==\n");
    Delete(root, 50);
    printf("\nDuyệt PreOrder: ");
    PreOrder(root);
    printf("\nDuyệt InOrder: ");
    InOrder(root);
    printf("\nDuyệt PostOrder: ");
    PostOrder(root);

    Free(root);
    root = NULL;

    return 0;
}

Trong hàm main, tôi đã cài đặt một BST với các phần tử sau:

25
├── 15
│   ├── 10
│   │   ├── 4
│   │   └── 12
│   └── 22
│       ├── 18
│       └── 24
└── 50
    ├── 35
    │   ├── 31
    │   └── 44
    └── 70
        ├── 66
        └── 90

Mời các bạn kiểm tra kết quả chạy của code:

Duyệt PreOrder: 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90
Duyệt InOrder: 4 10 12 15 18 22 24 25 31 35 44 50 66 70 90
Duyệt PostOrder: 4 12 10 18 24 22 15 31 44 35 66 90 70 50 25

==Thử thêm phần tử 15 vào BTS==
Duyệt PreOrder: 25 15 10 4 12 22 18 24 50 35 31 44 70 66 90
Duyệt InOrder: 4 10 12 15 18 22 24 25 31 35 44 50 66 70 90
Duyệt PostOrder: 4 12 10 18 24 22 15 31 44 35 66 90 70 50 25

==Thử xóa phần tử 50 khỏi BTS==
Duyệt PreOrder: 25 15 10 4 12 22 18 24 66 35 31 44 70 90
Duyệt InOrder: 4 10 12 15 18 22 24 25 31 35 44 66 70 90
Duyệt PostOrder: 4 12 10 18 24 22 15 31 44 35 90 70 66 25

5. Bài tập thực hành

Mời các bạn thực hành giải các bài toán liên quan đến cây tìm kiếm nhị phân:

• https://vn.spoj.com/problems/NKTREE/
• http://ntucoder.net/Problem/List?ThemeID=17
• https://www.hackerearth.com/practice/data-structures/trees/binary-search-tree/practice-problems/