[ 자료구조 ] 탐색 - 04 - 3 . 레드 블랙 트리 <구현>

 

[RBT.h]

#ifndef RBT
#define RBT

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

typedef int ElementType;

enum NodeColor
{
	Red,
	Black
};
typedef struct tagRBTNode
{
	//부모
	struct tagRBTNode* Parent;
	//왼쪽 자식
	struct tagRBTNode* Left;
	//오른쪽 자식
	struct tagRBTNode* Right;
	//색
	NodeColor Color;
	//데이터
	ElementType Data;

}RBTNode;

//트리의 삭제
void RBT_DestroyTree(RBTNode* Tree);
//노드의 생성
RBTNode* RBT_CreateNode(ElementType NewData);
//노드의 소멸
void RBT_DestroyNode(RBTNode* Destroy);
//노드의 출력
void RBT_PrintTree(RBTNode* Node, int Depth, int BlockCount);

//노드의 탐색
RBTNode* RBT_SearchNode(RBTNode* Tree, ElementType Target);
//최소노드의 탐색
RBTNode* RBT_SearchMinNode(RBTNode* Tree);

//노드의 삽입
void RBT_InsertNode(RBTNode** Tree, RBTNode* NewNode);
void RBT_InsertNodeHelper(RBTNode** Tree, RBTNode* NewNode);
void RBT_RebuildAfterInsert(RBTNode** Root, RBTNode* NewNode);

//노드의 삭제
RBTNode* RBT_RemoveNode(RBTNode** Root, ElementType Data);
void RBT_RebuildAfterRemove(RBTNode** Root, RBTNode* X);

//좌회전
void RBT_RotateRight(RBTNode** Root, RBTNode* Parent);
// 우회전
void RBT_RotateLeft(RBTNode** Root, RBTNode* Parent);

#endif

[RBT.cpp]

#include"RBT.h"

//잎노드 (전역선언 되어있는 더미)
extern RBTNode* Nil;

#pragma region 기본메서드

//트리의 삭제
void RBT_DestroyTree(RBTNode* Tree)
{
	if (Tree->Right != Nil)
		RBT_DestroyTree(Tree->Right);

	if (Tree->Left != Nil)
		RBT_DestroyTree(Tree->Left);

	Tree->Left = Nil;
	Tree->Right = Nil;
	RBT_DestroyNode(Tree);
}
//노드의 생성
RBTNode* RBT_CreateNode(ElementType NewData)
{
	RBTNode* NewNode = (RBTNode*)malloc(sizeof(RBTNode));
	NewNode->Parent = NULL;
	NewNode->Left = NULL;
	NewNode->Right = NULL;
	NewNode->Color = Black;
	return NewNode;
}
//노드의 소멸
void RBT_DestroyNode(RBTNode* Destroy)
{
	free(Destroy);
}
//노드의 출력
void RBT_PrintTree(RBTNode* Node, int Depth, int BlackCount)
{
	int i = 0;
	char c = 'X';
	int v = -1;
	char cnt[100];

	if (Node == NULL || Node == Nil)
		return;
	if (Node->Color == Black)
		BlackCount++;
	//부모가 있을떄
	if (Node->Parent != NULL)
	{
		//부모 표시
		v = Node->Parent->Data;
		//방향표시
		if (Node->Parent->Left == Node)
			c = 'L';
		else
			c = 'R';
	}
	//문자열에 저장

	if (Node->Left == Nil && Node->Right == Nil)
		sprintf_s(cnt, "------- %d", BlackCount);
	else
		sprintf_s(cnt, "");


	//노드번호 / 노드색상 / [부모의 왼쪽 오른쪽 여부,부모번호]
	printf("%d %s [%c,%d] %s\n", Node->Data, (Node->Color == Red) ? "Red" : "Black", c, v, cnt);

	RBT_PrintTree(Node->Left, Depth + 1, BlackCount);
	RBT_PrintTree(Node->Right, Depth + 1, BlackCount);
}

#pragma endregion

#pragma region 탐색

//노드의 탐색
RBTNode* RBT_SearchNode(RBTNode* Tree, ElementType Target)
{
	if (Tree == Nil)
		return NULL;

	//우측탐색진행
	if (Tree->Data < Target)
		return RBT_SearchNode(Tree->Right, Target);
	//좌측탐색진행
	else if (Tree->Data > Target)
		return RBT_SearchNode(Tree->Left, Target);
	//데이터를 찾았다면
	return Tree;
}

