#include <cassert>

class RBTree
{
  private:
    typedef enum tag_color
    {
      RED,
      BLACK
    }color_t;

    typedef struct tag_node
    {
      struct tag_node *p;
      struct tag_node *left;
      struct tag_node *right;
      int key;
      int data;
      color_t color;
    }node_t;

    node_t *root;
    node_t *nil;

    void Right_Rotate(node_t *x);
    void Left_Rotate(node_t *x);
    node_t *RB_Find_Successor(node_t *z) const;
    void RB_Insert_Fixup(node_t *z);
    node_t *RB_Find(int key);
    void RB_Delete_Fixup(node_t *x);
    void RB_Clear(node_t *x);


  public:
    RBTree();
    void RB_Insert(int key, int data);
    bool RB_Delete(int key);
    ~RBTree();
};


RBTree::RBTree()
{
  nil = new node_t;
  nil->left = 0;
  nil->right = 0;
  nil->p = 0;
  nil->color = BLACK;
  nil->key = 0;
  nil->data = 0;
  root = nil;
}

void RBTree::Left_Rotate(node_t *x)
{
  node_t *y = x->right;

  x->right = y->left;

  if (y->left != nil)
    (y->left)->p = x;
  y->p = x->p;
  if (x->p ==nil)
    root = y;
  else
    if (x == (x->p)->left)
      (x->p)->left = y;
    else
      (x->p)->right = y;

  y->left = x;
  x->p = y;
}

void RBTree::Right_Rotate(node_t *x)
{
  node_t *y = x->left;

  x->left = y->right;

  if (y->right != nil)
    (y->right)->p = x;
  y->p = x->p;
  if (x->p == nil)
    root = y;
  else
    if (x == (x->p)->left)
      (x->p)->left = y;
    else
      (x->p)->right = y;

  y->right = x;
  x->p = y;
}

void RBTree::RB_Insert_Fixup(node_t *z)
{
  node_t *y;

  while (z->p->color == RED)
    if (z->p == z->p->p->left)
    {
      y = z->p->p->right;
      if (y->color == RED)
      {
        z->p->color = BLACK;
        y->color = BLACK;
        z->p->p->color = RED;
        z = z->p->p;
      }
      else
      {
        if (z == z->p->right)
        {
          z = z->p;
          Left_Rotate(z);
        }
        z->p->color = BLACK;
        z->p->p->color = RED;
        Right_Rotate(z->p->p);
      }
    }
    else
    {
      y = z->p->p->left;
      if (y->color == RED)
      {
        z->p->color = BLACK;
        y->color = BLACK;
        z->p->p->color = RED;
        z = z->p->p;
      }
      else
      {
        if (z == z->p->left)
        {
          z = z->p;
          Right_Rotate(z);
        }
        z->p->color = BLACK;
        z->p->p->color = RED;
        Left_Rotate(z->p->p);
      }
    }

  root->color = BLACK;
}

void RBTree::RB_Insert(int key, int data)
{
  node_t *x, *y, *z = new node_t;

  z->data = data;
  z->key = key;

  if (root == nil)
  {
    root = new node_t;
    root->data = data;
    root->key = key;
    root->color = BLACK;
    root->left = nil;
    root->right = nil;
    root->p = nil;

    return;
  }

  y = nil;
  x = root;
  while (x != nil)
  {
    y = x;
    if (z->key <= x->key)
      x = x->left;
    else
      x = x->right;
  }
  z->p = y;
  if (y == nil)
    root = z;
  else
    if (z->key <= y->key)
      y->left = z;
    else
      y->right = z;

  z->left = nil;
  z->right = nil;
  z->color = RED;
  RB_Insert_Fixup(z);
}

/*void *RBTree::RB_Find(int key)
{
  node
}*/

RBTree::node_t *RBTree::RB_Find_Successor(node_t *z) const
{
  node_t *y;

  if (z->right != nil)
  {
    z = z->right;
    while (z->left != nil)
      z = z->left;

    return z;
  }
  y = z->p;
  while (y != nil && z== y->right)
  {
    z = y;
    y = y->p;
  }

  return y;
}

bool RBTree::RB_Delete(int key)
{
  node_t *x, *y, *z = root;
  bool fixup_flag = false;

  do
  {
    if (z->key == key)
      break;
    if (key < z->key)
      z = z->left;
    else
      z = z->right;
  } while (z != nil);

  if (z == nil)
    return false;
  else
  {
    if (z->left == nil || z->right == nil)
      y = z;
    else
      y = RB_Find_Successor(z);
  }
  if (y->left != nil)
    x = y->left;
  else
    x = y->right;
  x->p = y->p;
  if (y->p == nil)
    root = x;
  else
    if (y == y->p->left)
      y->p->left = x;
    else
      y->p->right = x;
  if (y != z)
  {
    z->key = y->key;
    z->data = y->data;
  }
  if (y->color == BLACK)
    fixup_flag = true;

  delete y;

  if (fixup_flag == true)
    RB_Delete_Fixup(x);

  return true;
}

void RBTree::RB_Delete_Fixup(node_t *x)
{
  node_t *w;

  while (x != root && x->color == BLACK)
    if (x == x->p->left)
    {
      w = x->p->right;
      if (w->color == RED)
      {
        w->color = BLACK;
        x->p->color = RED;
        Left_Rotate(x->p);
        //w = x->p->right;
      }
      if (w->left->color == BLACK && w->right->color == BLACK)
      {
        w->color = RED;
        x = x->p;
      }
      else
      {
        if (w->right->color == BLACK)
        {
          w->left->color = BLACK;
          w->color = RED;
          Right_Rotate(w);
          w = x->p->right;
        }
        w->color = x->p->color;
        x->p->color = BLACK;
        w->right->color = BLACK;
        Left_Rotate(x->p);
        x = root;
      }
    }
    else
    {
      w = x->p->left;
      if (w->color == RED)
      {
        w->color = BLACK;
        x->p->color = RED;
        Right_Rotate(x->p);
        //w = x->p->left;
      }
      if (w->right->color == BLACK && w->left->color == BLACK)
      {
        w->color = RED;
        x = x->p;
      }
      else
      {
        if (w->left->color == BLACK)
        {
          w->right->color = BLACK;
          w->color = RED;
          Left_Rotate(w);
          w = x->p->left;
        }
        w->color = x->p->color;
        x->p->color = BLACK;
        w->left->color = BLACK;
        Right_Rotate(x->p);
        x = root;
      }
    }
}

void RBTree::RB_Clear(node_t *x)
{
  if (x == 0)
    return;

  RB_Clear(x->left);
  RB_Clear(x->right);

  delete x;
}

RBTree::~RBTree()
{
  RB_Clear(root);
}

int main()
{

  RBTree tree;

  tree.RB_Insert(1, 1);
  tree.RB_Insert(2, 2);
  tree.RB_Insert(4, 4);
  tree.RB_Insert(5, 5);
  tree.RB_Insert(7, 7);
  tree.RB_Insert(8, 8);
  tree.RB_Insert(11, 11);
  tree.RB_Insert(14, 14);
  tree.RB_Insert(15, 15);

  tree.RB_Delete(2);
  tree.RB_Delete(7);
  tree.RB_Delete(8);
  tree.RB_Delete(1);

  return 0;
}