[자료구조] 이진 탐색 트리의 삽입,삭제 (재귀함수)

노드

typedef struct TreeNode
{
	int key;
	TreeNode* left, * right;
}TreeNode;

노드의 삭제

삭제에 필요한 함수

TreeNode* min_value_node(TreeNode* node)
{
	TreeNode* current = node;
	while (current->left != NULL)
	{
		current = current->left;
	}
	return current;
}

node의 가장 왼쪽에 있는 노드를 찾아 반환해줌

 

삭제 함수

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 // 원하는 key를 가진 노드를 찾았을때
	{
		if (root->left == NULL) // 자식이 없거나 왼쪽 자식이 비었고 오른쪽 자식만 존재
		{
			// 자식을 반환해주고 root는 삭제 -> 반환된 노드로 갱신될 것임. (ex1)
			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;
}

 

노드 링크의 갱신은 삭제할 노드 root의 부모에서

root->left = delete_node(root->left,key);를 불렀으니

delete_node(root->left,key)로 반환되는 포인터는 root의 right 노드이다. (아래의 코드에 의해서)

if (root->left == NULL) // 자식이 없거나 왼쪽 자식이 비었고 오른쪽 자식만 존재
{
	// 자식을 반환해주고 root는 삭제 -> 반환된 노드로 갱신될 것임. (ex1)
	TreeNode* temp = root->right;
	free(root);
	return temp;
}

 

 

만약 삭제할 노드가 두개의 서브트리를 가졌다면 아래의 코드를 실행한다.

// 왼쪽과 오른쪽 서브트리가 달려있을때
// 오른쪽 서브트리에서 제일 작은 값으로 교체해주자
TreeNode* temp = min_value_node(root->right); // 교체할 노드 탐색
root->key = temp->key; //교체
root->right = delete_node(root->right, temp->key); // 교체한 노드를 찾아 삭제(재귀)

교체해주고 또 재귀적으로 다시 삭제한 노드에 들어간 노드(key)를 찾아 삭제시켜준다.

 

노드의 삽입

노드의 생성 함수

TreeNode* new_node(int item)
{
	TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
	newNode->key = item;
	newNode->left = newNode->right = NULL;
	return newNode;
}

노드를 생성해 노드의 포인터를 반환한다.

 

삽입 함수

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