C언어 이진 탐색 트리 BST 구현하기

이진탐색트리 Binary Search Tree

이진 탐색 트리는 효율적인 탐색을 위한 트리이다.
부모의 왼쪽노드 있는 값은 부모보다 값이 작아야하며 오른쪽 노드에 있는 값은 부모보다 값이 크도록 한다.

이진탐색트리 binary search tree 를 구현하기 위한 구조체는 다음과 같다.
두 자식노드를 가리킬 수 있도록 left와 right가 있다.

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

필요한 함수

1. search
2. new_node
3. insert_node
4. min_value_node
5. delete_node
6. inorder 탐색

함수 설명

1) search

특정 key 값을 가진 노드를 찾기위한 함수다.

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

노드가 없으면 NULL 반환
key가 노드에 있으면 노드 반환
key가 노드의 key보다 작으면 노드left 호출(return)
key가 노드의 key보다 크면 노드right 호출(return)

2) new_node

노드를 삽입하려고 할 때 해당 노드가 NULL일 때 만들도록 하는 함수

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

노드에 메모리를 할당받고 key값을 정의해준 다음 left와 right를 NULL로 만들어 준다.
그리고 만든 노드를 반환한다.(return)

3) insert_node

새로운 노드를 추가하는 함수다.

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

노드가 NULL이라면 new_node 함수를 실행한다(return).
인자가 현재 노드의 key값보다 작으면 insert_node에 노드의 left를 넣어 호출한다.
인자가 현재 노드의 key값보다 크면 insert_node에 노드의 right를 넣어 호출한다. 
그리고 노드를 반환한다(return).

4) min_value_node

인자로 받은 노드의 key값과 가장 가까운 key값을 가진 노드를 찾는 함수이다.
함수에서는 노드의 가장 왼쪽아래 자식 노드를 찾아나가며 노드를 찾는다.

해당 함수의 존재 이유는 delete_node 함수에서 사용하기 위함이다. 특정 노드를 제거했을 때 자식노드가 양쪽 모두 존재한다면 가장 가까운 key값을 가진 노드로 교체해야한다. 때문에 실제로 더 좋은 이진탐색 트리를 만들기 위해서는 오른쪽도 찾고 key 값을 비교하여 더 가까운 값을 찾는 것이 좋다. 아래 코드에서는 편의를 위해 문제가 되지 않기에 left로만 가도록 했다.

TreeNode * min_value_node(TreeNode * node)
{
	TreeNode * current = node;

	while (current->left != NULL)
		current = current->left;

	return current;
}

5) delete_node

개념:

• 찾으려는 값이 key 값보다 작으면 왼쪽, 크면 오른쪽으로 가서 다시 함수 호출
• 값이 있으면 left, right에 노드가 있는지에 따라 다름
  • 한쪽에만 노드가 있으면 노드를 없애고 자식노드를 이어주기만 하면 됨
  • 양쪽 다 노드가 있으면 min_value_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 {
		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;
}

key 값을 찾지 못했을 때는 왼쪽 혹은 오른쪽 노드로 내려가면서 찾는다.
인자가 현재 노드의 key값보다 작으면 delete_node에 노드의 left를 넣어 호출한다.
인자가 현재 노드의 key값보다 크면 delete_node에 노드의 right를 넣어 호출한다. 
key값을 찾은 else문부터 보자면 먼저 if문으로 left에 값이 없는지 확인한다. 값이 없다면 right를 temp에 저장하고 free(root) 한다. 즉 노드를 없앤 것이다. 그리고 temp를 반환하는데 재귀를 통해 내려온 것이라면 바로 위의 root->right = delete_node(root->right, key); 처럼 반환된 값이 저장되어 연결된다.(left를 인자로 호출한 경우도 마찬가지)
if문에서 left에 값이 있고 else if 문에서 right에 값이 없어도 마찬가지 원리다.

둘 다 값이 있을 때가 복잡한데 TreeNode *temp = min_value_node(root->right); 부분으로 넘어간다. 이유는 left 자식노드나 right 자식노드를 위처럼 연결해줄 수 없기에 값을 대체할 노드를 하나 찾아와야 한다.
없앨 노드의 key와 가장 비슷한 key를 가진 노드로 대체해야하기 때문에 min_value_node 함수를 사용하며 아래 코드로 대체됨을 볼 수 있다.

6) inorder 탐색

이진탐색트리에서 굳이 필요하진 않은 함수이다.
inorder 방법으로 탐색을 구현했다. 

void inorder(TreeNode * root){
	if (root) {
		inorder(root->left);
		printf("[%d] ", root->key);  
		inorder(root->right);
	}
}

main 함수

int main()
{

	TreeNode * root = NULL;
	TreeNode * tmp = NULL;

	root = insert_node(root, 30);
	root = insert_node(root, 20);
	root = insert_node(root, 10);
	root = insert_node(root, 40);
	root = insert_node(root, 50);
	root = insert_node(root, 60);

	printf("In-order traversal in Binary Search Tree\n");
	inorder(root);
	printf("\n\n");

	if (search(root, 30) != NULL)
		printf("Find 30 in the BST \n");
	else
		printf("No 30 in the BST \n");
		
	return 0;
}