//최소노드의 탐색
RBTNode* RNT_SearchMinNode(RBTNode* Tree)
{
	if (Tree == Nil)
		return Nil;

	//최소노드라면 잎노드를 반환
	if (Tree->Left == Nil)
		return Tree;
	else
		//아니라면 좌측 자식에서 다시 탐색
		return RNT_SearchMinNode(Tree->Left);
}

#pragma endregion

#pragma region 삽입

//노드의 삽입
void RBT_InsertNode(RBTNode** Tree, RBTNode* NewNode)
{
	//노드에 삽입
	RBT_InsertNodeHelper(Tree, NewNode);

	//세팅
	NewNode->Left = Nil;
	NewNode->Right = Nil;
	NewNode->Color = Red;

	//규칙의 재정립
	RBT_RebuildAfterInsert(Tree, NewNode);
}
void RBT_InsertNodeHelper(RBTNode** Tree, RBTNode* NewNode)
{
	if ((*Tree) == NULL)
		(*Tree) = NewNode;

	//새 노드의 데이터가 트리의 데이터보다 작다면
	if ((*Tree)->Data > NewNode->Data)
	{
		//왼쪽에 자식이 없다면
		if ((*Tree)->Left == Nil)
		{
			(*Tree)->Left = NewNode;
			NewNode->Parent = (*Tree);
		}
		//자식이 있다면
		else
		{
			//재탐색
			RBT_InsertNodeHelper(&(*Tree)->Left, NewNode);
		}
	}
	//새 노드의 데이터가 트리의 데이터보다 크다면
	else if ((*Tree)->Data < NewNode->Data)
	{
		//오른쪽에 자식이 없다면
		if ((*Tree)->Right == Nil)
		{
			(*Tree)->Right = NewNode;
			NewNode->Parent = (*Tree);
		}
		//자식이 있다면
		else
		{
			//재탐색
			RBT_InsertNodeHelper(&(*Tree)->Right, NewNode);
		}
	}
	//같다면
	else
	{
		//왼쪽에서 재탐색
		RBT_InsertNodeHelper(&(*Tree)->Left, NewNode);
	}
}
void RBT_RebuildAfterInsert(RBTNode** Root, RBTNode* NewNode)
{
	//부모의 색이 검정이거나 새 노드가 루트라면 그만한다.
	while (NewNode != (*Root) && NewNode->Parent->Color == Red)
	{
		//부모가 좌측 자식이라면
		if (NewNode->Parent == NewNode->Parent->Parent->Left)
		{
			//삼촌은 우측자식
			RBTNode* Uncle = NewNode->Parent->Right;
#pragma region 삼촌이 빨간색
			//경우 1 : 삼촌의 색이 빨강일때
			if (Uncle->Color == Red)
			{
				//부모와 삼촌을 검정색으로 칠한다
				NewNode->Parent->Color = Black;
				Uncle->Color = Black;
				//할아버지를 빨간색으로 칠한다
				NewNode->Parent->Parent->Color = Red;
				//할아버지를 빨간색으로 칠했기에 할아버지를 새로 삽입한 
				//노드로 규정 , 규칙을 다시 살핀다
				NewNode = NewNode->Parent->Parent;
			}
#pragma endregion

#pragma region 삼촌이 검정색
			else
			{
				//경우2: 새로 삽입한 노드가 부모의 오른쪽자식 :
				//이 경우 문제를 새로 삽입한 노드가 부모의 왼쪽 자식으로 바꾼다
				if (NewNode == NewNode->Parent->Right)
				{
					//부모를 새로 삽입한 노드로 가정하고
					NewNode = NewNode->Parent;
					//좌회전 - 이때 새로 삽입합 노드는(부모였던)는 부모의 왼쪽자식이 된다
					RBT_RotateLeft(Root, NewNode);
				}

				//경우3: 새로 삽입한 노드가 부모의 왼쪽자식- 루트잎사이 검정노드 개수 유지를 위해
				//부모를 검정색으로
				NewNode->Parent->Color = Black;
				//할아버지를 빨간색으로
				NewNode->Parent->Parent->Color = Red;
				//부모를 할아버지의 위치로(왼->오)
				RBT_RotateRight(Root, NewNode->Parent->Parent);
			}
#pragma endregion

		}
		//부모가 우측 자식이라면
		{
			//삼촌은 좌측자식
			RBTNode* Uncle = NewNode->Parent->Left;
#pragma region 삼촌이 빨간색
			//경우 1 : 삼촌의 색이 빨강일때
			if (Uncle->Color == Red)
			{
				//부모와 삼촌을 검정색으로 칠한다
				NewNode->Parent->Color = Black;
				Uncle->Color = Black;
				//할아버지를 빨간색으로 칠한다
				NewNode->Parent->Parent->Color = Red;
				//할아버지를 빨간색으로 칠했기에 할아버지를 새로 삽입한 
				//노드로 규정 , 규칙을 다시 살핀다
				NewNode = NewNode->Parent->Parent;
			}
#pragma endregion

#pragma region 삼촌이 검정색
			else
			{
				//경우2: 새로 삽입한 노드가 부모의 왼쪽자식 :
				//이 경우 문제를 새로 삽입한 노드가 부모의 오른쪽 자식으로 바꾼다
				if (NewNode == NewNode->Parent->Left)
				{
					//부모를 새로 삽입한 노드로 가정하고
					NewNode = NewNode->Parent;
					//우회전 - 이때 새로 삽입합 노드는(부모였던)는 부모의 오른쪽자식이 된다
					RBT_RotateRight(Root, NewNode);
				}

				//경우3: 새로 삽입한 노드가 부모의 오른쪽자식 - 루트잎사이 검정노드 개수 유지를 위해
				//부모를 검정색으로
				NewNode->Parent->Color = Black;
				//할아버지를 빨간색으로
				NewNode->Parent->Parent->Color = Red;
				//부모를 할아버지의 위치로(오->왼)
				RBT_RotateLeft(Root, NewNode->Parent->Parent);
			}
#pragma endregion
		}
	}
}

