//Rbtree.h
#ifndef RBTREE
#define RETREE
typedef int type;
class Rbtree
{
    enum COLOR{RED,BLACK};
    typedef struct Node
    {
        Node();
        Node(type k);
        
        /*Node(const Node&);*/
        void* operator new(size_t size)
        {
            static int p = 0;
            static Node* array = static_cast<Node*>( malloc(200*sizeof(Node)) );
            if(p==200){
                p = 0;
                array = static_cast<Node*>( malloc(200*sizeof(Node)) );
            }
            return array + p++;
        }
        /*void operator delete(void* p)
        {
        }*/
        ~Node();
        Node  *p;
        Node  *left;
        Node  *right;
        COLOR color;
        type  key;
    };
    typedef Node* pNode;
    static pNode Nul;
    pNode root;
protected:
    pNode minNum     (const pNode z)const;
    pNode successor   (const pNode node)const;
    void  insertFixup (pNode node);
    void  delFixup      (pNode node);
    void  leftRotate  (pNode node);
    void  rightRotate (pNode node);
    void  print      (const pNode node)const;
    int   treeB     (pNode lp)const;
    pNode sele       (type z);
public:
    Rbtree ();
    ~Rbtree();
    bool checkLegal()const;
    bool select (type z);
    void insert (type z);
    bool dele   (type z);
    void print  ()const;
};

#endif  RETREE

//Rbtree.cpp
#include<Rbtree.h>
#include<iostream>
using std::cout;
using std::ends;
using std::endl;
Rbtree::pNode Rbtree::Nul = new Node;
Rbtree::Node::Node()
{
    color = BLACK;
    key = 0;
    left = 0;
    p = 0;
    right = 0;
}
Rbtree::Node::Node(type k)
{
    color = RED;
    key = k;
    left = Nul;
    right = Nul;
    p = Nul;
}

Rbtree::Node::~Node()
{
}


Rbtree::Rbtree()
{
    root = Nul;
}
void Rbtree::print(const pNode node)const
{
    if(node != Nul)
    {
        print(node->left);
        cout << node->key << ' ';
        print(node->right);
    }
}
void Rbtree::print()const
{
    if(root != Nul)
        print(root);
    cout << '\n';
}
inline void Rbtree::leftRotate(Rbtree::pNode x)
{
    pNode y = x->right;
    x->right = y->left;//移动叶子
    if(y->left != Nul)
        y->left->p = x;//确认移动叶子
    y->p = x->p;//左旋
    if(x->p == Nul)
        root = y;//为根的情况
    else
        if(x == x->p->left)
            x->p->left = y;//左旋，对接
        else
            x->p->right = y;
    y->left = x;
    x->p = y;
}
inline void Rbtree::rightRotate(Rbtree::pNode x)
{
    pNode y = x->left;
    x->left = y->right;
    if(y->right != Nul)
        y->right->p = x;
    y->p = x->p;
    if(x->p == Nul)
        root = y;
    else
        if(x == x->p->left)
            x->p->left = y;
        else
            x->p->right = y;
    y->right = x;
    x->p = y;
}
inline void Rbtree::insertFixup(pNode node)
{
    while(node->p->color == Rbtree::RED)
    {
        /*Rbtree::*/pNode pp = node->p;
        if(pp->p->left->color == pp->p->right->color)//都是红的
        {
            pp->p->left ->color = /*Rbtree::*/BLACK;
            pp->p->right->color = /*Rbtree::*/BLACK;
            pp->p->color = Rbtree::RED;
            node = pp->p;
        }
        else
        {
            if(pp == pp->p->left)
            {
                if(node == pp->right)
                {
                    node = pp;
                    leftRotate(node);
                }
                node->p->color = Rbtree::BLACK;
                node->p->p->color = Rbtree::RED;
                rightRotate(node->p->p);
            }
            else
            {
                if(node == pp->left)
                {
                    node = pp;
                    rightRotate(node);
                }
                node->p->color = Rbtree::BLACK;
                node->p->p->color = Rbtree::RED;
                leftRotate(node->p->p);
            }
        }
    }
    root->color = Rbtree::BLACK;
}
inline void Rbtree::insert(type z)
{
    pNode x = root;
    pNode y = Nul;
    while(x!=Nul)
    {
        y = x;
        if(z < x->key)
            x = x->left;
        else
            x = y->right;
    }
    pNode pz = new Node(z);
    if(y == Nul)
        root = pz;
    else
    {
        if(z < y->key)
            y->left = pz;
        else
            y->right = pz;
    }
    pz->p = y;
    insertFixup(pz);
}

