Chào các anh chị. Em có làm 1 hàm xóa 1 node trong cây nhị phân tìm kiếm. Toàn bộ code này em copy từ sách. Sau đây là vài thắc mắc của em:
- Điều thứ nhất đó là, khi em tạo cây nhị phân tìm kiếm từ chuỗi [10, 2, 6, 1] .Em muốn xóa node chứa phần tử số 2. Thì khi mà thực hiện x = x-> p_left (trong hàm FindNodeLeft) thì giá trị vùng nhớ của con trỏ x này là NULL (nghĩa là sau khi xóa NODE 2, phía bên PHẢI node số 6 là NULL). Tuy nhiên sau khi chạy hết hàm này thì em xem lại giá trị của cây thì thấy bên PHẢI node số 6 là một node khác NULL ( có giá trị - 1789 bla bla). Do đó khi truy vấn đến thì bị lỗi).
- Điều thứ hai đó là, đến bài toán này em mới thực sự rối cái x = x->p_left. Đây là lấy x trỏ đến vùng nhớ của x -> p_left. Nhưng đến bây giờ em mới nghe đó là phép đó là cập nhật vùng nhớ. nghĩa là cái NODE cha của x vẫn trỏ đến x sau khi x = x->p_left. Thực sự em không hiểu vấn đề này là sao. Bởi vì em nghĩ node cha của x là trỏ đến vùng nhớ của x cũng đang trỏ. Vậy khi x trỏ nơi khác rồi thì chả của x đâu thể chạy theo x được!. Đó là thắc mắc của em. Nếu em có lổ hổng trong kiến thức căn bản thì mong mọi người chỉ bảo ạ!
void FindNodeLeft(NODE* & p, NODE* &x){
if (x->p_left){
FindNodeLeft(p, x->p_left);
}
else{
p->key = x->key;
p = x;
x = x->p_left;
}
}
void Remove(NODE* &pRoot, int x){
if (!pRoot) return;
if (pRoot->key > x){
Remove(pRoot->p_left, x);
}
else if (pRoot->key < x){
Remove(pRoot->p_right, x);
}
else{
NODE* p = pRoot;
if (!pRoot->p_left){ pRoot = pRoot->p_right; }
else if (!pRoot->p_right){pRoot = pRoot->p_left;}
else{
NODE* x = pRoot->p_right;
FindNodeLeft(p, x);
}
delete[]p; p = nullptr;
}
}
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?