[Thuật toán] Một số phép toán trên cây nhị phân tìm kiếm

Cây nhị phân tìm kiếm (CNPTK) là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn khóa của tất cả các nút thuộc cây con phải.
Dưới đây là một ví dụ về cây nhị phân tìm kiếm:


Nhờ ràng buộc về khóa trên CNPTK, việc tìm kiếm trở nên có định hướng. Hơn nữa, do cấu trúc cây việc tìm kiếm trở nên nhanh đáng kể. Nếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N.

Cấu trúc cây:

1
2
3
4
5
6
7
typedef int item; //kieu item la kieu nguyen
struct Node
{
     item key; //truong key cua du lieu
     Node *Left, *Right; //con trai va con phai
};
typedef Node *Tree;  //cay
Vậy là ta đã có cấu trúc cây Tree. Giờ chúng ta sẽ thực hiện một số thao tác.

Thêm 1 phần tử vào cây

Việc thêm một phần tử X vào cây phải bảo đảm điều kiện ràng buộc của CNPTK. Ta có thể thêm vào nhiều chỗ khác nhau trên cây, nhưng nếu thêm vào một nút lá sẽ là tiện lợi nhất do ta có thể thực hiên quá trình tương tự thao tác tìm kiếm. Khi chấm dứt quá trình tìm kiếm cũng chính là lúc tìm được chỗ cần thêm.
01
02
03
04
05
06
07
08
09
10
11
12
13
14
int insertNode(Tree &T, item x) // chen 1 Node vao cay
{
    if (T != NULL)
    {
        if (T->key == x) return -1;  // Node nay da co
        if (T->key > x) return insertNode(T->Left, x); // chen vao Node trai
        else if (T->key < x) return insertNode(T->Right, x);   // chen vao Node phai
    }
    T = (Node *) malloc(sizeof(Node));
    if (T == NULL) return 0;    // khong du bo nho
    T->key = x;
    T->Left = T->Right = NULL;
    return 1;   // ok
}
Vậy là xong con ong.

Nhập cây

Việc nhập cây là việc lặp đi lặp lại chèn 1 phần tử vào cây đến một điều kiện nào đó thì dừng. Ở code dưới đây điều kiện dừng là nhập vào phần tử = 0.
01
02
03
04
05
06
07
08
09
10
11
12
13
14
void CreateTree(Tree &T)        // nhap cay
{
    int x;
    while (1)
    {
        printf("Nhap vao Node: ");
        scanf("%d", &x);
        if (x == 0) break// x = 0 thi thoat
        int check = insertNode(T, x);
        if (check == -1) printf("Node da ton tai!");
        else if (check == 0) printf("Khong du bo nho");
    }
}
Việc nhập đã xong, tuy thế thôi nhưng nhiều người khi code không biết nhập cây kiểu gì :3 (mình đã từng bị như vậy)

Duyệt cây

Thao tác duyệt cây trên cây nhị phân tìm kiếm hoàn toàn giống như trên cây nhị phân. Đặc biệt khi duyệt theo thứ tự giữa, trình tự các nút duyệt qua sẽ cho ta một dãy các nút theo thứ tự tăng dần của khóa. (1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 20, 23)
1
2
3
4
5
6
7
8
9
void LNR(Tree T)
{
     if(T!=NULL)
     {
      LNR(T->Left);
      printf("%d   ",T->key);
      LNR(T->Right);
     }
}
Việc duyệt theo thứ tự trước hoặc sau các bạn làm tương tự.

Tìm một Node có key = x trong cây

01
02
03
04
05
06
07
08
09
10
Node* searchKey(Tree T, item x)     // tim nut co key x
{
    if (T!=NULL)
    {
        if (T->key == x) { Node *P = T; return P;}
        if (T->key > x) return searchKey(T->Left, x);
        if (T->key < x) return searchKey(T->Right, x);
    }
    return NULL;
}
Việc tìm kiếm như trên mình đã nêu là rất đơn giản và nhanh đáng kể.

Xóa Node có key = x trong cây

