Download De un árbol - Biblioteca de la UNS

Tópicos I
Unidad I
Árboles, montículos y grafos
Semana 1
Arboles de búsqueda
Objetivos Generales
Entender el manejo, uso de algoritmos y
estructuras de datos avanzados, haciendo
énfasis en los algoritmos de internet,
seguridad y redes.
Objetivo Específico
Implementar
algoritmos
utilizando
estructura de datos avanzadas.
Objetivo Instruccional
Implementar algoritmos de búsqueda en
arboles binarios.
Contenidos
Análisis de algoritmos
Estructuras de datos
Arboles Binarios
Arboles de búsqueda
Análisis de algoritmos
Para la mayoría de los problemas existen varios
algoritmos diferentes. ¿Cómo elegir uno que
conduzca a la mejor implementación?
Normalmente los problemas a resolver tienen un “tamaño”
natural (en general, la cantidad de datos a procesar), al que se
denominara N y en función del cual se tratara de describir los
recursos utilizados (con frecuencia, la cantidad de tiempo empleado).
El punto de interés es el estudio del caso medio, es decir, el
tiempo de ejecución de un conjunto “tipo” de datos de
entrada, y el del peor caso, el tiempo de ejecución para la
configuración de datos de entrada mas desfavorable.
Análisis de algoritmos
Pasos a considerar en el análisis de
algoritmos
El primer paso del análisis de un algoritmo es establecer las
características de los datos de entrada que utilizara y decidir
cual es el tipo de análisis mas apropiado.
Idealmente, seria deseable poder obtener, para cualquier
distribución de probabilidad de las posibles entradas, la
correspondiente distribución de los tiempos empleados en la
ejecución del algoritmo. Pero no es posible alcanzar este ideal
para un algoritmo que no sea trivial, de manera que, por lo
regular, se limita el desarrollo estadístico intentando probar que
el tiempo de ejecución es siempre menor que algún “limite
superior” sea cual sea la entrada, e intentando obtener el
tiempo de ejecución medio para su entrada “aleatoria”.
Análisis de algoritmos
Pasos a considerar en el análisis de
algoritmos
El segundo paso del análisis de un algoritmo es identificar las
operaciones abstractas en las que se basa, con el fin de
separar el análisis de la implementación.
Así, por ejemplo, se separa el estudio del número de
comparaciones que realiza un algoritmo de ordenación del
estudio para determinar cuantos microsegundos tarda una
computadora concreta en ejecutar un código de maquina
cualquiera producido por un compilador determinado para el
fragmento de código if (a[i] < V)…
El primero dependerá de las propiedades el algoritmo, mientras
que el segundo dependerá de las propiedades de la
computadora.
Análisis de algoritmos
Pasos a considerar en el análisis de
algoritmos
El tercer paso del análisis de un algoritmo es analizarlo
matemáticamente, con el fin de encontrar los valores del caso
medio y del peor caso para cada una de las cantidades
fundamentales.
No es difícil encontrar un limite superior del tiempo de ejecución
de un programa – el reto es encontrar el mejor limite superior,
aquel que se encontraría si se diera la peor entrada posible –.
Esto produce el peor caso: el caso medio normalmente requiere
un análisis matemático mas sofisticado.
Análisis de algoritmos
Clasificación de los algoritmos
La mayoría de los algoritmos tienen un
parámetro primario N, normalmente el
numero de elementos de datos a procesar,
que afecta muy significativamente al tiempo
de ejecución.
El parámetro N podría ser el grado de un
polinomio, el tamaño de un archivo a
ordenar o en el que se va a realizar una
búsqueda, el número de nodos de un grafo,
etc.
Proporcionalidad del tiempo de ejecución de
un algoritmo
Análisis de algoritmos
Proporcionalidad
1
Características
La mayor parte de las instrucciones de la mayoría de los programas se
ejecutan una vez o muy pocas veces (constante)
Log N
Cuando el tiempo de ejecución de un programa es logarítmico, este será
ligeramente ms lento a medida que crezca N.
N
Cuando el tiempo de ejecución de un programa es lineal, eso significa
generalmente que para cada elemento de entrada se realiza una pequeña
cantidad de procesos.
N log N
Este tiempo de ejecución es el de los algoritmos que resuelven un problema
dividiéndolo en pequeños subproblemas, resolviéndolos
independientemente, y combinando después las soluciones.
N2
Cuando el tiempo de ejecución de un algoritmo es cuadrático, solo es
practico para problemas relativamente pequeños.
N3
Un algoritmo que procesa tríos de elementos de datos (por ejemplo un bucle
anidado triple) tiene un tiempo de ejecución cubico y no es útil mas que en
problemas pequeños.
2N
Pocos algoritmos con un tiempo de ejecución exponencial son susceptibles
de poder ser útiles en la practica, aunque aparecen de forma natural al
aplicar el método de la “fuerza bruta” en la resolución de problemas.
• Estructuras lineales
Estructuras de datos
Son flexibles pero son secuenciales, un elemento
detrás de otro. Vectores, listas.
• Estructuras no lineales
– Junto con los arboles, los grafos son estructuras
de datos no lineales
– Superan las desventajas de las listas
– Sus elementos se pueden recorrer de distintas
formas, no necesariamente uno detrás de otro
Son muy útiles para la búsqueda y recuperación
de información
Estructuras de datos
ARBOLES
Estructura que organiza sus elementos formando
jerarquías: PADRES e HIJOS

