albero.h

#ifndef ALBERO_H_INCLUDED
#define ALBERO_H_INCLUDED
#include "nodo.h"

class albero
{
    nodo *root;
    nodo *nil;
    void leftrotate(nodo *);
    void rightrotate(nodo *);
    void fixdelate(nodo *);
    void fixviolation(nodo *);
    void treeinsert(nodo *);
    void transplant(nodo *, nodo *);
    nodo *treeminimum(nodo *);

public:
    albero();
    void inserimento(int);
    void inorder(nodo *);
    void delate(nodo *);
    nodo *getroot(){return this->root;}
    ~albero(){;}
};

albero::albero()
{
    this->nil=new nodo(-1, nullptr, nullptr, nullptr, nero);
    root=nil;
    nil->setp(root);
}

void albero::leftrotate(nodo *nod)
{
    nodo *app=nod->getdx();
    nod->setdx(app->getsx());

    if(app->getsx()!=this->nil)
        app->getsx()->setp(nod);

    app->setp(nod->getp());

    if(nod->getp()==this->nil)
    {
        this->root=app;
    }
    else if(nod==nod->getp()->getsx())
    {
        nod->getp()->setsx(app);
    }
    else
        nod->getp()->setdx(app);

    app->setsx(nod);
    nod->setp(app);
}

void albero::rightrotate(nodo *nod)
{
    nodo *app=nod->getsx();
    nod->setsx(app->getdx());

    if(app->getdx()!=this->nil)
        app->getdx()->setp(nod);

    app->setp(nod->getp());

    if(nod->getp()==this->nil)
    {
        this->root=app;
    }
    else if(nod==nod->getp()->getdx())
    {
        nod->getp()->setdx(app);
    }
    else
        nod->getp()->setsx(app);

    app->setdx(nod);
    nod->setp(app);
}

void albero::treeinsert(nodo *nod)
{
    nodo *x=this->root;
    nodo *y=this->nil;

    while(x!=nil)
    {
        y=x;
        if(nod->getkey()<x->getkey())
            x=x->getsx();
        else
            x=x->getdx();
    }

    nod->setp(y);

    if(y==this->nil)
        this->root=nod;
    else if(nod->getkey()<y->getkey())
        y->setsx(nod);
    else
        y->setdx(nod);
}

void albero::fixviolation(nodo *app)
{
    while((app!=this->root) && (app->getp()->getcolore()==rosso))
    {
        if(app->getp()==app->getp()->getp()->getsx())
        {
            nodo *niu=app->getp()->getp()->getdx();
            if(niu->getcolore()==rosso)
            {
                app->getp()->setcolore(nero);
                niu->setcolore(nero);
                app->getp()->getp()->setcolore(rosso);
                app=app->getp()->getp();
            }
            else
            {
                if(app==app->getp()->getdx())
                {
                    app=app->getp();
                    this->leftrotate(app);
                }
                app->getp()->setcolore(nero);
                app->getp()->getp()->setcolore(rosso);
                this->rightrotate(app->getp()->getp());
            }
        }
        else
        {
            nodo *niu=app->getp()->getp()->getsx();
            if(niu->getcolore()==rosso)
            {
                app->getp()->setcolore(nero);
                niu->setcolore(nero);
                app->getp()->getp()->setcolore(rosso);
                app=app->getp()->getp();
            }
            else
            {
                if(app==app->getp()->getsx())
                {
                    app=app->getp();
                    this->rightrotate(app);
                }
                app->getp()->setcolore(nero);
                app->getp()->getp()->setcolore(rosso);
                this->leftrotate(app->getp()->getp());
            }
        }
    }
    this->root->setcolore(nero);
}

void albero::transplant(nodo *u, nodo *v)
{
    if(u->getp()==this->nil)
        this->root=v;
    else if(u==u->getp()->getsx())
        u->getp()->setsx(v);
    else
        u->getp()->setdx(v);

    v->setp(u->getp());
}

void albero::fixdelate(nodo *x)
{
    while(x!=this->root && x->getcolore()==nero)
    {
        if(x==x->getp()->getsx())
        {
            nodo *w=x->getp()->getdx();
            if(w->getcolore()==rosso)
            {
                w->setcolore(nero);
                x->getp()->setcolore(rosso);
                leftrotate(x->getp());
                w=x->getp()->getdx();
            }
            if(w->getsx()->getcolore()==nero && w->getsx()->getcolore()==nero)
            {
                w->setcolore(rosso);
                x=x->getp();
            }
            else
            {
                if(w->getdx()->getcolore()==nero)
                {
                    w->getsx()->setcolore(nero);
                    w->setcolore(rosso);
                    rightrotate(w);
                    w=w->getp()->getdx();
                }
                w->setcolore(x->getp()->getcolore());
                x->getp()->setcolore(nero);
                w->getdx()->setcolore(nero);
                leftrotate(x->getp());
                x=this->root;
            }
        }
        else
        {
            nodo *w=x->getp()->getsx();
            if(w->getcolore()==rosso)
            {
                w->setcolore(nero);
                x->getp()->setcolore(rosso);
                rightrotate(x->getp());
                w=x->getp()->getsx();
            }
            if(w->getdx()->getcolore()==nero && w->getdx()->getcolore()==nero)
            {
                w->setcolore(rosso);
                x=x->getp();
            }
            else
            {
                if(w->getsx()->getcolore()==nero)
                {
                    w->getdx()->setcolore(nero);
                    w->setcolore(rosso);
                    leftrotate(w);
                    w=w->getp()->getsx();
                }
                w->setcolore(x->getp()->getcolore());
                x->getp()->setcolore(nero);
                w->getsx()->setcolore(nero);
                rightrotate(x->getp());
                x=this->root;
            }
        }

    }
    x->setcolore(nero);
}

nodo *albero::treeminimum(nodo *a)
{
    if(a->getsx()==this->nil)
        return a;
    else
    {
        treeminimum(a->getsx());
    }
}

void albero::inserimento(int dato)
{
    nodo *app=new nodo(dato, this->nil, this->nil, this->nil, rosso);
    this->treeinsert(app);
    this->fixviolation(app);
}

void albero::inorder(nodo *n)
{
    if(n!=this->nil)
    {
        std::cout<<n->getkey()<<" ";
        (n->getcolore()==rosso) ? std::cout<<"rosso"<<std::endl : std::cout<<"nero"<<std::endl;
        inorder(n->getsx());
        inorder(n->getdx());
    }
}

void albero::delate(nodo *z)
{
    nodo *y=z;
    Colore yc=z->getcolore();
    if(z->getsx()==this->nil)
    {
        nodo *x=z->getdx();
        transplant(z, z->getdx());
       // if(yc==nero)
         //   fixdelate(x);
    }
    else if(z->getdx()==this->nil)
    {
        nodo *x=z->getsx();
        transplant(z, z->getsx());
       // if(yc==nero)
         //   fixdelate(x);
    }
    else
    {

        y=treeminimum(z->getdx());
        yc=y->getcolore();
        nodo *x=y->getdx();
        if(y->getp()==z)
            x->setp(y);
        else
        {
            transplant(y, y->getdx());
            y->setdx(z->getdx());
            y->getdx()->setp(y);
        }
        transplant(z, y);
        y->setsx(z->getsx());
        y->getsx()->setp(y);
        y->setcolore(z->getcolore());
        if(yc==nero)
            fixdelate(x);
    }
}

#endif //ALBERO_H_INCLUDED