Media Log

[탐색 알고리즘 강좌]


데이터를 찾아보자!

이진 탐색 트리(Binary Search Tree)




이번에는 이진 탐색(Binary Search)이 적용된 이진 트리(Binary Tree)에 대해서 알아볼 것입니다. 이진 트리(Binary Tree)에 대해 더 상세한 설명을 보고싶으시면 아래 링크를 방문하여 이진 트리에 대한 설명을 읽어보시기 바랍니다.

이진 트리(Binary Tree): http://blog.eairship.kr/215


우리가 알고 있는 이진 트리는 자식 노드가 최대 두 개의 노드를 지니고, 네 가지 성질을 지닙니다. 자식 노드가 아에 없거나, 왼쪽 자식 노드 혹은 오른쪽 자식 노드 하나만 존재하거나, 왼쪽과 오른쪽 자식 노드를 모두 지니는 경우입니다. 그렇다면, 우리가 배우게 될 이진 탐색 트리는 어떻게 자라야 할까요? 가장 핵심은 왼쪽 자식 노드가 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 커야한다는 것입니다. 예를 들어서, 아래와 같이 트리가 자라야 되겠죠?

만약에 14라는 데이터를 찾으려 한다면, 루트 노드의 값인 10보다 크므로 오른쪽 자식 노드인 17과 비교를 하게됩니다. 그런데 이 17이란 값보다 작기 때문에 왼쪽 자식 노드를 살펴봅니다. 그리고 찾으려는 값과 일치하는지 비교를 하게 되는데, 왼쪽 자식 노드가 가지고 있는 값이 14이므로 탐색을 종료합니다. 이 경우는 찾으려는 데이터가 트리 내에 존재하는 경우이고, 만약 찾으려는 데이터가 없다면 어떻게 될까요? 예를 들어, 16이란 데이터를 찾는다고 생각해봅시다.


우선 찾으려는 값은 루트 노드의 값인 10보다 크므로 오른쪽 서브트리를 살펴봅니다. 오른쪽 자식 노드의 값은 17이고, 찾으려는 값보다 크므로 왼쪽 자식 노드를 방문합니다. 그런데 왼쪽 자식 노드인 14는 아무런 자식 노드를 지니고 있지 않습니다. 자식 노드가 없으므로 오른쪽 자식 노드를 방문한다고 해도 NULL일 뿐입니다. 한번, 이진 탐색 트리에서의 탐색 알고리즘을 보도록 합시다.

Node* searchNode(Node* Tree, int findData)
{
	// Tree가 비어있다면 NULL을 반환한다.
	if (Tree == NULL) return NULL;
	// 데이터를 만약 찾았다면, 해당 노드의 주소를 반환한다.
	if (Tree->Data == findData)
		return Tree;
	// 찾으려는 데이터가 현재 노드의 데이터보다 작다면, 왼쪽 자식 노드에서 탐색을 다시 시작한다.
	else if (Tree->Data > findData)
		searchNode(Tree->Left, findData);
	// 찾으려는 데이터가 현재 노드의 데이터보다 크다면, 오른쪽 자식 노드에서 탐색을 다시 시작한다.
	else 
		searchNode(Tree->Right, findData);
}

위의 searchNode 함수는 데이터를 찾으면 그 노드의 주소값을 반환하고, 찾으려는 노드가 작다면 왼쪽 자식 노드에서 탐색을, 반대로 크다면 오른쪽 자식 노드에서 탐색을 다시 시작합니다. 이번에는, 이진 탐색 트리에서 삽입(Insert) 알고리즘을 한번 봐보도록 합시다.

void insertNode(Node* Tree, Node* newNode)
{
	 if (newNode->Data > Tree->Data) // 새로 삽입되는 노드의 값이 현재 노드의 값보다 크다면
	 {
		 // 현재 노드의 오른쪽 자식 노드가 존재하는 경우, 오른쪽 자식 노드에서 삽입을 다시 시작한다.
		 if (Tree->Right != NULL) insertNode(Tree->Right, newNode);
		 // 현재 노드의 오른쪽 자식 노드가 비어있는 경우, 오른쪽 자식 노드는 새로 추가되는 노드가 들어간다.
		 else Tree->Right = newNode;
	 }
	 else if (newNode->Data < Tree->Data) // 새로 삽입되는 노드의 값이 현재 노드보다 작다면
	{
		 // 현재 노드의 왼쪽 자식 노드가 존재하는 경우, 왼쪽 자식 노드에서 삽입을 다시 시작한다.
		 if (Tree->Left != NULL) insertNode(Tree->Left, newNode);
		 // 현재 노드의 왼쪽 자식 노드가 비어있는 경우, 왼쪽 자식 노드는 새로 추가되는 노드가 들어간다.
		 else Tree->Left = newNode;
	 }
}

