[C] 트리 : 이진 탐색 트리

binary search tree

이진 탐색 트리

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

 

이진 탐색 트리의 정의는 다음과 같다.

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

쉽게 말하자면

루트를 기준으로 작은 수는 왼쪽 노드에,

큰 수는 오른쪽 노드에 붙이면 된다.

---

18  26  7  12  3  31  27 이 랜덤하게 주어졌다고 하자.

 

그럼 우선 첫 번째 주어진 18을 루트로 잡는다.

그리고 두 번째 주어진 26은 18보다 크므로 오른쪽 자식노드로,

세 번째 주어진 7은 18보다 작으므로 왼쪽 자식노드로 넘긴다

 

18 26 7

 

그리고 네 번째 주어진 12는 18보다 작으므로 왼쪽 자식노드에,

왼쪽 자식노드인 7보다 크므로 7의 오른쪽 자식노드에 붙여준다.

 

다섯 번째 주어진 3도 마찬가지로 7과 비교하게 되는데,

7보다 작으므로 7의 왼쪽 자식노드에 붙여준다.

18 26 7 12 3 

 

여섯 번째 주어진 31은 18보다 크므로 오른쪽으로,

26보다 크므로 26의 오른쪽 자식노드에 붙여준다.

 

마지막 27은 18보다 크므로 오른쪽,

26보다 크므로 오른쪽,

31보다 작으니까 31의 왼쪽 자식노드에 붙여준다

18 26 7 12 3 31 27

위의 트리는 이진 탐색 트리가 된다.

---

그렇다면 이진 탐색 트리의

탐색, 삽입, 삭제 코드를 구현해보자!

 

그런데 이진 탐색 트리의 삭제는

복잡하니 정리를 먼저 해보자

(탐색, 삽입은 주석 참고)

 

삭제를 위해 고려해야 하는 것은 3가지가 있다

• 삭제하려는 노드가 단말 노드일 경우 = 이 경우에는 단순히 단말 노드만 지우면 된다.

• 삭제하려는 노드가 하나의 서브트리만 가질 경우 = 단말 노드를 지우고, 그 자리에 서브 트리를 올려주면 된다.

• 삭제하려는 노드가 두개의 서브트리를 가질 경우 = 가장 복잡한 부분!!

 

세 번째의 경우를 고려해보자

 

예시 트리

이러한 트리가 있다고 할 때

18 노드를 지우려고 해보자

 

그런데 자식 노드인 7이나 26을

18자리에 올리면 문제가 생긴다.

이진 탐색 트리가 성립이 안됨..

 

이진 탐색 트리를 유지하기 위해서

삭제하려는 노드(18)과 가장 가까운 숫자를 찾아야 한다.

 

가장 가까운 숫자는 12와 22인데,

12는 왼쪽 서브트리의 가장 오른쪽에 위치한 노드이고

22는 오른쪽 서브트리의 가장 왼쪽에 위치한 노드이다.

 

이 둘중 하나의 노드를, 삭제할 18이 있는 위치에 올려주면

18은 삭제되고, 이진 탐색 트리는 유지가 된다.

올리는 노드는 12나 22, 어느 것이어도 상관이 없다

 

아래 프로그램에서는 오른쪽 서브트리의

가장 왼쪽에 위치한 노드를 올리도록 하겠다

(위의 트리에서 18을 지운다고 하면 22를 올리게 되는 것임)

 

이를 토대로 삭제 함수를 만들 수 있다.

---

이진 탐색 트리 전체 프로그램

 

해당 트리를 가지고 테스트 해보겠다

예시 트리

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

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

//순환을 이용한 탐색
TreeNode* search1(TreeNode* node, int key) {
	//트리가 비어있을 경우
	if (node == NULL)
		return NULL;

	//찾는 값이(key) 해당 노드의 값(node->key)과 일치할 때
	if (key == node->key)
		return node;

	//찾는 값이 해당 노드의 값보다 작으면 왼쪽 노드 탐색
	else if (key < node->key)
		return search1(node->left, key);

	//찾는 값이 해당 노드의 값보다 크면 오른쪽 노드 탐색
	else
		return search1(node->right, key);
}

