Download TAD Árbol - EVA FING

Programación 2
10 - TADs Arboles
1
Arboles
Una estructura árbol (árbol general) con tipo base
T es,
1. O bien la estructura vacía
2. O bien un nodo de tipo T, llamado raíz del árbol,
junto con un número finito de estructuras de árbol,
de tipo base T, disjuntas, llamadas subárboles
En un teórico anterior introdujimos algunos conceptos
acerca de árboles. A continución presentamos los
TADs Arbol Binario y Arbol Binario de Búsqueda.
Pero antes queremos ver:
¿cómo representamos árboles generales?
2
Conceptos básicos
Hijo de la raíz
del árbol
Raíz del árbol
...............
Subárboles del árbol
Los elementos se llaman habitualmente nodos del árbol.
3
Un ejemplo de árbol general:
“estructura de directorios”
/usr*
marcos*
carlos*
luis*
libro* curso* basura.c agenda.c trabajo* curso*
cap1.r cap2.r est_alg1*
discreta* logica* prog1*
………………………………………………………………………
Una aplicación: listar un directorio
(recorridos de árboles)
4
¿Cómo representamos árboles generales?
En un árbol general el número de hijos por nodo puede
variar. Luego, una idea de representación consiste en
pensar que cada nodo tiene una “lista” de árboles
asociados (sus subárboles).
Una manera de hacer esto es considerando que cada
nodo se relaciona con su “primer hijo” y con su
“siguiente hermano”, conformando una estructura de
árbol binario.
Esta forma de representación establece una
equivalencia entre árboles generales y árboles
binarios: todo árbol general puede representarse
como uno binario y, todo árbol binario corresponde a
un determinado árbol general.
5
Arbol general - Arbol binario
Cada nodo tiene
un núnero finitio
de subárboles
b
Representación
como árbol binario:
* primer hijo
* siguiente
hermano
b
c
a
d
e
d
e
f g h i j k
……………………….
c
a
f g h i j k
……………………….
6
Un TAD Arbol General particular
Considere la siguiente definición de las operaciones del TAD
ArbolesGenerales no vacíos y sin elementos repetidos, de
un tipo genérico T:
ArbolHoja: Dado un elemento genera un árbol que sólo
contiene dicho elemento (como una hoja).
 Insertar: Dados un Arbol y dos elementos v y w, inserta
a v como el primer hijo de w en el árbol (hijo más a la
izquierda), siempre que w pertenezca al árbol y v no
pertenezca al árbol. En caso contrario, la operación no
tiene efecto.
 EsArbolHoja: Dado un árbol, retorna true si, y sólo si, el
árbol es un árbol hoja (con un solo elemento).
 Pertenece: Dados un árbol y un elemento, retorna true si
y sólo si el elemento pertenece al árbol.
7
Un TAD Arbol General particular (cont.)
 Borrar: Dados un árbol y un elemento, elimina al elemento
del árbol siempre que éste pertenezca al árbol, no sea la
raíz del mismo y no tenga ningún hijo. En caso contrario, la
operación no tiene efecto.
 Otras operaciones o variantes de las anteriores…
