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

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;
	}
}

xpRoot->p_right là khác nhau.

Đúng vậy.

p/s: con trỏ *x là biến trong khối nên ko bị báo trùng tên, nhưng bạn nên đặt tên khác vì x là số cần xóa rồi.

2 Likes

Em chưa hiểu ý anh là gì. Và anh cho em hỏi x = x -> p_left thực chất có phải như em nói ở trên phải không anh?

Cây ban đầu là 10 (6 (1 (L 2)))
vậy là p_right đang trỏ đến node đã xóa (0xfeeefeee).

3 Likes

Dạ không phải anh. Cây đầu là 10(2(1 (L 6)). Em thay data của 2 bằng 6. Rồi em xóa node số 6 đi. Trước khi xóa em có câu lệnh x = x->right. Trên mạng bảo là đây nghĩa là cập nhật node số 6 cũ bằng node null. Nghĩa là node cha của node số 6 sẽ được cập nhật trỏ đến null, điều này em thấy khó hiểu.Sau khi chạy hết hàm thì em nhận ra bên trái node số 6 (node số 2 cũ) không phải là NULL mà là 1 node có gia trị rác.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?