Download -INTRODUCCION ÁRBOLES:

INTRODUCCION ÁRBOLES:
Definiciones:
 Un árbol es una colección de nodos (del tipo que se
quiera), uno de los cuales se llama raíz junto con una
relación de “paternidad” que impone una estruc tura
jerárquica sobre los nodos.
 Una manera natural de definirl o es de forma
recursiva:
- Caso base: o el árbol esta vacío o tiene
un solo nodo.
- Caso general: un nodo raíz ( r ) y cero o
más subárboles A1, A2,..., An cada uno
de ellos tiene su raíz conectada a r
mediante una arista.
Ejemplo (índice de un libro):
libro
C1
1.1
C2
1.2
2.1.1
2.1
C3
2.2
2.1.2
Libro seria el nodo raíz (r).
Cada subárbol tendría raíz C1, C2, C3.
El subárbol con raíz C2 tendría como subárboles 2.1
y 2.2.
Partes de un árbol:
 Raíz: el nodo inicial o base de una estructura
en árbol.
 Nodo hoja: el nodo de un árbol que no tiene
hijos.
 Dos nodos son hermanos si tienen el mismo
padre.
 Un camino de un nodo N1 a otro Nk se define
como la secuencia de nodos N1, N2,..., Nk tal
que Ni es el padre de Ni+1 para 1 <= i < k.
 La longitud de este camino es el número de
aristas que lo forman, k -1.
 Existe un camino de longitud cero entre cada
nodo y él mismo. En un árbol hay exactamente
un camino entre la raíz y cada nodo.
 Un nodo es antecesor de un segundo si se
encuentra en el camino de la raíz a este.
 Un nodo es descendiente de un segundo si se
encuentra en el camino de este a algún nodo
hoja.
 La profundidad de un nodo es la longitud del
camino único entre la raíz y este.
 La altura de un nodo es el camino más largo
del nodo a una hoja. La altura de un árbol es
la altura de la raíz.
Ejemplo:
A
B
E
C
F
H
D
G
I
Raíz: A
Hojas: E, H, I, G, D.
B es padre de E, F.
F es hijo de B y hermano de E.
Camino de B a I, B—F—I.
Longitud 2.
Profundidad de F 2 y altura 1.
Recorridos:
Para recorrer un árbol se empieza por el nodo raíz y
se continúa por los hijos, de izquierda a derecha, de tal
manera que en cada nodo, antes de pasar al siguiente
hermano se recorren primero todos sus hijos, también de
izquierda a derecha.
 Recorrido en orden previo o preorden: en este
modo de recorrido, se trabaja en el nodo antes
de pasar al siguiente.
 Recorrido en orden posterior o postorden: en
este, se trabaja en cada nodo una vez que ya
se ha trabajado con todos sus hijos y no
antes.
 Recorrido en orden simétric o o inorden: en
esta forma de recorrido se trabaja en los
nodos hoja la primera y única vez que se pasa
por ellos y en el resto de nodos la segunda
vez.
Ejemplo:
1
2
3
5
8
4
6
9
Recorrido preorden:
1-2-3-5-8-9-6-10-4-7
Recorrido postorden:
2-8-9-5-10-6-3-7-4-1
Recorrido inorden:
2-1-8-5-9-3-10-6-7-4
7
10
RELACIÓN CON GRAFOS:
 Un grafo se define como sigue:
G = (V, A)
Donde
-V (G) es un conjunto finito, no
vacío, de vértices.
-A (G) es un conjunto de aristas (pares
de vértices)
 Un grafo dirigido es un grafo en el cual solo
puedes ir de un vértice a otro en una
dirección.
 Un grafo tiene un ciclo si posee una
trayectoria sin vértices repetidos, excepto el
primero y el último. Un grafo diremos que es
acíclico si no posee ciclos.
 Un grafo es conexo si todo par de vértices
esta unido por una trayectoria.
 Un árbol es un grafo dirigido, ací clico y
