hàm xóa node trong cây nhị phân tìm kiếm

hàm xóa node trong cây nhị phân tìm kiếm

void thaythe(tree &t,node *p)
{
    if(t->left) thaythe(t->left,p);
    //nếu nhánh bên trái còn tức là khác NULL thì tiếp tực nhảy đến nhánh bến trái
    //cho đến khi nào nó là cực trái thì thôi
    else//nó đã là node cực trái
    {
        p->key=t->key;
        //p là con trỏ truyền vào, mọi thay đỏi về bộ nhớ, ô nhớ hay giá trị đều thay đỏi trên
        //hàm xoa(tree &t,int x) đã gọi nó.
        //lúc này p là node cần xóa ở hàm xóa, ta không xóa node mà thay thế giá trị cho nó
        //rồi chuyển nó đến 1 ô nhớ khác, 
        //ô nhớ mà t đang tìm để thay thế để hàm xoa() gọi delete nó.
        p=t;//node t là node ta đã tìm ra để thay thế 
        //nên p=t; tức là sẽ xóa T thay cho p ban đầu
        //nên p(node sẽ xóa ở hàm ngoài) nhảy đến ô nhớ của node thay thế là node T , p=t;
        t=t->right;
        //vì t sẽ bị xóa thông qua p nên t phải nhay đến nhánh bên phải 
        //để làm liến mạch liên kết với cha như đã lý giải ở hàm xóa
        //vì sao lại trỏ right là không phải trỏ left?
        //vì T là node thay thế, là node cực trái, 
        //tức nhánh trái = NULL còn nhánh phải có thể khác NULL
        //hoắc bằng NULL, t không cần xác định, chỉ cần 
        //trỏ t->right để làm liền mạch liên kết đến node cha đã gọi đến nó
        //là ok.
    }
}
void xoa(tree &t,int x)//hàm xóa node trong cây nhị phân tìm kiếm
{
    if(t)//nếu cây t!=NULL
    {
        if(x<t->key) xoa(t->left,x);//nếu x < key xóa bên trái
        else if(x>t->key) xoa(t->right,x);//xóa bên phải
        else//đã tìm thấy node cần xóa
        {
            node *p=t;//gán node cần xóa cho p
            if(t->left==NULL) t=t->right;
            //nếu node cần xóa có 1 cây con bên phải
            else if(t->right==NULL) t=t->left;
            //hoặc 1 cây con bên trái
            //thì T được truyền vào trong đối số hàm nhảy sang trái hoăc sang phải như trên
            //vì sao nó liên kết được với node cha??
            //vì node cha đang trỏ đến con trỏ t (tree &t) 
            //ở dạng tham chiếu luôn nên mọi thay đổi trên t
            //thì đều thay đổi trên cấu trúc của node cha, node gọi đến hàm này
            //vì thế node cha của node cần xóa hiện tại 
            //sẽ trỏ đến t, và khi t=t->right; thì
            //node cha của node cần t cần xóa vẫn đang trỏ 
            //đến t với giá trị là ô địa chỉ mới t->right;
            else thaythe(t->right,p);
            //nếu ndoe t cần xóa có 2 nhánh con thì tìm node cực trái của nhánh phải
            //hoặc ngược lại cũng có thể được
            delete p;
        }
    }
    //lưu ý cần nhớ.
    //khi đối số của hàm là còn trỏ hoặc tham chiếu 
    //thì mọi thay đổi trên nó đều thay đổi đến biến của hàm đã gọi nó, 
    //thay đổi đến cụ diện chung của biến, của hàm đã gọi nó.
}