Algoritmos y Estructuras de Datos - VJ1215

Solución del ejercicio 8 del tema 3

Se proporcionan a continuación cinco soluciones:

La solución 1 es recursiva. Es la forma más simple de resolver este problema.

Su coste temporal en el peor caso es O(2^p). El peor caso se da, por ejemplo, cuando el árbol no tiene ningún nodo a profundidad p y está completo, con todos los nodos posibles, hasta profundidad p - 1.

Su coste espacial en el peor caso, sin contar el coste del propio árbol, es O(p), debido a que puede haber O(p) llamadas recursivas activas simultáneamente y la ocupación espacial propia de cada una en la pila de llamadas es O(1).
Las soluciones 2, 3 y 4 hacen un recorrido por niveles utilizando una cola, como la solución del ejercicio 7 (mostrarPorNiveles), y terminan cuando el nodo que va a ser insertado en la cola está a profundidad p.

El coste temporal en el peor caso de esas tres soluciones es O(2^p), puesto que esa es la cantidad de nodos que podrían ser visitados antes de encontrar uno a profundidad p o descubrir que no hay ninguno.

El coste espacial en el peor caso de esas tres soluciones, sin contar el propio árbol, es O(2^p), debido a que esa es la cantidad de elementos que podría haber en la cola cuando la cola contiene todos los nodos a profundidad p - 1.
En la solución 5 se utiliza una pila en vez de una cola, con lo cual no se recorren los nodos por niveles sino en un orden diferente que también es válido para resolver este problema: coincide con el orden en que se visitan los nodos recursivamente en la solución 1. La pila hace en esta solución un papel análogo al que hace la pila de llamadas en la solución 1.

El coste temporal en el peor caso de la solución 5 es O(2^p), por el mismo motivo que en las soluciones anteriores.

El coste espacial en el peor caso de la solución 5, sin contar el propio árbol, es O(p), porque esa es la cantidad de elementos que puede haber simultáneamente en la pila.

En el tema 6 extenderemos esos tipos de recorridos para aplicarlos a grafos y los denominaremos búsqueda en anchura y búsqueda en profundidad. Los árboles binarios con los que estamos trabajando ahora son un caso particular de grafo que permite algunas simplificaciones.

Solución 1 (recursiva)

bool Conjunto::verificarProfundidad(int p) const {

   return verificarProfundidad(p, raiz);

}

bool Conjunto::verificarProfundidad(int p, Nodo * n) const {

   if (n == nullptr)
      return false;

   if (p == 0)
      return true;

   return verificarProfundidad(p - 1, n->izquierdo) || verificarProfundidad(p - 1, n->derecho);

}

Solución 2 (no recursiva, con cola)

#include <queue>

bool Conjunto::verificarProfundidad(int p) const {
   
   if (raiz == nullptr)
      return false;

   if (p == 0)
      return true;

   queue<Nodo *> cola;
   
   cola.push(raiz);
   int tallaNivel = 1;
   int profundidad = 0;

   while (tallaNivel > 0) {

      for (int i = 0; i < tallaNivel; i++) {
	 Nodo * nodo = cola.front();
	 cola.pop();
	 if (nodo->izquierdo != nullptr) {
	    if (profundidad + 1 == p)
	       return true;
	    cola.push(nodo->izquierdo);
	 }
	 if (nodo->derecho != nullptr) {
	    if (profundidad + 1 == p)
	       return true;
	    cola.push(nodo->derecho);
	 }
      }

      tallaNivel = cola.size();
      profundidad++;

   }

   return false;

}

Solución 3 (no recursiva, con cola)

#include <queue>

bool Conjunto::verificarProfundidad(int p) const {
   
   if (raiz == nullptr)
      return false;

   if (p == 0)
      return true;
   
   queue<Nodo *> cola;
   
   cola.push(raiz);
   int tallaNivel = 1;
   int profundidad = 0;

   while (! cola.empty()) {
      
      Nodo * nodo = cola.front();
      cola.pop();

      if (nodo->izquierdo != nullptr) {
	 if (profundidad + 1 == p)
	    return true;
	 cola.push(nodo->izquierdo);
      }

      if (nodo->derecho != nullptr) {
	 if (profundidad + 1 == p)
	    return true;
	 cola.push(nodo->derecho);
      }

      if (--tallaNivel == 0) {
	 profundidad++;
	 tallaNivel = cola.size();
      }

   }
   
   return false;

}

Solución 4 (no recursiva, con cola)

#include <queue>

bool Conjunto::verificarProfundidad(int p) const {
   
   if (raiz == nullptr)
      return false;

   if (p == 0)
      return true;

   struct Par {
      Nodo * nodo;
      int profundidad;
      Par(Nodo * n, int p) : nodo{n}, profundidad{p} {}
   };

   queue<Par> cola;
   
   cola.push(Par(raiz, 0));

   while (! cola.empty()) {

      Nodo * nodo = cola.front().nodo;
      int profundidad = cola.front().profundidad;
      cola.pop();

      if (nodo->izquierdo != nullptr) {
	 if (profundidad + 1 == p)
	    return true;
	 cola.push(Par(nodo->izquierdo, profundidad + 1));
      }

      if (nodo->derecho != nullptr) {
	 if (profundidad + 1 == p)
	    return true;
	 cola.push(Par(nodo->derecho, profundidad + 1));
      }

   }

   return false;

}

Esto mismo se podría hacer con dos colas en vez de una cola de pares.

Solución 5 (no recursiva, con pila)

#include <stack>

bool Conjunto::verificarProfundidad(int p) const {
   
   if (raiz == nullptr)
      return false;

   if (p == 0)
      return true;

   struct Par {
      Nodo * nodo;
      int profundidad;
      Par(Nodo * n, int p) : nodo{n}, profundidad{p} {}
   };

   stack<Par> pila;
   
   pila.push(Par(raiz, 0));

   while (! pila.empty()) {

      Nodo * nodo = pila.top().nodo;
      int profundidad = pila.top().profundidad;
      pila.pop();

      if (nodo->izquierdo != nullptr) {
	 if (profundidad + 1 == p)
	    return true;
	 pila.push(Par(nodo->izquierdo, profundidad + 1));
      }

      if (nodo->derecho != nullptr) {
	 if (profundidad + 1 == p)
	    return true;
	 pila.push(Par(nodo->derecho, profundidad + 1));
      }

   }

   return false;

}

Esto mismo se podría hacer con dos pilas en vez de una pila de pares.