Skip to content

Instantly share code, notes, and snippets.

@hanjae-jea
Created June 15, 2013 00:26
Show Gist options
  • Save hanjae-jea/5786240 to your computer and use it in GitHub Desktop.
Save hanjae-jea/5786240 to your computer and use it in GitHub Desktop.
소스 코드에 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…
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment