Algoritmos y Estructuras de Datos (VJ1215)

Estas animaciones de David Galles te pueden ayudar a entender las operaciones con árboles binarios de búsqueda y árboles AVL:

• Binary Search Tree

• AVL Tree

Alternativamente, en esta carpeta puedes encontrar una animación realizada por Arsen Gogeshvili, que muestra más detalladamente lo que sucede en las rotaciones dobles. Existen emuladores de Flash con los que se puede ejecutar. En el fichero LEEME se indican dos de ellos.

1. Como ayuda para entender para qué sirve pasar punteros por referencia, prueba y entiende lo que sucede en este ejemplo. Después realiza este ejercicio.

   En el tema 2 se proporcionó también un primer ejemplo de puntero pasado por referencia, en la primera solución recursiva del ejercicio 5 del tema 2.

2. Vamos a empezar a utilizar en este tema un nuevo tipo de bucles introducidos en C++11, que se corresponden con lo que en otros lenguajes se denomina bucles foreach. Este ejemplo de uso de los bucles foreach en C++ sirve de presentación.

3. En estos ejemplos de errores de programación básica se ilustran errores relacionados con el uso de return que ya no deberías cometer. Fíjate bien en eso por si te sucede y pregunta al profesor en caso de duda.

1. Clase de teoría TE1 06/10
   Clase de prácticas LA2 y LA4 11/10, LA1 y LA3 13/10

   El tiempo estimado de resolución de este ejercicio completo es de 5 horas, correspondientes a 3 horas de trabajo presencial (1 hora de clase de teoría y 2 de prácticas) y 2 horas de trabajo no presencial (casa). En la segunda sesión de prácticas del tema 3 podrás empezar planteando las dudas que te hayan surgido en casa.

   Los ficheros que puedes encontrar en esta carpeta Conjunto/VersionInicial contienen una implementación del TAD Conjunto en la que se emplea un árbol binario de búsqueda para representar internamente los datos. Esa versión inicial se explicará en clase de teoría o prácticas. Puedes consultar al profesor las dudas que tengas. No te preocupes por no entender todo a la primera, basta con que lo acabes entendiendo al hacer los ejercicios.

   Si lo prefieres, puedes utilizar la versión inicial en OnlineGDB. Recuerda que puedes pulsar el botón "Fork this" para obtener una copia editable en la que puedes escribir tus soluciones.

   Partiendo de la versión inicial, realiza progresivamente los siguientes ejercicios. Compila y prueba tu solución de cada uno (con tu propio programa de test) antes de pasar al siguiente apartado, asegurándote de que tratas bien todos los casos.

   1. Añade un método público que devuelva la talla del conjunto.

      int talla() const;
      		  

      Su coste temporal debe ser O(1). Para conseguirlo, puedes añadir atributos y modificar otros métodos.

      Ten en cuenta que la talla del conjunto no cambia, en esta versión, si se intenta insertar un elemento que ya estaba o se intenta eliminar un elemento que no estaba.

      No confundas "talla" del conjunto con "altura" del árbol.

      Solución

   2. Añade un método público que devuelva la suma de todos los elementos del conjunto, visitando para ello recursivamente todos los nodos:

      int sumar() const;
      		  

      En este apartado no nos preocupa la eficiencia del método: no vamos a resolverlo teniendo la suma permanentemente actualizada como hemos hecho en el ejercicio anterior con la talla. Es un ejercicio para aprender a utilizar soluciones recursivas con árboles.

      Analiza su coste temporal y espacial.

      Ayuda

      Solución con ejemplo de error

   3. Añade un método público que sume 1 a cada uno de los elementos del conjunto:

      void incrementarTodos();
      		  

      Analiza su coste temporal y espacial.

      Ayuda

      Solución

   4. Añade un método público que muestre en la salida estándar los elementos del conjunto ordenados de menor a mayor.

      void mostrarOrdenados() const;
      		  

      Su coste temporal debe ser O(n), siendo n la talla del conjunto.

      Ayuda

      Solución con ejemplos de errores

   5. Añade un método público que devuelva un vector con los elementos del conjunto ordenados de menor a mayor.

      vector<int> obtenerOrdenados() const;
      		  

      Su coste temporal debe ser O(n), siendo n la talla del conjunto. Analiza su coste espacial.

      Ayuda

      Solución con ejemplos de errores

      Solución en OnlineGDB

   6. La versión inicial incluye un método para buscar un dato en el conjunto:

      bool buscar(int) const;
      		  

      Sustituye la implementación no recursiva por una implementación recursiva que tenga el mismo coste temporal.

      Solución con ejemplos de errores

   7. La versión inicial incluye un método para insertar un dato en el conjunto:

      void insertar(int);
      		  

      Sustituye la implementación recursiva por una implementación no recursiva que tenga el mismo coste temporal.

      Solución con ejemplos de errores

   8. Añade un método público que elimine todos los elementos del conjunto y libere toda la memoria reservada para almacenarlos.

      void vaciar();
      		  

      Debe tener coste temporal O(n), siendo n la talla del conjunto, y debe dejar el conjunto en un estado que permita realizar nuevas operaciones con él, como si estuviese recién construido.

      Ayuda

      Solución con ejemplos de errores

   9. Como solución del ejercicio 1.h, un estudiante propone implementar así el método vaciar:

      void Conjunto::vaciar() {
         while (raiz != nullptr)
            eliminar(raiz->dato);
      }
      		  

      Otro estudiante propone la siguiente solución:

      void Conjunto::vaciar() {
         while (raiz != nullptr)
            eliminar(minimoEnSubarbol(raiz));
      }
      		  

      ¿Esas soluciones resuelven correctamente el problema? ¿Cuál es su coste temporal en el peor caso? ¿En qué consiste el peor caso para cada solución? ¿Son mejores estas soluciones propuestas en el ejercicio 1.h?

      Solución

   10. Aprovechando que ya está implementado el método privado recursivo minimoEnSubarbol en la versión inicial, utilízalo para añadir un método público que devuelva el valor mínimo del conjunto. Debes lanzar una excepción si el conjunto está vacío.

       int consultarMinimo() const;
       		  

       En este apartado no nos preocupa la eficiencia del método: mejoraremos eso en el ejercicio 1.l.

       Solución

   11. Sustituye la implementación recursiva del método privado minimoEnSubarbol por una implementación no recursiva que tenga el mismo coste temporal. Tu solución del apartado anterior debe seguir funcionando.

       Solución con ejemplo de error

   12. Sustituye la implementación del método público consultarMinimo por una que tenga coste temporal O(1). Puedes hacer para ello los cambios que consideres conveniente en el resto de la clase (puedes, por tanto, añadir atributos y/o modificar métodos) siempre que con ello no empeore el coste temporal de ningún otro método.

       Solución

   13. Ejercicio opcional

       [Fuente: ejercicio 4.32 del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss]

       Diseña un algoritmo eficiente para, dado un árbol binario en el que cada nodo contiene un dato de tipo entero, averiguar si es un árbol binario de búsqueda (es decir, para todo nodo, los datos en su suárbol izquierdo son menores o iguales y los datos en su subárbol derecho son mayores o iguales que el dato en el propio nodo).

       Impleméntalo añadiendo el siguiente método privado a la clase Conjunto:

       bool esArbolBinarioDeBusqueda() const;
       		  

       Analiza el coste temporal de tu solución.

       Puedes utilizar ese método, por ejemplo, para comprobar que el resultado de cada inserción utilizando tu solución del apartado g es un arbol binario de búsqueda.

       Ayuda

       Solución con ejemplo de error

       Código de la solución (observa cómo se utiliza el nuevo método privado dentro de los métodos insertar y eliminar en esta implementación)