삽입 과정도 탐색 과정과 같이 간단해보이죠? 단지, 이진 탐색 트리의 핵심인 "크면 오른쪽! 작으면 왼쪽!"만 기억해도 어느정도 이해할 수 있는 부분입니다. 마지막으로는, 이진 탐색 트리에서 제거(Remove) 알고리즘을 한번 봐보도록 합시다.

Node* removeNode(Node* Tree, int data)
{
	// 임시로 쓰일 노드 포인터
	Node* tempNode;

	// 현재 노드가 NULL이라는 것은 비어있는 것을 의미한다.
	if (Tree == NULL) printf("해당하는 노드를 찾을 수 없습니다.\n");
	// 현재 노드의 값이 제거하려는 값보다 크다면, 왼쪽 자식 노드에서 제거하려는 값을 찾는다.
	else if (Tree->Data > data) Tree->Left = removeNode(Tree->Left, data);
	// 현재 노드의 값이 제거하려는 값보다 작다면, 오른쪽 자식 노드에서 제거하려는 값을 찾는다.
	else if (Tree->Data < data) Tree->Right = removeNode(Tree->Right, data);
	// 현재 노드의 값과 제거하려는 값이 같다면
	else
	{
		// 현재 노드의 왼쪽 자식 노드와 오른쪽 자식 노드가 모두 있는 경우
		if (Tree->Left != NULL && Tree->Right != NULL)
		{
			// 현재 노드의 오른쪽 노드에서 가장 값이 작은 노드의 주소값이 tempNode에 들어간다.
			// 가장 값이 작은 노드는 제일 왼쪽에 있는 노드라고 생각하면 된다.
			tempNode = findMinNode(Tree->Right);
			// 현재 노드의 값에다 값이 가장 작은 노드의 데이터를 대입한다.
			Tree->Data = tempNode->Data;
			// 현재 노드의 오른쪽 자식 노드에서 값이 가장 작은 노드를 제거한다.
			Tree->Right = removeNode(Tree->Right, tempNode->Data);
		}
		// 자식 노드가 없거나 한 쪽만 있는 경우
		else
		{
			// 임시 포인터 변수에다 Tree의 주소값을 대입한다.
			tempNode = Tree;
			// 현재 노드의 왼쪽 자식 노드가 비어있으면, 현재 노드는 현재 노드의 오른쪽 자식 노드가 된다.
			if (Tree->Left == NULL) Tree = Tree->Right;
			// 현재 노드의 오른쪽 자식 노드가 비어있으면, 현재 노드는 현재 노드의 왼쪽 자식 노드가 된다.
			else if (Tree->Right == NULL) Tree = Tree->Left;
			// tempNode를 메모리에서 해제한다.
			free(tempNode);
		}
	}

	// 현재 노드를 반환한다.
	return Tree;
}

추가로 잎 노드같은 경우에는 잎 노드의 오른쪽 자식 노드, 왼쪽 자식 노드가 없으므로 모두 NULL입니다. 즉, 잎 노드가 제거되는 경우에는 잎 노드에만 NULL이 들어가고 메모리에서 해제되는 것입니다. (제거 과정이 주석만으로도 부족하다면, 덧글로 올려주세요. 따로 제거가 이루어지는 과정을 추가로 달도록 하겠습니다.) 이번에는 전체 코드를 보여드리도록 하겠습니다.

예제:

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

typedef struct Node
{
	Node* Left;
	Node* Right;
	int Data;
} Node;

Node* createNode(int data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->Left = NULL;
	newNode->Right = NULL;
	newNode->Data = data;

	return newNode;
}

