=================================================================
Algoritmos y Estructuras de Datos (VJ1215) - Universitat Jaume I
Evaluacion continua - 2022/2023
24 de octubre de 2022
Ejercicio 2
Borrador
=================================================================

Con un arbol binario de busqueda (no equilibrado) las siguientes cuatro
soluciones tiene los siguientes costes en funcion de n:

* Coste temporal en el mejor caso: O(1).

* Coste temporal en el peor caso: O(n).

* Coste espacial en el peor caso sin contar el propio arbol: O(n).

Si el arbol fuese AVL, los costes serian estos:

* Coste temporal en el mejor caso: O(1).

* Coste temporal en el peor caso: O(log n).

* Coste espacial en el peor caso sin contar el propio arbol: O(log n).


Solucion 1
==========

int Conjunto::consultarProfundidad(float dato) const {
   return consultarProfundidad(dato, raiz);
}

int Conjunto::consultarProfundidad(float dato, Nodo * n) const {
   if (n == nullptr)
      return -1;
   if (n->dato == dato)
      return 0;
   int resultado;
   if (n->dato > dato)
      resultado = consultarProfundidad(dato, n->izquierdo);
   else
      resultado = consultarProfundidad(dato, n->derecho);
   if (resultado == -1)
      return -1;
   return resultado + 1;
}


Solucion 2
==========

int Conjunto::consultarProfundidad(float dato) const {
   return consultarProfundidad(dato, raiz, 0);
}

int Conjunto::consultarProfundidad(float dato, Nodo * n, int profundidad) const {
   if (n == nullptr)
      return -1;
   if (n->dato == dato)
      return profundidad;
   if (n->dato > dato)
      return consultarProfundidad(dato, n->izquierdo, profundidad + 1);
   return consultarProfundidad(dato, n->derecho, profundidad + 1);
}


Solucion 3
==========

int Conjunto::consultarProfundidad(float dato) const {
   int profundidad = 0;
   consultarProfundidad(dato, raiz, profundidad);
   return profundidad;
}

void Conjunto::consultarProfundidad(float dato, Nodo * n, int & profundidad) const {
   if (n == nullptr)
      profundidad = -1;
   else if (n->dato != dato) {
      profundidad++;
      if (n->dato > dato)
	 consultarProfundidad(dato, n->izquierdo, profundidad);
      else
	 consultarProfundidad(dato, n->derecho, profundidad);
   }
}


Solucion 4
==========

int Conjunto::consultarProfundidad(float dato) const {
   int resultado = -1;
   consultarProfundidad(dato, raiz, 0, resultado);
   return resultado;
}

void Conjunto::consultarProfundidad(float dato, Nodo * n, int profundidad, int & resultado) const {
   if (n == nullptr)
      return;
   if (n->dato == dato)
      resultado = profundidad;
   else if (n->dato > dato)
      consultarProfundidad(dato, n->izquierdo, profundidad + 1, resultado);
   else
      consultarProfundidad(dato, n->derecho, profundidad + 1, resultado);
}