Việc hủy một phần tử X ra khỏi cây phải bảo đảm điều kiện ràng buộc của CNPTK. Có 3 trường hợp khi hủy nút X có thể xảy ra:
– X là nút lá: Đơn giản chỉ cần hủy X vì nó không móc nối đến phần tử nào khác.
– X chỉ có 1 con (trái hoặc phải): Trước khi hủy X ta móc nối cha của X với con duy nhất của nó.
– X có đủ cả 2 con: ta không thể hủy trực tiếp do X có đủ 2 con. Ta sẽ hủy gián tiếp. Thay vì hủy X, ta sẽ tìm một phần tử thế mạng Q. Phần tử này có tối đa một con. Thông tin lưu tại Q sẽ được chuyển lên lưu tại X. Sau đó, nút bị hủy thật sự sẽ là Y giống như 2 trường hợp đầu. Vấn đề là phải chọn Y sao cho khi lưu Q vào vị trí của X, cây vẫn là CNPTK.
Có 2 phần tử thỏa mãn yêu cầu:
+ Phần tử nhỏ nhất (trái nhất) trên cây con phải.
+ Phần tử lớn nhất (phải nhất) trên cây con trái.
Việc chọn lựa phần tử nào là phần tử thế mạng hoàn toàn phụ thuộc vào ý thích của người lập trình. Trong code này tôi chọn phần tử phải nhất.
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int delKey(Tree &T, item x)     // xoa nut co key x
{
    if (T==NULL) return 0;
    else if (T->key > x) return delKey(T->Left, x);
    else if (T->key < x) return delKey(T->Right, x);
    else // T->key == x
    {
        Node *P = T;
        if (T->Left == NULL) T = T->Right;    // Node chi co cay con phai
        else if (T->Right == NULL) T = T->Left;   // Node chi co cay con trai
        else // Node co ca 2 con
        {
            Node *S = T, *Q = S->Left;
            // S la cha cua Q, Q la Node phai nhat cua cay con trai cua P
            while (Q->Right != NULL)
            {
                S = Q;
                Q = Q->Right;
            }
            P->key = Q->key;
            S->Right = Q->Left;
            delete Q;
        }
    }
    return 1;
}
Vậy là đã xóa xong một node.

Code tham khảo:

001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020
021
022
023
024
025
026
027
028
029
030
031
032
033
034
035
036
037
038
039
040
041
042
043
044
045
046
047
048
049
050
051
052
053
054
055
056
057
058
059
060
061
062
063
064
065
066
067
068
069
070
071
072
073
074
075
076
077
078
079
080
081
082
083
084
085
086
087
088
089
090
091
092
093
094
095
096
097
098
099
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<stdlib.h>
#include<stdio.h>
typedef int item; //kieu item la kieu nguyen
struct Node
{
     item key; //truong key cua du lieu
     Node *Left, *Right; //con trai va con phai
};
typedef Node *Tree;  //cay
int insertNode(Tree &T, item x) // chen 1 Node vao cay
{
    if (T != NULL)
    {
        if (T->key == x) return -1;  // Node nay da co
        if (T->key > x) return insertNode(T->Left, x); // chen vao Node trai
        else if (T->key < x) return insertNode(T->Right, x);   // chen vao Node phai
    }
    T = (Node *) malloc(sizeof(Node));
    if (T == NULL) return 0;    // khong du bo nho
    T->key = x;
    T->Left = T->Right = NULL;
    return 1;   // ok
}
void CreateTree(Tree &T)        // nhap cay
{
    int x;
    while (1)
    {
        printf("Nhap vao Node: ");
        scanf("%d", &x);
        if (x == 0) break// x = 0 thi thoat
        int check = insertNode(T, x);
        if (check == -1) printf("Node da ton tai!");
        else if (check == 0) printf("Khong du bo nho");
    }
}
// Duyet theo LNR
void LNR(Tree T)
{
     if(T!=NULL)
     {
      LNR(T->Left);
      printf("%d   ",T->key);
      LNR(T->Right);
     }
}
Node* searchKey(Tree T, item x)     // tim nut co key x
{
    if (T!=NULL)
    {
        if (T->key == x) { Node *P = T; return P;}
        if (T->key > x) return searchKey(T->Left, x);
        if (T->key < x) return searchKey(T->Right, x);
    }
    return NULL;
}
int delKey(Tree &T, item x)     // xoa nut co key x
{
    if (T==NULL) return 0;
    else if (T->key > x) return delKey(T->Left, x);
    else if (T->key < x) return delKey(T->Right, x);
    else // T->key == x
    {
        Node *P = T;
        if (T->Left == NULL) T = T->Right;    // Node chi co cay con phai
        else if (T->Right == NULL) T = T->Left;   // Node chi co cay con trai
        else // Node co ca 2 con
        {
            Node *S = T, *Q = S->Left;
            // S la cha cua Q, Q la Node phai nhat cua cay con trai cua P
            while (Q->Right != NULL)
            {
                S = Q;
                Q = Q->Right;
            }
            P->key = Q->key;
            S->Right = Q->Left;
            delete Q;
        }
    }
    return 1;
}
int main()
{
    Tree T;
    T=NULL; //Tao cay rong
    CreateTree(T); //Nhap cay
    //duyet cay
    printf("Duyet cay theo LNR: n");
    LNR(T);
    printf("n");
    Node *P;
    item x;
    printf("Nhap vao key can tim: ");
    scanf("%d", &x);
    P = searchKey(T, x);
    if (P != NULL) printf("Tim thay key %dn", P->key);
    else printf("Key %d khong co trong cayn", x);
    if (delKey(T, x)) printf("Xoa thanh congn");
    else printf("Khong tim thay key %d can xoan", x);
    printf("Duyet cay theo LNR: n");
    LNR(T);
    printf("n");
    return 0;
}
Mới hơn Cũ hơn

Biểu mẫu liên hệ