[알고리즘] ch 5. 탐색(2) - 이진 탐색 트리

5.4 이진 탐색 트리 

 

이진 탐색 트리 (Binary Serach Tree)

 

- '이진 탐색'을 위한 '이진 트리'

- 이진 탐색은 배열에만 사용 가능한 알고리즘 

  -> 이진 탐색을 사용하려면 데이터의 처음과 끝을 알아야 하고 데이터의 중앙 요소를 계산할 수 있어야 하며 계산된 중앙 요소에 즉시 접근할 수 있어야 함

  -> 링크드 리스트는 상기된 작업 불가 

 

- 이진 탐색 트리는 동적으로 노드를 추가하거나 제거할 수 있으면서 이진 탐색 알고리즘도 사용할 수 있게 함

 

5.4.1 이진 탐색 트리 표현

 

- 이진 탐색 트리 노드의 조건

 -> 이진 탐색 트리의 각 노드는 왼쪽 자식 노드보다 크고 오른쪽 자식 노드보다 작다

 

5.4.2 이진 탐색 트리의 기본 연산

 

- 이진 탐색 트리는 이진 탐색이 가능한 상태로 정렬되어 있어야 함

 

1) 이진 탐색 트리에서의 이진 탐색 

 

- 각 노드는 '중앙 요소'임

- 이진 탐색 트리의 뿌리 노드는 23이고 23은 트리 전체의 '중앙 요소'

- 23 노드의 오른쪽 하위 트리에는 23보다 큰 값을 가진 노드들만 있고, 왼쪽 하위 트리는 23보다 작은 값을 가진 노드들만 존재

 

- 하위 트리로 내려가도 같은 규칙이 적용

 - 11노드는 왼쪽 하위 트리의 중앙값

 - 138 노드는 오른쪽 하위 트리의 중앙값 

 

 

- 이진 탐색 과정

 - 중앙 요소를 찾아 좌우의 대소를 비교하여 탐색 범위를 정하는 과정을 반복

 

ex) 67 찾기

 

- 뿌리 노드인 23 노드와 목표값 67을 비교

 -> 목표값이 더 크므로 왼쪽을 버리고 오른쪽 하위 트리에 한정하여 탐색 대상을 좁힘

 

 - 139는 67보다 크므로 목표값은 139 노드의 왼쪽 하위 트리에 있음

 

이진 탐색 트리 구현 함수 BST_SearchNode 

//이진 탐색
BSTNode* BST_SearchNode(BSTNode* Tree, ElementType Target)
{
	if (Tree == NULL)
		return NULL;

	//목표값이 현재 노드와 같은 경우 
	if (Tree->Data == Target)
		return Tree;
	//목표값이 현재 노드보다 작은 경우 
	else if (Tree->Data > Target)
		return BST_SearchNode(Tree->Left, Target);
	//목표값이 현재 노드보다 큰 경우 
	else
		return BST_SearchNode(Tree->Left, Target);
}

 

2) 노드 삽입 연산

 

- 노드 삽입 연산의 핵심은 새 노드가 삽입될 곳이 어디인지 찾아내는 것

- 새 노드가 삽입될 곳을 이진탐색으로 찾아야 함

 

ex) 14 삽입

- 14는 23보다 작으므로 23의 왼쪽 하위 트리에 위치해야함

- 14는 11보다 크므로 11의 오른쪽 하위 트리에 위치해야함

 

노드 삽입 함수 BST_InsertNode

//노드 삽입
void BST_InsertNode(BSTNode* Tree, BSTNode* Child)
{
	//새 노드가 현재 노드보다 큰 경우 
	if (Tree->Data < Child->Data)
	{
		if (Tree->Right == NULL)
			Tree->Right = Child;
		else
			BST_InsertNode(Tree->Right, Child);
	}
	//새 노드가 현재 노드보다 작은 경우
	else if (Tree->Data > Child->Data)
	{
		if (Tree->Left == NULL)
			Tree->Left = Child;
		else
			BST_InsertNode(Tree->Left, Child);
	}
}

 

3) 노드 삭제 연산

 

- 먼저 이진 탐색을 통해 삭제할 노드 찾기 

 

- 삭제 노드가 단말 노드인 경우

  -> 부모 노드에서 자식 노드의 포인터를 NULL로 봉합하고 삭제한 노드의 주소 반환

 

