Download Letra práctico 9

Programación 2
Práctico 9 - TADs Árbol Binario de Búsqueda, Árbol
Finitario y Árbol n-ario
Objetivos
Trabajar con los tipos abstractos de datos Árbol Binario de Búsqueda, Árbol Finitario y Árbol
n-ario.
Desarrollar y analizar implementaciones para estos TADs.
Implementaciones Avanzadas.
Primera parte: Especificaciones de Árbol Binario de Búsqueda, Árbol
Finitario y Árbol n-ario.
Ejercicio 1
Desarrollar una especificación funcional (sólo funciones, no procedimientos) para el TAD Árbol Binario de Búsqueda (Binary Search Tree BST) de caracteres, la cual contenga un conjunto mínimo de
constructores, selectores, predicados y destructores para:
Crear un BST vacío.
Determinar si un BST es vacío o no
Inserción y supresión de un carácter en un BST.
Saber si un carácter pertenece un BST.
Ejercicio 2
Las funciones de la Figura 1 presentadas en el Práctico 4, forman una especificación para el TAD Árbol
Finitario (Finitary Tree FT) de naturales (ver Figura 1). Los Árboles n-arios son un caso particular de
los finitarios, donde cada nodo del árbol tiene n hijos. ¿Qué diferencias hay entre la especificación de
Árboles Finitarios y n-arios?
1
2
FTree nullFTree ();
/* Devuelve el á rbol vac í o */
3
4
5
FTree consFTree ( unsigned int x , ListFTree l );
/* Crea un á rbol no vac í o a partir de un natural y una lista de hijos ( sub á rboles ) */
6
7
8
bool IsEmptyFTree ( FTree t );
/* Determina si un á rbol dado es o no vac í o */
9
10
11
unsigned int rootFTree ( FTree t );
/* Devuelve el valor en la ra íz de un á rbol no vac í o */
12
13
14
ListFTree offspringFTree ( FTree t );
/* Devuelve la lista de hijos ( sub á rboles ) de la ra íz de un á rbol no vac ío */
Figura 1: Especificación del TAD Árbol Finitario (Finitary Tree FT) de naturales.
1
Programación 2
Práctico 9 - TADs Árbol Binario de Búsqueda, Árbol Finitario y Árbol n-ario
Segunda parte: Implementaciones de Árbol Binario de Búsqueda, Árbol
Finitario y Árbol n-ario.
Ejercicio 3
Desarrollar una implementación completa del TAD Árbol Binario de Búsqueda del Ejercicio 1.
Ejercicio 4
Desarrollar una implementación completa del TAD Árbol Finitario de naturales del Ejercicio 2, utilizando la representación de primer hijo - siguiente hermano.
Ejercicio 5
Desarrollar una implementación completa del TAD Árbol n-ario de naturales del Ejercicio 2, que tome
provecho de que todos los nodos del árbol tienen n hijos. ¿Qué representación considera adecuada para
representar los hijos?
Tercera parte: Implementaciones Avanzadas
Ejercicio 6
(Segundo Parcial 2009) Suponga que se define una variante de árboles binarios de búsqueda (BST)
balanceados según la cantidad de nodos de los subárboles. Se considera que un BST está balanceado
si para cada nodo se cumple que la diferencia de la cantidad de nodos de sus subárboles (izquierdo y derecho)
difiere en a lo sumo una unidad.
Considere la declaración del tipo de los árboles binarios de búsqueda de enteros que se presenta en
la Figura 2a, donde cada nodo de un árbol de tipo BST guarda en el campo CN la cantidad de nodos
del árbol cuya raíz es dicho nodo. Recordar que la cantidad de nodos de un árbol vacío es 0, por
definición. La Figura 2b presenta un ejemplo gráfico. Cada nodo se representa por un par de valores
donde la primer componente es el valor de dato y el segundo el de CN para dicho nodo. ⊥ representa
el árbol vacío.
(10,8)
1
2
3
4
5
6
struct BSNode {
int dato ;
unsigned int CN ;
BSNode * izq , * der ;
};
typedef BSNode * BST ;
(5,3)
(3,1)
(25,4)
(8,1)
(15,2)
⊥
(a) Definición de tipo para el TAD BST balanceado
(30,1)
(20,1)
(b) Ejemplo
Figura 2: BST balanceado. 6
Implementar una función recursiva insertar que, dados un árbol binario de búsqueda de enteros A de
tipo BST, y un entero x, inserte a x en A y retorne TRUE, si y sólo si, luego de la inserción cada nodo
cumple la condición de balanceo previamente definida. Tenga en cuenta las siguientes consideraciones:
Si x ya estaba en A, la función no deberá modificar el árbol y el resultado será TRUE.
La función insertar debe dejar el campo CN de cada nodo consistente con su definición, asumiendo que en el árbol parámetro se cumple que para cada nodo el campo CN contiene la cantidad de
nodos del árbol cuya raíz es dicho nodo y además, que cada nodo (del árbol parámetro) cumple
la condición de balanceo referida.
Instituto de Computación - Facultad de Ingeniería - UdelaR
Página 2 de 5
Programación 2
Práctico 9 - TADs Árbol Binario de Búsqueda, Árbol Finitario y Árbol n-ario
La función insertar debe recorrer un sólo camino del árbol parámetro. No se permite usar funciones o procedimientos auxiliares en este ejercicio, salvo las funciones que se presentan en la
Figura 3, las cuales se consideran predefinidas.
Cabe aclarar que no se pide balancear el árbol, sino simplemente insertar según el criterio de los
árboles binarios de búsqueda, actualizar los campos CN, que correspondan, y retornar un booleano
que indique si luego de la inserción se cumple la condición de balanceo definida, asumiendo que ésta
originalmente se verificaba en cada nodo del árbol parámetro. La firma de la función insertar es la
siguiente:
bool insertar ( BST &A , int x );
1
unsigned int abs ( int x );
/* Retorna el valor absoluto de x */
1
2
3
4
5
6
caso */
unsigned int cantNodos ( BST A );
/* Retorna 0 si A es el á rbol vac ío y el valor del campo CN de la ra íz de A en otro
Figura 3: Funciones auxiliares para el Ejericio 6.
Ejercicio 7
(Segundo Parcial 2011) Considere una agenda de teléfonos implementada como un árbol general de
caracteres (de ’0’ a ’9’), donde la raíz no tiene información y cada nodo representa a un dígito de
números telefónicos. Las listas de hermanos están ordenadas de forma lexicográfica. El camino de la
raíz a una hoja determina un número telefónico de la agenda, guardándose en cada hoja el nombre
del contacto asociado a ese número. Por ejemplo, el árbol de la figura Fig.4 contiene los contactos: 104
– bombero, 105 – ambulancia, 109 – patrullero, 16 – hora y 911 – emergencia.
()
9
1
⊥
0
4
bombero
6
hora
5
ambulancia
1
⊥
1
emergencia
9
patrullero
Figura 4: Ejemplo de agenda.
Se pide:
Definir la representación en C* del tipo Agenda, árbol general de caracteres implementado como
un árbol con semántica “primer hijo-siguiente hermano”, con la información del contacto en las
hojas. Considere que el tipo de la información del contacto es:
1
typedef
char * InfoContacto ;
Instituto de Computación - Facultad de Ingeniería - UdelaR
Página 3 de 5
Programación 2
Práctico 9 - TADs Árbol Binario de Búsqueda, Árbol Finitario y Árbol n-ario
Implementar, accediendo directamente a la representación, una función ObtenerContacto que, dados un número de teléfono y una agenda, retorne la información del contacto asociado a ese
número. La función tiene como precondiciones que el número de teléfono NO es vacío y que
debe tener exactamente un contacto asociado (esto es, que indica un camino de la raíz a una
hoja).
1
InfoContacto ObtenerContacto ( Telefono tel , Agenda agenda );
El tipo Telefono, de los números de teléfono, es una lista de caracteres. Utilice las operaciones
Primero y Resto del TAD Lista para operar sobre el parámetro tel; considere que estas operaciones
ya están implementadas. La operación Resto retorna un alias al resto de la lista parámetro (sin su
primer elemento).
Implementar, accediendo directamente a la representación, una función ImprimirAgenda que imprima en pantalla la información guardada en una Agenda que se pasa como parámetro.
1
void ImprimirAgenda ( Agenda agenda );
El formato de impresión, que muestra la estructura de árbol finitario que representa la agenda,
se especifica con el siguiente ejemplo.
Si tenemos una variable miagenda con el árbol de ejemplo (ilustrado en la Fig.4), entonces ImprimirAgenda(miagenda) deberá imprimir:
1
-0
–4=bombero
–5=ambulancia
–9=patrullero
-6=hora
9
-1
–1=emergencia
Ejercicio 8
Para trabajar con árboles balanceados es útil guardar en cada nodo información para verificar condiciones de equilibrio. Por ejemplo, en los árboles llamados AVL (que son árboles ABB balanceados)
puede guardarse en cada nodo la altura del árbol que tiene a dicho nodo como raíz.
Se pide, utilizando la siguiente definición de los árboles binarios de búsqueda de enteros, con información de la altura en cada nodo:
1
2
3
4
5
6
struct ABBNodo {
int dato ;
unsigned int altura ;
ABBNodo * izq , * der ;
};
typedef ABBNodo * ABB ;
Figura 5: Definición de tipo para el TAD ABB balanceado.
1. Implementar el procedimiento insertar que dado un ABB de enteros definido como en la Figura
5 y dado un entero, inserte a dicho elemento en el ABB (si ya no estaba) manteniendo la información de la altura de cada nodo. Notar que no se pide balancear el árbol, sino simplemente
insertar el elemento en el ABB dejando en cada nodo en el campo altura el valor correspondiente,
asumiendo que el árbol parámetro guarda en el campo altura de cada nodo el valor correcto. Este
procedimiento no puede usar funciones ni procedimientos auxiliares.
Instituto de Computación - Facultad de Ingeniería - UdelaR
Página 4 de 5
Programación 2
Práctico 9 - TADs Árbol Binario de Búsqueda, Árbol Finitario y Árbol n-ario
2. Implemente una función booleana que retorne TRUE si y sólo si un ABB (del tipo definido
anteriormente) es un AVL. Esto es, se cumple que para cada nodo del árbol la altura de sus
subárboles izquierdo y derecho difiere a lo sumo en 1. El árbol vacío es un AVL. Esta función no
puede usar funciones ni procedimientos auxiliares.
3. Indique los órdenes de tiempo de ejecución en el peor caso del procedimiento definido en la parte
1 y de la función definida en la parte 2. Justifique brevemente.
Instituto de Computación - Facultad de Ingeniería - UdelaR
Página 5 de 5