[TIL] 21-08-10

TreeNode  *search(TreeNode  *node,  int  key)
{
      if ( node == NULL )  return NULL;
      if ( key == node->key ) return node;
      else if ( key < node->key )
            return  search(node->left, key);  
      else
            return  search(node->right, key);
}

TreeNode * new_node(int item)  {
	TreeNode * temp = (TreeNode *)malloc(sizeof(TreeNode));
	temp->key = item;
	temp->left = temp->right = NULL;
	return temp;
}
TreeNode * insert_node(TreeNode * node, int key){
	//탐색 실패한 경우 삽입할 데이터를 가진 새로운 노드 추가
	if (node == NULL) return new_node(key);
	if (key < node->key)
		node->left = insert_node(node->left, key);
	else if (key > node->key)
		node->right = insert_node(node->right, key);
	//변경된 노드의 포인터 반환 
	return node;
}

TreeNode * min_value_node(TreeNode * node)
{
	TreeNode * current = node;
	// 최솟값을 가진 노드 = 맨 왼쪽 단말 노드
	while (current->left != NULL)
		current = current->left;
	return current;
}

// key 노드 삭제 후 루트 반환
TreeNode * delete_node(TreeNode * root, int key)  { 
	if (root == NULL) return root;
    	// 키가 루트보다 작으면 왼쪽 서브 트리에 있음
	if (key < root->key) 			
		root->left = delete_node(root->left, key);
    	// 키가 루트보다 크면 오른쪽 서브 트리에 있음
	else if (key > root->key) 		
		root->right = delete_node(root->right, key);
    	// 키가 루트와 같으면 이 노드를 삭제함
	else {				
    		//삭제할 노드가 오른쪽 서브트리만 가지고 있는 경우
            	//혹은 삭제할 노드가 단말 노드인 경우
		if (root->left == NULL) {	
			TreeNode * temp = root->right;
			free(root);
			return temp;
		}
    		//삭제할 노드가 왼쪽 서브트리만 가지고 있는 경우
            	//혹은 삭제할 노드가 단말 노드인 경우
		else if (root->right == NULL) {	
			TreeNode * temp = root->left;
			free(root);
			return temp;
		}
        	// 삭제할 노드가 두 개의 서브트리를 가지고 있는 경우
            	// 삭제할 노드의 우측 서브트리에서의 최솟값 = 삭제할 노드의 직후 노드
		TreeNode * temp = min_value_node(root->right); 		
		root->key = temp->key; 				
		root->right = delete_node(root->right, temp->key); 	
	}
	return root;
}