Los elementos de un árbol se llaman nodos

Si un nodo p tiene un enlace con un nodo m,

p es el padre y m es el hijo

Los hijos de un mismo padre se llaman: hermanos
A
B
D
E
C
F

Todos los nodos tienen al menos un padre, menos la raíz: A

Si no tienen hijos se llaman hoja: D, E, F y C

Un subárbol de un árbol

B
Es cualquier nodo del árbol junto con todos
sus descendientes
D
E
F
Estructuras de datos
TERMINOLOGIA
 Camino: Secuencia de nodos conectados
dentro de un árbol
 Longitud del camino: Es el número de nodos
menos 1 en un camino
 Nivel de un árbol: Es el número de nodos entre la
raíz y el nodo mas profundo del arbol
 Altura del árbol: Es el nivel mas alto del árbol
 Un árbol con un solo nodo tiene altura 1
 Nivel (profundidad) de un nodo: Es el número de
nodos entre el nodo y la raíz.
D
 Grado(aridad) de un nodo: Es el número de hijos
del nodo
 Grado(aridad) de un árbol: Máxima aridad de
sus nodos
A
B
E
C
F
TAD ARBOL: Definición Informal
Estructuras de datos
• Valores:
– Un nodo puede almacenar contenido y estar enlazado con
sus árboles hijos (pueden ser dos o varios)
• Operaciones: Dependen del tipo de árbol, pero en general
tenemos:
– Vaciar o inicializar el Arbol
• void Arbol_Vaciar (Arbol *A);
– Eliminar un árbol
• void Arbol_Eliminar(Arbol *A);
– Saber si un árbol esta vacío
• bool Arbol_EstaVacio(Arbol A);
– Recorrer un árbol
• void PreOrden(Arbol A)
• void EnOrden(Arbol A)
• void PostOrden(Arbol A)
Tipo Abstracto Datos
Estructuras de datos
TAD ARBOL: Definición Formal
<arbol> ::= <<NULL>> | <nodo>
<nodo> ::= <contenido>{<arbol>}
<contenido> ::= <<dato>>{<<dato>>}
A
 Tipo especial de árbol
Arboles Binarios
– Cada nodo no puede tener mas
de dos hijos
C
B
D
 Un árbol puede ser un conjunto
RAIZ
– Vacío, no tiene ningún nodo
A
– O constar de tres partes:
• Un nodo raíz y
B
• Dos subárboles binarios:
izquierdo y derecho
D
H
 La definición de un árbol binario
