Algoritmos y Estructuras de Datos (VJ1215)

Añadimos en cada nodo un atributo tallaIzquierdo para saber la cantidad de nodos de su subárbol izquierdo (valdrá 0 si el subárbol izquierdo está vacío).

class Conjunto {

   struct Nodo {
      int dato;
      int tallaIzquierdo;  // <------ MODIFICACION
      ...
	

Lo inicializamos a cero en el constructor de Nodo:

Conjunto::Nodo::Nodo(int elDato)
   : dato{elDato},
     tallaIzquierdo{0},  // <------ MODIFICACION
     izquierdo{nullptr},
     derecho{nullptr} {
}
	

Al insertar, sumamos 1 a cada nodo por el que pasamos si la inserción se realiza en su subárbol izquierdo. Para ello, hacemos que el método insertar recursivo devuelva un booleano que indique si la inserción se ha realizado (es decir, el dato no estaba ya en el árbol, puesto que no insertamos duplicados). Observa que todas las llamadas al método recursivo devuelven el booleano:

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

Al eliminar, restamos 1 a cada nodo por el que pasamos si la eliminación se realiza en su subárbol izquierdo. Para ello, hacemos que el método eliminar recursivo devuelva un booleano que indique si la eliminación se ha realizado (es decir, el dato estaba en el árbol). Observa que todas las llamadas al método recursivo devuelven el booleano:

bool Conjunto::eliminar(int unDato, Nodo * & n) {  // <------ MODIFICACION
   if (n == nullptr)
      return false;  // <------ MODIFICACION
   else if (unDato < n->dato)
      if (eliminar(unDato, n->izquierdo)) {  // <------ MODIFICACION
	 n->tallaIzquierdo--;                // <------ MODIFICACION
	 return true;                        // <------ MODIFICACION
      } else                                 // <------ MODIFICACION
	 return false;                       // <------ MODIFICACION
   else if (unDato > n->dato)
      return eliminar(unDato, n->derecho);   // <------ MODIFICACION
   else if (n->izquierdo != nullptr && n->derecho != nullptr) {
      n->dato = minimoEnSubarbol(n->derecho);
      return eliminar(n->dato, n->derecho);  // <------ MODIFICACION
   } else {
      Nodo * basura = n;
      if (n->izquierdo != nullptr)
	 n = n->izquierdo;
      else
	 n = n->derecho;
      delete basura;
      return true;  // <------ MODIFICACION
   }
}
	

Teniendo el atributo tallaIzquierdo actualizado en todos los nodos, lo utilizamos para encontrar recursivamente y eficientemente el k-ésimo menor elemento:

int Conjunto::buscarKesimo(int k) const {
   if (k < 0)
      throw string("Usando buscarKesimo con un valor de k que no existe");
   return buscarKesimo(k, raiz);
}

int Conjunto::buscarKesimo(int k, Nodo * n) const {
   if (n == nullptr) // Si tenemos laTalla, esto se podria sustituir por
                     // comprobar que k < laTalla en el metodo anterior
      throw string("Usando buscarKesimo con un valor de k que no existe");
   else if (k < n->tallaIzquierdo)
      return buscarKesimo(k, n->izquierdo);
   else if (k > n->tallaIzquierdo)
      return buscarKesimo(k - (n->tallaIzquierdo + 1), n->derecho);
   else
      return n->dato;
}
	

En la solución anterior, la siguiente implementación de insertar sería incorrecta, porque no se propaga el resultado booleano de las llamadas recursivas en todos los casos:

bool Conjunto::insertar(int unDato, Nodo * & n) {
   if (n == nullptr) {
      n = new Nodo(unDato);
      return true;
   } else if (unDato < n->dato) {
      if (insertar(unDato, n->izquierdo)) {
	 n->tallaIzquierdo++;
	 return true;
      }
   } else if (unDato > n->dato)
      insertar(unDato, n->derecho);
   else
      // No insertamos duplicados
      return false;
}
	

Alternativamente, en los métodos insertar y eliminar se puede utilizar un argumento booleano por referencia para saber si la inserción y la eliminación se han realizado. El resto de modificaciones coincidirían con las de la solución 1.

void Conjunto::insertar(int unDato) {
   bool insertado = true;  // <------ MODIFICACION
   insertar(unDato, raiz, insertado);  // <------ MODIFICACION
}

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

void Conjunto::eliminar(int unDato) {
   bool eliminado = true;  // <------ MODIFICACION
   eliminar(unDato, raiz, eliminado);  // <------ MODIFICACION
}

void Conjunto::eliminar(int unDato, Nodo * & n, bool & eliminado) {  // <------ MODIFICACION
   if (n == nullptr)
      eliminado = false;
   else if (unDato < n->dato) {
      eliminar(unDato, n->izquierdo, eliminado);  // <------ MODIFICACION
      if (eliminado)                              // <------ MODIFICACION
	 n->tallaIzquierdo--;                     // <------ MODIFICACION
   } else if (unDato > n->dato)
      eliminar(unDato, n->derecho, eliminado);    // <------ MODIFICACION
   else if (n->izquierdo != nullptr && n->derecho != nullptr) {
      n->dato = minimoEnSubarbol(n->derecho);
      eliminar(n->dato, n->derecho, eliminado);   // <------ MODIFICACION
   } else {
      Nodo * basura = n;
      if (n->izquierdo != nullptr)
	 n = n->izquierdo;
      else
	 n = n->derecho;
      delete basura;
   }
}
	

El método buscarKesimo de cualquiera de las soluciones anteriores se puede sustituir por el siguiente, en el que se hace el mismo cálculo de forma no recursiva:

int Conjunto::buscarKesimo(int k) const {
   if (k < 0)
      throw string("Usando buscarKesimo con un valor de k que no existe");
   Nodo * n = raiz;
   while (n != nullptr)
      if (k <  n->tallaIzquierdo)
	 n = n->izquierdo;
      else if (k > n->tallaIzquierdo) {
	 k -= (n->tallaIzquierdo + 1);
	 n = n->derecho;
      } else
	 return n->dato;

   // Si tenemos laTalla, lo siguiente se podria hacer al principio si k >= laTalla
   throw string("Usando buscarKesimo con un valor de k que no existe");
}
	

int Conjunto::buscarKesimo(int k) const {
   if (k < 0)
      throw string("Usando buscarKesimo con un valor de k que no existe");
   Nodo * n = raiz;
   while (n != nullptr)
      if (k <  n->tallaIzquierdo)
	 n = n->izquierdo;
      else if (k > n->tallaIzquierdo) {
	 n = n->derecho;
	 k -= (n->tallaIzquierdo + 1);
      } else
	 return n->dato;

   // Si tenemos laTalla, lo siguiente se podria hacer al principio si k >= laTalla
   throw string("Usando buscarKesimo con un valor de k que no existe");
}
	

Este código funciona incorrectamente por intentar acceder a n->tallaIzquierdo después de haber cambiado n con n = n->derecho.