EDA Tema 10 gmolto
Páginas: 13 (3128 palabras)
Publicado: 11 de septiembre de 2015
Tema 10- Representación Jerárquica:
Árboles Binarios
Índice general:
1.
La Estructura Jerárquica Árbol
Á
Tema 10- Representación
Jerárquica: Árboles Binarios
Definición y terminología asociada
C i
Caminos
entre
t nodos:
d
profundidad,
f did d nivel
i l y altura
lt
de
d un nodo
d
Relaciones entre nodos
1.
2
2.
3.
2
2.
El Árbol Binario
1.
2.
Germán Moltó
3.
Escuela Técnica Superior deIngeniería Informática
3.
Uni ersidad Politécnica de Valencia
Universidad
Objetivos
Conocer la estructura de Árbol Binario y sus principales
p
p
propiedades, operaciones y recorridos.
Introducir el Árbol Binario de Búsqueda
q
((ABB)) como una
de las EDAs más potentes orientadas a la búsqueda.
Conocer las operaciones
p
que
q soporta
p
un ABB y cómo su
coste varía en función de lo Equilibradoque esté el
Árbol.
3
Búsqueda Dinámica en un Árbol Binario
1.
1
Conceptos y propiedades
Definición y representación recursiva
Operaciones de exploración en profundidad y por niveles
Introducción al Árbol Binario de Búsqueda
2
Bibliografía
Libro de M.A. Weiss, “Estructuras de Datos en Java” (AdissonWesley, 2000).
Apartados 1 – 3 del capítulo 18 para las definiciones vistas en
t í
teoría. Apartado 5 del capítulo 6 para la introducción de las estructuras
de Árbol y Árbol Binario.
Libro de R. Wiener y L.J.J Pinson,, “Fundamentals of OOP and Data
Structures in Java” (Cambridge University Press, 2000).
Apartados 3, 4 y 9 del Capítulo 15
4
Justificación del Tema
Introducción: Estructuras Jerárquicas (I)
Estudiaremos diferentes implementaciones de los
modelos de Cola dePrioridad y Diccionario.
A menudo, los datos de una colección presentan una
relación jerárquica:
Montículo Binario
(Heap)
Implementación de
Cola de
Prioridad
Imposible representar linealmente con LEG o un array.
Ejemplo 1: Estructura de un directorio de librerías (al estilo del
laboratorio de prácticas):
Implementación de
Árbol Binario
Árbol Binario
de Búsqueda
I
Implementación
l
tió de
d
Diccionario
Implementación de
Tabla de Dispersión
(Hash)
NodoLEG
5
6
Introducción: Estructuras Jerárquicas (II)
Ejemplo
j p 2: Representación
p
de una expresión
p
aritmética
totalmente parentizada en notación infija.
Introducción: Estructuras Jerárquicas (III)
La estructura en Árbol:
((( ) (
(((a*b)+(c+d))*(e-f))
)) ( ))
*
*
a
e
+
b c
Relaciones jerárquicas entrelos datos de una colección.
Búsqueda en tiempos sublineales, lo que no se puede
conseguir
i usando
d una representación
ió lineal.
li l
Ejemplo: Representar la Colección de Palabras {mes, mesa,
meta,
t metro,
t coro y corona}.
}
+
Alternativa 1: Usando un array de cadenas:
f
d
8
String
St
i [] vCadenas
C d
= new String[6];
St i [6]
¿Cuál es el coste de buscar una palabradada en esa colección?
¿¿Existen instancias significativas?
g
Alternativa 2: Usando una lista enlazada de palabras.
7
LEG
¿Cuál es el coste?
¿Existen instancias significativas?
Introducción: Estructuras Jerárquicas (IV)
Alternativa 3: Empleamos un árbol para representar la
C l ió d
Colección
de Datos
D
Introducción: Estructuras Jerárquicas (V)
Ejemplo
j p de búsqueda
q
eficiente enestructura jjerárquica
q
basada en un árbol.
• Esta estructura jerárquica
es un Árbol Binario de
Búsqueda.
• Permite
P
i lla bú
búsqueda
d
guiada entre elementos
que implementan la
interfaz Comparable.
¿Cuál es el coste de buscar una palabra
con esta representación jerárquica?
¿Es mejor el coste lineal con el número
de palabras o proporcional a la
longitud de la palabra?
9
10
Introducción alos Árboles: Conceptos
Generales
Árbol de Ejemplo
Un Árbol es una estructura jerárquica que se define por:
Un conjunto de Nodos (uno de los cuales es distinguido
como la Raíz del Árbol).
Un
U conjunto
j
d
de Aristas
A i t de
d manera que:
Cualquier nodo H, a excepción de la raíz, está conectado
por medio de una Arista a un único nodo P.
P
Se dice entonces que P es el Padre de H...
Árboles Binarios
Índice general:
1.
La Estructura Jerárquica Árbol
Á
Tema 10- Representación
Jerárquica: Árboles Binarios
Definición y terminología asociada
C i
Caminos
entre
t nodos:
d
profundidad,
f did d nivel
i l y altura
lt
de
d un nodo
d
Relaciones entre nodos
1.
2
2.
3.
2
2.
El Árbol Binario
1.
2.
Germán Moltó
3.
Escuela Técnica Superior deIngeniería Informática
3.
Uni ersidad Politécnica de Valencia
Universidad
Objetivos
Conocer la estructura de Árbol Binario y sus principales
p
p
propiedades, operaciones y recorridos.
Introducir el Árbol Binario de Búsqueda
q
((ABB)) como una
de las EDAs más potentes orientadas a la búsqueda.
Conocer las operaciones
p
que
q soporta
p
un ABB y cómo su
coste varía en función de lo Equilibradoque esté el
Árbol.
3
Búsqueda Dinámica en un Árbol Binario
1.
1
Conceptos y propiedades
Definición y representación recursiva
Operaciones de exploración en profundidad y por niveles
Introducción al Árbol Binario de Búsqueda
2
Bibliografía
Libro de M.A. Weiss, “Estructuras de Datos en Java” (AdissonWesley, 2000).
Apartados 1 – 3 del capítulo 18 para las definiciones vistas en
t í
teoría. Apartado 5 del capítulo 6 para la introducción de las estructuras
de Árbol y Árbol Binario.
Libro de R. Wiener y L.J.J Pinson,, “Fundamentals of OOP and Data
Structures in Java” (Cambridge University Press, 2000).
Apartados 3, 4 y 9 del Capítulo 15
4
Justificación del Tema
Introducción: Estructuras Jerárquicas (I)
Estudiaremos diferentes implementaciones de los
modelos de Cola dePrioridad y Diccionario.
A menudo, los datos de una colección presentan una
relación jerárquica:
Montículo Binario
(Heap)
Implementación de
Cola de
Prioridad
Imposible representar linealmente con LEG o un array.
Ejemplo 1: Estructura de un directorio de librerías (al estilo del
laboratorio de prácticas):
Implementación de
Árbol Binario
Árbol Binario
de Búsqueda
I
Implementación
l
tió de
d
Diccionario
Implementación de
Tabla de Dispersión
(Hash)
NodoLEG
5
6
Introducción: Estructuras Jerárquicas (II)
Ejemplo
j p 2: Representación
p
de una expresión
p
aritmética
totalmente parentizada en notación infija.
Introducción: Estructuras Jerárquicas (III)
La estructura en Árbol:
((( ) (
(((a*b)+(c+d))*(e-f))
)) ( ))
*
*
a
e
+
b c
Relaciones jerárquicas entrelos datos de una colección.
Búsqueda en tiempos sublineales, lo que no se puede
conseguir
i usando
d una representación
ió lineal.
li l
Ejemplo: Representar la Colección de Palabras {mes, mesa,
meta,
t metro,
t coro y corona}.
}
+
Alternativa 1: Usando un array de cadenas:
f
d
8
String
St
i [] vCadenas
C d
= new String[6];
St i [6]
¿Cuál es el coste de buscar una palabradada en esa colección?
¿¿Existen instancias significativas?
g
Alternativa 2: Usando una lista enlazada de palabras.
7
LEG
¿Cuál es el coste?
¿Existen instancias significativas?
Introducción: Estructuras Jerárquicas (IV)
Alternativa 3: Empleamos un árbol para representar la
C l ió d
Colección
de Datos
D
Introducción: Estructuras Jerárquicas (V)
Ejemplo
j p de búsqueda
q
eficiente enestructura jjerárquica
q
basada en un árbol.
• Esta estructura jerárquica
es un Árbol Binario de
Búsqueda.
• Permite
P
i lla bú
búsqueda
d
guiada entre elementos
que implementan la
interfaz Comparable
¿Cuál es el coste de buscar una palabra
con esta representación jerárquica?
¿Es mejor el coste lineal con el número
de palabras o proporcional a la
longitud de la palabra?
9
10
Introducción alos Árboles: Conceptos
Generales
Árbol de Ejemplo
Un Árbol es una estructura jerárquica que se define por:
Un conjunto de Nodos (uno de los cuales es distinguido
como la Raíz del Árbol).
Un
U conjunto
j
d
de Aristas
A i t de
d manera que:
Cualquier nodo H, a excepción de la raíz, está conectado
por medio de una Arista a un único nodo P.
P
Se dice entonces que P es el Padre de H...
Leer documento completo
Regístrate para leer el documento completo.