이진 탐색 트리

이진 탐색 트리의 정의

1. 모든 원소는 유일한 키를 가짐
2. 왼쪽 서브 트리의 키들은 루트 키보다 작음
3. 오른쪽 서브 트리의 키들은 루트 키보다 큼
4. 왼쪽과 오른쪽 서브 트리 또한 이진 탐색 트리

 

- 찾아야 하는 값과 루트 노드의 값을 비교하여 탐색을 효율적으로 수행할 수 있음

- 이진 탐색 트리에서 탐색을 구현하는 방법으로는 순환적인 방법과 반복적인 방법 2가지가 존재

---

순환적인 탐색 연산

- 특정한 키 값을 가진 노드를 찾기 위해 주어진 값과 루트 노드의 키 값을 비교

- 이 결과는 아래의 3가지로 나뉨

• 주어진 키 값과 루트 노드의 키 값이 같을 경우: 탐색 종료
• 주어진 키 값이 루트 노드의 키 값보다 작을 경우: 루트 노드의 왼쪽 서브 트리에 대해 다시 탐색
• 주어진 키 값이 루트 노드의 키 값보다 클 경우: 루트 노드의 오른쪽 서브 트리에 대해 다시 탐색

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

- 매개변수 node가 NULL이 아니면 계속 반복

- node의 키 값이 key와 같으면 탐색 성공이므로 현재 노드 포인터를 반환하고 종료

- node의 키 값이 key보다 작으면 node 변수를 node의 왼쪽 자식을 가리키도록 변경

- node의 키 값이 key보다 크면 node 변수를 node의 오른쪽 자식을 가리키도록 변경

- node가 단말 노드까지 내려가 NULL이 될 때까지 위 반복을 계속

- 반복이 종료되었음에도 함수가 리턴되지 않았다면 실패한 탐색이므로 NULL 반환

---

이진 탐색 트리에서 삽입 연산

- 이진 탐색 트리에서는 같은 키 값을 가지는 노드가 없어야 함

- 이진 탐색 트리에 원소를 삽입하기 이전에 탐색 수행이 필수

- 탐색에 실패한 위치가 새로운 노드를 삽입하는 위치가 됨

9를 삽입하는 예

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* new_node(int item) {
	TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
	temp->key = item;
	temp->left = temp->right = NULL;

	return temp;
}

---

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

- 삽입 연산과 마찬가지로 삭제 전 탐색 수행 필수

- 삭제하려는 노드의 특징에 따라 3가지 케이스 존재

1. 삭제하려는 노드가 단말 노드일 경우
2. 삭제하려는 노드가 왼쪽 또는 오른쪽 서브 트리 중 하나만 가지고 있는 경우
3. 삭제하려는 노드가 두 개의 서브 트리를 모두 가지고 있는 경우

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

- 아래에 더 이상의 노드가 없으므로 단말 노드만 삭제하면 됨

- 단말 노드의 부모 노드를 찾아 부모 노드의 링크 필드를 NULL로 변경

- 노드를 동적으로 생성하였다면 단말 노드를 동적 메모리 해제

 

2. 삭제하려는 노드가 하나의 서브 트리만 가지고 있는 경우

- 노드를 삭제하고, 서브 트리는 삭제한 노드의 부모 노드에 연결

 

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

- 삭제되는 노드와 값이 가장 비슷한 노드를 부모 노드와 연결

- 왼쪽 서브 트리에서 가장 큰 값 또는 오른쪽 서브 트리에서 가장 작은 값이 삭제되는 노드와 가장 근접(둘 중 어느 것을 선택하여도 무방)

- 왼쪽 서브 트리에서 오른쪽 자식 링크를 타고/오른쪽 서브 트리에서 왼쪽 자식 링크를 타고 NULL을 만날 때까지 진행하면 찾을 수 있음

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

---

 

이진 탐색 트리의 분석

- 트리의 높이가 h일 때, 탐색, 삽입, 삭제 연산의 시간 복잡도는 O(h)

- n개의 노드를 가지는 이진 탐색 트리의 경우 일반적인 높이는 log₂n이므로

- 좌우의 서브 트리가 균형을 이루는 경우, 이진 탐색 트리 연산의 평균적인 시간 복잡도는 O(log₂h)

 

- 최악의 경우에는 한쪽으로 치우치는 경사 트리가 되어 시간 복잡도가 거의 O(n)

- 선형 탐색에 비해 시간적으로 이득 없음

- 이러한 최악의 경우를 방지하기 위해 트리의 높이를 log₂n으로 한정시키는 균형 기법 필요

---

전체 프로그램

#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* new_node(int item) {
	TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
	temp->key = item;
	temp->left = temp->right = NULL;

	return temp;
}

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

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

	return current;
}

//삽입
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* 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, 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");
	}
	return 0;
}

>>