- 삭제 노드의 자식이 있는 경우 

 

 ● 왼쪽과 오른쪽 중 어느 한쪽 자식 노드만 갖고 있는 경우  

  - 삭제할 노드의 자식을 삭제할 노드의 부모에 연결

 

 ex) 

  - 139 노드를 삭제하면 해당 노드를 가리키던 부모 노드(23)의 오른쪽 자식 포인터를 67 노드에 연결

 

 ● 양쪽 자식 노드를 모두 갖고 있는 경우 

   - 삭제된 노드의 오른쪽 하위 트리에서 가장 작은 값을 가진 노드(최솟값 노드)를 삭제된 노드의 위치에 옮겨놓음

   - 이진 탐색 트리의 특성(각 노드는 왼쪽 자식보다 크고 오른쪽 자식보다 작다) 유지 가능

 

 ex) 

  - 삭제할 11 노드의 오른쪽 하위 트리에서 가장 작은 13 노드를 옮겨 11 노드가 있던 자리에 놓음

  - 최솟값 노드의 자식이 없는 경우는 여기서 작업 끝남

  - 최솟값 노드는 오른쪽 자식만 존재 

   -> 최솟값 노드의 오른쪽 자식을 최솟값 노드의 원래 부모에게 연결함으로써 삭제 작업 마무리

   -> 15 노드를 16 노드의 왼쪽 자식으로 만들기 

 

노드 삭제 함수 BST_RemoveNode

//노드 삭제 
BSTNode* BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target)
{
	BSTNode* Removed = NULL;

	if (Tree == NULL)
		return NULL;

	//이진 탐색을 통해 삭제할 노드 찾기 
	if (Tree->Data > Target)
		Removed = BST_RemoveNode(Tree->Left, Tree, Target);
	else if (Tree->Data < Target)
		Removed = BST_RemoveNode(Tree->Right, Tree, Target);
	else // 목표값을 찾은 경우 
	{
		Removed = Tree;

		//단말 노드인 경우 바로 삭제 
		if (Tree->Left == NULL && Tree->Right == NULL)
		{
			if (Parent->Left == Tree)
				Parent->Left = NULL;
			else
				Parent->Right = NULL;
		}
		else //자식이 있는 경우 
		{
			//자식이 양쪽 다 있는 경우 
			if (Tree->Left != NULL && Tree->Right != NULL)
			{
				//최솟값 노드를 찾아 제거한 뒤 현재의 노드에 위치시킴
				BSTNode* MinNode = BST_SearchMinNode(Tree->Right);
				MinNode = BST_RemoveNode(Tree, NULL, MinNode->Data);
				Tree->Data = MinNode->Data;
			}
			else
			{
				//자식이 하나만 있는 경우 
				BSTNode* Temp = NULL;
				if (Tree->Left != NULL)
					Temp = Tree->Left;
				else
					Temp = Tree->Right;

				if (Parent->Left == Tree)
					Parent->Left = Temp;
				else
					Parent->Right = Temp;
			}
		}
	}

	return Removed;
}

 

5.4.3 이진 탐색 트리 예제 프로그램

 

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

typedef int ElementType;

typedef struct tagBSTNode
{
	struct tagBSTNode* Left;
	struct tagBSTNode* Right;

	ElementType Data;
}BSTNode;

//노드 생성
BSTNode* BST_CreateNode(ElementType NewData)
{
	BSTNode* NewNode = (BSTNode*)malloc(sizeof(BSTNode));
	NewNode->Left = NULL;
	NewNode->Right = NULL;
	NewNode->Data = NewData;

	return NewNode;
}

//노드 소멸
void BST_DestroyNode(BSTNode* Node)
{
	free(Node);
}

//트리 소멸
void BST_DestroyTree(BSTNode* Tree)
{
	if (Tree->Right != NULL)
		BST_DestroyTree(Tree->Right);
	if (Tree->Left != NULL)
		BST_DestroyTree(Tree->Left);

	Tree->Left = NULL;
	Tree->Right = NULL;

	BST_DestroyNode(Tree);
}

//이진 탐색
BSTNode* BST_SearchNode(BSTNode* Tree, ElementType Target)
{
	if (Tree == NULL)
		return NULL;

	//목표값이 현재 노드와 같은 경우 
	if (Tree->Data == Target)
		return Tree;
	//목표값이 현재 노드보다 작은 경우 
	else if (Tree->Data > Target)
		return BST_SearchNode(Tree->Left, Target);
	//목표값이 현재 노드보다 큰 경우 
	else
		return BST_SearchNode(Tree->Left, Target);
}

//최솟값 노드 찾기
BSTNode* BST_SearchMinNode(BSTNode* Tree)
{
	if (Tree == NULL)
		return NULL;
	if (Tree->Left == NULL)
		return Tree;
	else
		return BST_SearchMinNode(Tree->Left);
}