2. Partiendo de la implementación del ejercicio 1 (no partiendo de cero) y realizando las modificaciones que consideres conveniente, obtén una implementación del TAD Diccionario que permita almacenar datos de tipo entero (por ejemplo, la puntuación de un jugador) con claves de tipo cadena (por ejemplo, el nombre que identifica al jugador) empleando internamente un árbol binario de búsqueda.

   Puedes utilizar la clase string, que permite comparar cadenas con los operadores relacionales.

   Tu clase Diccionario debe ofrecer los siguientes métodos públicos:

   Diccionario();
   void  insertar(const string &, int); // Recibe clave y dato
   void  eliminar(const string &);      // Recibe clave
   int & buscar(const string &) const;  // Recibe clave, devuelve dato
   void  mostrarOrdenados() const;
   int   talla() const;
   void  vaciar();
   	      

   Observa que son análogos a los del TAD Conjunto, pero ahora las operaciones de eliminación y búsqueda se hacen por clave. La búsqueda devuelve el dato asociado a la clave, por referencia para poderlo modificar, y lanza una excepción en caso de no encontrarlo.

   Este ejemplo de uso podría producir esta salida. Al utilizar claves de tipo string, los elementos del diccionario se muestran ordenados en orden lexicográfico. Observa la interesante instrucción puntuaciones.buscar("Sevilla") = 66, en ella interviene un mecanismo que utilizamos por primera vez este curso: la devolución de un resultado por referencia, con el fin de que pueda ser modificado así.

   Solución