Se pide:
a) Especifique en C++ el TAD ArbolesGenerales.
b) Implemente el TAD ArbolesGenerales. Considere la
representación de árboles generales basada en árboles
binarios, como una estructura de datos (“primer hijo” –
“siguiente hermano”).
8
Otras variantes…
• Qué cambiaría en la especificación si el árbol
general permitiera elementos repetidos, siempre y
cuando no sean hermanos?
La noción de ruta absoluta (como en los file
systems) sería útil?
• Y si se permitieran elementos repetidos en
cualquier parte del árbol?
La noción de identificadores “1.3.4.1” (como en los
manejadores de versiones) sería útil?
• Cómo podría ser la especificación de un árbol
general con posiciones implícitas (rutas relativas
en vez de rutas absolutas en el caso de los file
9
systems)
TAD Arbol Binario (AB)
El tipo abstracto de datos Arbol Binario de
elementos de tipo Etype especifica la noción de un
conjunto finito de nodos tal que:
 o bien es vacío
 o consiste de un elemento de Etype (llamado
raíz) y dos árboles binarios de tipo Etype
disjuntos llamados subárbol izquierdo y
derecho de la raíz
10
Arbol Binario (AB)
11
Operaciones del TAD AB
(una alternativa...)
Se definen seis operaciones asociadas al TAD AB.
Constructoras: Vacio y CreoAB.
La primera operación permite construír un árbol vacio.
Dados un elemento de tipo Etype y dos árboles binarios,
CreoAB construye un árbol no vacío.
Predicado: EsVacio.
Esta operación es usada para testear si un árbol es o no
vacío.
Selectoras: Raiz, SubArbIzq y SubArbDer.
Estas operaciones permiten seleccionar la raíz, el
subárbol izquierdo y el derecho, respectivamente, de
un árbol no vacío.
12
Operaciones binarias y árboles binarios
Consideremos la fórmula 4 + 5 + 7.
El cálculo de izquierda a derecha de esta expresión
primero efectúa la suma de 4 y 5, obteniendo el
valor 9, y luego se calcula la suma de 9 y 7,
obteniendo el valor final 16.
El siguiente árbol binario refleja la estructura del
cómputo + ( + (4 , 5) , 7)
+
4
+
5
7
13
Operaciones binarias y árboles binarios (cont)
El siguiente árbol binario refleja la estructura de la
expresión 1 + 2 * 3
1
+
2
*
3
Esta estructura describe un cálculo de derecha a
izquierda de la expresión ya que las reglas de
precedencia de los operadores aritméticos indican
que la multiplicación debe efectuarse antes que la
suma.
14
Operaciones binarias y árboles binarios (cont)
El siguiente árbol binario refleja la estructura de la
expresión a + (x + y + z) * 3
+
'a'
*
+
3
+
'z'
'x'
'y’
En este caso la parentización fuerza una mezcla de
computaciones izquierda-derecha y derechaizquierda. Además algunas de las hojas son
caracteres que identifican los nombres que forman
15
parte de la expresión original.
Operaciones binarias y árboles binarios (cont)
Notar que cada operador es la raíz de un árbol
cuyos subárboles son no vacíos y naturalmente
también reflejan la estructura de una expresión.
No es este el caso de los valores e identificadores.
Cómo quedaría expresado este último árbol si
usamos los constructores del TAD AB para
elementos de un tipo char, por ejemplo?
Qué problemas genera la codificación y
decodificación de los datos si los elementos son
char, por ejemplo?
16
Operaciones binarias y árboles binarios (cont)
Notar que si el tipo de los elementos es refinado
como char (podría también ser *char) tenemos
una disminución en el nivel de abstracción.
Al procesar un árbol de expresiones es bastante
natural pensar que las acciones a tomar van a ser
fuertemente guiadas por los elementos que
ocurren en las raíces de los subárboles que
componen al árbol principal.
La uniformización de la representación de estos
elementos implica un esfuerzo extra de
procesamiento (discriminación y conversión).
17
Operaciones binarias y árboles binarios (cont)
Si las hojas fueran construídas de tal forma que se
pudiera directamente recuperar no solamente la
información que almacenan sino además qué tipo
de información es, el procesamiento de estos
elementos se vería simplificado.
Una posible solución es refinar el tipo T de los
elementos a una unión discriminada de la forma:
typedef int Valor; typedef char Operador;
typedef char Ident;
union E {Valor Val; Operador Op; Ident Id;};
enum TipoExpr {EsVal, EsOpComp, EsId};
struct T {E exp; TipoExpr tipo;};
18
Operaciones binarias y árboles binarios (cont)
Sin embargo, la anterior modificación no soluciona
el problema de redundancia de información que
se genera al construír el nodo correspondiente a
un valor o a un identificador. Esto queda claro por
ejemplo al crear un valor:
´3´
La construcción de la hoja que denota el valor 3
tiene que reflejar el hecho de que estamos
construyendo un nodo del árbol binario.
19
Operaciones binarias y árboles binarios (cont)
Un punto importante en el proceso de abstraer la
noción de expresión aritmética lineal a la de una
forma particular de árbol es el de reflejar que
estamos considerando componentes que poseen
estructuras diferentes y que proveen a su vez
distintos tipos de información.
Este análisis es el que motiva la decisión que hemos
tomado al definir el TAD Expre de expresiones:
20
TAD Expre
// Constructores
Expre ValorExpre(Valor Val)
// Crea una expresión atómica a partir de un valor
Expre VariableExpre(Ident id)
/* Crea una expresión atómica a partir de un
identificador de variable */
Expre OperExpre (Expre exp1, Expre exp2,
Operador op)
/* Crea una expresión compuesta aplicando un operador
a dos expresiones */
21
TAD Expre
// Discriminador (predicado)
TipoExpr QueTipoExpre(Expre e)
// retorna el tipo de la expresión
// Selectoras
Expre SubExpreIzq(Expre e)
/* pre-condición: la expresión es compuesta.
Retorna la sub expresión izquierda */
Expre SubExpreDer(Expre e)
/* pre-condición: la expresión es compuesta.
Retorna la sub expresión derecha */
22
TAD Expre
Operador MainOper(Expre e)
/* pre-condición: expre es una expresión compuesta
Retorna el operador principal */
Valor DarValor(Expre e)
/* pre-condición: la expresión es simple (un valor)
Retorna el valor que construye esa expresión */
Ident DarIdent(Expre e)
/* pre-condición: la expresión es un Identificador
Retorna el identificador */
void DestruirExpre(Expre & e)
/* destruye la expresión e y libera la memoria asociada */
23
Especificación de un ABB
#ifndef _ABB_H
#define _ABB_H
struct RepresenatcionABB;
typedef RepresentacionABB* ABB;
void crearABB (ABB &abb);
/* Devuelve en abb el arbol vacio. */
bool agregarABB (T t, ABB &abb);
/* Agrega el elemento t en abb y devuelve 'true' si t no esta
en abb. En otro caso no hace nada y devuelve 'false'. */
bool esVacioABB (ABB abb);
/* Devuelve 'true' si abb es vacio, 'false' en otro caso. */
T valorABB (ABB abb);
/* Devuelve el valor de la raiz de abb.
Precondicion: ! esVacioABB(abb). */
24
Especificación de un ABB
ABB arbolIzquierdo (ABB abb);
/* Devuelve el subarbol izquierdo de abb.
Precondicion: ! esVacioABB(abb). */
ABB arbolDerecho (ABB abb);
/* Devuelve el subarbol derecho de abb.
Precondicion: ! esVacioABB(abb).*/
void destruirABB (ABB &abb);
/* Libera toda la memoria ocupada por abb.*/
#endif /* _ABB_H */
25
Implementación de un ABB
#include "ABB.h"
#include <stddef.h>
#include <assert.h>
struct RepresentacionABB
{
RepresentacionABB* der;
RepresentacionABB* izq;
T valor;
};
void crearABB (ABB & abb)
{
abb = NULL;
}
bool esVacioABB (ABB abb)
{
return (abb == NULL);
}
26
Implementación de un ABB
bool agregarABB (T t, ABB &abb)
{
bool result;
if (esVacioABB (abb)) {
abb = new RepresentacionABB;
abb->der = NULL;
abb->izq = NULL;
abb->valor = t;
result = true;
}
else if (esMayor (abb->valor, t))
{
result = agregarABB (t, abb->izq);
}
else if (esMenor (abb->valor, t))
{
result = agregarABB (t, abb->der);
}
else result = false;
return result;
}
27
Implementación de un ABB
T valorABB (ABB abb)
{
assert (!esVacioABB (abb));
return abb->valor;
}
ABB
{
}
ABB
{
}
arbolIzquierdo (ABB abb)
assert (!esVacioABB (abb));
return abb->izq;
arbolDerecho (ABB abb)
assert (!esVacioABB (abb));
return abb->der;
28
Implementación de un ABB
void destruirABB (ABB &abb)
{
if(abb != NULL)
{
destruirABB(abb->izq);
destruirABB(abb->der);
delete(abb);
}
}
29
ABB - Análisis
Consideremos un AB (o ABB) completo:
n = 1 + 21 + 22 + … + 2h = 2h+1 - 1
Luego, la altura es O(log2 n) en el caso de un árbol
completo, pero O(n) de un árbol arbitrario. Por qué?
Qué podemos concluir de éste análisis sobre la
eficiencia en tiempo de ejecución de las operaciones
sobre un ABB ?
30
ABB - Análisis
Insertar, Buscar y Borrar tienen tiempo de ejecución
proporcional a log2 n (siempre se recorre un sólo
camino del árbol) si el árbol es completo pero,
la eficiencia puede caer a orden n si el árbol se
degenera (el caso extermo es una lista).
1
2
3
…..
n
31
ABB - Análisis
Si bien el orden de tiempo de ejecución promedio de
las operaciones citadas para ABB’s es O(log2 n),
el peor caso es O(n).
La idea es entonces tratar de trabajar con ABB’s
que sean “completos”, o al menos que estén
“balanceados”…
Tratando de refinar esta idea es que surgen los AVL
32
Arboles AVL
• Un árbol AVL (Adelson-Velskii y Landis) es una ABB
con una condición de equilibrio. Debe ser fácil
mantener la condición de equilibrio, y ésta asegura
que la profundidad del árbol es O(log (n)).
• La condición AVL: para cada nodo del árbol, la altura
de los subárboles izquierdo y derecho puede diferir a
lo más en 1 (hay que llevar y mantener la información
de la altura de cada nodo, en el registro del nodo).
33
Arboles AVL
• Así, todas las operaciones sobre árboles se
pueden resolver en O (log(n)), con la posible
excepción de la inserción (si se usa eliminación
perezosa - recomposición AVL tardía).
AVL Tree
AVL Tree
34
Arboles AVL (cont)
• Cuando se hace una inserción es necesario
actualizar toda la información de equilibrio para
los nodos en el camino a la raíz. La razón de que
la inserción sea potencialmente dificíl es que
insertar un nodo puede violar la propiedad de
árbol AVL.
6
6
2
9
2
9
1
4 8
1
4
3
3
5
ABB y AVL
ABB pero no AVL
35
Arboles AVL: rotaciones
• Al insertar (según la inserción ABB) el 7 en el AVL
anterior se viola la propiedad AVL para el nodo 9.
• Si éste es el caso, se tiene que restaurar la
propiedad AVL antes de dar por culminado el
proceso de inserción. Resulta que esto se puede
hacer siempre con una modificación al árbol,
conocida como rotación (simple y doble).
36
Arboles AVL (cont)
l
k
A
B
Rotación simple
C
A
k
l
B
C
•Ambos son ABB’s ?
•Qué implica una rotación con una implementación
dinámica del árbol ?
•Qué punteros cambian ?
•Qué pasa con las alturas de los subárboles A, B y C ?
•Coinciden los recorridos In-order de ambos árboles ?
37
Arboles AVL (cont)
• Insertar los elementos 1 al 7 a partir de un AVL
vacio.
• Luego, insertar los elementos 8 al 15 en sentido
inverso.
• NOTA: al insertar el 14, una rotación simple no
recompone la propiedad AVL.
• Cuando el elemento insertado se encuentra entre
los valores correspondientes a los nodos del árbol
a rotar (por violación de la propiedad AVL), una
rotación simple no recompone la propiedad AVL.
• Solución: usar una rotación doble, que involucra 4
subárboles en vez de 3.
38
Arboles AVL: rotación doble
l
k
A
D
m
B
l
A
m
B
Izq-Der
Der-Izq
k
C
k
A
C
D
A
m
B
l
C
m
l
B
D
k
C
D
39
Arboles AVL: inserción
• Completar la inserción del 14 al 8 en sentido
inverso.
• Algoritmo de inserción: insertar como en los
ABB y luego iniciar en el nodo insertado y subir en
el árbol, actualizando la información de equilibrio
en cada nodo del camino. Acabamos si se llega a
la raíz sin haber encontrado ningún nodo
desiquilibrado. Si no, se aplica una rotación
(simple o doble, según corresponda) al primer
nodo desiquilibrado que se encuentre, se ajusta
su equilibrio y ya está (no necesitamos llegar a la
raíz, salvo que se use eliminación perezosa).
40
Rebalanceando árboles AVL
Inserciones del tipo ABB que no conducen a un
árbol AVL
– 4 casos
1
2
– 1 y 4 son similares
– 2 y 3 son similares
3
4
41
Rebalanceando árboles AVL
Caso 1 solucionado por rotación simple
– Caso 4 es similar
42
Rebalanceando árboles AVL
Caso 2 necesita una rotación doble
– Caso 3 es similar
43
Arboles AVL: supresión
• Algoritmo de supresión: el algoritmo de
eliminación que preserva la propiedad AVL para
cada nodo del árbol es más complejo.
En general, si las eliminaciones son relativamente
poco frecuentes, puede utilizarse una estrategia
de eliminación perezosa.
• La pertenencia es igual que para los ABB.
• Por más detalles y el código de las operaciones
para una implementación de AVL con estructuras
dinámicas ver el libro de Mark Allen Weiss.
44