#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdarg.h>
#include <malloc.h>

#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

typedef enum {              //枚舉類型的狀態(tài)標記
    RBT_STATUS_OK,
    RBT_STATUS_MEM_EXHAUSTED,
    RBT_STATUS_DUPLICATE_KEY,
    RBT_STATUS_KEY_NOT_FOUND
} RbtStatus;

typedef enum { BLACK, RED } nodeColor;

typedef struct NodeTag {
    struct NodeTag *left;       // left child
    struct NodeTag *right;      // right child
    struct NodeTag *parent;     // parent
    nodeColor color;            // node color (BLACK, RED)
    int key;                // key used for searching
   } NodeType;
static NodeType leaf ={NULL,NULL,NULL,BLACK,0};

//static NodeType *root ={NULL,NULL,NULL,BLACK,0}; // root of red-black tree
  int  judge(NodeType *p)
  {
	if((p->left==NULL)&&(p->right==NULL))
	   return 1;
    else return 0;
	
	         
	 
  }
static void rotateLeft(NodeType *x) {         //左旋

    // rotate node x to left

    NodeType *y = x->right;

    // establish x->right link
    x->right = y->left;
    if (!judge(y->left)) y->left->parent = x;

    // establish y->parent link
    if (!judge(y)) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    } else {
	
		y->parent->color=BLACK;
		y->parent->key = 0;
		y->parent->left = NULL;
		y->parent->right = NULL;
		y->parent->parent = NULL;

    }

    // link x and y
    y->left = x;
    if (judge(x)) x->parent = y;
}


static void rotateRight(NodeType *x) {       //右旋

    // rotate node x to right

    NodeType *y = x->left;

    // establish x->left link
    x->left = y->right;
    if (judge(y->right)) y->right->parent = x;

    // establish y->parent link
    if (judge(y)) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    } else {
     y->parent->color=BLACK;
		y->parent->key = 0;
		y->parent->left = NULL;
		y->parent->right = NULL;
		y->parent->parent = NULL;
    }

    // link x and y
    y->right = x;
    if (!judge(x)) x->parent = y;
}


static void insertFixup(NodeType *x,NodeType *root) {

    // maintain red-black tree balance
    // after inserting node x

    // check red-black properties
    while (x != root && x->parent->color == RED) {  //出現(xiàn)了紅紅沖突
        // we have a violation
        if (x->parent == x->parent->parent->left) {    //如果x的父節(jié)點是祖先的左孩子，
            NodeType *y = x->parent->parent->right;    // y是x的叔叔
            if (y->color == RED) 
			{                                   //如果y是紅的
 
                // uncle is RED
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } 
			else 
			{                                                 //如果y 是黑的

                // uncle is BLACK
                   if (x == x->parent->right) 
				   {
                    // make x a left child
                       x = x->parent;
                        rotateLeft(x);
				   }

                // recolor and rotate
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateRight(x->parent->parent);
            }
        } else {                                       //  如果x的父節(jié)點是祖先的右孩子，（和上面是對稱的）                                  

            // mirror image of above code
            NodeType *y = x->parent->parent->left;
            if (y->color == RED) {

                // uncle is RED
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                // uncle is BLACK
                if (x == x->parent->left) {
                    x = x->parent;
                    rotateRight(x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateLeft(x->parent->parent);
            }
        }
    }
    root->color = BLACK;
}




  RbtStatus  rbtInsert(int key,NodeType *root) {
        NodeType *current, *parent, *x;
        x =(NodeType *)malloc(sizeof(NodeType));
    // allocate node for data and insert in tree

    // find future parent
    current = root;
    parent =root;
    while (!judge(current)) {
        if (compEQ(key, current->key)) 
            return RBT_STATUS_DUPLICATE_KEY;
        parent = current;
        current = compLT(key, current->key) ?
            current->left : current->right;

    }

    // setup new node
    if ((malloc (sizeof(*x))) == 0)
        return RBT_STATUS_MEM_EXHAUSTED;
    x->parent = parent;
    x->left = NULL;
    x->right = NULL;
    x->color = RED;
    x->key = key;
   

    // insert node in tree
    if(parent) {
        if(compLT(key, parent->key))
            parent->left = x;
        else
            parent->right = x;
    } else {
      x->parent->parent = parent;
      x->parent->left = NULL;
      x->parent->right = NULL;
      x->parent->color = RED;
      x->parent->key = key;
    }

    insertFixup(x,root);

    return RBT_STATUS_OK;

}



 void main()
  {   
     int a[7]= {1,2,3,4,5,6,7};

	 RbtStatus state;
      NodeType  *root;
      root = (NodeType *)malloc(sizeof( NodeType));
	  root->color=BLACK;
	  root->key = 0;
	  root->left = NULL;
	  root->right = NULL;
	  root->parent = NULL;
     int i;
	 for(i=0;i<7;i++)
	 {state = rbtInsert(a[i],root);}
      
     
  }