conexo.
 Los árboles abarcadores de coste mínimo son
grafos donde cada arista tiene asociad o un
coste, de manera que al moverte de un vértice
a otro lo hagas por el camino de menor coste.
Ejemplo: Redes de comunicación.
1
6
1
5
1
2
3
5
3
6
5
Grafo
1
5
4
6
6
4
2
2
5
3
3
4
4
5
2
6
árbol abarcador de coste mínimo
TIPOS DE ÁRBOLES BINARIOS:
Un árbol binario es un árbol en el que cada nodo puede
tener dos, uno o ningún hijo.
Árboles binarios de expresión:
Las expresiones están formadas por valores sobre
los que pueden ejecutarse operaciones bin arias. Las
distintas partes de la expresión tienen distintos niveles de
procedencia de evaluación, de tal manera que se puede
escribir una expresión en un árbol binario.
Dependiendo de la forma de recorrer el árbol la
expresión habrá que interpretarla de diferente manera.
Para tenerla escrita de la forma habitual habrá que
recorrer el árbol en orden simétrico.
Ejemplo de árbol de expresión:
*
_
12
+
3
4
1
Preorden: *(- (12 3)) (+ (4 1))
Postorden: ((12 3) -) ((4 1) +) *
Inorden: (12 – 3) * (4 + 1)
Montículos:
- Un árbol binario lleno es un árbol binario en el
que todas las hojas están al mismo nivel y cada
nodo que no es una hoja tiene dos hijos.
- Un árbol binario completo es un árbol binario
que es lleno o esta lleno hasta el penúltimo nivel
tan a la izquierda como sea posible
Un montículo debe ser un árbol binario
completo y para cada nodo del montículo, el valor
almacenado en ese nodo es mayor o igual que el valor de
cada uno de sus hijos.
La característica especial de los montículos es
que siempre sabemos donde esta el valor máximo (en la
raíz).Son útiles para la ordenación.
Ejemplo:
Valor máximo es 10 y se encuentra en la raíz del
árbol.
Es un árbol binario completo ya que esta lleno hasta
el penúltimo nivel y en el último nivel tiene los nodos
a la izquierda.
10
8
4
2
9
5
3
6
7
Árbol binario de búsqueda:
Es un árbol binario en el que el hijo izquierdo, si
existe, contiene un valor más pequeño que el del nodo
padre y el hijo derecho, si existe, contiene un valo r mayor
al del nodo padre.
Aplicaciones de los árboles binarios de búsqueda y
comparación con listas:
- Facilita la búsqueda, aunque no facilita
los accesos directos como sucedía con
los arrays. Suministra un acceso más
rápido y constante, así es convenient e
para aplicaciones en las que el tiempo de
búsqueda debe minimizarse.
- Ocupa más espacio que una lista
enlazada (contiene un puntero extra).
- Los algoritmos para manipular el árbol
son más complicados que los de las
listas.
Ejemplo de árbol binario de búsq ueda:
6
2
1
8
4
3
La raíz es 6 que es mayor que 2 y menor que 8.
Así el nodo que contiene el valor 2 es mayor que el valor
del nodo de la izquierda, 1 y menor que el valor del nodo
de la derecha.
Operaciones que suelen darse en los árboles binarios d e
búsqueda:


Estructura.
{Declaración de tipos}
ELEMENTO = T;
NODO = registro de
Valor: ELEMENTO; {Genérico}
izq: puntero a NODO;
der: puntero a NODO;
fin registro;
/* Implementación en C*/
struct nodo{
int valor;
struct nodo *izq;
struct nodo *der;
};
typedef struct nodo NODO;
Crear árbol.
/*Implementación en C*/
/*separar memoria para un nodo*/
NODO *getnode()
{NODO *p;
p=(NODO*) malloc (sizeof (NODO));
return p;
}
NODO *crea_arbol (int v)
{NODO *p;
p=getnode();
p->valor=v;
p->izq=NULL;
p->der=NULL;
return p;
}

Comprobar vació.
Vacia (A: NODO, resp: lógico)
Necesita: un árbol A y un valor lógico resp.
Modifica: resp, indicando si el árbol esta vació (
falso ) o no (cierto).
/* Implementación en C*/
int vacio (NODO *arbol)
{if (arbol==NULL) return 1;
else return 0;
}

Buscar: devuelve un putero al nodo del árbol que
tiene el valor buscado o nil si no existe el nodo. Primero
se mira si el árbol esta vacío, en tal caso el resultado
sería nil. Es importante hacer esta comprobación primero
pues sino intentarías buscar en una estructura vacía, lo
que causaría un error al ejecutarlo. Después se
comprueba si el valor buscado es la raíz del árbol y sino
se hacen llamadas recursivas a los subárboles izquie rdo y
derecho según la relación del valor buscado con la raíz.
/*Implementación en C*/
/*Buscar elementos en un arbol*/
NODO *buscar(int v, NODO *A){
if (vacio(A)==1){
printf ("\n elemento no encontrado");
return NULL;
}
else{
if(v < A->valor) buscar(v,A->izq);
else{
if(v > A->valor) buscar(v,A->der);
else return A;
}
}
}

Buscar_min y buscar_max: Devuelve punteros a los
elementos menor y mayor respectivamente. Se devuelven
punteros, en vez de los valores máximo y mínimo, para
que de esta forma las funciones sean lo más semejantes
posible a la de buscar, ya que de esta forma se simplifican
las cosas.
/*Implementación en C*/
/*buscar el minimo de un arbol*/
NODO *buscar_min (NODO *A)
{if (vacio(A)==1) return NULL;
else
{if (A->izq==NULL) return A;
else buscar_min (A->izq);
}
}
Seria muy parecido buscar el máximo.

Insertar: para insertar un nodo X en el árbol A se
llama a la función buscar y si X ya esta en el árbol no se
hace nada y sino se encuentra X se a ñade al final del
camino recorrido.
/*Implementación en C*/
/*Para insertar elementos*/
NODO *insertar (int v, NODO *A)
{
if (vacio(A)==1) {
A=crea_arbol (v);
if (vacio(A)==1) printf ("\n memoria agotada\n");
}
else
{
if (v < A->valor)
{
if(A->izq==NULL) A->izq=crea_arbol(v);
else insertar(v,A->izq);
}
if (v > A->valor)
{
if(A->der==NULL) A->der=crea_arbol(v);
else insertar(v,A->der);
}
/*Si v ya se encuentra en el arbol no se hace na da*/
}
return A;
}

