Binary Search Tree, with DSW balancing

gistfile1.hpp

#include <exception>
#include <cstdlib>
#include <iostream>

using namespace std;

class NodoInexistenteException : public exception {

};



template <typename T> class NodoBinario {
    private:
        T _valor;
        NodoBinario* _izquierdo;
        NodoBinario* _derecho;
        
    protected:
        T valor(T val) {
            this->_valor = val;
            return this->_valor;
        }
        
        virtual NodoBinario* izquierdo(NodoBinario* nodo) {
            this->_izquierdo = nodo;
            return this->_izquierdo;
        }
        
        virtual NodoBinario* derecho(NodoBinario* nodo) {
            this->_derecho = nodo;
            return this->_derecho;
        }
    
    public:   
        explicit NodoBinario() : _izquierdo(NULL), _derecho(NULL) {
        
        }
        
        explicit NodoBinario(T val) : _izquierdo(NULL), _derecho(NULL) {
            this->_valor = val;
        }
        
        virtual ~NodoBinario() {
            if(this->tieneIzquierdo()) {
                this->borrarIzquierdo();
            }
            if(this->tieneDerecho()) {
                this->borrarDerecho();
            }
        }
        
        explicit NodoBinario(const NodoBinario& nodo) : _izquierdo(NULL), _derecho(NULL) {
            this->valor(nodo.valor());
            
            if(nodo.tieneDerecho()) {
                this->derecho(new NodoBinario(*nodo.derecho()));                
            }
            if(nodo.tieneIzquierdo()) {
                this->izquierdo(new NodoBinario(*nodo.izquierdo()));
            }
            
        }
        
        NodoBinario& operator=(const NodoBinario& nodo) {
            if(this != &nodo) {
                this->valor(nodo.valor());
            
                if(nodo.tieneDerecho()) {
                    this->derecho(new NodoBinario(*nodo.derecho()));                
                }
                if(nodo.tieneIzquierdo()) {
                    this->izquierdo(new NodoBinario(*nodo.izquierdo()));
                }
                
                delete nodo;
            }
            return *this;
        }
        
        virtual NodoBinario* derecho() {
            //if(_derecho == NULL) {
            //    throw NodoInexistenteException();
            //}
            return this->_derecho;
        }
        virtual NodoBinario* izquierdo() {
            //if(_izquierdo == NULL) {
            //    throw NodoInexistenteException();
            //}
            return this->_izquierdo;
        }
        
        T valor() {
            return this->_valor;
        }
        
        bool tieneIzquierdo() {
            return this->_izquierdo != NULL;
        }
        
        bool tieneDerecho() {
            return this->_derecho != NULL;
        }
        
        virtual void borrarDerecho() {
            //if(!(this->tieneDerecho())) {
            //    throw NodoInexistenteException();
            //}
            delete this->_derecho;
            this->_derecho = NULL;
        }
        
        virtual void borrarIzquierdo() {
            //if(!(this->tieneIzquierdo())) {
            //    throw NodoInexistenteException();
            //}
            delete this->_izquierdo;
            this->_izquierdo = NULL;
        }
        
        unsigned int contarHijos() {
            int i = 0;
            if(this->tieneDerecho()) {
                ++i;
            }
            if(this->tieneIzquierdo()) {
                ++i;
            }
            return i;
        }
        
        void dump(unsigned int nodo = 0, unsigned int index = 0) {
            if(nodo == 0) {
                cout << "digraph g"<<index<<" {" << endl;
                cout << "node [shape = record,height=.1];" << endl;
            }
            
            cout << "node" << index << "_" << (this->valor()) << "[ label = \"<f0> | <f1> " << this->valor() << " | <f2>\"];" << endl;

            if(this->tieneIzquierdo()) {
                cout << "\"node"<< index << "_"  << (this->valor()) << "\":f0 -> \"node"<<index << "_" <<this->izquierdo()->valor()<<"\":f1" << endl;
                this->izquierdo()->dump(1, index);
            }

            if(this->tieneDerecho()) {
                cout << "\"node" << index << "_" << (this->valor()) << "\":f2 -> \"node"<<index << "_" <<this->derecho()->valor()<<"\":f1" << endl;
                this->derecho()->dump(1, index);
            }
            
            if(nodo == 0) {
                cout << "}" << endl;
            }
        };

        void dumpInOrder() {
            if(this->tieneIzquierdo()) {
                this->izquierdo()->dumpInOrder();
            }
            cout << this->valor() << " ";
            if(this->tieneDerecho()) {
                this->derecho()->dumpInOrder();
            }
        }
};