es recursiva
– La definición global depende de si
misma
C
E
I
Sub. Izq.
F
G
J
Sub. Der.
ARBOLES BINARIOS LLENOS
Arboles Binarios
 Un árbol de altura h, esta lleno si:
– Todas sus hojas están en el nivel h
– Los nodos de altura menor a h tienen siempre 2
hijos
 Sea T un árbol
– Si T esta vacío,
• Entonces T es un árbol binario lleno de altura 0
– Si T no esta vacío, y tiene h>0
• Esta lleno si los subárboles de la raíz, son
ambos árboles binarios llenos de altura h-1
Arboles Binarios
ARBOLES BINARIOS COMPLETOS
Un árbol de altura h esta
completo si:
– Todos los nodos hasta el nivel h-2
tienen dos hijos cada uno y
– En el nivel h-1, si un nodo tiene un
hijo derecho, todas las hojas de su
subarbol izquierdo están a nivel h
Si un árbol esta lleno, también
esta completo
OTROS
Arboles Binarios
• Un árbol equilibrado es cuando
– La diferencia de altura entre los subárboles
de cualquier nodo es máximo 1
• Un árbol binario equilibrado totalmente
– Los subárboles izquierdo y derecho de
cada nodo tienen las misma altura: es un
árbol lleno
• Un árbol completo es equilibrado
– Por definición
• Un árbol lleno es totalmente equilibrado
– Por definición
RECORRIDOS
Arboles Binarios
Recorrer es:
– Visitar todos los elementos de una estructura
Como recorrer un árbol
– Hay tantos caminos, ¿cual escoger?
– Existe tres recorridos típicos
• Nombrados de acuerdo a la posición de la raíz
– Preorden: raíz - subarbol izq. - subarbol der.
– Enorden : subarbol izq. - raíz - subarbol der.
– Postorden : subarbol izq. - subarbol der. - raíz
EJEMPLO PREORDEN
Arboles Binarios
1. Visitar raiz
2. Preorden al Subarbol Izq.
3. Preorden al Subarbol Der.
G
1
D
2
B
A
4
3
C
5
K
E
H
6
9
F
J
7
10
8
M
L
13
I
11
G-D-B-A-C-E-F-K-H-J-I-M
G
G-D-B-A-C-E
G-D-B-A-C
G-D-B-A
G-D-B
G-D-B-A-C-E-F
G-D-B-A-C-E-F-K
G-D-B-A-C-E-F-K-H
G-D-B-A-C-E-F-K-H-J
G-D-B-A-C-E-F-K-H-J-I
-D
G-D-B-A-C-E-F-K-H-J-I-M-L
12
Arboles Binarios
AB y NODOAB: Definición Formal
<ab>::= nulo | <nodoab>
<nodoab>::=<contenido> + <izq> + <der>
<izq>::=<ab>
<der>::=<ab>
<contenido>::<<dato>>|{<<dato>>}
AB Y NODOAB: Declaración
Arboles Binarios
• Un árbol binario: es conjunto de nodos
– Solo se necesita conocer el nodo raíz
• Cada nodo
typedef struct NodoAB{
Generico G;
– Dos enlaces: árbol hijo izquierdo, árbol hijo
NodoAB *izq, *der;
}NodoAB;
derecho
– Tiene Contenido y
• Un nodo hoja, es aquel cuyos dos enlaces
apuntan a null
• De un árbol solo se necesita conocer su raíz
– La raíz, que es un nodo, puede definir al
árbol
typedef struct NodoAB *AB;
NODOAB: Operaciones
Arboles Binarios
Son elementos de un árbol que:
– Almacenan información (contenido),
– Conocen hijo izquierdo y derecho, ambos son nodos
Operaciones Básicas
– Crear un nuevo nodo hoja
• NodoAB *NodoAB_CrearHoja(Generico G);
– Eliminar hoja existente
• void NodoAB_Eliminar (NodoArbol **A);
– Saber si el nodo es o no hoja
• bool NodoAB_EsHoja(NodoArbol *p);
Arboles Binarios
NODOAB: Mas Operaciones
Consultas de los campos de un nodo
– Generico NodoAB_ConsultaContenido(NodoAB *nodo);
– NodoAB *NodoAB_Izq (NodoAB *nodo);
– NodoAB *NodoAB_Der(NodoAB *nodo);
Cambiar los campos de un nodo
– void NodoAB_SetContenido (NodoAB *nodo , Generico G);
– void NodoAB_SetIzq(NodoAB *nodo, NodoAB *enlace);
– void NodoAB_SetDer(NodoAB *nodo, NodoAB *enlace);
Arboles Binarios
AB: CREAR NODO HOJA
Se debe crear un nodo nuevo: un nodo hoja
NodoAB *NuevaHoja(Generico G){
NodoAB *nuevo;
nuevo = (NodoAB *)malloc(sizeof(NodoAB));
nuevo->G = G;
nuevo->izq = NULL;
nuevo->der= NULL;
return nuevo;
}
AB: Mas Operaciones
• Eliminar
Arboles Binarios
– AB_Eliminar(AB *A);
• Estado del Arbol
– bool AB_EstaVacio(AB A);
• Añadir y remover nodos
– void AB_InsertarNodo(AB *A, NodoAB *nuevo)
– NodoAB *AB_SacarNodoxContenido(AB *A, Generico G,
Generico_fnComparar fn);
– NodoAB * AB_SacarNodoxPos(AB *A, NodoAB *pos);
• Busqueda por contenido
– NodoArbol *AB_Buscar(AB A, Generico G, Generico_fnComparar fn
);
• Recorridos
– void AB_PreOrden(AB A);
– void AB_PosOrden(AB A);
– void AB_EnOrden(AB A);
Arboles Binarios
AB: Creando e Instanciando
Un Arbol Vacío, es aquel cuyo nodo raíz apunta a
NULL
void AB_Vaciar(AB *A){
*A = NULL;
}
Para crear una variable tipo Arbol, y empezarla a usar:


