문과생이 이해한 트리(삭제)

출처 : <c언어로 쉽게 풀어쓴 자료구조> + 학교 수업

 

void delete_node(TreeNode **root, int key) {
	TreeNode* p = NULL;
	TreeNode* t = *root;

	//키 탐색
	while (t != NULL && t->key != key) {
		p = t;
		t = (key < t->key) ? t->left : t->right;
	}

	if (t == NULL) {
		printf("Key is not in the tree");
		return;
	}

	//단말 노드인 경우
	if ((t->left == NULL) && (t->right == NULL)) {
		if (p != NULL) {
			if (p->left == t) p->left = NULL;
			else p->right = NULL;
		}
		else {
			*root = NULL;
		}
	}
	//하나의 자식만 가지는 경우
	else if ((t->left == NULL) || (t->right == NULL)) {
		TreeNode* child = (t->left != NULL ? t->left : t->right);
		if (p != NULL) {
			if (p->left == NULL) p->left = child;
			else p->right = child;
		}
		else {
			*root = child;
		}
	}
	//두 개의 자식을 가지는 경우
	else {
		TreeNode* delete_p = t;
		TreeNode* delete = t->right;

		while (delete->left != NULL) {
			delete_p = delete;
			delete = delete->left;
		}

		if (delete_p->left == delete) delete_p->left = delete->right;
		else delete_p->right = delete->right;

		t->key = delete->key;
		t = delete;
	}
	free(t);
}

 

 교재에 있는 코드랑 좀 다른 거 같아서 가져와따. 일단 이진탐색트리에서 노드를 삭제하는 경우는 3가지인데, 

 

1. 자식이 없는 경우

2. 자식이 하나 있는 경우

3. 자식이 두 개 있는 경우

 

 

#삭제할 key값 탐색

 일단 이게 초기 메모리 상태라고 가정하고, 삭제할 노드를 찾아야 한다. 

 

 

 t가 NULL이 아니고 t가 key값이 아닐 때까지 t->key의 크기에 따라 키값이 t->key값보다 작으면 왼쪽, 크면 오른쪽으로 간다. 

 

-while 1회전

-while 2회전

 여기서 key값과 t->key값이 동일 하므로 while문을 종료한다.

 

그리고 만약 현재 t는 NULL이 아니지만 저 마지막 노드까지 key값이 없으면 while문이 한번 더 돌아가서 t가 NULL이 된다. 이 때는 더 이상 노드가 없으므로 트리 안에 key값이 없다는 말이 된다. 

 

 

#자식이 없는 경우

 

(단말 노드란 자식이 하나도 없는 노드를 의미한다. )

 

 이 때 p가 NULL이 아닐 것을 검사하는 이유는, p의 초깃값이 NULL이고, t의 초깃값이 root이기 때문....!! 그니까, p가 NULL이라는 의미는 key값이 root 노드에 있다는 말이다. 

 

 아무튼 현재 key값은 root 노드에 없기 때문에 if문 실행! 삭제하는 방법은 매우 간단하다. 삭제할 노드가 t라면 t의 부모노드가 p이니까. t가 p의 왼쪽에 있는지, 오른쪽에 있는지 확인한 뒤 NULL로 바꿔주면 된다. 

 

 

 요러케!!!

 

 

 

#자식이 하나 있는 경우

 이번에는 key값이 3이라고 해보자. 현재 key값이 3인 노드는 n3로 자식 노드가 한 개 잇는 상태이다.

 

 child 포인터를 하나 선언하고 현재 삭제할 노드는 자식이 하나 있는 노드이기 때문에, 왼쪽과 오른쪽 중에 자식이 있는 노드가 어딘지 검사한 다음 child에 저장한다. 

 

 

 요러케. 그리고 요기선 t가 아니라 p의 노드를 바꿔서 t노드를 삭제한다. 일단 마찬가지로 t의 위치가 p의 왼쪽에 있는지 오른쪽에 있는지 확인한다.

 

 지금은 p의 왼쪽에 t가 있으므로 p->left를 child로 바꿔준다. 

 

 

 

#자식이 두 개 있는 경우

 

  여기서 delete_p는 삭제할 노드의 부모 노드이다. 

 

 이게 초기 상태이고, while문을 사용해서 후계자를 찾는다. 

 

-while 1회전

 

 

 자 이제 노드를 삭제 해보자. 자 여기서도 삭제할 노드가 왼쪽에 있는지, 오른쪽에 있는지 확인하고 delete->right 즉 NULL 값을 넣어준다. 

 

 

 

 

 즉 자식이 두 개 일때는 해당 노드를 삭제할 것이 아니라. 해당 노드와 key값이 가장 유사한 노드를 찾아 그 노드의 key값과 삭제할 노드의 key값을 변경하는 것이다.