// -----------------------------------------------------------
// ---- Livro Algoritmos (CORMEN): Capitulo 13 ---------------
// ---- Arvore Vermelho-Preto (ou Rubro-Negra ou Red-Black) --
// -----------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <climits>
#include <cfloat>
#include <windows.h>
using namespace std;

typedef struct node {
	double chave;
	struct node* pai;
	struct node* esq;
	struct node* dir;
	string cor;// "red", "black"
} node;


typedef struct Tree {
    node* raiz;
    node* nil;
    int N; //numero de elementos
} Tree;

void RBFreeTree(Tree& T);
void RB_Create(Tree& T);
void RB_PrintInOrder(Tree& T, node* no,int altura);
node* RB_Search(Tree& T, node* no, double k);
node* RB_SearchIter(Tree& T, node* no, double k);
node* RB_Minimum(Tree& T, node* no);
node* RB_Maximum(Tree& T, node* no);
node* RB_Sucessor(Tree& T, node* no);
node* RB_Predecessor(Tree& T, node* no);
void RB_Insert(Tree& T, node* z);
void RB_Delete(Tree& T, node* z);


// ------------------------------------------------------------
// --- MAIN ---------------------------------------------------
// ------------------------------------------------------------
int main() {
    Tree T;
    RB_Create(T);

    int i,j;
    int N = 20;
    srand (time(NULL));

    for (i=0;i<N;i++) {
        node* no = new node;
        no->pai = T.nil;
        no->esq = T.nil;
        no->dir = T.nil;
        no->chave = (double) rand()/RAND_MAX;
        RB_Insert(T, no);
    }

    while (T.raiz!=T.nil) {
        RB_PrintInOrder(T, T.raiz,0);
        RB_Delete(T, T.raiz);
        cout<<endl;
    }
    RBFreeTree(T);
    return 0;
}



// ------------------------------------------------------------
// --- MANUTENCAO DE ARVORE VERMELHO-PRETO
// ------------------------------------------------------------
void RB_Create(Tree& T) {
    T.N = 0;
    T.nil = new node;
    T.raiz = T.nil;
    T.nil->pai = T.nil;
    T.nil->esq = T.nil;
    T.nil->dir = T.nil;
    T.nil->cor = 1;
    T.nil->chave = -DBL_MAX;
}

// ------------------------------------
// Apaga da memoria a subarvore enraizada em no
// ------------------------------------
void RBFreeSubtree(Tree& T, node* no) {
    if ((no==NULL)||(no==T.nil)) return;
    RBFreeSubtree(T, no->esq);
    RBFreeSubtree(T, no->dir);
    free(no);
}

// ------------------------------------
// Apaga a arvore da memoria
// ------------------------------------
void RBFreeTree(Tree& T) {
    RBFreeSubtree(T, T.raiz);
    delete T.nil;
}

// ------------------------------------
// Imprime em ordem os valores da subarvore de no
// ------------------------------------
void RB_PrintInOrder(Tree& T, node* no, int altura) {
    if (no==T.nil) return;
    RB_PrintInOrder(T, no->esq, altura+1);
    cout<<no->chave<<" , "<<no->cor<<" , "<<altura<<endl;
    RB_PrintInOrder(T, no->dir, altura+1);
}

// ------------------------------------
// Procura recursivamente um no com valor k na subarvore de no
// ------------------------------------
node* RB_Search(Tree& T, node* no, double k) {
    if ((no==T.nil)||(no->chave==k)) {
        return no;
    }
    if (k < no->chave) {
        return RB_Search(T, no->esq, k);
    } else {
        return RB_Search(T, no->dir, k);
    }
}

// ------------------------------------
// Procura iterativamente um no com valor k na subarvore de no
// ------------------------------------
node* RB_SearchIter(Tree& T, node* no, double k) {
    while ((no!=T.nil)&&(no->chave!=k)) {
        if (k < no->chave)
            no = no->esq;
        else
            no = no->dir;
    }
    return no;
}

// ------------------------------------
// Retorna o no com valor minimo na subarvoore de no
// ------------------------------------
node* RB_Minimum(Tree& T, node* no) {
    while (no->esq != T.nil) {
        no = no->esq;
    }
    return no;
}

// ------------------------------------
// Retorna o no com valor maximo na subarvoore de no
// ------------------------------------
node* RB_Maximum(Tree& T, node* no) {
    while (no->dir!=T.nil) {
        no = no->dir;
    }
    return no;
}

// ------------------------------------
// Retorna o sucessor de no
// ------------------------------------
node* RB_Sucessor(Tree& T, node* no) {
    if (no->dir != T.nil) {
        return RB_Minimum(T, no->dir);
    }
    node* pai = no->pai;
    while ((pai != T.nil)&&(pai->esq!=no)) {
        no = pai;
        pai = pai->pai;
    }
    return pai;
}

// ------------------------------------
// Retorna o predecessor de no
// ------------------------------------
node* RB_Predecessor(Tree& T, node* no) {
    if (no->esq != T.nil) {
        return RB_Maximum(T ,no->esq);
    }
    node* pai = no->pai;
    while ((pai!=T.nil)&&(pai->dir!=no)) {
        no = pai;
        pai = pai->pai;
    }
    return pai;
}


// ------------------------------------
// LEFT-ROTATE
// ------------------------------------
void LeftRotate(Tree& T, node* x) {
    node* y = x->dir;
    x->dir = y->esq;
    if (y->esq!=T.nil) y->esq->pai = x;
    y->pai = x->pai;
    if (x->pai==T.nil) T.raiz = y;
    else if (x==x->pai->esq)
        x->pai->esq = y;
    else
        x->pai->dir = y;
    y->esq = x;
    x->pai = y;
}