//노드 삽입
void BST_InsertNode(BSTNode* Tree, BSTNode* Child)
{
	//새 노드가 현재 노드보다 큰 경우 
	if (Tree->Data < Child->Data)
	{
		if (Tree->Right == NULL)
			Tree->Right = Child;
		else
			BST_InsertNode(Tree->Right, Child);
	}
	//새 노드가 현재 노드보다 작은 경우
	else if (Tree->Data > Child->Data)
	{
		if (Tree->Left == NULL)
			Tree->Left = Child;
		else
			BST_InsertNode(Tree->Left, Child);
	}
}

//노드 삭제 
BSTNode* BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target)
{
	BSTNode* Removed = NULL;

	if (Tree == NULL)
		return NULL;

	//이진 탐색을 통해 삭제할 노드 찾기 
	if (Tree->Data > Target)
		Removed = BST_RemoveNode(Tree->Left, Tree, Target);
	else if (Tree->Data < Target)
		Removed = BST_RemoveNode(Tree->Right, Tree, Target);
	else // 목표값을 찾은 경우 
	{
		Removed = Tree;

		//단말 노드인 경우 바로 삭제 
		if (Tree->Left == NULL && Tree->Right == NULL)
		{
			if (Parent->Left == Tree)
				Parent->Left = NULL;
			else
				Parent->Right = NULL;
		}
		else //자식이 있는 경우 
		{
			//자식이 양쪽 다 있는 경우 
			if (Tree->Left != NULL && Tree->Right != NULL)
			{
				//최솟값 노드를 찾아 제거한 뒤 현재의 노드에 위치시킴
				BSTNode* MinNode = BST_SearchMinNode(Tree->Right);
				MinNode = BST_RemoveNode(Tree, NULL, MinNode->Data);
				Tree->Data = MinNode->Data;
			}
			else
			{
				//자식이 하나만 있는 경우 
				BSTNode* Temp = NULL;
				if (Tree->Left != NULL)
					Temp = Tree->Left;
				else
					Temp = Tree->Right;

				if (Parent->Left == Tree)
					Parent->Left = Temp;
				else
					Parent->Right = Temp;
			}
		}
	}

	return Removed;
}

//중위 순회 
void BST_InorderPrintTree(BSTNode* Node)
{
	if (Node == NULL)
		return;

	//왼쪽 하위 트리 출력
	BST_InorderPrintTree(Node->Left);

	//뿌리 노드 출력
	printf(" %d", Node->Data);

	//오른쪽 하위 트리 출력
	BST_InorderPrintTree(Node->Right);
}

//탐색 결과 출력
void PrintSearchResult(int SearchTarget, BSTNode* Result)
{
	if (Result != NULL)
		printf("Found: %d\n", Result->Data);
	else
		printf("Not Found: %d\n", SearchTarget);
}

int main(void)
{
	//노드 생성
	BSTNode* Tree = BST_CreateNode(123);
	BSTNode* Node = NULL;

	//트리에 노드 추가 
	BST_InsertNode(Tree, BST_CreateNode(22));
	BST_InsertNode(Tree, BST_CreateNode(9918));

	BST_InsertNode(Tree, BST_CreateNode(424));
	BST_InsertNode(Tree, BST_CreateNode(17));
	BST_InsertNode(Tree, BST_CreateNode(3));

	BST_InsertNode(Tree, BST_CreateNode(98));
	BST_InsertNode(Tree, BST_CreateNode(34));

	BST_InsertNode(Tree, BST_CreateNode(760));
	BST_InsertNode(Tree, BST_CreateNode(317));
	BST_InsertNode(Tree, BST_CreateNode(1));

	int SearchTarget = 17;
	Node = BST_SearchNode(Tree, SearchTarget);
	PrintSearchResult(SearchTarget, Node);

	SearchTarget = 117;
	Node = BST_SearchNode(Tree, SearchTarget);
	PrintSearchResult(SearchTarget, Node);

	//트리 출력
	BST_InorderPrintTree(Tree);
	printf("\n");

	//특정 노드 삭제 
	printf("Removing 98...\n");

	Node = BST_RemoveNode(Tree, NULL, 98);
	BST_DestroyNode(Node);

	BST_InorderPrintTree(Tree);
	printf("\n");

	//새 노드 삽입
	printf("Inserting 111..\n");

	BST_InsertNode(Tree, BST_CreateNode(111));
	BST_InorderPrintTree(Tree);
	printf("\n");

	//트리 소멸
	BST_DestroyTree(Tree);

	return 0;

}

 

5.4.4 이진 탐색 트리의 문제점

- 이진 탐색 트리는 동적으로 크기가 증가하는 데이터도 잘 처리하며 탐색 속도도 빠름

- 아래에 그림 처럼 기형적으로 성장하면 검색 효율이 극단적으로 떨어짐

- 불균형한 성장은 이진 탐색 트리의 높이를 높여서 검색 효율을 심각하게 저하