Thắc mắc về cây nhị phân tìm kiếm

Vu_Le1 · November 24, 2020, 2:43pm

Chào các anh chị và các bạn. Bài viết trước mình nhận thấy bài viết lủng củng nên ít tương tác. Nên mình xin viết lại câu hỏi cho rõ ràng hơn. Mong mọi người thông cảm vì đăng 2 bài cùng câu hỏi.
Trước tiên, đây là code của hàm xóa một node bất kì:

void FindNodeLeft(NODE* &p, NODE* &y){
	if (y->p_left){
		FindNodeLeft(p,y->p_left);
	}
	else{
		p->key = y->key;
		p = y;
		y = y->p_right;
	}
}
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* Y = pRoot->p_right;
			FindNodeLeft(p, Y);
		} 
		delete[]p; p = nullptr;
	}
}

CODE này em copy hoàn toàn từ một thầy trên Youtube, và nó cũng y hệt trong sách nữa. Nên mình tin là nó đúng. Khi debug mình thấy vấn đề, đây là phần giải thích và thắc mắc của mình:

Thứ nhất, hàm này dùng để xóa 1 NODE bất kì, trong đây có 3 trường hợp:

NODE là lá, việc xóa nó đơn giản chỉ là xóa và cập nhật liên kết của NODE cha của nó vào con trỏ NULL.
NODE có 1 con, xóa NODE này bằng cách xóa nó và cập nhật liên kết giữa cha của nó vào con trỏ con của nó.
Việc xóa 2 trường hợp này thì phần code khá đơn giản. Nhưng nó có sử dụng câu lệnh: pRoot = pRoot->p_right hoặc pRoot = pRoot->p_left, nghĩa là cập nhật liên kết giữa cha của pRoot và con là pRoot->p_right hoặc pRoot->p_left. Để sau này khi mà duyệt thì không bị truy cập vào vùng nhớ bị thu hồi. Em debug 2 trường hợp này và thấy nó hoạt động bình thường, nên em tin là đúng mặc dù em chưa từng biết công dụn của câu lệnh đó là như vậy.
Thứ 3 là phần em bị mắc bug. Đó là xóa NODE có 2 lá, có 2 cách làm đó là tìm phần tử trái nhất bên cây con phải, hoặc là phải nhất của cây con trái. Và mình chọn cách thứ nhất. Trước tiên mình xin trình bày các biến cho các anh chị dễ hiểu. Đó là p = Proot, pRoot là NODE mình muốn xóa, x là NODE mình tìm được NODE trái nhất cây con phải (NODE thế thân). Theo như mình biết thì cách làm trường hợp này là không XÓA NODE CẦN XÓA, mà chỉ cần đổi data với NODE thế thân, rồi xóa NODE thế thân đi.

Đây là tóm tắt cách làm của em. Em viết ra vậy cho mọi người dễ hình dung nhất và mong mọi người giúp đỡ.

Thứ 2, là phần bug. Mảng số nguyên mà em cấp vào để tạo cây nhị phân lần lượt là 10, 2,1,6 viết theo cây nhị phân đó là (1 <- 2 -> 6 ) <- 10 -> null. Em muốn xóa NODE số 2. Khi CODE chạy đến phần

x->key = y->key;
x = y;
y = y->p_right;

với lệnh đầu tiên x là NODE số 2, y là NODE số 6. Đến lệnh số 2, thì x và y cùng trỏ đến NODE số 6. Lệnh số 3 là y trỏ đến NULL.

Vấn đề em nhận ra đó là theo như trong clip 1 thầy trên Utube bảo thì lệnh
y = y->p_right; nghĩa là cập nhật liên kết giữa NODE cha của y đến NODE con của y. Nghĩa là nối liên kết giữa NODE số 2 (data lúc đầu) đến NULL. Nhưng khi debug thì em lại thấy thực chất không có liên kết gì hết. NODE số 2 (data lúc đầu) bên nhánh phải nó không trỏ đến NULL mà vẫn trỏ đến NODE thế thân (data lúc đầu là 6). Nên khi xóa NODE thế thân đi thì mắc lỗi truy cập vùng nhớ thu hồi. Bằng chứng là hình ảnh sau khi chạy xong hàm. NODE có data là 6, pRight của nó là 1 NODE lạ (NODE pRight hàng thứ 4) bằng chứng là nó trỏ đến vùng nhớ bị xóa. Nghĩa là lệnh y = y->p_right; mà dùng để cập nhật liên kết không có tác dụng.

Đó là vấn đề của em. Em mong bài viết dài này sẽ giúp a/c hình dung rõ hơn và giúp em. Em bị bí cái này mấy ngày nay rồi. Xin cảm ơn mọi người!

rogp10 · November 24, 2020, 12:59pm

Vì tham số bạn truyền vào nằm ngoài cây nên cây không được cập nhật đúng, chứ cách làm là đúng rồi

Vu_Le1 · November 24, 2020, 1:00pm

Vậy nghĩa là mình phải sử dụng NODE nằm trong cây phải không ạ?
Nếu như vậy thì em phải sửa làm sao anh?

rogp10 · November 24, 2020, 1:28pm

Chỗ này đây:

Bạn truyền thẳng vào mới ra đúng.

Vu_Le1 · November 24, 2020, 1:43pm

Được rồi ạ. Em cảm ơn anh nhiều. Nhưng anh ơi, a có thể giải thích cho em cái NODE trong cây hay NODE ở ngoài được không? Đều là con trỏ cả mà anh?

Stanley00 · November 25, 2020, 4:08am

Nếu code này bạn code bằng C, chỉ dùng con trỏ thay vì dùng reference của C++, bạn sẽ dễ thấy tại sao lại như vậy hơn.

Còn đây là đoạn code nhỏ mô tả vấn đề tại sao:

C++

#include <iostream>

void f1(int* const p){
    std::cout << *p << ' ' << &p << '\n';
}

void f2(int* const &p){
    std::cout << *p << ' ' << &p << '\n';
}

int main(){
    int x=42;
    int* px = &x;
    int* &py = px;
    int* pz = &x;

    f1(&x);
    f1(px);
    f1(py);
    f1(pz);

    std::cout << "=================\n";

    f2(&x);
    f2(px);
    f2(py);
    f2(pz);
}

Vu_Le1 · December 17, 2020, 4:01pm

Em cảm ơn anh. Lâu rồi chưa gặp anh!