Ejercicios selectos: árboles binarios (C++).

Representación de un ABB.

1. Siguiendo las consideraciones descritas en el blog respecto a un ABB (entrada Árbol binario de búsqueda (ABB)), realice manualmente, es decir, en papel y lápiz, la inserción de la siguiente secuencia de elementos: 14, 15, 4, 9, 7, 18, 3, 5, 16, 4, 20, 17.
1. Aplique el recorrido en pre orden al árbol resultante.
2. Aplique el recorrido en orden al árbol resultante.
3. Aplique el recorrido en post orden al árbol resultante.
4. Aplique también el recorrido en pre orden inverso.
5. Aplique el recorrido en orden inverso al árbol resultante.
6. Aplique finalmente el recorrido en post orden inverso.
2. Realice lo mismo que en el ejercicio anterior pero con la secuencia de números invertida, i.e.: 17, 20, 4, 16, 5, 3, 18, 7, 9, 4, 15, 14.
1. Aplique el recorrido en pre orden al árbol resultante.
2. Aplique el recorrido en orden al árbol resultante.
3. Aplique el recorrido en post orden al árbol resultante.
4. Aplique también el recorrido en pre orden inverso.
5. Aplique el recorrido en orden inverso al árbol resultante.
6. Aplique finalmente el recorrido en post orden inverso.
3. Modifique el Ejemplo abb para que permita leer números desde la entrada estándar. Corrobore con el programa y los recorridos obtenidos en los ejercicios anteriores que el árbol que genera el programa es el mismo que el que se obtiene en papel y lápiz.
4. Basándose en el Ejemplo abb realice las modificaciones correspondientes para que, a través de nuevos métodos, proporcione solución a lo siguiente:
1. Dadas dos referencias a dos nodos cualesquiera de un árbol binario, determine si r1 es padre de r2 (vea la figura que aparece al inicio de esta sección).
2. Dadas dos referencias a dos nodos cualesquiera de un árbol binario, determine si r2 es hijo de r1 (vea la figura que aparece al inicio de esta sección).
3. Dada una referencia a un nodo cualquiera de un árbol binario, determine si dicho nodo es o no un nodo hoja.
4. Dadas dos referencias a dos nodos cualesquiera de un árbol binario, determine si r1 es ancestro de r2.
5. Dadas dos referencias a dos nodos cualesquiera de un árbol binario, determine si r2 es descendiente de r1.
6. Dada una referencia a un nodo cualquiera de un árbol binario, determine su nivel.
7. Determinar la altura o profundidad de un árbol binario.
8. Determinar si un árbol binario es o no un árbol estrictamente binario.
9. Determinar si un árbol binario es o no un árbol binario completo de profundidad p.
10. La implementación de las operaciones complementarias (en todos los casos nd es una referencia a un nodo cualquiera de un árbol binario.):
1. obten_padre: regresa una referencia al padre de nd.
2. obten_hermano: regresa una referencia al hermano de nd.
3. es_izquierdo: regresa true si nd es un hijo izquierdo de algún otro nodo en el árbol binario, y false en caso contrario.
4. es_derecho: regresa true si nd es un hijo derecho de algún otro nodo en el árbol binario, y false en caso contrario.
11. Determinar el número de nodos de un árbol binario.
12. La suma (se asume que el árbol binario almacena números) de todos los nodos del árbol binario.
5. Modifique el Ejemplo abb para que almacene otro tipo de objetos datos además de int. Pruebe con al menos las siguientes clases (pruebe ambos esquemas de inserción: recursivo e iterativo):
1. float.
2. string.
3. persona y cientifico (del Ejemplo herencia).
6. Modifique el Ejemplo abb para que:
1. En lugar de insertar números aleatorios en el árbol binario de búsqueda, solicite al usuario un número de datos n. Posteriormente deberá leer de la entrada estándar cada uno de los n datos, mismos que serán insertados en el ABB correspondiente.
2. Realice las comprobaciones de los recorridos y árboles generados manualmente. Un recorrido en preorden o postorden le hará saber si el árbol generado es correcto, tome en consideración que un recorrido en orden no le arrojará información útil al respecto.
3. Implemente los recorridos inversos descritos en la entrada (Árboles binarios (recorridos)). Nota: respecto a los recorridos inversos, resultaría sumamente conveniente que, previo a su implementación, realizara el diagrama de clases UML correspondiente basándose en el presentado en la entrada ABB (representación y diseño).
7. Con base en las consideraciones planteadas en el blog respecto a la eliminación de un ABB y al diagrama de clases UML presentado en la entrada ABB (eliminación), implemente la eliminación de elementos para un árbol binario de búsqueda, así como las modificaciones correspondientes mostradas en dicho diagrama.
8. Dada la siguiente secuencia de números: 4, 5, 7, 2, 1, 3, 6, genere en papel y lápiz su correspondiente ABB. Se deberá ilustrar paso a paso el proceso de inserción y realizar la comprobación de cada árbol con el programa generado en el Ejercicio 6.
9. Realice lo mismo que en el ejercicio anterior pero con la secuencia de números invertida, i.e.: 6, 3, 1, 2, 7, 5, 4.
10. Dada la siguiente secuencia de números: 4, 5, 7, 2, 1, 3, 6, genere en papel y lápiz su correspondiente árbol AVL. Se deberá ilustrar paso a paso el proceso de inserción y rebalanceo.
11. Realice lo mismo que en el ejercicio anterior pero con la secuencia de números invertida, i.e.: 6, 3, 1, 2, 7, 5, 4.
12. Dada la siguiente secuencia de números: 8, 9, 11, 15, 19, 20, 21, 7, 3, 2, 1, 5, 6, 4, 13, 14, 10, 12, 17, 16, 18, generar:
1. El correspondiente ABB.
2. El correspondiente árbol AVL.
3. El correspondiente ABB pero con la secuencia de números invertida.
4. El correspondiente árbol AVL pero con la secuencia de números invertida.
5. En cada caso se deberá ilustrar paso a paso en cada uno de los árboles generados, el correspondiente proceso de inserción.
13. Respecto al ejercicio anterior:
1. ¿Qué conjeturas puede obtener?
2. ¿En qué tipo de árbol se genera el árbol de altura mínima?
3. ¿Cuáles serían las ventajas y desventajas de uno y otro esquema de representación de árbol y por qué?
14. Considere la figura (a) que aparece al final de esta entrada de ejercicios, misma que representa un árbol AVL. Utilizando papel y lápiz:
1. Elimine la siguiente secuencia de elementos: 4, 8, 6, 5, 2, 1, 7.
2. Deberá ilustrar paso a paso:
1. Los balances de cada uno de los nodos.
2. La identificación del nodo a eliminar y el proceso de rebalanceo a aplicar en caso de ser necesario.
3. El correspondiente árbol AVL.
3. La solución final al ejercicio se presenta en la figura (b).
15. Genere el diagrama de clases UML que represente el diseño de un árbol AVL con base en lo expuesto en el blog. Puede basarse en el diagrama de la entrada ABB (representación y diseño). La idea de este ejercicio es que su diseño derive en una implementación.
16. Realice la implementación de un árbol AVL. Tome en consideración que, además de mantener los elementos ordenados como en un ABB, en cada inserción deberá verificar el balance de los nodos involucrados, y que en caso de ser necesario, deberá aplicar los mecanismos de rebalanceo descritos en el blog para asegurar que el árbol generado es siempre un árbol AVL.
17. En la entrada Árboles binarios balanceados (AVL) se discuten los aspectos de los árboles AVL relacionados con el rebalanceo después de la inserción. Sin embargo, ¿qué pasa con la eliminación de elementos? Apoyándose en el blog y en el ejercicio anterior, analice y resuelva los aspectos implicados en la eliminación de nodos en un árbol AVL, e implemente una operación que permita realizar la eliminación de un elemento. Asegúrese de mantener siempre un árbol AVL.

(a) Árbol AVL inicial para la eliminación (adaptada del libro Algoritmos y Estructuras de Datos de Niklaus Wirth).

(b) Árbol AVL final después del proceso de eliminación.