Trong quá trình xóa một phần tử (hay một Node) có trong cây nhị phân tìm kiếm cần phải đảm bảo được điều kiện ràng buộc của cây nhị phân tìm kiếm. Có 3 trường hợp xóa phần tử X trong cây có thể sảy ra đó là:

• Xóa phần tử là node lá
• Xóa phần tử là node có 1 cây con (trái hoặc phải).
• Xóa phần tử là node có đủ cả 2 cây con

1. Cách xóa phần tử trong cây nhị phân tìm kiếm

Trước khi thực hiện hành động xóa Node trong cây ta cần kiểm tra cây đó có tồn tại phần tử hay không? Nếu như cây có tồn tại thì mới thực hiện xóa, ngược ngại thì sẽ kết thúc hàm xóa luôn. Tiếp theo, ta cần có giá trị khóa X được sử dụng để thực hiện việc xóa Node trong cây theo khóa X.

Trường hợp đầu tiên, khóa X là trùng với Node lá ta sẽ xóa bỏ đi Node này và gán liên kết từ cha của nó thành rỗng. Xem hình minh họa bên dưới:

Trường hợp thứ hai, khóa X là trùng với Node có 1 cây con (trái hoặc phải). Ta sẽ gán liên kết từ cha của nó xuống cây con duy nhất của nó, sau đó xóa đi nút này. Xem hình minh họa bên dưới:

Trường hợp cuối cùng đó là khóa X là trùng với Node có 2 cây con. Khi đó ta không thể xóa trực tiếp Node vì có đủ 2 cây con. Vì vậy, ta cần thực hiện xóa gián tiếp như sau:

• Thay vì xóa đi Node có khóa X, ta sẽ tìm một phần tử thay thế, giả sử là Node P. Phần tử này có tối đa một con.
• Thông tin lưu tại Node P sẽ được chuyển lên lưu tại node có khóa X
• Sau đó, nút bị xóa sẽ là Node P giống như 2 trường hợp đầu.

Chú ý: Ta cần chọn Node P sao cho khi lưu Node P vào vị trí của Node X, cây vẫn là cây nhị phân tìm kiếm. Có 2 phần tử thỏa mãn yêu cầu: (1) Phần tử nhỏ nhất (trái nhất) trên cây con phải. (2) Phần tử lớn nhất (phải nhất) trên cây con trái. Trong đoạn code của mình, tôi sẽ chọn phần tử trái nhất trên cây con phải làm phân tử thay thế.

Ví dụ: Khi cần xóa phần tử có khóa X = 18 ra khỏi cây, phần tử có khóa X = 23 được chọn là phần tử thay thế:

2. Hàm xóa phần tử trong cây nhị phân tìm kiếm

Hàm thêm xóa phần tử trong cây sẽ là một hàm đệ quy vì trong quá trình xóa phần tử sẽ gọi lại chính hàm này để xóa phần tử trong cây theo đúng quy tắc của cây nhị phân tìm kiếm.

Hàm void DeleteNode(Tree &root, int X) dưới đây nhận đầu vào là node gốc Tree &root và tham số khóa int X để sử dụng cho việc tìm kiếm và xóa đi Node có data trùng với khóa X.

void DeleteNode(Tree &root, int X){
    //neu cay rong thi ket thuc ham xoa
    if(root== NULL){
        return;
    }
    //neu khoa X nho hon data cua node dang xet
    if(root->data > X){
        //de quy ham xoa theo nhanh trai
        return DeleteNode(root->left, X);
    }
    //neu khoa X lon hon data cua node dang xet
    if (root->data < X){
        //de quy ham xoa theo nhanh phai
        return DeleteNode(root->right, X);
    }
    //tao node p lam node the mang
    Node* p = root;
    //neu cay con trai la rong
    if(root->left == NULL){
        //gan lai node goc theo nhanh phai
        root = root->right;
    }else if(root->right == NULL){//neu cay con phai la rong
        //gan lai node goc theo nhanh trai
        root = root->left;
    }else{ // nguoc lai, neu cay co du 2 con
        //su dung node the mang
        FindReplNode (p, root->right);
    }
    //xoa di node p
    delete p;
}

Hàm tiếp theo là hàm void FindReplNode (Tree &p, Tree &q) là hàm tìm phần tử thế mạng cho Node P.

void FindReplNode(Tree &p, Tree &q){
    if(q->left){
        FindReplNode(p, q->left);
    }else{
        p->data = q->data;
        p = q;
        q = q->right;
    }
}

Để hiểu rõ hơn, về cách thực hiện của hai hàm DeleteNode và hàm FindReplNode, các bạn có thể chuyển tới phần 4. Chương trình xóa phần tử trong cây nhị phân tìm kiếm

3. Hàm xóa toàn bộ các Node có trong cây

Việc toàn xóa toàn bộ cây có thể được thực hiện thông qua thao tác duyệt cây theo thứ tự sau:

