Curso 2024/2025
Añadimos en Conjunto un atributo minimo
de tipo Nodo *
:
class Conjunto { ... Nodo * minimo; // <------ MODIFICACION
Lo inicializamos a nullptr
en el constructor:
Conjunto::Conjunto() : raiz{nullptr}, minimo{nullptr}, // <------ MODIFICACION laTalla{0} { }
Devolvemos minimo->dato
en el método consultarMinimo
:
int Conjunto::consultarMinimo() const { if (minimo == nullptr) throw string("Intentando consultar minimo de conjunto vacio"); return minimo->dato; // <------ MODIFICACION }
Actualizamos minimo
al insertar si el nuevo dato es el
mínimo. Si utilizamos
la solución 3 del ejercicio
2.e, podemos modificarla así:
void Conjunto::insertar(int unDato, Nodo * & n) { n = new Nodo(unDato); if (minimo == nullptr || unDato <= minimo->dato) // <------ MODIFICACION minimo = n; // <------ MODIFICACION laTalla++; }
Modificamos también el
metodo minimoEnSubarbol
para que, en vez de
devolver el dato mínimo, devuelva la dirección del nodo en el
que está:
class Conjunto { ... Nodo * minimoEnSubarbol(Nodo *) const; // <------ MODIFICACION
Conjunto::Nodo * Conjunto::minimoEnSubarbol(Nodo * n) const { // <------ MODIFICACION // Sabiendo que n != nullptr while (n->izquierdo != nullptr) n = n->izquierdo; return n; // <------ MODIFICACION }
Con ello podemos actualizar minimo
al eliminar si se elimina
el mínimo, como se muestra a continuación:
void Conjunto::eliminar(int unDato, Nodo * & n) { if (n == nullptr) return; if (unDato < n->dato) eliminar(unDato, n->izquierdo); else if (unDato > n->dato) eliminar(unDato, n->derecho); else if (n->izquierdo != nullptr && n->derecho != nullptr) { n->dato = minimoEnSubarbol(n->derecho)->dato; // <------ MODIFICACION eliminar(n->dato, n->derecho); } else { Nodo * basura = n; if (n->izquierdo != nullptr) n = n->izquierdo; else n = n->derecho; if (basura == minimo) // <------ MODIFICACION if (raiz != nullptr) // <------ MODIFICACION minimo = minimoEnSubarbol(raiz); // <------ MODIFICACION else // <------ MODIFICACION minimo = nullptr; // <------ MODIFICACION delete basura; laTalla--; } }
Si nuestra implementación tiene ya el método vaciar
, faltaría
también que al finalizar el mismo el nuevo atributo minimo
quede con valor nullptr
.
void Conjunto::vaciar() { vaciar(raiz); raiz = nullptr; minimo = nullptr; // <------ MODIFICACION laTalla = 0; } void Conjunto::vaciar(Nodo * n) { if (n != nullptr) { vaciar(n->izquierdo); vaciar(n->derecho); delete n; } }
Pregunta 1 Cuando se
comprueba if (raiz != nullptr)
, ¿puede suceder
que raiz
sea nullptr
?
Si raiz
fuese nullptr
, la
eliminación terminaría antes en if (n == nullptr)
return
.
Respuesta 1 Lo que se está comprobando ahí
no es si raiz
era nullptr
inicialmente, sino si ha pasado a ser nullptr
tras la eliminación. Eso sucedería si inicialmente había un
solo nodo, tras ejecutarse la instrucción n =
n->derecho
, en la que n
sería raiz
pasada por referencia.
Pregunta 2 ¿La instrucción minimo
= minimoEnSubarbol(raiz)
no va a obtener el mismo
mínimo que ahora hay, en lugar de uno nuevo?
Respuesta 2 No, porque eso se hace después de haber modificado
el árbol eliminando unDato
. Se obtiene el mínimo del nuevo árbol.
Para actualizar minimo
al eliminar también
podríamos hacer lo siguiente, teniendo en cuenta que, si el
conjunto no queda vacío, el nuevo mínimo será el mínimo del
subárbol derecho del viejo mínimo si existe dicho subárbol
derecho, o su padre en caso contrario:
class Conjunto { ... void eliminar(int, Nodo * &, Nodo *); // <------ MODIFICACION
void Conjunto::eliminar(int unDato) { eliminar(unDato, raiz, nullptr); // <------ MODIFICACION } void Conjunto::eliminar(int unDato, Nodo * & n, Nodo * padre) { // <------ MODIFICACION if (n == nullptr) return; if (unDato < n->dato) eliminar(unDato, n->izquierdo, n); // <------ MODIFICACION else if (unDato > n->dato) eliminar(unDato, n->derecho, n); // <------ MODIFICACION else if (n->izquierdo != nullptr && n->derecho != nullptr) { n->dato = minimoEnSubarbol(n->derecho)->dato; // <------ MODIFICACION eliminar(n->dato, n->derecho, n); } else { Nodo * basura = n; if (n->izquierdo != nullptr) n = n->izquierdo; else n = n->derecho; if (basura == minimo) // <------ MODIFICACION if (basura->derecho != nullptr) // <------ MODIFICACION minimo = minimoEnSubarbol(basura->derecho); // <------ MODIFICACION else // <------ MODIFICACION minimo = padre; // <------ MODIFICACION delete basura; laTalla--; } }
Las modificaciones a realizar en los restantes métodos serían las mismas de la solución 1.