3. 1. Si un árbol binario de búsqueda tiene n nodos, ¿entre qué valores mínimo y máximo se encuentra su altura?

      Solución

   2. Añade a la versión inicial de la clase Conjunto un método público que devuelva la altura de árbol:

      int altura() const;
      		  

      Si el árbol está vacío, devuelve -1.

      Solución

4. Diseña un algoritmo recursivo eficiente cuya entrada sea un árbol binario de búsqueda y cuya salida sea un booleano que indique si todos los nodos tienen cero o dos hijos. ¿Cuál es el coste temporal de tu solución?

   Impleméntalo añadiendo el siguiente método público a la versión inicial de la clase Conjunto:

   bool noHayHijoSinHermano() const;
   	      

   Solución

   Código de la solución

5. Diseña un algoritmo eficiente cuya entrada sean dos árboles binarios y cuya salida sea un booleano que indique si son iguales (con los mismos datos y la misma estructura). ¿Cuál es el coste temporal de tu solución?

   Impleméntalo añadiendo el siguiente método público a la versión inicial de la clase Conjunto:

   bool arbolesIguales(const Conjunto &) const;
   	      

   Solución

   Código de la solución

6. Clase de teoría TE1 13/10

   [Fuente: ejercicio 4.40 del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss]

   Diseña un algoritmo eficiente para mostrar por niveles el contenido de todos los nodos de un árbol binario: debe mostrar primero el contenido de la raíz, después el de los nodos que están a profundidad 1, después el de los nodos que están a profundidad 2, y así sucesivamente. ¿Cuál es el coste temporal de tu algoritmo?

   Impleméntalo añadiendo el siguiente método público a la versión inicial de la clase Conjunto:

   void mostrarPorNiveles() const;
   	      

   Ayuda

   Solución

7. En un árbol, si existen, la raíz está a profundidad 0, los hijos de la raíz están a profundidad 1, los nietos de la raíz están a profundidad 2, etcétera.

   Diseña un algoritmo cuya entrada sean un árbol binario y un entero p, y cuya salida sea un booleano que indique si existe algún nodo que esté a profundidad exactamente p. Puede suceder que el árbol esté vacío.

   Impleméntalo añadiendo el siguiente método público a la versión inicial de la clase Conjunto:

   bool verificarProfundidad(int) const;
   	      

   1. Resuelve el problema de forma recursiva.

   2. Resuelve el problema de forma no recursiva.

   Analiza el coste temporal en el peor caso y el coste espacial en el peor caso de cada solución en función de p (no en función de la talla del árbol), sin contar el coste espacial del propio árbol.

   Solución

   Código de la solución

8. Suponiendo que Multiconjunto internamente utiliza un árbol binario de búsqueda (como Conjunto en el ejercicio 1 pero modificado para aceptar elementos duplicados), considera el siguiente algoritmo de ordenación, que consiste en insertar los datos a ordenar en el árbol y a continuación realizar un recorrido en inorden del mismo para obtenerlos ordenados (como en la solución del ejercicio 1.e):

   void ordenar(vector<int> & v) {
   
      Multiconjunto multiconjunto;
   
      for (int dato : v)
         multiconjunto.insertar(dato);
   
      v = multiconjunto.obtenerOrdenados();
   
   }
   	      

   ¿Cuáles son los costes temporal y espacial de ese algoritmo?

   Solución

   Código de la solución