#pragma endregion

#pragma region 삭제

//노드의 삭제
RBTNode* RBT_RemoveNode(RBTNode** Root, ElementType Data)
{
	//삭제될 노드
	RBTNode* Removed = NULL;
	//대체노드
	RBTNode* Successor = NULL;
	//삭제 대상
	RBTNode* Target = RBT_SearchNode((*Root), Data);

	if (Target == NULL)
		return NULL;

#pragma region 삭제대상 정하기
	//삭제대상이 한쪽만자식이 있거나 없는 경우
	if (Target->Left == Nil || Target->Right == Nil)
	{
		//타겟이 삭제대상
		Removed = Target;
	}
	//자식이 모두 있는 경우
	{
		//삭제대상은 우측자식에서 최소노드를 찾아 넣어준다
		Removed = RBT_SearchMinNode(Target->Right);
		//최소값 노드의 값을 타겟노드에 넣어준다
		Target->Data = Removed->Data;
	}
#pragma endregion

#pragma region 대체노드 정하기
	//왼쪽자식이 있을때
	if (Removed->Left != Nil)
		//대체노드는 왼쪽 자식
		Successor = Removed->Left;
	else//(삭제대상은 자식이 둘 다 있을 수 없다 (최소값 노드는 왼쪽 자식이 없기에))
		//대체노드는 오른쪽 자식
		Successor = Removed->Right;
#pragma endregion

#pragma region 대체노드와 부모노드 연결
	//대체노드와 부모 연결
	Successor->Parent = Removed->Parent;

	//부모와 대체노드 연결
	//삭제노드가 루트였다면
	if (Removed->Parent == NULL)
		(*Root) = Successor;
	else
	{
		//삭제노드의 위치에 맞게 대체노드를 넣어준다
		if (Removed == Removed->Parent->Left)
			Removed->Parent->Left = Successor;
		else
			Removed->Parent->Right = Successor;
	}
#pragma endregion

#pragma region RBT규칙의 재조립
	//만약 삭제노드의 색이 검정이라면 
	if (Removed->Color == Black)
		RBT_RebuildAfterRemove(Root, Successor);
#pragma endregion

	return Removed;
}
void RBT_RebuildAfterRemove(RBTNode** Root, RBTNode* Successor)
{
	//받은 대체노드는 이중흑색 노드이기도 하다
	//형제노드
	RBTNode* Sibling = NULL;

	while (Successor->Parent != NULL && Successor->Color == Black)
	{
		//대체노드가 부모의 좌측자식일때
		if (Successor == Successor->Parent->Left)
		{
			//형제노드는 부모의 우측자식
			Sibling = Successor->Parent->Right;

#pragma region 형제의 색이 빨강일떄
			if (Sibling->Color == Red)
			{
				//삼촌을 검정색으로
				Sibling->Color = Black;
				//부모를 빨간색으로
				Successor->Parent->Color = Red;
				//부모를 기준으로 좌회전
				RBT_RotateLeft(Root, Successor->Parent);
				//이제 문제는 형제가 검정색일때로 변경됨
			}
#pragma endregion

#pragma region 형제의 색이 검정일떄
			else
			{
				//형제의 자식이 모두 검정일때(삼촌이 잎일때도 포합)
				if (Sibling->Left->Color == Black && Sibling->Right->Color == Black)
				{
					//형제를 빨간색으로 칠하고
					Sibling->Color = Red;
					//부모에게 이중흑색을 넘긴다(부모가 빨강이라면 검은색을 칠하고 종료)
					//아니라면 다시 탐색
					Successor = Successor->Parent;
				}
				else
				{
					//형제의 왼쪽 자식이 빨간색일때 (오른쪽이 검정색일때)
					if (Sibling->Left->Color == Red)
					{
						//왼쪽 자식을 검정색으로 칠한다
						Sibling->Left->Color = Black;
						//형제를 빨간색으로 칠한다
						Sibling->Color = Red;
						//형제를 우회전한다 .
						RBT_RotateRight(Root, Sibling);
						//형제를 다시 등록한다 .
						Sibling = Successor->Parent->Right;
						//이 결과 해당 문제는 형제의 오른쪽 자식이 빨강,왼쪽이 검정으로 변경
					}
					//형제의 오른쪽 자식이 빨간색일때 (왼쪽이 검정색일때)
					//형제 노드에 부모의 색을 칠한다
					Sibling->Color = Successor->Parent->Color;
					//부모는 검정색으로 칠한다
					Successor->Parent->Color = Black;
					//형제노드의 오른쪽 자식에 검정색을 칠한다
					Sibling->Right->Color = Black;
					//대체노드의 부모를 기준으로 좌회전
					RBT_RotateLeft(Root, Successor->Parent);
					//이중흑색을 루트에 넘긴다
					Successor = (*Root);
				}
			}
#pragma endregion 
		}
		//대체노드가 부모의 우측자식일때
		else
		{
			//형제노드는 부모의 좌측자식
			Sibling = Successor->Parent->Left;

#pragma region 형제의 색이 빨강일떄
			if (Sibling->Color == Red)
			{
				//형제를 검정색으로
				Sibling->Color = Black;
				//부모를 빨간색으로
				Successor->Parent->Color = Red;
				//부모를 기준으로 우회전
				RBT_RotateRight(Root, Successor->Parent);
				//이제 문제는 형제가 검정색일때로 변경됨
			}
#pragma endregion

#pragma region 형제의 색이 검정일떄
			else
			{
				//형제의 자식이 모두 검정일때(형제가 잎일때도 포합)
				if (Sibling->Left->Color == Black && Sibling->Right->Color == Black)
				{
					//형제를 빨간색으로 칠하고
					Sibling->Color = Red;
					//부모에게 이중흑색을 넘긴다(부모가 빨강이라면 검은색을 칠하고 종료)
					//아니라면 다시 탐색
					Successor = Successor->Parent;
				}
				else
				{
					//형제의 오른쪽 자식이 빨간색일때 (왼쪽이 검정색일때)
					if (Sibling->Right->Color == Red)
					{
						//오른쪽 자식을 검정색으로 칠한다
						Sibling->Right->Color = Black;
						//형제를 빨간색으로 칠한다
						Sibling->Color = Red;
						//형제를 좌회전한다 .
						RBT_RotateRight(Root, Sibling);
						//형제를 다시 등록한다 .
						Sibling = Successor->Parent->Left;
						//이 결과 해당 문제는 형제의 왼쪽 자식이 빨강,오른쪽이 검정으로 변경
					}
					//형제의 왼쪽 자식이 빨간색일때 (오른쪽이 검정색일때)
					//형제 노드에 부모의 색을 칠한다
					Sibling->Color = Successor->Parent->Color;
					//부모는 검정색으로 칠한다
					Successor->Parent->Color = Black;
					//형제노드의 왼쪽 자식에 검정색을 칠한다
					Sibling->Left->Color = Black;
					//대체노드의 부모를 기준으로 우회전
					RBT_RotateRight(Root, Successor->Parent);
					//이중흑색을 루트에 넘긴다
					Successor = (*Root);
				}
			}
#pragma endregion 
		}
	}
	//대체노드의 색을 검정으로 칠한다
	Successor->Color = Black;
}