• Xóa theo cây con trái
• Xóa theo cây con phải
• Xóa theo nút gốc.

Hàm void RemoveTree(Tree &root) nhận đầu vào là Tree &root là cây cần xóa. Sau đó thực hiện kiểm tra nếu node root còn tồn tại thì thực hiện đệ quy sang nhanh trái của cây và đệ quy sang nhánh phải của cây sau đó xóa đi node gốc

void RemoveTree(Tree &root){
    //neu van ton tai node goc
    if(root){
        //de quy sang nhanh trai
        RemoveTree(root->left);
        //de quy sang nhanh phai
        RemoveTree(root->right);
        //xoa node goc
        delete(root);
    }
}

4. Chương trình xóa phần tử trong cây nhị phân tìm kiếm

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    //khai bao du lieu cua node co kieu du lieu int
    int data;
    //khai bao con tro den cay con trai
    Node* left;
    //khai bao con tro den cay con phai
    Node* right;

};
typedef struct Node* Tree;
Tree root;

void Init (Tree &root){   
    //gan node goc ve NULL
    root = NULL;
}

Node* CreateNode (int x){
    //tao node moi
    Node* p = new Node;
    //neu cay nhi phan khong rong
    if (p != NULL){
        //gan cay con trai va cay con phai mac dinh bang NULL
        p->left = NULL;
        p->right = NULL;
        //gan data bang x
        p->data = x;
    }
    //tra ve node p
    return p;
}
int InsertNode(Tree &root, Node*p){
    //neu node root khac rong thi thuc hien them vao cay
    if (root != NULL){
        //neu 2 data cua 2 node bang nhau thi ket thuc
        if (root->data==p->data){
            return 0;
        }
        //neu khoa cua root lon hon khoa cua p thi goi de quy trai 
        if (root->data > p->data){
            return InsertNode(root->left, p);
        }
        else{//neu khoa cua root nho hon khoa cua p thi goi de quy phai 
            return InsertNode(root->right,p);
        }
    }else { //truong hop neu node root la rong thi them node p vao node root
        root = p;
    }
}

void Input(Tree &root){
    int n;
    printf ("NHAP SO LUONG NODE CAN THEM: "); 
    scanf("%d",&n);
    for(int i=1; i<=n;i++){
        int x;
        printf ("NHAP DATA CUA NODE %d: ",i); 
        scanf("%d",&x);
        //tao node p co data = x
        Node* p = CreateNode(x);
        //them node p co data x vao trong cay
        InsertNode(root, p);
    }
}

void NLR(Tree root){
    if (root!=NULL){
        //hien thi du lieu cua tung node sau khi duyet
        printf("%d \t",root->data);
        //su dung de quy de duyet tiep cay con trai
        NLR(root->left);
        //su dung de quy de duyet tiep cay con phai
        NLR(root->right);
    }
}

void FindReplNode(Tree &p, Tree &q){
    if(q->left){
        FindReplNode(p, q->left);
    }else{
        p->data = q->data;
        p = q;
        q = q->right;
    }
}

void DeleteNode(Tree &root, int X){
    //neu cay rong thi ket thuc ham xoa
    if(root== NULL){
        return;
    }
    //neu khoa X nho hon data cua node dang xet
    if(root->data > X){
        //de quy ham xoa theo nhanh trai
        return DeleteNode(root->left, X);
    }
    //neu khoa X lon hon data cua node dang xet
    if (root->data < X){
        //de quy ham xoa theo nhanh phai
        return DeleteNode(root->right, X);
    }
    //tao node p lam node the mang
    Node* p = root;
    //neu cay con trai la rong
    if(root->left == NULL){
        //gan lai node goc theo nhanh phai
        root = root->right;
    }else if(root->right == NULL){//neu cay con phai la rong
        //gan lai node goc theo nhanh trai
        root = root->left;
    }else{ // nguoc lai, neu cay co du 2 con
        //su dung node the mang
        FindReplNode (p, root->right);
    }
    //xoa di node p
    delete p;
}

void RemoveTree(Tree &root){
    //neu van ton tai node goc
    if(root){
        //de quy sang nhanh trai
        RemoveTree(root->left);
        //de quy sang nhanh phai
        RemoveTree(root->right);
        //xoa node goc
        delete(root);
    }
}
int main(){
    //tao cay voi node goc la root
    Tree root;
    //khoi tao cay
    Init(root);
    //nhap n phan tu vao cay
    Input(root);
    //duyet cay theo NLR
    printf("Duyet cay theo NLR\n");
    NLR(root);
    //tao khoa X = 5
    int X = 5;
    //goi ham xoa node theo khoa X
    DeleteNode(root,X);
    //duyet cay theo NLR
    printf("\nCay sau khi xoa node co khoa X = 5\n");
    NLR(root);
    //goi ham huy toan bo cay
    RemoveTree(root);
}