이진 탐색 트리

이진 탐색 트리는 모든 원소가 유일한 키를 갖으며, 왼쪽 서브 트리의 키들은 모두 루트 키보다 작고, 오른쪽 서브 트리의 키들은 모두 루트의 키보다 큰 트리를 말한다.

위 그림처럼 루트 노드의 키값 22를 기준으로 왼쪽 서브 트리의 키값은 15로 22보다 작고, 오른쪽 서브 트리의 키값은 45로 22보다 크다. 이 형태가 계속해서 반복되므로 왼쪽과 오른쪽 서브 트리는 모두 이진 탐색 트리 형태이다.

이진 탐색 트리를 중위 순회 방식으로 순회하면 어느 정도 정렬된 상태를 유지하고 있음을 알 수 있다.

5→7→10→15→16→18→19→20→22→36→45>60

구현

순환적인 탐색 연산

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인 경우에는 마지막 노드까지 도달한 것이므로 NULL을 반환한다.

찾고자 하는 키값이 해당 노드의 키값보다 작으면 왼쪽으로 이동하고, 크면 오른쪽으로 이동한다. 만약 찾고자 하는 키값을 가진 노드를 발견하면 해당 노드를 반환한다.

반복적인 탐색 연산

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

삽입 연산

이진 탐색 트리에서 원소를 삽입하기 위한 순서는 다음과 같다.

1. 같은 키값을 갖는 노드가 있는지 탐색
2. 중복된 노드가 없다면, 단말 노드의 하위 노드로 추가

구현

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

insert_node 함수는 맨 처음 NULL값을 가진 루트 포인터가 들어온다.

삭제 연산

먼저 삭제하고자 하는 키값이 있는지 탐색하고, 아래의 3가지 경우를 고려하여 삭제한다.

1. 노드가 단말 노드일 경우

단말 노드인 경우에는 자식 노드가 없으므로 부모 노드를 찾아 NULL을 삽입하여 연결을 끊고, 단말 노드를 메모리 해제 해주면 된다.

2. 노드가 서브 트리중 하나만 가지고 있는 경우

이 경우에는 삭제하는 노드의 부모 노드와 자식 노드를 연결하고, 삭제 노드를 메모리 해주면 된다.

3. 노드가 두개의 서브 트리를 모두 가지고 있는 경우

이 경우에는 삭제된 노드를 현재 존재하는 노드 중 어떤 것을 갖고 올 것인지 고민해야 한다.

18을 삭제하려고 하면, 18의 자식 노드들 중 가장 가까운 수는 12와 22이이다. 즉, 왼쪽 서브 트리의 가장 오른쪽에 있는 노드 혹은 오른쪽 서브 트리 중 가장 왼쪽에 있는 노드이다.

둘 중 어느 것을 갖고 와도 상관없지만 여기서는 오른쪽 서브트리의 가장 작은 값으로 대체하고자 한다.

구현

// 이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고 
// 새로운 루트 노드를 반환한다. 
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;
}

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

	// 맨 왼쪽 단말 노드를 찾으러 내려감
	while (current->left != NULL)
		current = current->left;

	return current;
}

여기서 핵심은 삭제 노드를 오른쪽 서브 트리의 가장 작은 값으로 대체할 때, 삭제할 노드를 실제로 소멸시키는 것이 아니라 값만 대체해 주고, 실제로는 오른쪽 서브 트리의 가장 작은 값만 소멸시키는 것이 핵심이다.

전체 코드

#include <stdio.h>
#include <stdlib.h>

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

// 순환적인 탐색 함수
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* iterating_search(TreeNode* node, int key) {
	while (node != NULL) {
		if (key == node->key)
			return node;
		else if (key < node->key)
			node = node->left;
		else
			node = node->right;
	}
	return NULL;
}
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;
}
// 이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고 
// 새로운 루트 노드를 반환한다. 
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;
}

// 중위 순회
void inorder(TreeNode * root) {
	if (root) {
		inorder(root->left);// 왼쪽서브트리 순회
		printf("[%d] ", root->key);  // 노드 방문
		inorder(root->right);// 오른쪽서브트리 순회
	}
}

int main(void)
{
	TreeNode * root = NULL;
	TreeNode * tmp = NULL;

	/*
		   40
	   20	   50
    10	 30      60
	*/
	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("이진 탐색 트리 중위 순회 결과 \n");
	inorder(root);
	printf("\n\n");
	if (search(root, 30) != NULL)
		printf("이진 탐색 트리에서 30을 발견함 \n");
	else
		printf("이진 탐색 트리에서 30을 발견못함 \n");

	root = delete_node(root, 20);
	printf("%d 삭제\n", root->key);
	inorder(root);
	return 0;
}

이진 탐색 트리의 분석

이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이를 h라고 했을 때 O(h)인데, 일반적으로 이진 트리의 높이는 $log_2n$이므로 시간 복잡도는 $O(log_2n)$이 된다.

그러나 최악의 경우에는 한쪽으로 치우치는 경사 트리가 되어서 트리의 높이가 n이 된다. 이 경우에 시간 복잡도는 O(n)이 된다.

이런 최악의 경우는 선형 탐색에 비하여 시간적으로 이득이 없기 때문에 이를 방지하기 위해 트리를 균형 있게 만드는 AVL트리를 비롯한 여러 기법들이 개발되었다.

출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구
https://dream-and-develop.tistory.com/146