Rbtree::pNode Rbtree::minNum(Rbtree::pNode node)const
{
    while(node->left != Nul)
    {
        node = node->left;
    }
    return node;
}
Rbtree::pNode Rbtree::sele(type z)
{
    pNode k = root;
    while(k != Nul)
    {
        if(k->key == z)
            return k;
        else
            if(k->key > z)
                k = k->left;
            else
                k = k->right;
    }
    return Nul;
}
bool Rbtree::select(type z)
{
    if(sele(z) == Nul)
        return false;
    else
        return true;        
}
bool Rbtree::dele(type z)
{
    pNode Z = sele(z);
    if(Z == Nul)
        return false;

    //delnode是要删除的点
    pNode delnode = Nul;
    if(Z->left == Nul || Z->right == Nul)
        delnode = Z;
    else
        delnode = successor(Z);

    //用child保存delnode的孩子
    pNode child = Nul;
    if(delnode->left != Nul)
        child = delnode->left;
    else
        child = delnode->right;
        child->p = delnode->p;
    if(delnode->p == Nul)
        root = child;
    else
    {
        
        //完成新父子对接
        if(delnode == delnode->p->left)
            delnode->p->left = child;
        else
            delnode->p->right = child;
    }
    if(delnode != Z)
        Z->key = delnode->key;
    if(delnode->color == BLACK)
        delFixup(child);
    return true;
}
void Rbtree::delFixup(Rbtree::pNode node)
{
    while(node != root && node->color == BLACK)
    {
        if(node == node->p->left)//node's left child
        {
            pNode w = node->p->right;//w是node的兄弟
            if(w->color == RED)//case 1
            {
                w->color = BLACK;
                node->p->color = RED;
                leftRotate(node->p);
                w = node->p->right;//重新设置node的兄弟
            }

            if(w->left->color == BLACK && w->right->color == BLACK)//case 2
            {
                w->color = RED;
                node = node->p;
            }
            else//w的左右孩子至少一个为RED
            {
                if(w->right->color == BLACK)//case 3,w'l is red && w'r is black
                {
                    w->color = RED;
                    w->left->color = BLACK;
                    rightRotate(w);
                    w = node->p->right;
                }
                //w的右孩子必为RED
                w->color = w->p->color;//左旋后以w为新根的子树的左右树黑点不变。case 4
                w->p->color = BLACK;//要和上一句一起看。保证左子树的重黑被消去
                w->right->color = BLACK;//右子树补上一个黑
                leftRotate(node->p);
                //能到这里的里是处理完成的
                node = root;//为了跳出和保证根为黑
            }
        }//end if
        else//node's right child
        {
            pNode w = node->p->left;
            if(w->color == RED)
            {
                w->color = BLACK;
                node->p->color = RED;
                rightRotate(node->p);
                w = node->p->left;
            }
            if(w->left->color == BLACK && w->right->color == BLACK)
            {
                w->color = RED;
                node = node->p;
            }
            else
            {
                if(w->left->color == BLACK)
                {
                    w->color = RED;
                    w->right->color = BLACK;
                    leftRotate(w);
                    w = node->p->left;
                }
                w->color = w->p->color;
                w->p->color = BLACK;
                w->left->color = BLACK;
                rightRotate(node->p);
                //能到这里的里是处理完成的
                node = root;//为了跳出和保存根为黑
            }
        }//end else
    }//end while
    node->color = BLACK;
}
int Rbtree::treeB(Rbtree::pNode r)const
{
    if(r == Nul) return 1;
    int lb = treeB(r->left);
    int rb = treeB(r->right);
    if(lb != rb || lb == -1 ||
        (r->color == RED && (r->left->color == RED||r->right->color == RED))
        )
        return -1;
    else
        return (r->color == BLACK) ? lb+1 : lb;
}
bool Rbtree::checkLegal()const
{
    if(root->color != BLACK || treeB(root) == -1/* */)
        return false;
    else
        /*cout << "BLACK "<< treeB(root) << endl;*/
        return true;
}
Rbtree::pNode Rbtree::successor(pNode z)const
{
    z = z->right;
    return minNum(z);
}
Rbtree::~Rbtree()
{
}

#include"stdafx.h"
#include "stdio.h"
#include "iostream"
#include "Rbtree.h"
#include <algorithm>
using namespace std;
int main()
{
    /*typedef multiset<int> Rbtree;*/
    Rbtree mytree;
    int array[200000];
    for(int i = 0; i < 20000; ++i)
        array[i] = rand();
    for(int i = 0; i < 20000; ++i)
    {
        mytree.insert(array[i]);    
    }
    for(int i = 0; i < 20000;++i)
        if(mytree.dele(i))
            if(!mytree.checkLegal()){
                cout << "error " << i << endl;
                system("pause");
            }
            else cout << i << ends;
    /*mytree.print();*/
    return 0;
}