/**
 * @file red_black_tree.cpp
 * @author Shirish Reddy <shirishreddy89@gmail.com>
 * 
 * red_black_tree: A red black tree gaurantees all the operations like insert, delete
 * predecessor, successor in O(log N) time 
 *
 * Nodes in red black trees have almost same fields as in BST, except for a new entity called 'color' is added to each node.
 *
 * Red black trees satisfies the following five properties
 * 1. Every node of the tree must be either red or black
 * 2. The root and all the leaf nodes should be black
 * 3. Every red node should have as its parent only a black node Or Every red node should have its children as black nodes
 * 4. For each node all paths from node to descendent leaves contain same number of black nodles also called as black-height bh(x)
 *
 * Structure of a RB Tree may change after each modification of insert or delete to maintain the RB properties
 */

#include <iostream>

using namespace std;

/**
 * structure defining the node of Binary search tree
 * each node has link to left child, right child, parent and the key data, and color
 * color represented by char c: 'r' => red 'b' => black
 */
struct node {
	node *left, *right, *p;
	int key; char color;
} *sentinel;

void rb_fixup(node**, node*);
void rb_insert(node**, node*);
void left_rotate(node**, node*);
void right_rotate(node**, node*);

/**
 * rb_insert- Inserts a node in to the red black tree while still trying ot maintain the red black tree properties
 *
 * We continue insertion process in the same way as BST_insert except in the last we call rb_fixup to maintain RB properties
 * every new node inserted in to the tree must be of color red: 'r'
 * 
 * @param: Red black tree and node to be inserted
 * @return: returns nothing since it modifies the reference to the tree not the copy.
 */
void rb_insert(node** T, node* z)
{
	node* y = sentinel;
	node* x = *T;
	
	while(x!=sentinel) {
		y = x;
		if( z->key < x->key)
			x = x->left;
		else
			x = x->right;
	}
	z->p = y;
	if(y == sentinel) 
		*T = z;
	else {
		if( z->key < y->key)
		y->left = z;
		else
		y->right = z;
	}
	z->left = sentinel;
	z->right = sentinel;
	z->color = 'r'; 	//New nodes should be of color Red
	
	rb_fixup(T, z);		//Node z is inserted into the Tree following BST property now call rb_fixup to maintain RB property
}

/**
 * rb_fixup - fixes the Tree and makes it a red black tree again by ensuring the properties
 */
void rb_fixup(node **T, node *z)
{	
	node* y;
	while(z!=*T && z->p->color == 'r') {
		if (z->p == z->p->p->left ) {
			y = z->p->p->right; 	//y is z's uncle
			if( y->color == 'r') {  //if z's uncle y has red color , same as z's parent, we color them black the the grand parent with red
				z->p->color = 'b'; //CASE 1
				y->color = 'b';	   //CASE 1	
				z->p->p->color = 'r';//CASE 1
				z = z->p->p;	    //CASE 1
			}
			
			else{
				if (z == z->p->right) { //if z's is towards right of the parent then perform a left rotate 
					z = z->p;	 //CASE 2
					left_rotate(T, z); //CASE 2
				}
						//Case 3 color the parent of new z black and grand parent to red and right rotate so that RB property is maitained
				z->p->color = 'b';	//CASE 3
				z->p->p->color = 'r';   //CASE 3
				right_rotate(T,z->p->p);
			}
		}
		else if (z->p == z->p->p->right){	//same as above if condition with right <-> left
			y = z->p->p->left;
			if(y->color == 'r') {
				z->p->color = 'b';
				y->color = 'b';
				z->p->p->color = 'r';
				z = z->p->p;
			}
			else {
				if( z == z->p->left) {
					z = z->p;
					right_rotate(T,z);
				}
			
				z->p->color = 'b';
				z->p->p->color = 'r';
				left_rotate(T,z->p->p);
			}
		}
	}
	(*T)->color = 'b';
}
	
/**
 * left_rotate - rotate the tree given x, assumes right[x] != NULL
 */
void left_rotate(node **T, node *x)
{
	node *y = x->right; 
	x->right = y->left; 	//turn Y's left subtree into X's left Right subtree
	y->left->p = x;
	y->p = x->p;
	if(x->p == sentinel) { //if x is root
		*T = y;
	}
	else {
		if (x == x->p->left)
			x->p->left = y;
		else
			x->p->right = y;
	}
	y->left = x;		//put X on y's left
	x->p = y;
}

/**
 * right_rotate - rotate the tree given x, assumes left[x]!=NULL
 */
void right_rotate(node **T, node *x)
{
	node *y = x->left;
	x->left = y->right;
	y->right->p = x;
	y->p = x->p;
	if(x->p == NULL) {
		*T = y;
	}
	else {
		if( x == x->p->right)
			x->p->right = y;
		else
			x->p->left = y;
	}
	y->right = x;
	x->p = y;
}


int main()
{
	sentinel = new node;
	sentinel->key = 0;
	sentinel->left = NULL;
	sentinel->right = NULL;
	sentinel->color = 'b';
	node* T = sentinel;
	node* z = new node;
	z->key = 12;
	rb_insert(&T, z);
	cout<<T->color<<endl;
	cout<<T->key<<endl;
	
	node* z1 = new node;
	z1->key = 26;
	rb_insert(&T, z1);
	cout<<T->right->color<<endl;
	cout<<T->right->key<<endl;
	node* z2 = new node;
	z2->key = 112;
	rb_insert(&T, z2);
	cout<<T->right->right->color<<endl;
	cout<<T->key<<T->color<<" "<<T->left->key<<T->left->color<<" "<<T->right->key<<T->right->color<<endl;	
	delete z;
	delete z1;
	delete z2;
	return 0;
}

b
12
r
26
b
26b 12r 112r