9. Este ejercicio se ha movido al tema 1, ejercicio 28.

10. Clase de teoría TE1 13/10

    En un árbol AVL inicialmente vacío se insertan los siguientes datos, en este orden: 9, 8, 1, 2, 3, 4, 5, 6 y 7. Dibuja el árbol resultante tras cada inserción. Dibuja el resultado de eliminar el 3 y después el 2 a partir del último árbol.

    Vídeo de la solución (secuencia de inserciones).

    Repite el ejercicio empleando alguna de las animaciones recomendadas en el apartado Recursos.

    Compara el árbol AVL y el árbol binario de búsqueda que se obtienen con esa secuencia de operaciones. Para ello, puedes utilizar también la animación Binary Search Tree.

11. Clase de teoría TE1 20/10

    Responde las siguientes preguntas sobre el siguiente árbol AVL. Verifica tus soluciones, cuando sea posible, empleando alguna de las animaciones recomendadas en el apartado Recursos.

    

    1. Propón una secuencia de operaciones de inserción que, partiendo de un árbol vacío, dé como resultado ese árbol sin realizar ninguna rotación.

    2. ¿Qué rotaciones provoca la eliminación del 13? Dibuja el resultado.

    3. Observa que el árbol inicial tiene talla 12 y altura 4. ¿Hay alguna forma de obtener un árbol AVL de menor talla con esa misma altura?

    4. ¿Cuántos elementos habría que añadir como mínimo al árbol AVL inicial para obtener un árbol AVL de altura 5? Propón una secuencia de operaciones de inserción que lo consiga.

       Ayuda

12. Clase de teoría TE1 15/12

    Considera de nuevo el algoritmo de ordenación del ejercicio 8. Si en vez de un árbol binario de búsqueda se emplea un árbol AVL, el algoritmo se denomina AVL Sort. ¿Cúales son los costes temporal y espacial en ese caso?

    Solución

13. [Fuente: ejercicio 4.22 del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss]

    Estamos utilizando árboles AVL para implementar el TAD Conjunto. Cada nodo tiene un atributo altura para guardar la altura del subárbol cuya raíz es ese nodo.

    Diseña un algoritmo recursivo que compruebe:

    1. que en todos los nodos está bien calculado el atributo altura; y

    2. que en todos los nodos se cumple la propiedad de equilibrio de los árboles AVL.

    Si en todos los nodos está bien calculado dicho atributo y se cumple dicha propiedad, devolverá cierto. En caso contrario, devolverá falso. El coste temporal de tu solución debe ser O(n) siendo n la talla del conjunto.

    Impleméntalo añadiendo el siguiente método público a la versión inicial de la clase Conjunto, además de añadir el atributo altura en Nodo:

    bool verificarEquilibrioAVL() const;
    	      

    Ese método podría tener utilidad para depurar posibles errores en otros métodos.

    Solución

14. [Fuente: adaptación del ejercicio 4.35 del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss]

    Diseña un algoritmo recursivo cuya entrada sea un entero positivo h y cuya salida sea un árbol AVL de altura h con la mínima cantidad posible de nodos para esa altura. En los nodos puedes poner los valores que quieras, pero deben ser diferentes y cumplir la relación de orden de los árboles AVL (que es la de los árboles binarios de búsqueda). Además cada nodo debe tener un atributo con la altura del subárbol del que es raíz. El coste temporal de tu solución debe ser O(n) siendo n la cantidad de nodos.

    Impleméntalo añadiendo el siguiente método público a la versión inicial de la clase Conjunto, además de añadir el atributo altura en Nodo:

    void crearMinimoAVL(int);
    	      

    Solución

