// -----------------------------------------------------------
// ---- Livro Algoritmos (CORMEN): Capitulo 12 ---------------
// ---- Arvore de Busca Binaria (Binary Search Tree) ---------
// -----------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <climits>
#include <windows.h>
using namespace std;


typedef struct node {
	double chave;
	struct node* pai;
	struct node* esq;
	struct node* dir;
	int cor;
	node() {pai=esq=dir=NULL;} //inicializacao
} node;


typedef struct Tree {
    node* raiz;
    int N; //numero de elementos
    Tree() {raiz=NULL; N=0;} //inicializacao
} Tree;


// ----------------------------------------
// Algoritmos basicos
// ----------------------------------------
void TreeFree(node* pno);
void TreePrintInOrder(node* pno);
node* TreeSearch(node* pno, double k);
node* TreeSearchIter(node* pno, double k);
node* TreeMinimum(node* pno);
node* TreeMaximum(node* pno);
node* TreeSucessor(node* pno);
node* TreePredecessor(node* pno);
void TreeInsert(Tree& T, node* pno);
void TreeDelete(Tree& T, node* pno);


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

    int i;
    int N = 20;

    srand (time(NULL));
    for (i=0;i<N;i++) {
        node* pno = new node;
        pno->chave = (double) rand()/RAND_MAX;
        TreeInsert(T,pno);
    }

    TreePrintInOrder(T.raiz);
    TreeFree(T.raiz);

    return 0;
}



// ------------------------------------------------------------------------------------------------
// ---- Manutencao de bsTree ----------------------------------------------------------------------
// ------------------------------------------------------------------------------------------------

// Apaga da memoria a arvore enraizada em pno
void TreeFree(node* pno) {
    if (pno==NULL) return;
    TreeFree(pno->esq);
    TreeFree(pno->dir);
    delete pno;
}

// Imprime em ordem os valores da subarvore de pno
void TreePrintInOrder(node* pno) {
    if (pno==NULL) return;
    TreePrintInOrder(pno->esq);
    cout<<pno->chave<<endl;
    TreePrintInOrder(pno->dir);
}

// Procura recursivamente um no com valor k na subarvore de pno
node* TreeSearch(node* pno, double k) {
    if ((pno==NULL)||(pno->chave==k)) {
        return pno;
    }
    if (k < pno->chave) {
        return TreeSearch(pno->esq, k);
    } else {
        return TreeSearch(pno->dir, k);
    }
}
// Procura iterativamente um no com valor k na subarvore de no
node* TreeSearchIter(node* pno, double k) {
    while ((pno!=NULL) && (pno->chave!=k))
    {
        if (k < pno->chave)
            pno = pno->esq;
        else
            pno = pno->dir;
    }
    return pno;
}

// Retorna o no com valor minimo na subarvoore de no
node* TreeMinimum(node* pno) {
    while (pno->esq != NULL) {
        pno = pno->esq;
    }
    return pno;
}

// Retorna o no com valor maximo na subarvoore de no
node* TreeMaximum(node* pno) {
    while (pno->dir!=NULL) {
        pno = pno->dir;
    }
    return pno;
}

// Retorna o sucessor de no
node* TreeSucessor(node* pno) {
    if (pno->dir!=NULL) {
        return TreeMinimum(pno->dir);
    }
    node* pai = pno->pai;
    while ((pai!=NULL) && (pai->esq!=pno))
    {
        pno = pai;
        pai = pai->pai;
    }
    return pai;
}

// Retorna o predecessor de no
node* TreePredecessor(node* pno) {
    if (pno->esq!=NULL) {
        return TreeMaximum(pno->esq);
    }
    node* pai = pno->pai;
    while ((pai!=NULL) && (pai->dir!=pno)) {
        pno = pai;
        pai = pai->pai;
    }
    return pai;
}

// Insere um no jah alocado na memoria
void TreeInsert(Tree& T, node* z) {
    node* pai = NULL;
    node* pno = T.raiz;
    while (pno!=NULL) {
        pai = pno;
        if (z->chave < pno->chave)
             pno = pno->esq;
        else pno = pno->dir;
    }
    z->pai = pai;
    if (pai==NULL) T.raiz = z;
    else if (z->chave < pai->chave)
         pai->esq = z;
    else pai->dir = z;
    T.N++;
}





// Remove no da arvore e a reorganiza
void Transplant(Tree& T, node* u, node* v) {
    if (u==NULL) return;
    if (u->pai==NULL) {
        T.raiz = v;
    } else if (u==u->pai->esq) {
        u->pai->esq = v;
    } else {
        u->pai->dir = v;
    }
    if (v!=NULL) v->pai = u->pai;
}
void TreeDelete(Tree& T, node* z) {
    if (z->esq==NULL) {
        Transplant(T, z, z->dir);
    } else if (z->dir==NULL) {
        Transplant(T, z, z->esq);
    } else {
        node* suc = TreeSucessor(z);
        if (suc->pai!=z) {
            Transplant(T, suc, suc->dir);
            suc->dir = z->dir;
            suc->dir->pai = suc;
        }
        Transplant(T, z, suc);
        suc->esq = z->esq;
        suc->esq->pai = suc;
    }
}