#include <stdexcept>
#include <cmath>

using namespace std;

template <typename T> class NodoBinarioDeBusqueda : public NodoBinario<T> {
    private:
        enum Rotacion { IZQUIERDA, DERECHA };
 
        void rotar(NodoBinarioDeBusqueda<T>* abuelo, NodoBinarioDeBusqueda<T>* padre, NodoBinarioDeBusqueda<T>* pivote, Rotacion r) {
            if(r == IZQUIERDA) {
                if(pivote->tieneIzquierdo()) {
                    padre->derecho(pivote->izquierdo());
                } else {
                    padre->derecho(NULL);
                }
                pivote->izquierdo(padre);
            } else {
                if(pivote->tieneDerecho()) {
                    padre->izquierdo(pivote->derecho());
                } else {
                    padre->izquierdo(NULL);
                }
                pivote->derecho(padre);
            }
            // que quede bien
            if(abuelo != NULL) {
                if(abuelo->tieneDerecho() && abuelo->derecho() == padre) {
                    abuelo->derecho(pivote);
                } else {
                    abuelo->izquierdo(pivote);
                }
            }     
        }
        
        void comprimir(int tamanio) {
            // curvo dos nodos hasta hacerlos un arbol
            // básicamente voy salteando de a 2,
            // y giro hacia la izquierda, usando
            // a cada nodo como padre, y a su hijo
            // como pivote
            NodoBinarioDeBusqueda<T>* scanner;
            NodoBinarioDeBusqueda<T>* hijo;
            int i;
            scanner = this;

            for(i = 0; i < tamanio; i++) {
                hijo = scanner->derecho();
                scanner->derecho(hijo->derecho());
                scanner = scanner->derecho();
                this->rotar(NULL, hijo, scanner, this->IZQUIERDA);
            }
            // no lo hago para el último nodo (no 
            // tendría contra quien hacerlo)

        }
        
        void arreglarRaiz(NodoBinarioDeBusqueda<T>* raizActual) {
            // me dan una raiz, quiero transformarme en ella.
            // primero, encuentro mi padre.
            NodoBinarioDeBusqueda<T>* padre = raizActual;
            while(!(padre->derecho() == this || padre->izquierdo() == this)) {
                if(this->valor() > padre->valor()) {
                    padre = padre->derecho();
                } else {
                    padre = padre->izquierdo();
                }
            }
            // me acuerdo el valor y punteros de la raiz actual
            NodoBinarioDeBusqueda<T>* raizIzquierda = raizActual->izquierdo();
            NodoBinarioDeBusqueda<T>* raizDerecha = raizActual->derecho();
            T valorRaiz = raizActual->valor();
            // reemplazo a los punteros de la raiz con los
            // punteros del nodo en el que estoy parado
            raizActual->derecho(this->derecho());
            raizActual->izquierdo(this->izquierdo());
            raizActual->valor(this->valor());
            
            // le digo a mi padre que su nuevo hijo es
            // el que solia ser la raiz
            if(padre->izquierdo() == this) {
                padre->izquierdo(raizActual);
            } else {
                padre->derecho(raizActual);
            }
            // por ultimo, me convierto en la raiz
            this->derecho(raizDerecha);
            this->izquierdo(raizIzquierda);
            this->valor(valorRaiz);

        }       
        
        virtual bool derecho(NodoBinarioDeBusqueda<T>* nodo) {
            return NodoBinario<T>::derecho(nodo);
        }
        
        virtual bool izquierdo(NodoBinarioDeBusqueda<T>* nodo) {
            return NodoBinario<T>::izquierdo(nodo);
        }

    public:
        

        NodoBinarioDeBusqueda(T val) : NodoBinario<T>(val){
            
        }
        NodoBinarioDeBusqueda() : NodoBinario<T>(){
        
        }
        
        virtual NodoBinarioDeBusqueda<T>* derecho() {
            return static_cast<NodoBinarioDeBusqueda<T>*> (NodoBinario<T>::derecho());
        }
        
        virtual NodoBinarioDeBusqueda<T>* izquierdo() {
            return static_cast<NodoBinarioDeBusqueda<T>*> (NodoBinario<T>::izquierdo());
        }
        
        
        
        NodoBinarioDeBusqueda* buscar(T val) {
            if(this->valor() == val) {
                return this;
            }
            if(val > this->valor()) {
                if(this->tieneDerecho()) {
                    return this->derecho()->buscar(val);
                } else {
                    throw NodoInexistenteException();
                }
            } else {
                if(this->tieneIzquierdo()) {
                    return this->izquierdo()->buscar(val);
                } else {
                    throw NodoInexistenteException();
                }
            }
        }
        
        void borrar(T val) {
            NodoBinarioDeBusqueda* nodoABorrar = NULL;
            if(this->tieneDerecho()) {
                if(this->derecho()->valor() == val) {
                    nodoABorrar = this->derecho();
                } else if(val > this->valor()) {
                    return this->derecho()->borrar(val);
                }
            }
            if(this->tieneIzquierdo()) {
                if(this->izquierdo()->valor() == val) {
                    nodoABorrar = this->izquierdo();
                } else if(val < this->valor()) {
                    return this->izquierdo()->borrar(val);
                }
            }
            if(nodoABorrar == NULL) {
                // ultima chance - eramos la raiz?
                if(val == this->valor()) {
                    nodoABorrar = this;
                } else {
                    throw NodoInexistenteException();
                }
            }
            
            unsigned int hijos = nodoABorrar->contarHijos();
            switch(hijos) {
                case 0:
                    // esta intentando borrar la raiz, y la raiz no tiene hijos?
                    if(nodoABorrar == this) {
                        throw logic_error("No se puede borrar a la raiz de una arbol sin hijos.");
                    }
                    // no tiene hijos, lo saco al toque
                    if(this->tieneDerecho() && this->derecho() == nodoABorrar) {
                        this->borrarDerecho();
                    } else {
                        this->borrarIzquierdo();
                    }
                    break;
                case 1:
                    // tiene un hijo.
                    // cuelgo al hijo del nodo al padre del nodo
                    // (donde el nodo solía estar), y borro al nodo
                    NodoBinarioDeBusqueda<T>* hijo;
                    
                    // busco que hijo es el que tiene
                    if(nodoABorrar->tieneDerecho()) {
                        hijo = nodoABorrar->derecho();
                    } else {
                        hijo = nodoABorrar->izquierdo();
                    }
                    
                    // soy el derecho o izquierdo de mi padre?
                    // en ambos casos, me reemplazo acorde
                    if(this != nodoABorrar) {
                        if(this->tieneDerecho() && this->derecho() == nodoABorrar) {
                            this->derecho(hijo);
                        } else {
                            this->izquierdo(hijo);
                        }
                    } else {
                        // estoy borrando a la raiz
                        // no puedo hacer this = this->derecho() o
                        // this = this->izquierdo(), entonces
                        // copio manualmente
                        if(this->tieneDerecho()) {
                            if(this->derecho()->tieneIzquierdo()) {
                                this->izquierdo(this->derecho()->izquierdo());
                            }
                            this->valor(this->derecho()->valor());
                            if(this->derecho()->tieneDerecho()) {
                                this->derecho(this->derecho()->derecho());
                            }
                        } else {
                            if(this->izquierdo()->tieneDerecho()) {
                                this->derecho(this->izquierdo()->derecho());
                            }
                            this->valor(this->izquierdo()->valor());
                            if(this->izquierdo()->tieneIzquierdo()) {
                                this->izquierdo(this->izquierdo()->izquierdo());
                            }
                        }
                    }
                                  
                    break;
                case 2:
                    // pobre, tiene esposa e hijos y lo voy a matar =(
                    // busco el nodo mas grande de su rama izquierda
                    // (simétricamente, podría buscar el nodo mas chico
                    // de su rama derecha, convendría balancear esto un poco)
                    NodoBinarioDeBusqueda* predecesor = nodoABorrar->izquierdo()->maximo();
                    // cambio mi valor por el mas grande de los que son mas chicos que yo,
                    // así mantengo la propiedad del arbol binario de busqueda.
                    // luego, borro al nodo duplicado.
                    T valNuevo = predecesor->valor();
                    this->borrar(valNuevo);
                    nodoABorrar->valor(predecesor->valor());
                    break;
            }
            
        }

        bool insertar(T val) {
            if(this->valor() == val) {
                // decido no permitir duplicados
                return false;
            }
            if(val > this->valor()) {
                if(this->tieneDerecho()) {
                    return (this->derecho()->insertar(val));
                } else {
                    this->derecho(new NodoBinarioDeBusqueda(val));
                    return true;
                }
            } else {
                if(this->tieneIzquierdo()) {
                    return (this->izquierdo()->insertar(val));
                } else {
                    this->izquierdo(new NodoBinarioDeBusqueda(val));
                    return true;
                }
            }
            
        }
        
        NodoBinarioDeBusqueda* maximo() {
            if(this->tieneDerecho()) {
                return this->derecho()->maximo();
            }
            return this;
        }
        
        NodoBinarioDeBusqueda* minimo() {
            if(this->tieneIzquierdo()) {
                return this->izquierdo()->minimo();
            }
            return this;
        }
        
        void balancear() {
            // creamos la raiz falsa
            NodoBinarioDeBusqueda<T>* pseudo_raiz = new NodoBinarioDeBusqueda();
            
            // tamaño de la liana resultante
            int tamanio;
            
            pseudo_raiz->derecho(this);
            // convierto el arbol a una lista
            // simplemente enlazada, ordenada
            // de menor a mayor, con una
            // raiz falsa, usada solo para
            // que sea mas facil el algoritmo
            pseudo_raiz->ArbolALiana(tamanio);
            
            // una vez que es una lista enlazada,
            // vamos curvando a la izquierda
            // una y otra vez a la liana,
            // cada vez formando un sub-arbol
            // balanceado. Ver Q. Stout & B. Warren,
            // Tree Rebalancing in Optimal Time and Space
            pseudo_raiz->LianaAArbol(tamanio);
            
            // quiero siempre apuntar a la raiz,
            // pero despues de balancear, no 
            // necesariamente sigo siéndola
            this->arreglarRaiz(pseudo_raiz->derecho());
            
            // no necesitamos la raiz, era
            // temporaria
            pseudo_raiz->derecho(NULL);
            delete pseudo_raiz;  
        }
        
        void ArbolALiana(int &tamanio) {
            NodoBinarioDeBusqueda<T>* cola;
            NodoBinarioDeBusqueda<T>* resto;
            NodoBinarioDeBusqueda<T>* temp;
            
            // cola es la liana que se va formando
            cola = this;
            
            // todo lo que todavia no "enliané",
            // esto inicialmente es la raiz
            // verdadera (por esto creamos
            // la raiz falsa, que ahora está
            // en cola)
            resto = this->derecho();
            tamanio = 0;
            while(1) {
                if(!resto->tieneIzquierdo()) {
                    // muevo la cola hacia abajo
                    // ...si si, escribí eso. 
                    // esto es porque ya terminamos
                    // el sub-arbol de la izquierda                   
                    cola = resto;
                    ++tamanio;
                    if(resto->tieneDerecho()) {
                        resto = resto->derecho();
                    } else {
                        break;
                    }
                } else {
                    // tenemos algo en la izquierda,
                    // lo queremos en la derecha, 
                    // entonces rotamos.
                    temp = resto->izquierdo();
                    rotar(cola, resto, temp, this->DERECHA);
                    resto = temp;
                }
            }
        }
        
        void LianaAArbol(int tamanio) {        
            int hojas = tamanio + 1 - pow(2, floor(log2(tamanio + 1)));
            // "curvamos" las primersa hojas
            // de la liana, trivialmente 
            // las hojas estan balanceadas
            this->comprimir(hojas);
            
            tamanio -= hojas;
            while(tamanio > 1) {
                // volvemos a curvar una y otra vez
                // las lianas, siempre produciendo 
                // arboles balanceados a la izquierda,
                // hasta que no tengamos suficientes 
                // hojas (porque puede ser que no
                // tengamos 2^m - 1 hojas)
                this->comprimir(tamanio / 2);
                tamanio = tamanio/2;
            }
            
        }
};



#include <iostream>
#include <ctime>
#include <sys/time.h>

using namespace std;

int main() {
    srand ( time(NULL) );
    int limit = 500,
        root = rand() % limit,
        total = (2<<5)-1,
        i = total;
    NodoBinarioDeBusqueda<int> Arbol(root);
    while(i--) {
        Arbol.insertar(rand() % limit);
    }
    
    Arbol.balancear();
    Arbol.dump();    
    return 0;
}