Download Pr ctica N 4: Tipo de dato - Centro de Computación Gráfica

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.
16. Representar gráficamente el árbol AVL correspondiente.
17. Elimine claves consecutivamente hasta encontrar un desequilibrio y dibuje la estructura del árbol tras efectuarse la oportuna
restauración.
18. Qué condiciones debe cumplir un árbol general para que su árbol binario asociado sea balanceado? ¿y ABB? ¿y AVL?
19. 22. 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.
20. 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
21. 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)
22. Dado un arreglo de N enteros ordenados ascendentemente, realice un algoritmo eficiente que construya el árbol AVL
correspondiente, como método constructor.
23. Indique y justifique de qué orden son las operaciones de insertar y eliminar en
 un árbol de búsqueda
 un árbol AVL
24. ¿Qué es más eficiente: Insertar en un árbol AVL, o insertar en un arreglo ordenado?
GDAYED/2011
2