Instanciarlo (crear variable)
Vaciar el árbol
AB A;
AB_Vaciar(&A);
Para añadirle una hoja al árbol, crear hoja:
A = NodoAB_CrearHoja(Generico_CrearEntero(1));
A
1
Arboles Binarios
RECORRIDOS: Implementación
• Como ya se reviso, las operaciones de recorrido son
recursivas
• Ejemplo: EnOrden
– Recorrer EnOrden al subarbol izquierdo
– Visitar nodo raiz
– Recorrer EnOrden al subarbol derecho
• En todo algoritmo recursivo debemos buscar dos
casos:
– Básico, en que momento termina la recursividad
– Recursivo, donde la función se llama a si misma
Caso Básico
 Si AB_EstaVacio(raiz)
Terminar de recorrer
Caso Recursivo
 Si !AB_EstaVacio(raiz)
AB_EnOrden(raiz->izq);
Mostrar raiz->I
AB_EnOrden(raiz->der);
Arboles Binarios
OPERACION ENORDEN
void AB_EnOrden(AB A, Generico_fnImprimir imprimir){
if(!AB_EstaVacio(A)){
AB_EnOrden(A->izq,imprimir);
imprimir(A->G);
AB_EnOrden(A->der,imprimir);
}
}
A
4
Arbol Vacio!, Terminar
B
C
2
6
D
E
F
G
1
3
5
7
Arboles Binarios
APLICACIÓN: Evaluación de
Expresiones
• Ya se sabe lo de las expresiones
– InFija, operador en medio
– PreFija, operador antes de dos operandos
– PosFija, operador luego de dos operandos
• Para evaluar una expresión dada, podríamos
– Pasarla a posfija y usar solo pilas
– Pasarla a posfija y usar pilas y un árbol de
expresión
Arboles Binarios
ARBOL DE EXPRESION
• Arboles que representan expresiones
en memoria
– Todos los operadores tienen dos operandos
• La raiz puede contener el operador
• Hijo izq: operando 1, Hijo derecho: operando 2
– Ejemplo:
(a+b)
(a+b)*c
+
a
*
+
b
a
c
b
Ejercicio en Clase
Arboles Binarios
• Construya arboles de expresión para:
(X+(Y*Z)) * (A-B)
• Deducir la expresión del siguiente A.B.
+
a
*
b
+
c
d
Arboles Binarios
Evaluar una expresión aritmética
en infija
La expresión se transforma a la expresión
posfija
– Esto, ya sabemos como hacerlo
Crear un árbol de expresión
– Para esto se va a usar una pila y un árbol de
caracteres
Usando el árbol, evaluar la expresión
Crear un árbol de expresión
Arboles Binarios
• Los operandos serán siempre nodos hoja del árbol
• Los operadores serán nodos padre
A*B-C*D+H
AB*CD*-H+
+
D
H
B
A
C
*
A
C
B
D
A
B
A
*
*
B
*
*
-
*
H
C
D
C
D
Evaluación de la expresión
postfija
Arboles Binarios
•
•
Lo ideal es recuperar los dos operandos, el operador, y ejecutar la
opción
¿Que recorrido es el ideal?
– PostOrden
Para evaluar el árbol:
Si el árbol tiene un solo nodo y este almacena un
operando
El resultado de la evaluación es el valor de ese
operando
+
-
H
A
1. Res1 = Evaluó subarbol izquierdo
*
*
B
C
Si no
D
A*
(A
y*BB) y- (C*D)
CyD+
(C*D)
y HH
2. Res2 = Evaluó subarbol derecho
3. Recupero la info de la raiz y efectuo la operación
allí indicada, entre Res1 y Res2
Árbol binario de búsqueda
Árbol de búsqueda
• Los elementos en un árbol
– Hasta ahora no han guardado un orden
55
– No sirven para buscar elementos
30
• Los arboles de búsqueda
– Permiten ejecutar en ellos búsqueda
binaria
4
• Todos los nodos del sub. Der. Tienen una
clave mayor que la clave de la raíz
85
41
– Dado un nodo:
• Todos los nodos del sub. Izq. Tienen una
clave menor que la clave de la raíz
75
6
4
9
5
Árbol de búsqueda
TAD ABB: Definición
 Valores:
