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

이진탐색트리

이진탐색트리 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;
}