Download Árboles Binarios de Búsqueda y AVL
Document related concepts
Transcript
UNIVERSIDAD CENTRAL DE VENEZUELA FACULTAD DE CIENCIAS ESCUELA DE COMPUTACIÓN ALGORITMOS Y ESTRUCTURAS DE DATOS PRÁCTICA DE ÁRBOLES BINARIOS DE BÚSQUEDA Y AVL 1. 2. 3. 4. 5. 6. 7. 8. Sean A y B, Árboles Binarios de Búsqueda (ABB), se dice que A es de menor dominio que B, si el menor elemento de A es mayor o igual que el menor elemento de B, y si el mayor elemento de A es menor o igual que el mayor elemento de B. Defina una operación que verifique si un Árbol Binario de Búsqueda es de menor dominio que otro. Defina una operación para el tipo de dato ABB, que retorne la altura de un árbol de búsqueda. Dado un árbol AVL, hacer una operación que calcule los factores de balance de todos sus nodos. Dado un árbol binario cualquiera, realice una operación que calcule la altura de cada uno de sus nodos. Responda cada una de las siguientes preguntas: a) Todo árbol binario balanceado es perfectamente balanceado? b) Para generar un árbol binario balanceado, a partir de una secuencia de elementos, siempre es necesario realizar rotaciones. c) ¿Qué relación existe entre la altura de un árbol binario de búsqueda y la eficiencia de la búsqueda? d) ¿Cuál es la altura máxima y mínima que puede tener un árbol binario de búsqueda con 200 nodos? e) ¿Cuántos antecesores tiene un nodo en el n-ésimo nivel de un árbol binario de búsqueda. f) ¿La complejidad en tiempo de la operación de búsqueda de un elemento en un árbol binario de búsqueda es siempre una función logarítmica dependiente del número de nodos? g) Se tiene un conjunto de k elementos de tipo entero ordenada en forma ascendente y sin elementos repetidos. A partir de esta secuencia, ¿podría formarse un árbol AVL sin realizar rotaciones? h) ¿Todo árbol de altura mínima es un árbol perfectamente balanceado? i) ¿Todo árbol perfectamente balanceado es un árbol balanceado? j) ¿Es posible construir el árbol general a partir de su árbol binario equivalente? k) ¿Todo árbol general tiene un árbol binario equivalente? Construya el Árbol Binario de Búsqueda Balanceado (AVL) que se obtiene a partir de las inserciones sucesivas de los elementos de la siguiente secuencia de enteros: 12, 3, 2, 5, 4, 7, 9, 11, 14, 10; deberá hacerlo paso a paso, indicando los factores de balanceo de cada nodo y las rotaciones que realice; si las rotaciones son dobles, también hágalas paso a paso. Repita el ejercicio para la secuencia de enteros 20, 15, 16, 12, 9, 8, 4, 1. Como una extensión de la clase Arbin elabore la operación EsPerfBal, la cual dado un árbol binario indique si éste es perfectamente balanceado. Muestre gráficamente cómo queda el árbol AVL dado, y qué tipo de rotación se efectúa al realizar secuencialmente (independientemente) cada una de las siguientes operaciones: Insertar(A,27); Insertar(A,8); Insertar(A,0); Eliminar(A,27); Eliminar(A,8); Eliminar(A,15); Eliminar(A,25); 9. Dado un árbol de búsqueda con n nodos, realice un algoritmo para eliminar los n/2 nodos con las menores claves, de tal manera que el árbol resultante sea de búsqueda. 10. En caso de ser cierta la siguiente proposición, demuéstrela formalmente. En caso de ser falsa, de un contraejemplo que así lo evidencie. “Para cualquier árbol AVL se cumple que para cualquier par de hojas la diferencia de nivel siempre es como máximo uno”. 1 UNIVERSIDAD CENTRAL DE VENEZUELA FACULTAD DE CIENCIAS ESCUELA DE COMPUTACIÓN ALGORITMOS Y ESTRUCTURAS DE DATOS 11. Proponga un esquema de almacenamiento para árboles AVL y ABB con claves repetidas. Defínala gráfica y formalmente, redefina las primitivas que sean necesarias, y defina las nuevas primitivas que así lo sean. 12. Suponga que cuenta con una lista de enteros, donde estos están desordenados y además existen enteros repetidos. Se desea que usted elabore un algoritmo que permita obtener un árbol AVL (ABB balanceado) con dicha lista, pero sin realizar rotaciones. Utilice las primitivas de lista y árboles binarios. 13. ¿Será posible definir un árbol general y que este sea balanceado? En caso de que su respuesta sea negativa justifique porque. En caso de que su respuesta sea positiva, proponga la estructura de datos necesaria, e indique de que manera (textual y algorítmicamente) como deberían elaborarse los algoritmos de inserción y eliminación. 14. Forme un ABB y un AVL con las siguientes secuencias de enteros: 50,25,75,10,40,60,90,35,45,70,42 10,75,34,22,64,53,41,5,25,74,20,15,90 38,24,17,95,83,44,99,72,56,61 21,5,9,14,48,2,18,24,72,36 10,20,30,40,50,60,70,80,90,9,8,7,4,5,6,1,2 60,20,1,10,40,30,55,80,68,64,72,84,82,89.92,90,87,86,75 50,10,6,20,40,28,46,100,80,666 50,25,22,15,40,30,33,44,75,60,90,80,20,15,28 15. Dada la secuencia de claves enteras:100,29,71,82,48,39,101,22,46, 17,3,20,25,10. Representar gráficamente el árbol AVL correspondiente. Elimine claves consecutivamente hasta encontrar un desequilibrio y dibuje la estructura del árbol tras efectuarse la oportuna restauración. 16. Qué condiciones debe cumplir un árbol general para que su árbol binario asociado sea balanceado? ¿y ABB? ¿y AVL? 17. El Código Internacional MORSE asocia a cada letra del alfabeto una secuencia de pulsos cortos (“.”) y/o pulsos largos (“-“). Ejemplo: E = . , G = - - . , L = . - . -. Suponga que se tiene una lista donde se encuentran todas las letras del alfabeto, donde cada posición de la lista tiene la letra asociada y una cola de pulsos que corresponden a la codificación de la letra en dicho lenguaje. A partir de dicha lista proponga un esquema que permita realizar la búsqueda de una letra de la forma más eficiente. Elabore los algoritmos que carguen dicha estructura, y luego los que permiten hacer la codificación y decodificación de mensajes. 18. Suponga que tenemos números entre 1 y 1000 en un ABB y queremos buscar la clave 363 ¿Cuáles de las siguientes secuencias no pudieron haber sido las secuencias de nodos visitados? 2,252,401,398,330,344,397,363. 924,220,911,244,898,258,362,363 925,202,911,240,912,245,363 2,399,387,219,266,382,381,278,363 935,278,347,621,299,392,358363 19. Suponga un árbol ABB que es almacenado en un arreglo, siguiendo el siguiente esquema: Si se recorre el arreglo secuencialmente, se obtiene el recorrido en preorden del árbol. Se indica para cada nodo la posición del hijo derecho y la existencia o no del hijo izquierdo mediante un campo lógico, que si vale falso indica que no existe izquierdo, y si vale cierto tiene hijo izquierdo y es el siguiente en la secuencia del arreglo. Un nodo X es vacío si X = -1. Proponga una estructura de datos que soporte a dichos árboles. Lleve tres de los árboles ABB de la pregunta 23 a esta estructura, y elabore los algoritmos de inserción y eliminación, los cuales deben tener el siguiente perfil: Procedure Insertar(Ref ABB A, Integer X) y Procedure Eliminar(Ref ABB A, Integer X) 20. Dado un arreglo de N enteros ordenados ascendentemente, realice un algoritmo eficiente que construya el árbol AVL correspondiente, como método constructor. 21. Indique y justifique de qué orden son las operaciones de insertar y eliminar en un árbol de búsqueda un árbol AVL 22. En cuánto a eficiencia, ¿qué es mejor: insertar en un árbol AVL, o insertar en un arreglo ordenado? GDAYED/2012 2