뇌를 자극하는 알고리즘 - 6. 탐색 : 이진 탐색 트리(Binary Search Tree)

구현소스

BinarySearchTree.h

#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H

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

typedef int Element;

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

	Element Data;

} BSTNode;


BSTNode*	BST_CreateNode(Element NewData);
void		BST_DestroyNode(BSTNode* Node);
void		BST_DestroyTree(BSTNode* Tree);

BSTNode*	BST_SearchNode(BSTNode* Tree, Element Target);
BSTNode*	BST_SearchMinNode(BSTNode* Tree);
void		BST_InsertNode(BSTNode* Tree, BSTNode* Child);
BSTNode*	BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, Element Target);

void BST_InorderPrintTree(BSTNode* Node);

#endif

---------------------------------------------------------
BinarySearchTree.cpp

#include "BinarySearchTree.h"



BSTNode* BST_CreateNode(Element 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)
{
	// 후위 순회로 전체 Node들의 메모리를 해제한다.
	if(Tree->Left != NULL)
		BST_DestroyTree(Tree->Left);

	if(Tree->Right != NULL)
		BST_DestroyTree(Tree->Right);

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

	BST_DestroyNode(Tree);
}

// 이진 탐색 트리의 Target 과 일치하는 Data를 가진 노드의 주소를 반환하는 함수
BSTNode* BST_SearchNode(BSTNode* Tree, Element Target)
{
	if(Tree==NULL)
		return NULL;

	if(Tree->Data > Target) // Tree의 Data가 Target 보다 큰 경우 : Target은 Tree의 왼쪽에 존재
		return BST_SearchNode(Tree->Left , Target);
	else if(Tree->Data < Target) // Tree의 Data가 Target보다 작은 경우 : Target은 Tree의 오른쪽에 존재
		return BST_SearchNode(Tree->Right, Target);
	else // 일치 할 경우 Node의 주소를 반환한다.
		return Tree;

}

// 매개변수인 Tree의 하위노드들중 최소 값을 가진 Node의 주소를 반환 
BSTNode* BST_SearchMinNode(BSTNode* Tree)
{
	if(Tree == NULL)
		return NULL;

	if(Tree->Left == NULL) // Left Child가 존재하지 않을시 Tree가 최소 값을 가진 Node
		return Tree;
	else // 그외의 경우는 Tree의 Left Child로 다시 한번 재귀 호출
		return BST_SearchMinNode(Tree->Left);

}

// 새로운 Node인 매개변수 Child를 Tree(Root Node)의 적절한 위치에 연결 시켜주는 함수
void BST_InsertNode(BSTNode* Tree, BSTNode* Child)
{
	// 이진 탐색 트리의 특성상
	// Child의 Data 값에 따라 위치가 정해짐 (Tree의 Data보다 작을시 Left, 클시 Right)
	
	if(Tree->Data < Child->Data) // Child->Data가 Tree->Data보다 클시 -> Right
	{
		if(Tree->Right == NULL)
			Tree->Right = Child;
		else
			BST_InsertNode( Tree->Right , Child );
		// Tree의 Right 차일드에서 다시 한번 Child Node의 적절한 위치를 판별 - 재귀
	}
	else if( Tree->Data > Child->Data )
	{
		if(Tree->Left == NULL)
			Tree->Left = Child;
		else
			BST_InsertNode( Tree->Left , Child );
		// Tree의 Left 차일드에서 다시 한번 Child Node의 적절한 위치를 판별 - 재귀
	}

	// 이진 탐색트리의 구축 조건에 같은 크기 Data가 들어간다는 조건은
	//없으므로 큰 것과 작은 것만 구별하고 각 노드의 Data는 겹치지 않는다.

}

BSTNode* BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, Element 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 // 삭제될 노드를 찾은 경우
	{
		// 총 세가지 경우를 판별 해야됨.
		// 1. 삭제될 노드가 잎 노드인 경우 - Parent의 Link만 제거하면 끝
		// 2. 삭제될 노드가 자식이 있는 경우
		//   - 자식이 양쪽 다 있는 경우 : 삭제될 노드 오른쪽 아래의 최소값 노드를 찾아 최소값 노드와 관련된 
		//                              링크를 해제(제거)후 삭제될 노드의 자리로 이동.
		//   - 자식이 하나만 있는 경우 : Parent는 삭제될 노드를 더이상 가리키지 않고 삭제될 노드의 자식을 가리킴.
		if(Tree->Left == NULL && Tree->Right == NULL)
		{ // 삭제 대상 노드가 잎 노드인 경우
			if(Parent->Left == Tree) // 잎노드의 Left Child인 경우
				Parent->Left = NULL;
			else // 잎노드의 Right Child인 경우
				Parent->Right = NULL;

		}
		else
		{ // 삭제 대상 노드의 차일드가 존재할 경우
			if(Tree->Left != NULL && Tree->Right !=NULL)
			{ //  삭제 대상 노드가 자식이 양쪽 다 있는 경우
				BSTNode* MinNode = BST_SearchMinNode(Tree->Right);
				// 오른쪽 아래의 최소값 노드를 찾은 후
				
				Removed = BST_RemoveNode(Tree, NULL, MinNode->Data);
				// 최소값 노드와 관련된 링크를 해제시키고 - 삭제 대상으로 등록

				Tree->Data = MinNode->Data;
				// 그 다음 원래 삭제 대상이였던 Node의 데이터를 MinNode의 데이터로 바꾼다.
			}
			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);


}

---------------------------------------------------------
main.cpp

#include "BinarySearchTree.h"

int main()
{
	BSTNode* Tree = BST_CreateNode(123); // 이진 탐색 트리의 Root Node

	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) );
	// 현재 트리 상태

	//                 123
	//             22       9918
	//           17  98   424
	//          3       317  760
	//         1

	printf(" - Current Data...\n");
	BST_InorderPrintTree(Tree);
	printf("\n");

	// 특정 노드 삭제 Test

	// 삭제할 노드가 자식이 둘다 있는 경우
	printf("  - Remove 123 Node...\n");	
	BST_DestroyNode(BST_RemoveNode(Tree,NULL,123));
	BST_InorderPrintTree(Tree);
	printf("\n");
	// 현재 트리 상태
	//                 317
	//             22       9918
	//           17  98   424
	//          3            760
	//         1
	// - 이때에 원래 삭제될 노드였던 123 노드의 Data가 317로 바뀌고, 실제로 삭제되는 노드는
	//  원래의 317 노드가 된다.

	// 삭제할 노드가 자식이 하나만 있는 경우
	printf("  - Remove 17 Node...\n");	
	BST_DestroyNode(BST_RemoveNode(Tree,NULL,17));
	BST_InorderPrintTree(Tree);
	printf("\n");

	// 현재 트리 상태
	//                 317
	//             22       9918
	//           3  98    424
	//         1            760
	//         
	
	// 삭제할 노드가 잎 노드인 경우
	printf("  - Remove 760 Node...\n");	
	BST_DestroyNode(BST_RemoveNode(Tree,NULL,760));
	BST_InorderPrintTree(Tree);
	printf("\n");
	// 현재 트리 상태
	//                 317
	//             22       9918
	//           3  98    424
	//         1           
	//

	BST_DestroyTree(Tree);		

	return 0;
}

---------------------------------------------------------

실행결과