Created
June 15, 2013 00:26
-
-
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…
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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