[Data structure] 이진트리 (Binary Tree)

이진트리 (Binary Tree)

이번시간은 이진트리 (Binary Tree)에 대해서 알아보겠습니다. 정말 재미있는 녀석입니다. 

이진트리가 되기 위해선 몇 가지 특징이 있습니다.

우선 이진트리는 가질 수 있는 자식노드의 최대갯수는 2개입니다. 또한 왼쪽 자식 노드는 부모 노드보다 값이 작고, 오른쪽 자식 노드는 부모 노드보다 값이 큽니다. 

또한 이진트리에는 여러 종류가 존재하는데 완전이진트리 라는 것은 이상적으로 모든 노드에 2개씩 자식노드를 가지고 있는 형태입니다. 단 마지막 단계에서는 왼쪽에서부터 채워지는 형태를 취합니다. 

포화이진트리는 마지막레벨은 단말노드이면서 나머지는 모두 자식이 2개씩 보유하고 있습니다.

뭐 이렇게 이진트리에 대해서 알아보았고, 이진트리를 순회하는 방법에는 지난시간 배웠던

전위, 중위, 후위 순회방식이 있다고 했습니다.

2017/10/30 - [Algorithm/BackJoon] - [TREE] 백준 1991 트리 순회(Tree Order)

자 이제 이진트리에서 노드를 삽입하고 삭제하는 방법에 대해서 알아보겠습니다.

*탐색 시 규칙

1 ) 입력 값과 현재 노드 값이 같은 경우, 검색 종료 (성공)

2 ) 입력 값보다 현재 노드의 값이 큰 경우, 왼쪽 서브트리로 이동

3 ) 입력 값보다 현재 노드의 값이 작은 경우, 오른족 서브트리로 이동

*삽입 시 규칙

1 ) 루트노드가 현재 없는 경우, 삽입노드는 루트노드로 삽입됩니다.

2 ) 삽입할 노드가 이미 트리에 존재하는 경우, 실행하지 않습니다.

3 ) 삽입할 노드가 트리에 존재하지 않고, 루트 노드가 존재하는 경우 자신의 위치를 찾아 삽입됩니다. 이 때 탐색이 실패하는 경우에 삽입됩니다. 즉 더 이상 서브트리가 없는 경우가 실패한 경우이고 실패 위치가 삽입 노드의 위치입니다.

*삭제 시 규칙

1 ) 삭제하려는 노드의 자식이 없는 경우, 노드를 삭제하고 부모노드가 자식을 가리키고 있는 포인터를 NULL 지정합니다.

2 ) 삭제하려는 노드의 자식이 1개 있는 경우, 부모 노드에게 자신의 자식 노드를 즉 손자인 노드를 인계하고 자신은 삭제됩니다.

3 ) 삭제하려는 노드의 자식이 2개 있는 경우, 우선 오른쪽 서브트리에서 가장 작은 노드를 찾고 그 노드가 삭제하려는 노드의 자리를 대신합니다. 만약 대체하려는 노드의 자식이 있는 경우라면, 대체하려는 노드의 부모노드에게 자식을 인계합니다. 

4 ) 삭제하려는 노드가 트리에 없는 경우, 실행하지 않습니다.

생각보다 삭제시 규칙은 복잡하기 때문에 더 공부가 필요할 것 같습니다.... 위 규칙을 토대로 C언어로 코드를 짜면 아래와 같습니다. (사실 제대로 트리 상태를 확인하려면, 트리순회를 통해 노드를 출력해야하지만, 아래 코드는 생략되어있습니다. 향후 과제로 해보겠습니다...)

// BinaryTree.cpp: 콘솔 응용 프로그램의 진입점을 정의합니다.
//

#include <stdio.h>
#include <malloc.h>

struct TreeNode {
	int key;
	TreeNode *LNode;
	TreeNode *RNode;
};

struct Tree {
	TreeNode *Root;
};

//초기화 하는 함수
void init(Tree *target) {
	target->Root = NULL;
}

//단지 찾고자 하는 data의 존재 유무만 파악하는 함수
bool searchNode(Tree *target, int data) {
	
	TreeNode *curr = target->Root;
	while (1) {
		if (curr->key == data) {
			printf("값이 있습니다.\n");
			return true;
		}
		if (curr->key < data) {
			if (curr->RNode == NULL)return false;
			curr = curr->RNode;
		}
		else {
			if (curr->LNode == NULL)return false;
			curr = curr->LNode;
		}
	}
}

