/* Author: Leonardone @ NEETSDKASU */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef enum _bool { False, True = !False } Bool, *LPBool;
typedef enum _color { Black, Red } Color, *LPColor;

typedef struct _node {
	Color color;
	struct _node *left;
	struct _node *right;
	int key;
} Node, *LPNode;

typedef struct _tree{
	LPNode root;
} Tree, *LPTree;

LPTree initTree(LPTree tree);
LPTree addTreeValue(LPTree tree, int value);
Bool isRed(LPNode node);
void turnColor(LPNode node);
LPNode newNode(int key);
LPNode addNode(LPNode node, LPNode newnode);
LPNode checkRight(LPNode node);
LPNode checkLeft(LPNode node);

void printCharString(char c, int n);
void printNode(LPNode node, int depth, char c);
void printTree(LPTree tree);

int main(void) {
	
	Tree tree;
	int i;
	
	srand(time(NULL));
	
	initTree(&tree);
	
	for (i = 1; i < 55; i++) {
		addTreeValue(&tree, rand() % 100);
	}
	
	printTree(&tree);
	
	return 0;
}

void printCharString(char c, int n) {
	while (n-- > 0) {
		putchar(c);
	}
}

void printNode(LPNode node, int depth, char c) {
	if (node == NULL) {
		//printCharString(' ', depth * 5);
		//puts("null");
		return;
	}
	printNode(node->right, depth + 1, '/');
	printCharString(' ', depth * 5);
	putchar(c);
	putchar(isRed(node) ? 'R' : 'B');
	printf("%02d\n", node->key);
	printNode(node->left, depth + 1, '\\');
}

void printTree(LPTree tree) {
	if (tree == NULL) {
		puts("NULL");
	}
	printNode(tree->root, 0, '-');
}

LPTree initTree(LPTree tree) {
	if (tree != NULL) {
		tree->root = NULL;
	}
	return tree;
}

LPTree addTreeValue(LPTree tree, int value) {
	if (tree != NULL) {
		tree->root = addNode(tree->root, newNode(value));
		if (tree->root->color == Red) {
			tree->root->color = Black;
		}
	}
	return tree;
}

Bool isRed(LPNode node) {
	return (node != NULL && node->color == Red) ? True : False;
}

void turnColor(LPNode node) {
	if (node != NULL) {
		node->color = (node->color == Red) ? Black : Red;
	}
}

LPNode newNode(int key) {
	LPNode node = (LPNode)malloc(sizeof(Node));
	if (node != NULL) {
		node->color = Red;
		node->left = NULL;
		node->right = NULL;
		node->key = key;
	}
	return node;
}

LPNode checkRight(LPNode node) {
	LPNode temp1, temp2;
	if (node == NULL || isRed(node) || !isRed(node->right)) {
		return node;
	}
	temp1 = node->right;
	if (isRed(temp1->right)) {
		turnColor(node);
		turnColor(temp1);
		if (isRed(node->left)) {
			turnColor(node->left);
		} else {
			node->right = temp1->left;
			temp1->left = node;
			return temp1;
		}
	} else if (isRed(temp1->left)) {
		turnColor(node);
		if (isRed(node->left)) {
			turnColor(temp1);
			turnColor(node->left);
		} else {
			temp2 = temp1->left;
			turnColor(temp2);
			node->right = temp2->left;
			temp1->left = temp2->right;
			temp2->left = node;
			temp2->right = temp1;
			return temp2;
		}
	}
	return node;
}

LPNode checkLeft(LPNode node) {
	LPNode temp1, temp2;
	if (node == NULL || isRed(node) || !isRed(node->left)) {
		return node;
	}
	temp1 = node->left;
	if (isRed(temp1->left)) {
		turnColor(node);
		turnColor(temp1);
		if (isRed(node->right)) {
			turnColor(node->right);
		} else {
			node->left = temp1->right;
			temp1->right = node;
			return temp1;
		}
	} else if (isRed(temp1->right)) {
		turnColor(node);
		if (isRed(node->right)) {
			turnColor(temp1);
			turnColor(node->right);
		} else {
			temp2 = temp1->right;
			turnColor(temp2);
			node->left = temp2->right;
			temp1->right = temp2->left;
			temp2->right = node;
			temp2->left = temp1;
			return temp2;
		}
	}
	return node;
}

LPNode addNode(LPNode node, LPNode newnode) {
	if (node == NULL) {
		return newnode;
	}
	if (newnode == NULL) {
		return node;
	}
	if (newnode->key > node->key) {
		node->right = addNode(node->right, newnode);
		node = checkRight(node);
	} else {
		node->left = addNode(node->left, newnode);
		node = checkLeft(node);
	}
	return node;
}