[Trees] Binary Tree Deletion 이해

이 노드 삭제구조 를 이해하는데 3일이 걸렸다.. 드디어 오늘 코드 작동 순서를 이해했는데 와 ART 그자체. 어떻게 이런 구조와 순서를 생각해냈지 대단할뿐. 왜 직접적으로 사용이안될수있지만 Data structure를 반드시 탄탄하게 공부하라는 이유를 알것같다.  

음... 코드로 어떤 형상을 머리로 그려내는것은 정말 어려운일. 그림의 순서도로 코드 전체를 쉽게 한번에 이해할 수 있는 툴은 없을까. Ex) 코드가 한줄 한줄 넘어갈때마다 매치하면서 그 코드가 표현해내는 데이터 구조모형을 나타낸다면 정말 쉬워질텐데 임펙트 있게 정리할 방도가 마땅히 떠오르지않는다.  한줄 한줄 쓴다면 정리시간이 배로 걸릴것이고 흠. 매치해주는 툴이 있다면 좋을듯.

 

 

---

Node* deletion(struct Node* root, int key){

	if(root == NULL){ // 처음 ROOT에 아무것도없다면 널 반환하기, prevention of exm
		return NULL;
	}

	if(root->left == NULL && root -> right == NULL){ // 하나의 루트노드만 있는경우
		if(root->key == key){ // 초기 값이 제거하고자하는값이라면? 

		       return NULL;
		}
		else{
	 		return root;
		}		
	}

	queue <Node*> q; //이거 타입 숙지 하기
	q.push(root); // 초기 노드를 큐에 밀어넣는다. 

	Node* temp; //deepest node를 가르키게된다. 
	Node* last; //deepest node의 parent node를 저장하면서 끝맺음 할때 사용
	Node* key_node = NULL;

	//DO level order traversal to find deepest
	
	while(!q.empty()){ //큐가 엠티가 될떄까지 계속 돈다 ,큐로 노드 좌우를 확인하네 !
		temp = q.front(); // temp은 마지막에 결국 deepest node를 저장한다!
		q.pop(); // level order 로 같은층 순서로 저장된다는 order traveral !wow

		if(temp -> key == key)
			key_node = temp;
		if(temp -> left){
			last = temp; // temp의  parent 를 저장하게 된다! 
			q.push(temp->left); 
		}
		if(temp -> right){
			last = temp;
			q.push(temp->right);
		}
	}

	if(key_node != NULL){ //전체적인 목적 : deepest node를 끝맺음 해준다. 
		
		key_node -> key = temp->key; //deepest node의 key를 제거한 노드에 치환

		if(last ->right == temp) //끌어온 deepest node를 가르키는 포인터를 널로 바꿈
			last ->right = NULL; 
		else
			last->left = NULL;
		delete (temp); // obj not allocated 즉 해제

	} // deletion.. 복잡하지만 이해완료.. beauty네 
	
	return root;
}

  

기억해야할 KICK

* 삭제노드가 삭제되는 이미지가 아니라 삭제 노드에 Deepest node(가장 깊은 노드) 값이 씌워지는것이다.

• 전체를 순환해주는 Level order traverse시 queue<Node*>를 이용해서 하나하나 제거할 노드값 위치를 찾는다.
• 순환시 deepest 노드를 찾아 제거할 노드의 값과 바꿔줄 준비를한다.
• 제거할 노드의 값들을 deepest node 바꾸고 이 노드는 끝맺음으로 NULL 포인터로 처리된다.