[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", ¶m);
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;
}
'자료구조' 카테고리의 다른 글
[자료구조] 우선순위 큐와 힙 - 02 . 힙 구현 (0) | 2023.03.31 |
---|---|
[자료구조] 우선순위 큐와 힙 - 01 . 우선순위 큐와 힙 (0) | 2023.03.30 |
[ 자료구조 ] 탐색 - 04 - 2 . 레드 블랙 트리 <삭제> (0) | 2023.03.10 |
[ 자료구조 ] 탐색 - 04 - 1 . 레드 블랙 트리 <회전 , 삽입> (0) | 2023.03.07 |
[ 자료구조 ] 탐색 - 03 . 이진 탐색 트리 (0) | 2023.03.07 |