Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2023/2024

Solución del ejercicio 9.a del tema 3

Añadimos en Conjunto un atributo laTalla (no puede llamarse igual que el método talla):

class Conjunto {
   ...
   int laTalla;  // <------ MODIFICACION
      

Lo inicializamos a cero en el constructor:

Conjunto::Conjunto() : 
   raiz{nullptr},
   laTalla{0} {  // <------ MODIFICACION
}
      

Lo hemos de incrementar al insertar un dato, solo si el dato no estaba. Por ello, lo hacemos cuando se hace new:

void Conjunto::insertar(int unDato) {
   insertar(unDato, raiz);
   // No es correcto incrementar laTalla aqui porque si el dato esta duplicado no se inserta
}

void Conjunto::insertar(int unDato, Nodo * & n) {
   if (n == nullptr) {
      n = new Nodo(unDato);
      laTalla++;  // <------ MODIFICACION
   } else if (unDato < n->dato)
      insertar(unDato, n->izquierdo);
   else if (unDato > n->dato)
      insertar(unDato, n->derecho);
   // No insertamos duplicados
}
      

Lo hemos de decrementar al eliminar un dato, solo si el dato estaba. Por ello, lo hacemos cuando se hace delete:

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);
      eliminar(n->dato, n->derecho);
   } else {
      Nodo * basura = n;
      if (n->izquierdo != nullptr)
	 n = n->izquierdo;
      else
	 n = n->derecho;
      delete basura;
      laTalla--;  // <------ MODIFICACION
   }
}
      

Lo devolvemos en el método talla:

int Conjunto::talla() const {
   return laTalla;
}