Eliminar: Hay que tener en cuenta varias
posibilidades:
- Si el nodo es una hoja se puede eliminar
sin más.
- Si el nodo tiene un hijo hay que ajustar el
puntero del padre al hijo del nodo a
eliminar. Si se quiere liberar el nodo
eliminado hay que conservar un puntero
a este.
- Cuando el nodo a eliminar tiene dos hijos
lo que se hace es sustituir el nodo por el
menor del subárbol derecho y luego se
elimina este último, ya de manera
sencilla dado que no tendrá nunca hijo
izquierdo puesto que es el menor del
subárbol.
Si el número de eliminaciones esperadas no es
demasiado grande se usa también la eliminación perezosa,
en la que en vez de eliminar realmente un nodo, solo se
marca como eliminado. La penalización de tiempo es muy
pequeña y si luego se quiere volver a insertar el nodo
eliminado no hace falta tener que crear una celda nueva,
que requiere mucho trabajo, sino sólo quitar la marca.
Árboles AVL ( Adelson-Velskii y Landis ):
Son árboles binarios de búsqueda con una condición
de equilibrio, la cual debe ser fácil de mantener. Dicha
propiedad asegura que la profundidad del árbol sea O (log
n).
La idea de equilibrio más sencilla sería que los
subárboles izquierdo y derecho fuesen igual de profundos,
pero esto no evita que el árb ol sea demasiado profundo.
Otra idea seria que todos los nodos tuviesen los dos
subárboles a la misma altura, pero esto, teniendo en
cuenta que la altura de un árbol vacío se define como –1,
se restringe a los árboles de (2^k) -1 nodos, con lo cual no
es muy útil.
Los árboles AVL son árboles binarios en los que la
diferencia de altura entre los subárboles de cada nodo no
puede ser superior a uno. Hay que mantener en la
estructura de nodo información sobre la altura.
6
2
1
8
4
7
3
Todas las operaciones son iguales que en los
árboles binarios de búsqueda, excepto la inserción y la
eliminación, a no ser que esta sea perezosa, dado que
estas pueden alterar la condición de equilibrio en el árbol.
Para poder hacer siempre estas operaciones hay
que introducir una modificación al árbol, la rotación.
- Rotación sencilla:
K2
k1
Z
K2
X
Y
K1
X
Y
Z
Los dos son árboles binarios de búsqueda. Hay
que tener en cuenta que k1 es menor que k2 en ambos
árboles, que todos los elementos del subárbol X son
menores que k1, todos los elementos del subárbol Z son
mayores que k2 y todos los elementos del subárbol Y
están entre k1 y k2. La transformación del uno al otro se
llama rotación. La rotación cambia la estructura del árbol,
pero esta no deja de ser un árbol binario de búsqueda.
La rotación se puede hacer en cualquier nodo
del árbol. Para mantener la condición de equilibrio de los
AVL lo que se hace cuando se inserta un elemento es ir
recorriendo el árbol desde el nodo insertado hasta la raíz,
comprobando a cada paso si se conserva la condición de
equilibrio y si no es así se hace una rotación, que en
muchos casos sirve para mantener la condición de
equilibrio.
6
6
2
8
1
4
2
7
3
1
7
4
6,5
8
6,5
3
- Rotación doble:
Existe un caso en el que la rotación simple no re compone
el árbol, ejemplo.
4
4
2
1
6
3
2
5
7
1
6
3
5
5
15
15
14
7
14
El problema anterior se soluciona con la rotación doble como se
indica a continuación:
K3
K2
K1
K3
K1
A
K2
D
B
A
B
C
C
Aplicando la rotación doble al ejemplo nos queda el árbol siguiente:
4
2
1
6
3
5
14
7
15
Árboles desplegados:
En los árboles desplegados, después de tener
acceso a un nodo, este se lleva hasta la raíz.
el
Si el nodo que se mueve es muy profundo, por
camino se cambian muchos nodos que son
D
relativamente profundos, y de esta manera cabe esperar
que con la reestructuración se hagan también más rápidos
los futuros accesos a estos nodos.
Algunos estudios han demostrado que los
accesos a un nodo al que ya se ha accedido con
anterioridad son mucho más frecuentes de lo que cabría
esperar, lo cual hace que estos árboles, además de tener
una buena cota de tiempo en teoría sean buenos en la
práctica. Tampoco hace falta mantener la información
relativa a la altura o equilibrio, lo que puede ahorrar
espacio y simplificar el código en cierta medida.
Despliegue: rotaremos en el camino de acceso
al nodo de abajo hacia arriba. Si X es un nodo, distinto de
la raíz, en el camino de acceso en el que estamos rotando:
rotamos.
-
Si el padre de X es la raíz, simplemente
Sino; X tiene un padre ( P ) y un abuelo ( A ):
 Zig-zag; X es un hijo izquierdo y P
un hijo derecho ( o al revés ). En
este caso se hace una rotación
doble como la de los AVL
a
x
p
D
p
a
x
A
A
B
C
B
C
D
 Zig-zig: ambos, X y P, son hijos
izquierdos ( o derechos )
a
x
p
p
D
C
x
A
B
A
B
a
C
D