Node* searchNode(Node* Tree, int findData)
{
	if (Tree == NULL) return NULL;
	if (Tree->Data == findData)
		return Tree;
	else if (Tree->Data > findData)
		searchNode(Tree->Left, findData);
	else 
		searchNode(Tree->Right, findData);
}

void insertNode(Node* Tree, Node* newNode)
{
	 if (newNode->Data > Tree->Data)
	 {
		 if (Tree->Right != NULL) insertNode(Tree->Right, newNode);
		 else Tree->Right = newNode;
	 }
	 else if (newNode->Data < Tree->Data)
	 {
		 if (Tree->Left != NULL) insertNode(Tree->Left, newNode);
		 else Tree->Left = newNode;
	 }
}

Node* findMinNode(Node* Tree)
{
	if (Tree == NULL) return NULL;
	if (Tree->Left != NULL) return findMinNode(Tree->Left);
	else return Tree;
}

Node* removeNode(Node* Tree, int data)
{
	Node* tempNode;

	if (Tree == NULL) printf("해당하는 노드를 찾을 수 없습니다.\n");
	else if (Tree->Data > data) Tree->Left = removeNode(Tree->Left, data);
	else if (Tree->Data < data) Tree->Right = removeNode(Tree->Right, data);
	else
	{
		if (Tree->Left != NULL && Tree->Right != NULL)
		{
			tempNode = findMinNode(Tree->Right);
			Tree->Data = tempNode->Data;
			
			Tree->Right = removeNode(Tree->Right, tempNode->Data);
		}
		else
		{
			tempNode = Tree;
			if (Tree->Left == NULL) Tree = Tree->Right;
			else if (Tree->Right == NULL) Tree = Tree->Left;
			free(tempNode);
		}
	}

	return Tree;
}

void printTree(Node* Tree)
{
	if (Tree == NULL) return;
	printTree(Tree->Left);
	printf("%d ", Tree->Data);
	printTree(Tree->Right);
}

int main()
{
	Node* Tree = createNode(10);
	Node* findNode;
	int input;

	insertNode(Tree, createNode(5));
	insertNode(Tree, createNode(1));
	insertNode(Tree, createNode(6));
	insertNode(Tree, createNode(17));
	insertNode(Tree, createNode(14));
	insertNode(Tree, createNode(21));

	while(1)
	{
		scanf("%d", &input);
		findNode = searchNode(Tree, input);

		if (findNode != NULL) 
		{
			printf("해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 %#x 입니다.\n", findNode);
			removeNode(Tree, input);
			printf("현재 트리 출력: ");
			printTree(Tree); printf("\n");
		}
		else printf("노드를 찾을 수 없었습니다.\n");

	}
	return 0;
}

결과:

6
해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0x498d50 입니다.
현재 트리 출력: 1 5 10 14 17 21
5
해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0x498ce0 입니다.
현재 트리 출력: 1 10 14 17 21
14
해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0x498dc0 입니다.
현재 트리 출력: 1 10 17 21
17
해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0x498d88 입니다.
현재 트리 출력: 1 10 21


위의 예제는 입력된 데이터를 가지고, 그 데이터를 지니고 있는 노드가 트리 내에 존재하는지 확인합니다. 만약 존재할 경우에, 그 노드를 제거하고 현재 트리내에 있는 모든 노드의 데이터를 출력합니다. 삽입된 노드는 위에서 예로 설명드렸던 그림과 동일하게 노드가 존재합니다. 이러한 이진 트리 탐색에서는 한쪽으로만 몰린 사향 이진 트리에서 최악의 효율성을 보입니다. 사향 이진 트리에서의 시간 복잡도는 O(n)이며, 완전 이진 트리와 비슷한 경우는 O(log2(n))의 효율성을 보인다는 것입니다. 이 때문에, 이진 탐색 트리의 형태는 완전 이진 트리와 비슷하게 구성하시는게 좋습니다. 조금 복잡한가요?


