과제로부터해방된RBT

참고!
아래 파일은 한개의 C파일과 4개의 헤더파일로 구성되어 있음!

MAIN.C

#include <stdio.h>
#include "node.h"
#include "insertion.h"
#include "rotation.h"
#include "correctTree.h"

int main(void)
{
	//루트노드
	rbnode root;
	//삽입버퍼노드
	rbnode val;
	//NIL 노드
	rbnode nil;
	int input;

	//NIL 할당
	nil = create_nil();
	//첫 루트노드는 NIL
	root = nil;

	int i = 0, size = 0, sk = 0, ch = 0;
	printf("Enter the number of input data in RBT\n");
	scanf_s("%d", &size);
	printf("---------\n");

	//사이즈만큼 반복하여 노드 생성
	while (i < size) {
		printf("Enter data in RBT\n");
		scanf_s("%d", &input);
		printf("---------\n");
		printf("Key=%3d\n", input);

		//노드 할당
		val = create_node(input, nil);
		//노드 삽입
		root = rb_insert(root, val, nil);
		printf("---------\n\n");
		i++;
	}
	//메뉴 구성
	while (1) {
		printf("\n1. Display\t2. Exit\t\t3.Search\n");
		printf("Enter your choice:");
		scanf_s("%d", &ch);

		switch (ch) {
		case 1:
			//display
			printf("\n* display RB tree*\n");
			printf("----------------------------------------------------------------------\n");
			inorder(root, nil);
			printf("----------------------------------------------------------------------\n");
			break;
		case 2:
			//exit
			free(root);
			free(val);
			free(nil);
			exit(0);
			break;
		case 3:
			//search
			printf("Enter the Data value:");
			scanf_s("%d", &sk);
			if (searchNode(root,nil,sk)) {
				printf("the Data %d is found!\n",sk);
			}
			else {
				printf("Sorry, Search Failed..\n");
			}
			printf("\n");
			break;
		default:
			printf("wrong option!!\n");
			break;
		}

	}


	return 0;
}



---------------------------------------------------------------------------------------------------------
CORRECTTREE.H

#pragma once
#include "node.h"
#include "rotation.h"
//정렬 함수 및 검색 함수 헤더(로테이션,노드 의존)
rbnode fix(rbnode root, rbnode input, rbnode nil)
{
	rbnode uncle;
	while (input->p->color == RED) {
		//부모의 색이 빨강색인 경우
		if ((input->p) == (input->p->p->left)) {
			//
			uncle = input->p->p->right;
			if (uncle->color == RED) {
				input->p->color = BLACK;
				uncle->color = BLACK;
				input->p->p->color = RED;

				input = input->p->p;
			}
			else {
				if (input == input->p->right) {
					input = input->p;
					root = left_rotate(root, input, nil);
				}
				input->p->color = BLACK;
				input->p->p->color = RED;
				root = right_rotate(root, input->p->p, nil);
			}
		}
		else {
			uncle = input->p->p->left;
			if (uncle->color == RED) {
				input->p->color = BLACK;
				uncle->color = BLACK;
				input->p->p->color = RED;

				input = input->p->p;
			}
			else {
				if (input == input->p->left) {
					input = input->p;
					root = right_rotate(root, input, nil);
				}
				input->p->color = BLACK;
				input->p->p->color = RED;
				root = left_rotate(root, input->p->p, nil);
			}
		}
	}
	root->color = BLACK;
	//루트 노드를 리턴!
	return root;
}
int searchNode(rbnode root,rbnode nil, int sk) {
	//검색 실패시 0(false), 성공시 1(true)
	if (root->key == sk) {
		//검색 성공
		return 1;
	}
	if (root == nil) {
		//검색 실패
		return 0;
	}
	//재귀하며 계속 검색
	if (sk < root->key) {
		return searchNode(root->left, nil, sk);
	}
	else {
		return searchNode(root->right, nil, sk);
	}
}





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

INSERTION.H

#pragma once
#include "node.h"
#include "correctTree.h"
//트리에 노드삽입함수 관련 정의 헤더(정렬 함수, 노드 의존)
rbnode rb_insert(rbnode root, rbnode input, rbnode nil) {
	rbnode tree = nil;
	rbnode r = root;

	while (r != nil) {
		tree = r;
		if ((input->key) < (r->key))
			r = r->left;
		else
			r = r->right;
	}

	input->p = tree;

	if (tree == nil)
		root = input;
	else if ((input->key) < (tree->key))
		tree->left = input;
	else
		tree->right = input;

	input->left = nil;
	input->right = nil;
	input->color = RED;
	//루트 노드를 받아 다시 리턴!
	return fix(root, input, nil);
}




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

NODE.H

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

enum COLOR { RED, BLACK };
typedef enum COLOR COLOR;
//노드 생성과 노드 출력, 노드 검사 헤더


struct node
{
	int    key;
	COLOR   color;
	struct node* left;
	struct node* right;
	struct node* p;
};

typedef struct node NODE;
typedef NODE* rbnode;

rbnode create_node(int input, rbnode nil)
{
	//노드할당함수
	rbnode newNode = (rbnode)malloc(sizeof(NODE));
	newNode->key = input;
	//노드끝은 항상 NIL로 수렴
	newNode->left = nil;
	newNode->right = nil;
	newNode->p = nil;

	return newNode;
}

rbnode create_nil()
{
	//NIL노드할당함수
	rbnode nil = (rbnode)malloc(sizeof(NODE));
	//키값은 0
	nil->key = 0;
	//NULL 포인터
	nil->left = NULL;
	nil->right = NULL;
	nil->p = NULL;
	//NIL은 검은색으로 처리
	nil->color = BLACK;

	return nil;
}

void inorder(rbnode root, rbnode nil)
{
	//중위순회를 이용한 출력함수
	//LEFT,DRIVE,RIGHT(LDR)
	if (root != nil)
	{
		inorder(root->left, nil);
		printf("left child <%2d> - root<%2d> - <%2d> right child \n parent of root :\
			%2d , color : %4s\n\n", root->left->key, root->key, root->right->key,
			root->p->key, (root->color == RED) ? "red" : "black");
		inorder(root->right, nil);
	}

}






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

ROTATION.H

#pragma once
#include "node.h"
//노드 정렬시 로테이션 함수 정의 헤더(노드 의존)
rbnode left_rotate(rbnode root, rbnode node, rbnode nil) {
	//node변수 위치가 가운데로 가게 됨.
	rbnode tmp = node->right;
	node->right = tmp->left;

	if (tmp->left != nil)
		tmp->left->p = node;

	tmp->p = node->p;
	if (node->p == nil) root = tmp;
	else if (node == node->p->left)
		node->p->left = tmp;
	else
		node->p->right = tmp;

	tmp->left = node;
	node->p = tmp;

	return root;

}

rbnode right_rotate(rbnode root, rbnode node, rbnode nil) {
	rbnode tmp = node->left;
	node->left = tmp->right;

	if (tmp->right != nil)
		tmp->right->p = node;

	tmp->p = node->p;
	if (node->p == nil) root = tmp;
	else if (node == node->p->right)
		node->p->right = tmp;
	else
		node->p->left = tmp;

	tmp->right = node;
	node->p = tmp;

	return root;

}