[자료구조] - 이진 탐색 트리 /탐색/삽입/삭제/응용

이진 탐색 트리 : 이진 트리 기반의 탐색을 위한 자료 구조

• 정의
  • 모든 원소의 키는 유일한 키를 가진다.
  • 왼쪽 서브 트리 키들은 루트 키보다 작다.
  • 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
  • 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

순차적인 탐색 연산

• 비교한 결과가 같으면 탐색이 성공적으로 끝난다.
• 비교한 결과가, 주어진 키 값이 루트 노드의 키값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작한다.
• 비교한 결과가, 주어진 키 값이 루트 노드의 키값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다.

순환적인 탐색노드

// 순환적인 탐색 함수
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 * 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;  // 탐색에 실패하였을 경우 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;
}

이진 탐색 트리에서 삭제 연산

1. 삭제하려는 노드가 단말 노드일 경우

단말 노드의 부모노드를 찾아서 부모노드안의 링크필드를 NULL로 만들어서 연결을 끊으면 된다.

2. 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우

자기 노드는 삭제하고 서브트리는 자기 노드의 부모 노드에 붙여주면 된다.

3. 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우

삭제되는 노드와 가장 값이 비슷한 노드를 후계자로 선택하여야 한다.
그래야만 다른 노드를 이동시키지 않아도 이진 탐색 트리가 그대로 유지된다. 그렇다면 가장 비슷한 노드는 누구일까? 바로 왼쪽 서브트리에서 제일 큰 값 or 오른쪽 서브트리에서 제일 작은 값이다.

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

전체 프로그램

#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* 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; // 탐색에 실패하였을 경우 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;

	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);
	root = insert_node(root, 30);

	printf("이진 탐색 트리 중위 순회 결과 \n");
	inorder(root);
	printf("\n\n");
	if (search(root, 30) != NULL)
		printf("이진 탐색 트리에서 30을 발견함 \n");
	else
		printf("이진 탐색 트리에서 30을 발견못함 \n");
	return 0;
}

이진 탐색 트리의 분석

트리의 높이가 h라고 했을 때 탐색, 삽입, 삭제 연산의 시간 복잡도는 O(h)이다.
따라서 n개의 노드를 가지는 이진 탐색 트리의 경우 이진 트리의 높이는 일반적으로 upper(log2n)이므로 O(log2n)이다. 그러나 최악의 경우 한쪽으로만 치우치는 경사 트리가 되어서 트리의 높이가 n이된다. 이 경우에는 O(n)이된다.

이진 탐색 트리의 응용 : 영어 사전

// 이진 탐색 트리를 사용한 영어 사전
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>

#define MAX_WORD_SIZE	 100
#define MAX_MEANING_SIZE 200

// 데이터 형식
typedef struct 
{
	char word[MAX_WORD_SIZE];		// 키필드
	char meaning[MAX_MEANING_SIZE];
}element;
// 노드의 구조
typedef struct TreeNode 
{
	element key;
	struct TreeNode *left, *right;
} TreeNode;