15. Clase de prácticas LA2 y LA4 18/10, LA1 y LA3 20/10

    [Fuente: adaptación del ejercicio 4.48 del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss]

    Este es un ejercicio que requiere pensar bastante para diseñar el algoritmo antes de implementarlo.

    Partiendo de nuevo de la implementación Conjunto/VersionInicial y realizando las modificaciones que consideres conveniente, añade un método público que reciba un entero k y devuelva el k-ésimo menor elemento del conjunto (contando desde 0).

    int buscarKesimo(int) const;
    	      

    Por ejemplo, si el conjunto contiene los datos {41, 62, 23, 34, 15, 56} entonces el 0-ésimo menor elemento es 15, el 3-ésimo menor elemento es 41, el 5-ésimo menor elemento es 62, etc. Debes lanzar una excepción si k es negativo o mayor o igual que la talla del conjunto.

    El coste temporal de buscarKesimo debe ser O(h) siendo h la altura del árbol. Como tenemos un árbol binario de búsqueda no equilibrado, eso es O(n); pero si cambiásemos el árbol por un árbol AVL, el coste temporal de buscarKesimo debería ser O(log n).

    Puedes añadir atributos y hacer modificaciones en otros métodos solamente si ello no afecta a su coste temporal: si tenían coste temporal O(h), deben seguir teniendo ese coste.

    Antes de empezar a programar, debes encontrar una solución al problema con el coste temporal que se pide. Es un reto difícil que abordaremos en clase. Tras haberlo intentado, si no se te ocurre ninguna solución, mira esta ayuda. Si necesitas más ayuda, puedes consultar el apartado 19.2 "Estadísticas de orden" del libro "Estructuras de datos en Java" (2013) de M. A. Weiss o el apartado 18.2 "Búsqueda por posición en el orden" de "Estructuras de datos en Java" (2000) del mismo autor (esto no aparece resuelto en la versión en C++ que utilizamos habitualmente).

    Además de realizar tus propias pruebas, puedes utilizar este programa TestKesimo.cpp para probar tu solución (debe producir esta salida TestKesimo.salida; puedes utilizar diff o sdiff en un terminal para comparar tu salida con esa):

    wget http://www3.uji.es/~vjimenez/AED/TEMA3/Conjunto/kesimo/TestKesimo.cpp
wget http://www3.uji.es/~vjimenez/AED/TEMA3/Conjunto/kesimo/TestKesimo.salida
g++ TestKesimo.cpp Conjunto.cpp
./a.out > misalida
diff TestKesimo.salida misalida
sdiff TestKesimo.salida misalida

    Si trabajas con OnlineGDB, para redirigir la salida hacia un fichero puedes introducir run > misalida en su Command line. Con eso, el botón Run te abrirá el fichero misalida en una nueva pestaña y luego lo podrás descargar con el botón Download Code.

    Opcionalmente, implementa dos versiones del método buscarKesimo: una recursiva y una no recursiva.

    Solución con ejemplos de errores

    Código de la solución

16. Ejercicio opcional

    Este ejercicio se basa en la solución del anterior.

    Queremos implementar una variante del TAD Conjunto que permita realizar las siguientes operaciones:

    void insertar(int x); // inserta x en el conjunto si no está ya en él
    void eliminar(int x); // elimina x del conjunto si está en él
    bool buscar(int x) const; // devuelve true si y solo si x está en el conjunto
    int tallaEntreLimites(int, int) const;
    	      

    Con la nueva operación, c.tallaEntreLimites(x, y) debe devolver la cantidad de elementos en el conjunto c que son mayores o iguales que x y menores o iguales que y.

    El coste temporal de tallaEntreLimites debe ser O(h) siendo h la altura del árbol. Como tenemos un árbol binario de búsqueda no equilibrado, eso es O(n); pero si cambiásemos el árbol por un árbol AVL, el coste temporal de tallaEntreLimites debería ser O(log n).

    1. Explica qué añadirías en el árbol para soportar también con coste temporal O(h) la operación tallaEntreLimites, sin que deje de ser O(h) el coste temporal de las otras tres operaciones. Si harías cambios que afectan de algún modo a las tres primeras operaciones, descríbelos. No es necesario que implementes eso.

    2. Añade la operación tallaEntreLimites a la implementación del ejercicio 15.

    Ayuda

    Solución