문과생이 이해한 트리(삽입, 삭제)

출처 : <c언어로 쉽게 풀어쓴 자료구조> + 학교 수업

 

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

typedef struct TreeNode {
	int 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* 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);
	}
}

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

	return 0;
}

 

 

 대망의 이진 탐색 트리 삽입, 삭제 노드... 후. 사실 방금 연구실에 거의 새 크기의 벌레가 들어왔는데 5분간 발견되지 않는다. 마음이 너무 심란하다ㅜㅜㅜㅜ

 

 

~이진 탐색 트리란~

 

이진 탐색 트리란 탐색 작업을 효율적으로 하기 위한 자료구조로, 다음 사진과 같은 조건이 필요하다. 그니까,

key(왼쪽 서브트리) < key(root 노드) < key(오른쪽 서브트리) 

 

요로케!!! 이래서 중위 순회를 하면 오름차순으로 정렬된 값을 얻을 수 있따.

 

 

 

 

#main()

 

 

#insert_node(root, 30)

 

 처음에 node가 NULL이면 root 자체 즉, 트리 구조가 없다는 말이니까 일단 root 노드를 만든다. 

 

 

 

#insert_node(root, 20)

 그리고 이제 node 즉, root가 NULL이 아니므로 다음 if문을 검사한다. 현재 key값은 20, node가 가리키는 key 값은 30이므로 node의 왼쪽으로 가야 한다.

 

 

 

 요케. 

 

#insert_node(root, 10)

 

 HU... 순환 함수를 계속 호출하다 이렇게 쌓여 버렸da....   

 

 일단 새 노드를 만들고 맨 위 함수를 종료하면 20' 노드의 왼쪽으로 new_node가 반환된다.

 

  이케. 그리고 또 10'의 왼쪽이 20'로 반환되고 반환되면 요래 된다.

 

 

 

 나머지 40, 50, 60은 root노드의 data인 30보다 크므로 root의 오른쪽에 삽입된다. 

 

 

 

 이케 되겠쥬?

 

 

#inorder()

 

 중위 순회는 앞선 포스팅을 참고해주길 바라요

 

 

#search() 

 

 search 노드도 넘나 쉬운 것... 어차피 root를 기준으로 찾는 값이 현재 node가 가리키는 값보다 작으면 왼쪽, 크면 오른쪽으로 가면 된당..

 

 

 

#delete_node()

 그리고 이건 교재 코드에는 없지만 삭제가 시험 범위기 때문에... 내가 추가한 코드다. 

 

 

 

 

현재 키값(40)이 node가 가리키는 값(30)보다 크므로 48줄 else if문을 실행한다. 

 

 

여기가 바로 삭제하려는 노드를 찾았을 때 실행하는 코드다. 

 

 두번째 순환 함수에서 root의 오른쪽 주소값인 50번지를 temp를 저장하고 root를 free한 다음 temp를 return한다. 여기서 첫번째 순환함수 코드를 잘 보면. root->right로 받았다. 

 

 

 

 그러니까 요런 식으로 삭제 되는 거!