소스 코드에 Test_Tree(Tree* , rb_insert 함수 이름, rb_delete 함수 이름만 적어서 호출하면 쓰실 수 있습당.) ex) Test_Tree(tree, rb_insert, rb_delete); rb_insert(Tree *tree, Node *z), rb_delete(Tree *tree, Node *z) 이렇게 구현만 되어있음 됩니다... HW#14 Special 과제인 Red-Black Tree Visual Test Code입니다. 본 HW#14.c 코드의 같은 파일에 저장하신 후에 #include "파일이름.h"을 본 코드에 추가해주면 됩니다. 이 코드를 집어넣을때 주의하실건 #incl…

Red_Black_tree_visualization_test.h

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

enum rb {red, black};

typedef struct node {
    int key;
	enum rb color;
	struct node *left;
	struct node *right;
	struct node *parent;
}Node;

typedef struct tree {
	struct node *root;
	struct node *nil;
}Tree;

typedef struct print{
	int key;
	int level;
	enum rb color;
}Print;

int c = 0;

void Test_Tree(Tree* tree, void (*insert)(Tree *tree, Node *z), void *(deleteion)(Tree *tree, Node *z));
void tree_print(Tree* tree, Print *label);
void tree_travel(Tree* tree, Node* node, int level, Print *label);
int check_rb_variable(Tree* tree);
int check_rb_value_include(Tree* tree, int value);	// in : 1 , not inclueded : 0
int check_in_rb_value(Tree* tree, Node* node, int key);
Node* find_key_chked(Tree* tree, int value);
void log_print(int *logging, int logCount, FILE *out);
int check_rb_black_count(Tree *tree, Node *node);
int check_rb_black_child(Tree *tree, Node *node);

void Test_Tree(Tree *tree, void (*insert)(Tree *tree, Node *z), void *(deletion)(Tree *tree, Node *z))
{
	FILE *log_out = fopen("Log.txt","a");
	Node *node;
	Print *label = (Print*)malloc(sizeof(Print));
	int *logging = (int*)malloc(sizeof(int));
	int key, in, nodeCount = 0, logCount = 0;
	while( 1 ){
		SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 15); // [White:Black]
		printf("Node의 key를 입력해주세요 = ");
		if( scanf("%d",&key) == EOF || key == -1 ) break;
		
		c = 0;
		if( check_rb_value_include(tree, key) == 1 ){  // delete
			// init
			logging[logCount] = -key;
			
			logging = (int*)realloc(logging, sizeof(int)*(++logCount));
			label = (Print*)realloc(label, sizeof(Print)*(--nodeCount));

			deletion(tree, find_key_chked(tree, key));
		}
		else{								// insert
			node = (Node*)malloc(sizeof(Node));
			node->key = key;

			logging[logCount] = key;

			logging = (int*)realloc(logging, sizeof(int)*(++logCount));
			label = (Print*)realloc(label, sizeof(Print)*(++nodeCount));

			insert(tree, node);
		}

		tree_print(tree, label);

		
		SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), 15); // [White:Black]
		printf("\n");

		if( check_rb_variable(tree) == FALSE ){
			printf("Your Red-Black Tree is Broken!\n");
			printf("Printing your log files...\n");
			fprintf(log_out,"YOUR Tree Status------------------\n");
			tree_print(tree, label);
			fprintf(log_out,"Input Log ------------------------\n");
			log_print(logging, logCount, log_out);
			fclose(log_out);
			system("Log.txt");
			exit(0);
		}
	}
}

void tree_print(Tree *tree, Print *label)
{
	int i,j, flag;
	HANDLE consoleHandle = GetStdHandle(STD_OUTPUT_HANDLE);
	SetConsoleTextAttribute(consoleHandle, 15*16);

	if( tree->root != tree->nil )
		tree_travel(tree, tree->root, 0, label);
	// color Code : 252 [Red:White] , 240 [Black:White]
	for( i = 0 ; ; i ++ ){
		flag = 0;
		for( j = 0 ; j < c ; j ++ ){
			
			if( label[j].level == i ){
				if( label[j].color == red ) SetConsoleTextAttribute(consoleHandle, 252 );
				else SetConsoleTextAttribute( consoleHandle, 240 );
				printf("%-3d", label[j].key);
				flag = 1;
			}
			else
				printf("%3c",' ');
		}
		for( ; j < 24 ; j ++ ){
			printf("%3c",' ');
		}
		if( flag == 0 ) break;
		printf("\n");
	}
}

void tree_travel(Tree *tree, Node *node, int level, Print *label)
{	
	if( node == tree->nil ) return;

	tree_travel(tree,node->left,level+1, label);

	label[c].key = node->key;
	label[c].level = level;
	label[c].color = node->color;
	c++;


	tree_travel(tree,node->right, level+1, label);
}

int check_rb_variable(Tree *tree)
{
	if( tree->root == tree->nil ) return TRUE;
	// root -> leaf black Count
	if( check_rb_black_count(tree, tree->root) == FALSE ) return FALSE;
	// red -> black Child
	if( check_rb_black_child(tree, tree->root) == FALSE ) return FALSE;
	return TRUE;
}

int check_rb_value_include(Tree *tree, int value)
{
	if( tree->root != tree->nil )
		return check_in_rb_value(tree,tree->root, value);
	return 0;
}

int check_in_rb_value(Tree *tree, Node* node, int key)
{
	if( node == tree->nil ) return 0;
	if( node->key > key )
		return check_in_rb_value(tree, node->left, key);
	else if( node->key < key )
		return check_in_rb_value(tree, node->right, key);
	else return 1;
}

Node* find_key_chked(Tree* tree, int value)
{
	Node *curNode = tree->root;
	while( curNode->key != value ){
		if( curNode->key > value )
			curNode = curNode->left;
		else 
			curNode = curNode->right;
	}
	return curNode;
}

void log_print(int *logging, int logCount, FILE *out)
{
	int i;
	for( i = 0 ; i < logCount ; i ++ ){
		if( logging[i] < 0 ) 
			fprintf(out,"#%-3dDELETE : %d\n", i, -logging[i]);
		else
			fprintf(out,"#%-3dINSERT : %d\n", i, logging[i]);
	}

}

int check_rb_black_count(Tree* tree, Node* node)
{
	int left, right;
	if( node == tree->nil ) return 1;
	left = check_rb_black_count(tree, node->left);
	right = check_rb_black_count(tree, node->right);
	if( left != FALSE && left == right )
		return left + (node->color==black?1:0);
	return FALSE;
}

int check_rb_black_child(Tree *tree, Node* node)
{
	if( node == tree->nil ) return TRUE;
	else if( !check_rb_black_child(tree, node->left) || !check_rb_black_child(tree, node->right) ) return FALSE;
	else if( node->color == black ) return TRUE;
	else if( node->left->color == black && node->right->color == black ) return TRUE;
	else return FALSE;
}