Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2021/2022

3. Conjuntos y diccionarios mediante árboles de búsqueda

Horas de clases presenciales: 8 (4 teoría + 4 prácticas)
Horas de trabajo no presencial: 12
Ratio: 3 horas no presenciales por cada clase de 2 horas

  1. Árboles binarios de búsqueda
  2. Árboles AVL

Recursos

En este tema nos basaremos en el capítulo 4 "Trees" del libro "Data Structures and Algorithm Analysis in C++" (2014) de M. A. Weiss. Los árboles, los árboles binarios, los árboles binarios de búsqueda y los árboles AVL se introducen en estos apartados:

De las implementaciones, evitaremos aquello que requeriría conocer un curso de Programación Avanzada con C++ previamente y nos fijaremos, fundamentalmente, en los algoritmos de inserción, búsqueda y eliminación.

El código fuente de ese libro también está disponible online. Sería especialmente interesante que observes cómo las implementaciones de los algoritmos de inserción y eliminación en árboles AVL se diferencian de las de los árboles binarios de búsqueda solamente en que terminan llamando a un método balance para restaurar el equilibrio del árbol, y que veas lo que hace ese método empleando rotaciones y cómo están implementadas las rotaciones:

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

En estos vídeos puedes ver ejemplos, proporcionados por estudiantes, de aplicación de los árboles en el campo de los videojuegos:

Recursos en castellano y recursos opcionales

Alternativamente, puedes recurrir a los capítulos 18 "Árboles" y 19 "Árboles de búsqueda binaria" del libro "Estructuras de datos en Java" (2013) del mismo autor (el título "Árboles de búsqueda binaria" es una traducción incorrecta de "Binary search trees", el nombre correcto en castellano es "Árboles binarios de búsqueda"). Aunque las implementaciones en Java que describe no nos interesan ahora, puedes utilizar ese libro para entender los algoritmos y complementarlo con el trabajo que haremos en clase para entender las implementaciones en C++.

  • 18.1 Árboles generales
    • 18.1.1 Definiciones
    • 18.1.2 Implementación
  • 18.2 Árboles binarios (primera página)
  • 19.1 Ideas básicas
    • 19.1.1 Las operaciones
  • 19.4 Árboles AVL
    • 19.4.1 Propiedades
    • 19.4.2 Rotación simple
    • 19.4.3 Rotación doble
    • 19.4.4 Resumen de la inserción AVL

Si con los textos anteriores no entiendes el tema, también puedes encontrar explicaciones alternativas, empleando C++, en los capítulos 12 "Búsqueda: árboles binarios y tablas dispersas" y 15 "Árboles" del libro "TADs, estructuras de datos y resolución de problemas con C++" (2006) de L. R. Nyhoff:

  • 12.2 Introducción a los árboles binarios
  • 12.3 Los árboles binarios como estructura de datos recursiva
  • 12.4 Árboles binarios de búsqueda
  • 15.2 Árboles equilibrados: árboles AVL

Opcionalmente, esta clase de Erik Demaine sobre árboles AVL en el curso 6.006 Introduction to Algorithms, Fall 2011 (MIT OpenCourseWare: Massachusetts Institute of Technology) es una explicación alternativa recomendable de este tema.

Opcionalmente, si tienes 15 minutos mira el capítulo 1 "El número áureo" de la muy recomendable serie de matemáticas de Antonio Pérez "Más por menos" (ahora disponible completa en RTVE a la carta). También te pueden interesar el capítulo 6 "Fibonacci, la magia de los números" (incluyendo el ejemplo de que la importancia de los algoritmos y el tiempo de cálculo es muy anterior a la existencia de los ordenadores, minuto 3:50) y el vídeo "There Will Be Blood / Through Numbers" por Ali Shirazi.

Ejercicios

Entre los resultados de aprendizaje que establece el plan de estudios de la titulación (que se pueden consultar también en el apartado "Actividades y competencias: Resultados" del SIA), a este tema le corresponden estos: "implementar y utilizar correctamente árboles" y "utilizar conjuntos y diccionarios y comprender su posible implementación mediante árboles". Aunque hay otras aplicaciones importantes de los árboles en videojuegos, como ilustran los vídeos del apartado anterior, ajustaremos el escaso tiempo disponible a lo que establece el plan de estudios. Ello te dará una base para poder implementar y utilizar árboles en otras asignaturas y en tu trabajo profesional.

En la mayoría de los ejercicios de este tema utilizaremos la implementación de la clase Conjunto que se proporciona en el ejercicio 1 (correspondiente a la primera sesión de prácticas). En algunos de los ejercicios posteriores al 1 no respetaremos el principio de ocultación de la información, por el cual los métodos públicos de la clase Conjunto no deberían depender de que internamente los datos estén en un árbol. Nuestro interés no será ese sino hacer ejercicios con árboles e implementar los algoritmos.

Algunos conceptos previos con C++

  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 las soluciones del tema 2 se proporcionaron también dos ejemplos de punteros pasados por referencia, en la solución del ejercicio 2.h del tema 2 y 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 los ejercicios de este tema, hay errores de programación básica relacionados con el uso de return que ya no deberías cometer: (i) no devolver ningún resultado en funciones que deben devolverlo; (ii) en funciones que no deben devolver ningún resultado, tratar de devolverlo o trabajar como si lo devolvieran; (iii) llamar a una función para obtener el resultado que devuelve y no hacer nada con él. Fíjate bien en eso por si te sucede y pregunta al profesor en caso de duda. En estos ejemplos de errores de programación básica sucede eso.

Árboles binarios de búsqueda

  1. Clase de teoría TE2 28/09, TE1 30/09
    Clase de prácticas LA2 y LA4 05/10, LA1 y LA3 07/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

    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 prueba (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. Observa la interesante instrucción d.buscar("seis") = -6, 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

    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

  3. 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 prueba

  4. 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 prueba

  5. Clase de teoría TE2 05/10, TE1 07/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

  6. 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 prueba

  7. Clase de teoría TE2 05/10

    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 prueba

  8. Clase de teoría TE2 05/10

    Un árbol biselado (splay tree) es un árbol binario de búsqueda en el que los algoritmos de inserción y eliminación son diferentes de los que hemos estudiado, consiguiendo tener coste amortizado O(log n) y coste en el peor caso O(n). Sin necesidad de saber cómo funcionan esos algoritmos, sabiendo que tienen esos costes, analiza cuál sería el coste temporal en el peor caso del algoritmo de ordenación del ejercicio 8 si sustituimos el árbol por un árbol biselado.

    Solución

Árboles AVL

  1. Clase de teoría TE2 19/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 la animación AVL Tree de David Galles.

    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.

  2. Responde las siguientes preguntas sobre el siguiente árbol AVL. Verifica tus soluciones, cuando sea posible, empleando la animación AVL Tree de David Galles.

    Árbol AVL

    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

  3. Clase de teoría TE2 05/10

    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

  4. [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. Para depurar posibles errores en el código, diseña un algoritmo recursivo que devuelva el valor falso si en cualquier nodo está mal calculado el atributo que indica la altura del subárbol del que es raíz o no 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. 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;
    	      

    Solución

  5. [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. 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

  6. Clase de prácticas LA1 y LA3 14/10, LA2 y LA4 19/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 prueba

  7. 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

Opcionalmente, en las evaluaciones de cursos anteriores puedes encontrar más ejercicios de este tema si quieres seguir practicando.