#pragma endregion

#pragma region 회전

// 우회전 (좌측자식이 부모의 위치로 이동)
void RBT_RotateRight(RBTNode** Root, RBTNode* Parent)
{
	RBTNode* LeftChlid = Parent->Left;
	//부모의 왼쪽자식으로 왼쪽자식의 오른쪽자식을 넣어준다
	Parent->Left = LeftChlid->Right;

	//왼쪽자식의 오른쪽자식이 있었다면 부모를 변경
	if (LeftChlid->Right != Nil)
		LeftChlid->Right->Parent = Parent;

	//좌측자식의 부모를 조부모로 변경
	LeftChlid->Parent = Parent->Parent;
	//부모가 루트였다면 루트로 변경
	if (Parent->Parent == NULL)
		(*Root) = LeftChlid;
	else
	{
		//부모의 그전 위치에 넣어준다
		if (Parent == Parent->Parent->Right)
			Parent->Parent->Right = LeftChlid;
		else
			Parent->Parent->Left = LeftChlid;
	}
	//부모와 좌측자식을 연결
	LeftChlid->Right = Parent;
	Parent->Parent = LeftChlid;
}

// 좌회전 - (우측자식이 부모의 위치로 이동)
void RBT_RotateLeft(RBTNode** Root, RBTNode* Parent)
{
	RBTNode* RightChlid = Parent->Left;
	//부모의 오른쪽자식으로 오른쪽자식의 왼쪽자식을 넣어준다
	Parent->Right = RightChlid->Left;

	//오쪽자식의 왼쪽자식이 있었다면 부모를 변경
	if (RightChlid->Left != Nil)
		RightChlid->Left->Parent = Parent;

	//우측자식의 부모를 조부모로 변경
	RightChlid->Parent = Parent->Parent;
	//부모가 루트였다면 루트로 변경
	if (Parent->Parent == NULL)
		(*Root) = RightChlid;
	else
	{
		//부모의 그전 위치에 넣어준다
		if (Parent == Parent->Parent->Right)
			Parent->Parent->Right = RightChlid;
		else
			Parent->Parent->Left = RightChlid;
	}
	//부모와 우측자식을 연결
	RightChlid->Left = Parent;
	Parent->Parent = RightChlid;
}