// 만약 e1 < e2 이면 -1 반환
// 만약 e1 == e2 이면 0 반환
// 만약 e1 > e2 이면 1 반환
int compare(element e1, element e2)
{
	return strcmp(e1.word, e2.word);
}
// 이진 탐색 트리 출력 함수
void display(TreeNode * p)
{
	if (p != NULL)		// 중위 순회 출력
	{
		display(p->left);
		printf("%s:%s\n", p->key.word, p->key.meaning);
		display(p->right);
	}
}
// 이진 탐색 트리 탐색 함수
TreeNode * search(TreeNode * root, element key)
{
	TreeNode * p = root;
	while (p != NULL) {
		if (compare(key, p->key) == 0)
			return p;
		else if (compare(key, p->key) < 0)
			p = p->left;
		else if (compare(key, p->key) > 0)
			p = p->right;
	}
	return p; 	// 탐색에 실패했을 경우 NULL 반환
}
TreeNode * new_node(element item)
{
	TreeNode * temp = (TreeNode *)malloc(sizeof(TreeNode));
	temp->key = item;
	temp->left = temp->right = NULL;
	return temp;
}
TreeNode * insert_node(TreeNode * node, element key)
{
	// 트리가 공백이면 새로운 노드를 반환한다. 
	if (node == NULL) return new_node(key);

	// 그렇지 않으면 순환적으로 트리를 내려간다. 
	if (compare(key, node->key)<0)
		node->left = insert_node(node->left, key);
	else if (compare(key, node->key)>0)
		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, element key)
{
	if (root == NULL) return root;

	// 만약 키가 루트보다 작으면 왼쪽 서브 트리에 있는 것임
	if (compare(key, root->key)<0)
		root->left = delete_node(root->left, key);
	// 만약 키가 루트보다 크면 오른쪽 서브 트리에 있는 것임
	if (compare(key, root->key)>0)
		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 help()
{
	printf("\n**** i: 입력, d: 삭제, s: 탐색, p: 출력, q: 종료 ****: ");
}
// 이진 탐색 트리를 사용하는 영어 사전 프로그램 
int main(void)
{
	char command;
	element e;
	TreeNode * root = NULL;
	TreeNode * tmp;

	do {
		help();
		command = getchar();
		getchar();		// 엔터키 제거
		switch (command) {
		case 'i':
			printf("단어:");
			gets(e.word);
			printf("의미:");
			gets(e.meaning);
			root = insert_node(root, e);
			break;
		case 'd':
			printf("단어:");
			gets(e.word);
			root=delete_node(root, e);
			break;
		case 'p':
			display(root);
			printf("\n");
			break;
		case 's':
			printf("단어:");
			gets(e.word);
			tmp = search(root, e);
			if (tmp != NULL)
				printf("의미:%s\n", tmp->key.meaning);
			break;
		}

	} while (command != 'q');
	return 0;
}

그 외

책에서 연습 문제로 작성해본 추가 함수가 있다.

// 균형 트리 확인 함수

void isBalanced(TreeNode* node) {

	int left_height;
	int right_heght;

	left_height = get_height(node->left);
	right_heght = get_height(node->right);

	if (left_height - right_heght == 1 || left_height - right_heght == -1) {
		printf("균형 트리입니다.\n\n");
	}
	else printf("균형 트리가 아닙니다.\n\n");
}

// 노드의 합 구하기 함수

int get_node_sum(TreeNode* node) // 전체노드의 수
{

	int left_size, right_size;
	if (node == NULL) return 0;

	left_size = get_node_sum(node->left);
	right_size = get_node_sum(node->right);
	return (node->key + left_size + right_size);
}

// 노드가 가지는 값 중 찾는 값보다 작은 값 출력

void search_small_than_key(TreeNode * node, int key)
{
	if (node == NULL) return NULL;
	if (key > node->key) {
		printf("%d보다 작은 노드: %d\n", key, node->key);
		search_small_than_key(node->left, key);
		search_small_than_key(node->right, key);
	}
	else if (key <= node->key)
		return search_small_than_key(node->left, key);
}

// 이진 트리에서 자식이 하나만 있는 노드의 개수를 반환하는 함수

int find_leftorright(TreeNode* root) {
	if (root == NULL)
		return 0;
	int count = 0;
	if ((root->left == NULL && root->right != NULL) || (root->left != NULL && root->right == NULL))
		count++;
	count = count + find_leftorright(root->left) + find_leftorright(root->right);
	return count;
}

//이진 트리에서 최소값, 최대값 찾기

#define MAX 987654321
#define MIN -987654321

int Max(int a, int b) {
	if (a < b)
		return b;
	return a;
}

int Min(int a, int b) {
	if (a < b)
		return a;
	return b;
}

int search_min_key(TreeNode* root) {
	if (root == NULL) return MAX;
	int min = root->key;
	min = Min(min, search_min_key(root->left));
	min = Min(min, search_min_key(root->right));
	return min;
}

int search_max_key(TreeNode* root) {
	if (root == NULL) return MIN;
	int min = root->key;
	min = Max(min, search_max_key(root->left));
	min = Max(min, search_max_key(root->right));
	return min;
}

이진 탐색 트리를 중위 순회하면 data를 내림차순으로 정렬 할 수 있다.
그렇다면 오른쪽 노드부터 찾는다면 data를 오름차순으로 정렬 할 수 있다.

// 중위 순회 - 내림차순

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