우선은 이진 탐색 트리에 관한 내용은 여기서 그만 쓰도록 하겠습니다. 수고하셨고, 다음 강좌에서는 우선순위 큐에 대해 알아보도록 하겠습니다.

  1. namoeye at 2014.03.23 19:13 신고 [edit/del]

    글 너무 잘봤습니다.
    근데 궁금한게 있는데 왜 removeNode함수에서
    Tree->Right=removeNode(Tree->Right, TempNode->data); 를 왜 하는거죠?
    (전체코드에서는 67번줄입니다)
    현재 노드에서 오른쪽 노드 중 가장 작은 값을 제거하는거라고 설명을 하셨는데..
    이해가 안가는 부분이
    제 생각으로는 removeNode에서 Node가 반환이 되어
    Tree->Right에 대입하게 된다면 현재 노드의 오른쪽에 가장작은 값을 가지는 노드가 대입되는것 아닌가요?
    궁긍합니다.

    Reply
  2. ss at 2014.05.10 20:47 신고 [edit/del]

    노드가 하나일때
    삭제할 노드의 부모노드와 삭제할 노드의 하나있는 자식노드와 link가 되야 되는데 안되네요
    수정부탁드립니다.

    Reply
    • BlogIcon EXYNOA at 2014.05.10 23:03 신고 [edit/del]

      현재 삭제할 노드의 자식 노드가 하나일 경우에, 현 노드를 삭제해버린 경우 부모 노드와 삭제한 노드의 자식 노드는 정상적으로 연결이 됨을 확인했습니다.

      6
      해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0x4694a8 입니다.
      현재 트리 출력: 1 (Left: 0, Right: 0)5 (Left: 1, Right: 0)10 (Left: 5, Right: 17
      )14 (Left: 0, Right: 0)17 (Left: 14, Right: 21)21 (Left: 0, Right: 0)
      5
      해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0x469438 입니다.
      현재 트리 출력: 1 (Left: 0, Right: 0)10 (Left: 1, Right: 17)14 (Left: 0, Right:
      0)17 (Left: 14, Right: 21)21 (Left: 0, Right: 0)
      -------------------------------------------------------------
      1
      해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0x459470 입니다.
      현재 트리 출력: 5 (Left: 0, Right: 6)6 (Left: 0, Right: 0)10 (Left: 5, Right: 17
      )14 (Left: 0, Right: 0)17 (Left: 14, Right: 21)21 (Left: 0, Right: 0)
      5
      해당 노드를 찾았습니다! 노드를 제거합니다. 노드의 위치는 0x459438 입니다.
      현재 트리 출력: 6 (Left: 0, Right: 0)10 (Left: 6, Right: 17)14 (Left: 0, Right:
      0)17 (Left: 14, Right: 21)21 (Left: 0, Right: 0)

  3. at 2014.11.03 23:15 신고 [edit/del]

    tempNode=Tree;
    if(Tree->Right==NULL)
    Tree=Tree->Left;
    else if(Tree->Left==NULL)
    Tree=Tree->Right;
    free(tempNode);
    이부분에서요 왼쪽에만 자식이 있는경우 Tree=Tree->Left이거하고 나서
    free(Tree->Left)를 해줘야 하는거 아니에요?

    Reply
  4. 냉이크래커 at 2016.03.27 01:00 신고 [edit/del]

    간결하고 이해하기 쉬운코드 잘 보았습니다. 그런데 재귀호출 위주로 된 소스라 실제로 사용하긴 좀 어렵지 않을까요? 재귀호출 사용안하소스로 혹시 올려주실수 있을까요.. 고맙습니다.

    Reply
  5. 지나가던사람 at 2017.01.17 23:20 신고 [edit/del]

    좋은 글 감사합니다 ^^* 많은 도움 되었습니다.

    Reply
  6. 동적프밍 at 2017.03.31 01:33 신고 [edit/del]

    좋은 코드 보고 갑니다. 스택을 이용한것도 좋지만 시스템 성능 저하를 덜시키는 반복문으로 하면 더 좋을것 같네요

    Reply
  7. 행인 at 2018.03.09 20:01 신고 [edit/del]

    엄청납니다

    Reply
  8. 행인2 at 2018.03.13 08:47 신고 [edit/del]

    input을 아래와 같이 주면 14를 Remove한 뒤 PrintTree를 하면서 Exception이 나는데 이유를 모르겠네요...
    14를 지운 후 Tree pointer에 쓰레기값이 들어가 잇어요.
    10
    17
    5
    21
    6
    14
    1

    Reply

submit

티스토리 툴바