Download Árbol binario - Informática y Sistemas de Computación

Unidad 4.- Estructuras no lineales.
4.1 Árboles.
4.1.1 Definición.
4.1.2 Representación en memoria de árboles.
4.1.2.1 Árboles generales.
4.1.2.2 Árboles binarios.
4.1.3 Recorridos en un árbol binario.
4.1.3.1 Preorden.
4.1.3.2 Inorden.
4.1.3.3 Posorden.
4.1.4 Balanceo de árboles binarios.
4.1.5 Clases para la implementación de árboles.
4.2 Grafos.
4.2.1 Definición.
4.2.2 Tipos de grafos.
4.2.3 Representación de grafos en memoria.
4.2.4 Clases para la implementación de grafos.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Definición
Un árbol es una colección de elementos, llamados
nodos, uno de los cuales se distingue con el nombre
de raíz, los cuales mantienen una relación
(parentezco) que define una estructura jerárquica
entre ellos.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Concepto de árbol
 Estructura Jerárquica no lineal, dinámica.
 Relaciones padre-hijo entre nodos.
 Ejemplos: sistema de archivos, estructura de un
libro, diagrama organizacional, árboles genealógicos,
etc.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Concepto de árbol
 Un árbol se caracteriza por estar formado por un
conjunto finito de nodos, conectados por una serie de
aristas, tales que verifican que:
 hay un único nodo especial llamado raíz.
 los nodos restantes se dividen en árboles mas
pequeños llamados subárboles.
 cada nodo, excepto la raíz, tiene un único nodo padre.
 la definición de árbol implica tener una estructura
recursiva (por la división en subárboles).
 la representación de los árboles se realiza con
notaciones típicas de los árboles genealógicos.
 hay un único camino desde la raíz hasta cada nodo.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Terminología básica
 Raíz: único nodo sin padre. Ej.: nodo A
 Nodo interno: tiene al menos un hijo. Ej.: nodos B, F, C
 Nodo hoja (externo): nodo sin hijos. Ej.: nodos E, I, J,
K, G, H, D
 Descendiente directo: hijo.
Ej.: B es descendiente directo de A
 Descendiente: hijo, nieto, etc…
Ej.: I es descendiente de F, B y A
 Subárbol: árbol formado por
un nodo y sus descendientes.
Ej.: los nodos encerrados en
el triangulo
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Terminología básica
 Grado de un nodo: Num. de descendientes directos.
Ej.: el nodo B es grado 2.
 Grado de un árbol: el grado mayor de sus nodos. Ej.: el
nodo A y F son los de mayor grado (3), por lo tanto el
árbol es grado 3.
 Árbol binario: árbol de grado 2,
cada nodo tiene como mucho dos
descendientes directos.
 Árbol multicamino: árbol de
grado mayor que 2, cada nodo
puede tener n descendientes
directos.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Terminología básica
 Profundidad de un nodo: Num. de predecesores. Ej.:
profundidad de A es 0, profundidad de H es 2.
 Altura del árbol: es igual a la profundidad de su nodo
mas profundo + 1. Ej.: la profundidad de I, J y K que son
los nodos mas profundos es 3 por lo tanto la altura de
árbol es 3 + 1 = 4.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Terminología básica
 Camino: existe un camino del nodo X al nodo Y, si
existe una sucesión de nodos que permita llegar desde X
hasta Y, su longitud es el número de aristas que lo
conforman.
camino(A,K)= {A, B, F, K}
longitud 3
camino(C,K)= {} no hay camino
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Recorrido Preorden
 Se visita primero la raíz, luego el subárbol izquierdo y
por ultimo el subárbol derecho, esto de manera recursiva
para cada subárbol partiendo de la raíz.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Recorrido Inorden
 Se visita primero el subárbol izquierdo, luego la raíz y
por ultimo el subárbol derecho, esto de manera recursiva
para cada subárbol partiendo de la raíz.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Recorrido Postorden
 Se visita primero el subárbol izquierdo luego el
subárbol derecho y por ultimo la raíz, esto de manera
recursiva para cada subárbol partiendo de la raíz.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Ejemplo: expresiones aritméticas
 nodos internos: operadores.
 nodos hoja: operandos.