#pragma endregion

[Test.cpp]

#include"RBT.h"
RBTNode* Nil;

int main(void)
{
	RBTNode* Tree = NULL;
	RBTNode* Node = NULL;
	Nil = RBT_CreateNode(0);
	Nil->Color = Black;

	while (true)
	{
		int cmd = 0;
		int param = 0;
		char buffer[10];

		printf("Enter command number : \n");
		printf("(1) : CreateNode , (2) : RemoveNode , (3) : SearchNode\n");
		printf("(4) : DisplayTree , (5) Quit \n");
		printf("Command Number");

		fgets(buffer, sizeof(buffer) - 1, stdin);
		sscanf(buffer, "%d", &cmd);

		if (cmd < 1 || cmd>5)
		{
			printf("잘못된 번호입니다");
			continue;
		}
		else if (cmd == 4)
		{
			RBT_PrintTree(Tree, 0, 0);
			printf("\n");
			continue;
		}
		else if (cmd == 5)
			break;

		printf("Enter Params (1~2000):\n");
		fgets(buffer, sizeof(buffer) - 1, stdin);
		sscanf(buffer, "%d", &param);

		if (param < 1 || param>200)
		{
			printf("잘못된 번호입니다 : %d\n", param);
			continue;
		}

		switch (cmd)
		{
		case 1:
			RBT_InsertNode(&Tree,RBT_CreateNode(param));
			break;
		case 2:
			Node = RBT_RemoveNode(&Tree, param);
			if (Node == NULL)
				printf("삭제할 노드가 없습니다 : %d\n", param);
			else
				RBT_DestroyNode(Node);
			break;
		case 3:
			Node = RBT_SearchNode(Tree, param);

			if (Node == NULL)
				printf("찾는 노드가 없습니다 : %d\n", param);
			else
				printf("찾았습니다 : %d (Color : %s)\n", Node->Data, Node->Color ? "Red" : "Black");
			break;
		}
		printf("\n");
	}
	RBT_DestroyTree(Tree);
	return 0;
}