// ------------------------------------
// RIGHT-ROTATE
// ------------------------------------
void RightRotate(Tree& T, node* y) {
    node* x = y->esq;
    y->esq = x->dir;
    if (x->dir!=T.nil) x->dir->pai = y;
    x->pai = y->pai;
    if (y->pai==T.nil) T.raiz = x;
    else if (y==y->pai->dir)
        y->pai->dir = x;
    else
        y->pai->esq = x;
    x->dir = y;
    y->pai = x;
}

// ------------------------------------
// Corrige a arvore apos uma insercao
// ------------------------------------
void RB_InsertFixup(Tree& T, node* z) {
    while (z->pai->cor=="red") {
        if (z->pai == z->pai->pai->esq) {
            node* y = z->pai->pai->dir;
            if (y->cor=="red") {
                z->pai->cor = "black";
                y->cor = "black";
                z->pai->pai->cor = "red";
                z = z->pai->pai;
            } else {
                if (z==z->pai->dir) {
                    z = z->pai;
                    LeftRotate(T,z);
                }
                z->pai->cor = "black";
                z->pai->pai->cor = "red";
                RightRotate(T, z->pai->pai);
            }
        } else {
            node* y = z->pai->pai->esq;
            if (y->cor=="red") {
                z->pai->cor = "black";
                y->cor = "black";
                z->pai->pai->cor = "red";
                z = z->pai->pai;
            } else {
                if (z==z->pai->esq) {
                    z = z->pai;
                    RightRotate(T,z);
                }
                z->pai->cor = "black";
                z->pai->pai->cor = "red";
                LeftRotate(T, z->pai->pai);
            }
        }
    }
    T.raiz->cor = "black";
}

// ------------------------------------
// Insere um no alocado na memoria
// ------------------------------------
void RB_Insert(Tree& T, node* z) {
    node* y = T.nil;
    node* x = T.raiz;
    while (x!=T.nil) {
        y = x;
        if (z->chave < x->chave)
             x = x->esq;
        else x = x->dir;
    }
    z->pai = y;
    if (y==T.nil) T.raiz = z;
    else if (z->chave < y->chave)
         y->esq = z;
    else y->dir = z;
    z->esq = T.nil;
    z->dir = T.nil;
    z->cor = "red";
    RB_InsertFixup(T,z);
}





// ------------------------------------
// Transplanta o no v no lugar do no u
// ------------------------------------
void RB_Transplant(Tree& T, node* u, node* v) {
    if (u==T.nil) return;
    if (u->pai==T.nil) {
        T.raiz = v;
    } else if (u==u->pai->esq) {
        u->pai->esq = v;
    } else {
        u->pai->dir = v;
    }
    v->pai = u->pai;
}
// ------------------------------------
// Reorganiza a arvore apos uma remocao
// ------------------------------------
void RB_DeleteFixup(Tree& T, node* x) {
    while ((x!=T.raiz)&&(x->cor=="black")) {
        if (x==x->pai->esq) {
            node* w = x->pai->dir;
            if (w->cor=="red") {
                w->cor = "black";
                x->pai->cor = "red";
                LeftRotate(T, x->pai);
                w = x->pai->dir;
            }
            if ((w->esq->cor=="black")&&(w->dir->cor=="black")) {
                w->cor = "red";
                x = x->pai;
            } else {
                if (w->dir->cor=="black") {
                    w->esq->cor = "black";
                    w->cor = "red";
                    RightRotate(T,w);
                    w = x->pai->dir;
                }
                w->cor = x->pai->cor;
                x->pai->cor = "black";
                w->dir->cor = "black";
                LeftRotate(T,x->pai);
                x = T.raiz;
            }
        } else {
            node* w = x->pai->esq;
            if (w->cor=="red") {
                w->cor = "black";
                x->pai->cor = "red";
                RightRotate(T,x->pai);
                w = x->pai->esq;
            }
            if ((w->dir->cor=="black")&&(w->esq->cor=="black")) {
                w->cor = "red";
                x = x->pai;
            } else {
                if (w->esq->cor=="black") {
                    w->dir->cor = "black";
                    w->cor = "red";
                    LeftRotate(T,w);
                    w = x->pai->esq;
                }
                w->cor = x->pai->cor;
                x->pai->cor = "black";
                w->esq->cor = "black";
                RightRotate(T,x->pai);
                x = T.raiz;
            }
        }
    }
}
// ------------------------------------
// Remove um no da arvore
// ------------------------------------
void RB_Delete(Tree& T, node* z) {
    if (z==T.nil) return;
    node* x;
    node* suc = z;
    string suc_cor_original = suc->cor;
    if (z->esq==T.nil) {
        x = z->dir;
        RB_Transplant(T,z,x);
    } else if (z->dir==T.nil) {
        x = z->esq;
        RB_Transplant(T,z,x);
    } else {
        suc = RB_Sucessor(T,z);
        suc_cor_original = suc->cor;
        x = suc->dir;
        if (suc->pai!=z) {
            RB_Transplant(T,suc,x);
            suc->dir = z->dir;
            suc->dir->pai = suc;
        } else {
            x->pai = suc;
        }
        RB_Transplant(T,z,suc);
        suc->esq = z->esq;
        suc->esq->pai = suc;
        suc->cor = z->cor;
    }
    if (suc_cor_original=="black") RB_DeleteFixup(T,x);
}