Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 9.k del tema 3

Solución 1

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 9.f, 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;
   }
}

Los estudiantes preguntan

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.

Solución 2

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.