– Conjunto de elementos
– Dado un nodo p,
<abb>::= NULL | <abb_nodo>
<abb_nodo>::=<clave>+<contenido>+<izq>+<der>
<izq>::=<abb>
<der>::=<abb>
<clave>::<<dato>>|{<<dato>>}
<contenido>::<<dato>>|{<<dato>>}
• Los nodos del árbol izquierdo almacenan valores mayores al
de p
• Los nodos del árbol derecho almacenan valores menores al
de p
 Operaciones
– Son las mismas operaciones que para un AB
– Pero en este caso ya tenemos reglas suficientes que nos
indican como:
• Insertar
• Sacar
• Buscar
typedef struct ABB_Nodo{
Generico clave, G;
ABB_Nodo *izq, *der;
}ABB_Nodo;
Árbol de búsqueda
Crear con clave
• Como el nodo ahora tiene un campo clave
– Cambian un poco las operaciones del nodo
• Ejemplo
NodoAB *NuevaHoja(Generico clave, Generico contenido){
NodoArbol *nuevo;
nuevo = malloc(sizeof(NodoArbol));
nuevo->clave = clave;
nuevo->G = contenido;
nuevo->izq = NULL;
nuevo->der= NULL;
return nuevo;
}
Árbol de búsqueda
CREACION DE UN ABB
• Un árbol de búsqueda debe mantener
– A la derecha valores mayor a la raíz
– A la izquierda valores menor a la raíz
• Ejemplo:
– Construya árbol con los siguientes elementos:
• 8, 3, 1, 20, 10, 5, 4
8
3
20
1
5
4
10
Árbol de búsqueda
Ejercicio en clase
• Construya el árbol para almacenar:
12, 8, 7, 16, 11
?
Árbol de búsqueda
Búsqueda de un nodo
• Dada una clave, devolver el nodo
que la contiene
• Se comienza en la raíz
– Si el árbol esta vacío
• No se encontró
– Si clave buscada es igual a la clave del
nodo evaluado
Buscar(raiz,25)
Buscar(raiz,5)
• Se encontró
Si no
• Si la clave buscada es mayor a la del
nodo evaluado
– Buscar en el subarbol derecho
• Si no
1
– Buscar en el subarbol izquierdo
8
3
20
5
4
10
No existe
Árbol de búsqueda
Implementación de la
búsqueda
NodoABB *ABB_Buscar(ABB A, Generico clave, Generico_fnComparar comp){
if(ABB_EstaVacio(A)) return NULL;
if(f(clave, A->clave) == 0) return A;
if(f(clave, A->clave) > 0))
return ABB_Buscar(A->der, clave, comp);
else
return ABB_Buscar(A->izq, clave, comp);
}
Árbol de búsqueda
Inserción de un nodo
• Muy parecido a la búsqueda
• Debo insertar en la posición
correcta
– El árbol debe mantener sus
propiedades
• Pasos:
Insertar(raiz,15)
15>8…der
15<20…izq
8
15>10
…der
3
1
– Crear una nueva hoja
– Buscar en el árbol donde ponerla
– Enlazar el nuevo nodo al árbol
5
4
10
20
Insertar
aqui
15
Árbol de búsqueda
Implementación de la inserción
bool ABB_Insertar(ABB *A, NodoABB *nuevo, Generico_fnComparar f){
if(!ABB_EstaVacio(*A)){
if(f(nuevo->clave, (*A)->clave) >0)
ABB_Insertar((*A)->der, nuevo,f);
} else{
}
else if(f(nuevo->clave, (*A)->clave) <0)
ABB_Insertar((*A)->izq,nuevo,f);
else
return FALSE;
//Si esta vacio, alli insertar
*A = nuevo;
}
return TRUE;
Árbol de búsqueda
Eliminación de un nodo
• Es mas compleja que la inserción
• Al sacar un nodo del árbol
Eliminar(raiz,34)
– El árbol debe mantener sus propiedades
– El árbol debe reajustarse
• Pasos:
– Buscar el nodo p que se va a eliminar
6
34
28
18
90
25
– Si el nodo a eliminar tiene menos de dos hijos 20
28
• Subir el nodo hijo a la posición del nodo
eliminado
nmayor
Si no
• Ubicar el nodo q con la mayor de las claves
menores
• Reemplazar contenido de p con el del nodo q
• Eliminar el nodo q que se encontró en el primer
paso
100
Árbol de búsqueda
Implementación de sacar un
nodo
NodoABB *ABB_SacarNodoxContenido(ABB *A, Generico clave,
Generico_fnComparar fn) {
NodoABB *p, *tmp = *A;
if(ABB_EstaVacio(*A)) return NULL;
if(fn((*A)->clave, clave) < 0)
return(ABB_SacarNodoxContenido(&(*A)->der, clave,
fn));
else if(fn((*A)->clave, clave) >0)
return(ABB_SacarNodoxContenido(&(*A)->izq, clave, fn));
}
if((*A)->der == NULL)
(*A) = (*A)->izq;
else if((*A)->izq == NULL)
(*A) = (*A)->der;
else
tmp = ABB_SacarRaiz(A);
return tmp;
REVISAR…
Métodos de búsqueda elementales:
–
–
–
–
Búsqueda secuencial
Búsqueda binaria
Búsqueda por árbol binario
Búsqueda directa en arboles binarios
Métodos de ordenación elementales:
–
–
–
–
–
Ordenación por selección
Ordenación por inserción
Ordenación de burbuja
Ordenación de shell
Ordenación rápida (Quicksort)
Tópicos I
Unidad I
Árboles, montículos y grafos
Semana 1
Arboles de búsqueda