Download Árboles Binarios de Búsqueda - Docencia FCA-UNAM

ESTRUCTURAS DE DATOS
AVANZADAS
Árboles y Grafos
¿Qué son las estructuras de datos
avanzadas?
Son estructuras compejas no lineales y dinámicas
donde en su ejecución varia el número de elementos
y uso de memoria a lo largo del programa.
Entre este tipo de estructuras podemos mencionar a
los árboles, grafos y redes.
¿Qué es un Árbol?
• Son Estructuras de Datos no lineales. Es una
colección de nodos donde cada uno, además de
almacenar información, guarda la dirección de
sus sucesores
• Es una estructura de datos jerárquica.
• La relación entre los elementos es de uno a
muchos.
Terminología
• Nodo: Cada elemento en un árbol.
• Nodo Raíz: Primer elemento agregado al árbol.
Nodo Raíz
A
C
B
D
E
H
F
G
K
Más terminología
• Nodo Padre: Se le llama así al nodo predecesor de un elemento.
• Nodo Hijo: Es el nodo sucesor de un elemento.
• Hermanos: Nodos que tienen el mismo nodo padre.
A
C
B
D
E
H
Nodo Padre
F
F y G son Nodos Hijos de C
F y G son hermanos
G
K
Más terminología
• Nodo Hoja: Aquel nodo que no tiene hijos.
A
C
B
D
E
H
F
G
K
D, H, F y K son Nodos Hojas
Más terminología
• Subárbol: Todos los nodos descendientes por la izquierda
o derecha de un nodo.
A
C
B
D
E
H
F
G
K
Subárbol izquierdo de C
Subárbol derecho de C
Altura y Niveles
A
Altura
del árbol
=4
Nivel 0
C
B
D
E
Nivel 1
F
H
La Altura es la cantidad de niveles.
G
Nivel 2
K
Nivel 3
Elementos del árbol
• Nodo Raíz, Nodos Hijos, Nodos Hermanos, Altura, Recorridos,
Dirección.
• Todo Árbol tiene un solo Nodo Raíz.
• Los Árboles pueden tener o no Nodos Hijos. En caso de
tenerlos, pueden existir Nodos Hermanos.
• Si únicamente tiene un Nodo Raíz, su Altura = 0 y su Nivel = 1.
• Los Recorridos pueden ser en preorden, postorden y en
orden.
• Un Árbol puede recorrerse en dirección Top-Down de arriba
abajo, de abajo arriba, (Down-Top). A partir de su rama
Izquierda o a partir de su rama Derecha.
Tipos de árbol
Llenos
Binarios
Completos
Equilibrados
Por su estructura
Degenerados
Balanceados
Tipos de árboles
Binarios
Por su recorrido
Binarios de búsqueda
B
B+
B*
Multicamino
B+ Prefijos
De Bits
2-4
R
Árbol Binario de Búsqueda (ABB)
• Este tipo de árbol permite almacenar
información ordenada.
• Reglas a cumplir:
– Cada nodo del árbol puede tener 0, 1 ó 2 hijos.
– Los descendientes izquierdos deben tener un valor
menor al padre.
– Los descendientes derechos deben tener un valor
mayor al padre.
Ejemplos de ABB…
21
30
33
13
5
18
25
36
32
40
15
33
21
41
43
¿Por qué no son ABB?
21
5
33
13
17
18
15
25
6
1
22
2
40
4
Definición en C++ del ABB…
struct nodo{
int nro;
struct nodo *izq, *der;
};
typedef struct nodo *ABB;
/* es un apuntador de tipo nodo que hemos llamado ABB, que ulitizaremos
para mayor facilidad de creacion de variables */
Proceso para buscar un nodo...
Buscar el 25
Paso
1
¿El 25 es mayor o
menor que el 21?
21
18
21
33
13
10
Paso
2
33
13
25
40
10
Paso
3
21
33
13
10
18
18
25
40
Encontrado
25
¿El 25 es
mayor o menor
que el 33?
40
Proceso para agregar nodos...
•
Reglas: (busca y agrega hojas)
– El valor a insertar no existe en el árbol.
– El nuevo nodo será un Nodo Hoja del árbol.
•
Procedimiento
1. Buscar el Nodo Padre del nodo a agregar.
2. Agregar el nodo hoja.
Ejemplo
Agregar el valor 26
Paso
1
¿El 26 es mayor o
menor que el 21?
21
18
18
10
Paso
4
21
33
13
10
40
25
25
25
10
18
40
21
33
13
40
¿El 26 es
mayor o menor
que el 33?
33
13
18
Paso
3
21
33
13
10
Paso
2
40
25
Se encontró el Nodo
Padre
26
Agregar el nodo
Recorrido de árboles
•
•
Es el proceso de visitar de una manera
sistemática, exactamente una vez, cada nodo
en una estructura de datos de árbol
(examinando y/o actualizando los datos en
los nodos).
Tales recorridos están clasificados por el
orden en el cual son visitados los nodos.
Recorrido de árboles
Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en
preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo,
comenzando con el nodo de raíz:
1.Visite la raíz
2.Atraviese el sub-árbol izquierdo
3.Atraviese el sub-árbol derecho
Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden
(simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
1.Atraviese el sub-árbol izquierdo
2.Visite la raíz
3.Atraviese el sub-árbol derecho
Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en
postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
1.Atraviese el sub-árbol izquierdo
2.Atraviese el sub-árbol derecho
3.Visite la raíz
¿Qué es un grafo?
• Son Estructuras de Datos complejas no lineales,
en las cuales cada elemento puede tener cero o
más sucesores y cero o más predecesores. Están
formados por nodos (vértices: representan
información) y por arcos (aristas: relaciones
entre la información) .
Tipos de grafos
Grafos dirigidos
• En un grafo generalizado su dirección puede estar
especificada o no. Por el contrario en el grafo dirigido o
también conocido como digrafo, el conjunto de sus aristas
tienen una dirección definida y está determinado por un
par de conjuntos G=(V,A) donde V es un conjunto vacío
llamado vértices o nodos y A es un conjunto de pares
ordenados de elementos de V llamados aristas o arcos que
van del primer al segundo nodo dentro del par.
Grafos ponderados
• Son útiles para medir las distancias en un mapa.
• Por ejemplo el caso de un repartidor de muebles que tiene que
recorrer varias ciudades de México conectadas entre si por las
carreteras que hay entre la Ciudad de México, Guadalajara y
Monterrey, su misión es optimizar la distancia recorrida (minimizar el
tiempo, prever tráfico y atascos). El grafo correspondiente tendrá
como vértices estas ciudades y como aristas la red de carreteras y la
valoración, peso o ponderación será la distancia que hay entre ellas.
Para tal efecto, es preciso atribuir a cada arista un número específico,
ponderación, peso o coste según el contexto, y se obtiene así un grafo
valuado o ponderado.
• Un grafo ponderado o grafo con valores o pesos es un grafo G (V, E),
en el que a cada arista se le asigna un valor real no negativo o peso.
Sobre el conjunto de aristas se introduce una función peso ( w: E->R+
) donde el peso de un subgrafo de un grafo ponderado es la suma de
los pesos de todas sus aristas.
Gráfica de grafo ponderado
Operaciones con Grafos
• Insertar vértice (nodo). Es La operación de inserción de un nuevo nodo.
• Insertar arista. (arco). Cuando se inserte una nueva arista en el grafo, habrá que
añadir un nuevo nodo a la lista de adyacencia (lista que almacena los nodos a los
que un vértice puede acceder mediante una arista) del nodo origen, así si se añade
la arista (A,C), se deberá incluir en la lista de adyacencia de A el vértice C como
nuevo destino.
• Eliminar vértice. Esta operación es inversa a la inserción de l nodo
• Eliminar arista. Eliminación de la relación, se borra un arco del grafo.
• Otras operaciones.- Las operaciones adicionales que puede incluir un grafo son muy
variadas. Además de las clásicas de búsqueda de un elemento o recorrido del grafo,
también podemos encontrarnos con ejecución de algoritmos que busquen caminos
más cortos entre dos vértices, o recorridos del grafo que ejecuten alguna operación
sobre todos los vértices visitados, por citar algunas operaciones de las más usuales.