void addNode(Tree *target, int data) {
	TreeNode *NewNode = (TreeNode*)malloc(sizeof(TreeNode));
	//루트노드가 없는 경우
	if (target->Root == NULL) {
		target->Root = NewNode;
		NewNode->LNode = NULL;
		NewNode->RNode = NULL;
		NewNode->key = data;
		return;
	}

	//삽입할 data가 이미 존재하는 경우
	if (searchNode(target, data)) {
		printf("이미 존재하는 값입니다.\n");
		return;
	}
	
	//삽입될 data의 자리를 알기위해서 어느정도 탐색이 필요한 경우
	//루트노드가 단말노드가 아니며, 이미 존재하는 data도 없는 경우
	NewNode->LNode = NULL;
	NewNode->RNode = NULL;
	NewNode->key = data;
	TreeNode *curr = target->Root;

	while (1) {
		//data가 더 큰경우 즉 오른쪽 서브트리에서 탐색해야함
		if (curr->key < data) {
			if (curr->RNode == NULL) {
				curr->RNode = NewNode;
				return;
			}
			//다음 탐색을 위해 curr의 RNode를 설정한다.
			curr = curr->RNode;
		}
		else {
			if (curr->LNode == NULL) {
				curr->LNode = NewNode;
				return;
			}
			//다음 탐색을 위해 curr의 LNode를 설정한다.
			curr = curr->LNode;
		}
	}

}

int deleteNode(Tree *target, int data) {
	TreeNode *curr1 = target->Root;
	TreeNode *curr2 = NULL;
	TreeNode *par_parent = NULL;
	TreeNode *parent = NULL;
	TreeNode *child = NULL;
	TreeNode *left_temp = NULL;
	int key_return = 0;

	//없는 data값을 삭제할 순 없다.
	if (!searchNode(target, data)) {
		printf("없는 값입니다.\n");
		return 0;
	}

	//특정 data값까지 이동한다.
	while(curr1->key != data){
		//오른족 서브트리로..
		if (data > curr1->key) {
			par_parent = parent;
			parent = curr1;
			curr1 = curr1->RNode;
		}
		else {
			par_parent = parent;
			parent = curr1;
			curr1 = curr1->LNode;
		
		}
	}
	//삭제하려는 노드가 단말노드일 경우
	if (curr1->LNode == NULL && curr1->RNode == NULL) {
		key_return = curr1->key;
		if (parent->LNode == curr1)
			parent->LNode = NULL;
		if (parent->RNode == curr1)
			parent->RNode == NULL;
		free(curr1);
		return key_return;
	}

	//삭제하려는 노드의 자식이 1개일 경우
	if (curr1->LNode == NULL || curr1->RNode == NULL) {
		child = (child->LNode == NULL) ? curr1->RNode : curr1->LNode;

		if (parent->LNode == curr1)
			parent->LNode = child;
		else
			parent->RNode = child;
	
		key_return = curr1->key;
		free(curr1);
		return key_return;
	}

	//삭제하려는 노드의 자식이 2개일 경우
	if (curr1->LNode != NULL && curr1->RNode != NULL) {
		curr2 = curr1;
		curr2 = curr2->RNode;

		if (curr2->LNode == NULL) { //오른쪽으로 한칸 이동 후 왼쪽 노드가 없을 때 
			left_temp = curr1->LNode; 
			child = curr2;

			if (parent->RNode==curr1)
			{
				parent->RNode = child;
				child->LNode = left_temp;

			}else if (parent->LNode == curr1)
			{
				parent->LNode = child;
				child->LNode = left_temp;
			}

				key_return = curr1->key;
				free(curr1);
				return key_return;
		
		}
		//오른쪽으로 한칸 이동 후 왼쪽 노드가 있을 때
		while (curr2->LNode != NULL) {
			parent = curr2;
			curr2 = curr2->LNode;
		}
		parent->LNode = NULL;
		curr1->key = curr2->key;
		free(curr2);
	}

	return 0;


}


int main()
{

	Tree T;
	init(&T);

	addNode(&T, 30);
	addNode(&T, 10);
	addNode(&T, 40);
	addNode(&T, 24);
	addNode(&T, 14);
	addNode(&T, 46);

	searchNode(&T, 10);


    return 0;
}