2(a – 1) + 3b
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Ejemplo:
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Implementación
basada en enlaces
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Árboles Binarios de Búsqueda
 Un árbol binario de búsqueda es un árbol binario en
el que para cada nodo n,
 todas las claves de los nodos del subárbol
izquierdo son menores que la clave de n (o
igual).
 y todas las del subárbol derecho mayores
(o igual)
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Ejemplo:
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Ejemplo:
Unidad 4. Estructuras no lineales.
4.1 Árboles.
 En algunos casos se exige que el árbol sea completo,
es decir que todo nodo interno tenga sus dos
descendientes.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Operaciones:
 Búsqueda.
 Inserción.
 Eliminación
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Búsqueda
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Búsqueda
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Inserción
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Inserción
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Ejemplo de Inserción
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Ejemplo de Inserción
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Eliminación
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Algoritmo para borrar un nodo de un árbol binario de búsqueda.
Para borrar un nodo con información X se presentan los siguientes casos.
1.- Que el nodo no exista: no se realiza ninguna acción.
2.- El nodo a eliminar tiene 0 o 1 hijo: El padre del nodo a eliminar (abuelo)
toma como hijo al nodo nieto.
3.-El nodo a eliminar tiene 2 hijos: El nodo con la información X no se borra
físicamente, se realiza una sustitución de información, (solo datos) con una
de las siguientes acciones.
a) La información mayor del subárbol izquierdo.
b) La información menor del subárbol derecho.
c) Después de la sustitución el valor que sustituyo al nodo X se
manda a eliminar partiendo del subárbol donde se encuentra.
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Eliminación
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Eliminación
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Árbol binario: operaciones del TAD
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Árboles Equilibrados
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Árboles Equilibrados
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Árboles Equilibrados
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Árboles Equilibrados
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Árboles Equilibrados
Unidad 4. Estructuras no lineales.
4.1 Árboles.
Árboles Equilibrados
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Introducción
• Los grafos sirven para representar relaciones
arbitrarias (no necesariamente jerárquicas) entre
objetos de datos
PLAZA DE
CASTILLA
GUZMAN
EL BUENO
NUEVOS
MINISTERIOS
CUATRO
CAMINOS
AVDA. DE
AMÉRICA
CANAL
GREGORIO
MARAÑÓN
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Introducción: aplicaciones
• Circuitos electrónicos
– Tarjetas impresas
– Circuitos integrados
• Redes de transporte
– Autopistas
– Vuelos
• Redes de ordenadores
– LANs
– Internet
– Web
• Bases de datos
– Diagramas
entidad/relación
lab-a01
Lab-a02
it.uc3m.es
inf.uc3m.es
uc3m.es
telefonica.net
rediris.net
otro.net
juan
pablo
david
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Fundamentos: definiciones
• Un grafo consiste en un conjunto de vértices o nodos y
un conjunto de arcos. Se representa con el par G =
(V,A).
• Un arco o arista está formado por un par de nodos u y
v, y se representa por (u,v)
• Un grafo es dirigido si los pares de nodos que forman
los arcos son ordenados y se representan u  v. Un
grafo no dirigido es aquel que los arcos están formados
por pares de nodos no ordenados, se representa u  v.
• Si (u,v) es una arista en A(G), entonces u y v se dice
que son vértices adyacentes.
• Un arco tiene, a veces, asociado un factor de peso, en
cuyo caso se dice que es un grafo valorado.
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Fundamentos: grafos dirigidos
b
Grafo no dirigido
V(G1) = {a,b,c,d}
A(G1) = {(a,b),(a,d),(b,c),(b,d)}
d
a
c
Grafo dirigido
V(G2) = {1,3,5,7,9}
A(G2) = {(1,3),(3,1),(9,1),
(3,5),(5,7)}
3
9
5
1
7
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Fundamentos
• Grado de un nodo
– En un grafo dirigido
• Grado de un nodo u = nº de aristas que contienen a u
– En un grafo dirigido
• Grado de entrada de u = nº de arcos que llegan a u
• Grado de salida de u = nº de arcos que salen de u
• Grafos conexos
– Un grafo no dirigido es conexo si existe un camino entre
cualquier par de nodos que forman el grafo
– Ejemplos:
grafo conexo
grafo no conexo con dos
componentes conexas
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Fundamentos: camino
• Un camino P de longitud n en
el grafo G desde u0 a un es la
secuencia de n+1 vértices P =
(u0, u1, ..., un) tal que (ui,ui+1)
son arcos de G para 0  i  n
• Un camino es simple si todos
los nodos que forman el
camino son distintos,
pudiendo ser iguales los
extremos del camino
• Ejemplo:
– P1 es simple
– P2 no es simple
a
U
c
V
b
d
P2
P1
X
e
W
g
f
Y
h
Z
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Fundamentos: ciclos y bucles
• Un ciclo es un camino
simple cerrado con u0=un,
compuesto al menos por
tres nodos
• Un ciclo es simple si
todos sus vértices y arcos
son distintos
• Un arco que va desde un
vértice a sí mismo (u,u) se
denomina bucle
• Ejemplo
– C1 es un ciclo simple
– C2 es un ciclo no simple
a
U
c
V
b
d
C2
X
e
C1
g
W
f
h
Y
Z
Unidad 4. Estructuras no lineales.
4.2 Grafos.
TAD GRAFO
•
Composición:
<grafo> :: = {<vertice>} + {<arista>}
<vertice> ::= <<refVertice>> + [<<info>>]
<arista> ::= <<refVertice>> + <<refVertice>>
<grafoEtiquetado> :: = {<vertice>} + {<aristaEtiquetada>}
<vertice> ::= <<refVertice>> + [<<info>>]
<aristaEtiquetada> ::= <<refVertice>> + <<refVertice>> +
<<etiqueta>>
Unidad 4. Estructuras no lineales.
4.2 Grafos.
TAD GRAFO: Operaciones
Creación del grafo
crearGrafo (grafo)
Inclusión de vértices
insertarVertice(grafo, vertice)
Eliminación de vértices borrarVertice(grafo, referenciaVertice)
Inclusión de aristas
insertarArista(grafo, vertice1, vertice2)
Borrar aristas
Recorrido del grafo
borrarArista(grafo,arista)
recorrer(grafo,tipoRecorrido)
Unidad 4. Estructuras no lineales.
4.2 Grafos.
TAD GRAFO: Operaciones
Acceso a los vertices
Modificación de vertices
info(referenciaVertice)  Informacion
grado(referenciaVertice)  Entero
gradoEntrante(referenciaVertice)  Entero
gradoSaliente(referenciaVertice)  Entero
adyacentes(referenciaVertice)  {referenciaVertice}
incidentes{referenciaVertice)  {referenciaVertice}
esAdyacente(refenciaVertice1, referenciaVertice2) Boolean
asignarInfo(referenciaVertice, valorInformacion)
Acceso a las aristas
vertices(referenciaArista)  (refVertice, refVertice)
destino(referenciaArista)  refVertice
origen(referenciaArista)  refVertice
etiqueta((referenciaArista)  etiqueta
Modificación de aristas
asignarEtiqueta(referenciaArista, valorEtiqueta)
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Representación: matriz de adyacencia
• Matriz de adyacencias
Sea G = (V,A) un grafo de n nodos, suponemos que los
nodos V = {u1,...,un} están ordenados y podemos
representarlos por sus ordinales {1,2,...,n}.
La representación de los arcos se hace con una matriz A de
nxn elementos aij definida:
1 si hay arco (ui,uj)
aij
0 si no hay arco (ui,uj)
• Optimización
Usar la diagonal principal de la matriz de adyacencia para
representar la existencia de un vértice
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Representación: matriz de adyacencia
3
1
1
3
5
1
4
2
2
2
4
0
0
0
0
0
1
0
1
0
0
1
3
0
1
0
0
0
0
0
0
0
1
0
0
1
0
0
5
6
1
2
2
0
1
1
1
1
0
0
1
4
1
0
0
0
1
1
0
0
0
0
0
0
0
1
0
6
0
0
0
2
0
0
0
0
0
0
0
1
0
0
2
0
0
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Representación
• Matriz de adyacencia
– Poco eficiente si el nº de vértices varía a lo largo del
tiempo de vida del grafo
– Puede darse el caso de que el nº de vértices sea
mayor del previsto inicialmente
– Poco eficiente cuando el grafo tiene pocos arcos (la
matriz es “dispersa”)
• Listas de adyacencia
– Representar una lista de todos los vértices
– Cada objeto vértice guarda una lista de adyacencia
con un objeto arista para cada vértice alcanzable
desde él
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Representación: listas de adyacencia
• Ejemplo
3
2
1
3
2
3
3
1
4
1
5
4
4
5
1
2
4
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Recorridos
• Primero en profundidad
• Primero en anchura
– Visitar vértice inicial vi
– Visitar vértice inicial vi
– Visitar vértice adyacente a vi
– Visitar todos los vértices
adyacentes a vi
... proceder así hasta
encontrar uno ya visitado...
– Al terminar, comenzar a
visitar los adyacentes a
– Volver atrás hasta llegar a
los adyacentes a vi
un vértice con adyacentes
sin visitar
... proceder así hasta que
no queden vértices por
– El recorrido termina cuando
visitar
volviendo atrás llegamos al
vértice innicial vi y no
quedan adyacentes por
recorrer
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Recorridos
• Profundidad
• Anchura
RPA(vi)
{
RPP(vi)
marcar vi como visitado
{
meter vi en cola q
marcar vi como visitado
mientras cola q no vacía
para cada vk adyacente a v
sacar v de cola q
si vk no visitado
para cada vk adyacente a v
entonces RPP(vk)
si vk no visitado
}
entonces
marcar vk visitado
meter vk en cola q
}
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Recorridos: operaciones auxiliares
• Marcar vértice como visitado
– Si los vértices están identificados por algún tipo ordinal,
emplear un conjunto que contenga los identificadores de
los vértices visitados
• Encontrar los vértices adyacentes
– Con matrices de adyacencia: recorrer la fila
correspondiente al vértice, buscando columnas a TRUE
– Con listas de adyacencia: recorrer la lista
• Cola de vértices visitados en anchura
– Operaciones del TAD Cola
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Recorrido primero en profundidad
2
3
1
6
3
1
7
10
4
11
9
2
10
4
11
12
13
8
8
5
5
7
9
6
12
1, 3, 6, 10, 13, 12, 9, 5, 2, 4, 7, 8, 11
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Recorrido primero en profundidad
1
2
3
4
5
6
7
8
9
10
11
12
13
1
2
3
4
5
6
7
8
9 10 11 12 13
0
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
1
0
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
0
1
2
4
3
6
10
7
11
8
5
9
12
13
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Recorrido primero en anchura
4
3
1
1
5
6
8
10
7
2
4
3
6
11
9
11
13
8
2
7
5
10
9
12
12
1, 3, 4, 2, 6, 7, 8, 5, 10, 11, 9, 13, 12
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Recorrido primero en anchura
1
2
3
4
5
6
7
8
9
10
11
12
13
1
2
3
4
5
6
7
8
9 10 11 12 13
0
1
1
1
0
0
0
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
0
0
1
0
0
1
0
1
1
0
0
0
0
0
0
1
1
1
0
0
1
1
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
1
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
1
1
0
0
0
0
0
0
1
1
0
0
0
1
0
1
0
0
0
0
0
0
0
1
1
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
0
0
0
0
0
1
1
1
0
1
2
3
4
5
6
7
8
9
10
11
12
13
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Árbol reducido/de expansión
• Un árbol puede verse como un caso
particular de un grafo: un grafo
conexo acíclico
• Para obtener el árbol reducido de un
grafo hay que eliminar todas las
aristas que producen ciclos, pero
manteniéndolo conexo
– Aplicación: encaminamiento en
redes de comunicaciones
• No existe un único árbol reducido de
un grafo, pues dependerá del nodo
de partida y de la forma de recorrerlo
• Cuando el grafo es valorado, puede
calcularse el árbol de expansión de
coste mínimo
grafo
Árbol de
expansión
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Árbol reducido (anchura)
6
3
1
10
7
4
11
13
8
2
5
9
12
Unidad 4. Estructuras no lineales.
4.2 Grafos.
Árbol reducido (profundidad)
6
3
1
10
7
4
11
13
8
2
5
9
12