#include<stdio.h>
#include<malloc.h>
#include<iostream>

using namespace std;

bool RED   = true;
bool BLACK = false;

typedef struct node{
    int date;
    struct node *left;
    struct node *right;
    bool color;
}node;
node *root;

bool isRed(node *h);
node *rotateLeft(node *h);
node *rotateRight(node *h);
void filpColor(node *h);
void Put(int val);
node *Tput(node *h,int val);

bool isRed(node *h)
{
    if(h==NULL)    return false;
    else        return h->color==RED;
}

node *rotateLeft(node *h)
{
    node *x;
    x = h->right;
    x->date = h->right->date;
    h->right = x->left;
    x->left = h;
    x->color = h->color;
    h->color = RED;
    return x;
}
node *rotateRight(node *h)
{
    node *x;
    x = h->left;
    x->date = h->left->date;
    h->left = x->right;
    x->right = h;
    x->color = h->color;
    h->color = RED;
    return x;
}

void filpColor(node *h)
{
    h->color = RED;
    h->left->color = BLACK;
    h->right->color = BLACK;
}

void Put(int val)
{
    root =    Tput(root,val);
    root->color = BLACK;
}

node *Tput(node *h,int val)
{
    if(h==NULL)
    {
        node *temp;
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->color = RED;
        temp->date = val;
        return temp;
    }
   
    if(h->date<val)         h->right = Tput(h->right,val);
    else if(h->date>val) h->left  = Tput(h->left,val);
    else h->date = val;
   
    if(isRed(h->right)&&!isRed(h->left))      
        rotateLeft(h);
    if(isRed(h->right)&&isRed(h->left->left))
        rotateRight(h);
    if(isRed(h->right)&&isRed(h->left))         
        filpColor(h);
   
    return h;   
}

void print(node *h)
{
    if(h==NULL)    return;
    if(h!=NULL)
    {
        printf("%d\n",h->date);
        print(h->left);
        print(h->right);
    }
}

int main()
{
    Put(10);
    Put(12);
    Put(15);
    Put(7);
    Put(14);
    Put(3);
    Put(0);
    Put(5);
    print(root);
}