//반복을 이용한 탐색
//더 쉽고 효율성이 높음
TreeNode* search2(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(element item) {
	TreeNode* tmp = (TreeNode*)malloc(sizeof(TreeNode));
	tmp->key = item;
	tmp->left = NULL;
	tmp->right = NULL;
	return tmp;
}

//새로운 노드 삽입
TreeNode* insert_node(TreeNode* root, element key) {
	if (root == NULL) return new_node(key); //구조체 타입의 메모리를 동적할당
	if (key < root->key) {
		//단말 노드를 만날 때 까지 순환, 값이 작으니 왼쪽 노드에 삽입
		root->left = insert_node(root->left, key);
	}
	else if (key > root->key) {
		root->right = insert_node(root->right, key);
	}
	return root;
}

//노드들 중 가장 큰 값을 가진 노드 반환
TreeNode* max_value_node(TreeNode* node) {
	TreeNode* current = node;
	while (current->right != NULL)
		current = current->right;
	return current;
}

//노드들 중 가장 작은 값을 가진 노드 반환
TreeNode* min_value_node(TreeNode* node) {
	TreeNode* current = node;
	while (current->left != NULL)
		current = current->left;
	return current;
}

//노드 삭제
//key값을 받아서 해당 key가 있는 노드를 삭제하고
//삭제된 자리에 새로 올라가는 노드를 반환한다.
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;
		}

		//해당 노드가 두개의 서브트리를 가질 때
		//오른쪽 서브트리에서 가장 왼쪽에 있는 노드 찾기 (22)
		TreeNode* temp = min_value_node(root->right);
		//찾은 노드 루트에 올리기 (22를 18 위치에)
		root->key = temp->key;
		//올라간 노드(22)가 원래 있던 자리를 지워줘야 한다.
		//루트(22)의 오른쪽 서브트리는 = 오른쪽 서브트리에서 원래 있던 노드(22)를 지운 것
		root->right = delete_node(root->right, temp->key);
	}
	return root;
	//35를 root->key로 가진 트리를 return..

	//22를 root->key로 가진 서브 트리를 return하는게 아닌가? 하며 혼란스러웠지만
	//91번째 line에의해
	//(35를 root키로 가지는 트리의 left, 즉) root->left == (22를 root->key로 가진 서브트리)
	//가 되는 것임.
	//즉 22를 root->key로 가진 서브트리는 우항의 return 값이다
}

//중위 순회
//이진 탐색 트리에서 중위 순회를 이용하면
//오름 차순으로 값이 순회됨
void inorder(TreeNode* root) {
	if (root != NULL) {
		inorder(root->left);
		printf("[%d] ", root->key);
		inorder(root->right);
	}
}

int main() {
	TreeNode* root = NULL;

	root = insert_node(root, 35);
	root = insert_node(root, 18);
	root = insert_node(root, 26);
	root = insert_node(root, 30);
	root = insert_node(root, 7);
	root = insert_node(root, 3);
	root = insert_node(root, 12);
	root = insert_node(root, 22);
	
	inorder(root);
	printf("\n");

	root = delete_node(root, 18);
	inorder(root);
	printf("\n");

	TreeNode* tmp = max_value_node(root);
	printf("가장 큰 값= %d\n", tmp->key);

	TreeNode* tmp2 = min_value_node(root);
	printf("가장 작은 값= %d\n", tmp2->key);

	int search;
	printf("\n찾으시는 값을 입력하세요 : ");
	scanf("%d", &search);

	printf("\n순환 탐색의 결과\n");
	if (search1(root, search) != NULL)
		printf("%d는 트리에 있습니다.\n", search);
	else
		printf("%d는 트리에 없습니다.\n", search);

	printf("\n반복 탐색의 결과\n");
	if (search2(root, search) != NULL)
		printf("%d는 트리에 있습니다.\n", search);
	else
		printf("%d는 트리에 없습니다.\n", search);

}

해당 프로그램은 위의 트리에서 18을 지운 것이다.

그리고 22를 18의 위치에 올렸다.

 

지운 18을 탐색해 본 결과

트리에 없다고 뜬다.

출력 결과

출력 결과는 위에서 부터

 

-원래 트리를 중위 순회

-18을 지운  트리를 중위 순회

-트리에서 가장 큰 값과 작은 값 찾기

-입력 값이 트리에 존재하는지 탐색한 결과

 

 

 

[참고자료] C언어로 쉽게 풀어 쓴 자료구조, 생능출판, 천인국 공용해 하상호 지음