=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Evaluacion continua - 2022/2023
24 de octubre de 2022
Ejercicio 3
Borrador
=================================================================

Con un arbol binario de busqueda (no equilibrado) las siguientes tres
soluciones tiene los siguientes costes en funcion de n:

* Coste temporal en el mejor caso: O(1). Sucede cuando tenemos un
  arbol de talla n en el que la raiz no tiene hijo derecho.

* Coste temporal en el peor caso: O(n). Sucede cuando tenemos un arbol
  de talla n en el que ningun nodo tiene hijo izquierdo.

Si el arbol fuese AVL, ambos costes pasarian a ser O(log n). Eso seria
lo que costaria llegar desde la raiz hasta el maximo, y eso seria
tambien lo que costaria balancear el arbol tras eliminarlo.


Solucion 1
==========

void Conjunto::eliminarMaximo() {

    if (raiz != nullptr)
        eliminarMaximo(raiz);

}

void Conjunto::eliminarMaximo(Nodo * & n) {

    if (n->derecho != nullptr)
        eliminarMaximo(n->derecho);
    else {
        Nodo * basura = n;
        n = n->izquierdo;
        delete basura;
    }

}


Solucion 2
==========

void Conjunto::eliminarMaximo() {

    if (raiz != nullptr)
        if (raiz->derecho != nullptr)
            eliminarMaximo(raiz);
        else {
            Nodo * basura = raiz;
            raiz = raiz->izquierdo;
            delete basura;
        }

}

void Conjunto::eliminarMaximo(Nodo * padre) {

    if (padre->derecho->derecho != nullptr)
        eliminarMaximo(padre->derecho);
    else {
        Nodo * basura = padre->derecho;
        padre->derecho = basura->izquierdo;
        delete basura;
    }

}


Solucion 3
==========

void Conjunto::eliminarMaximo() {

    if (raiz != nullptr)
        if (raiz->derecho != nullptr)
            eliminarMaximo(raiz, raiz->derecho);
        else {
            Nodo * basura = raiz;
            raiz = raiz->izquierdo;
            delete basura;
        }

}

void Conjunto::eliminarMaximo(Nodo * padre, Nodo * n) {

    if (n->derecho != nullptr)
        eliminarMaximo(n, n->derecho);
    else {
        padre->derecho = n->izquierdo;
        delete n;
    }

}