Programacion- arboles
Árboles, Árbol Binario, Árbol Binario de Búsqueda
Karim Guevara Puente de la Vega
UCSM, 2013
Objetivos
Introducir el Árbol como una forma de representar una
colección de datos entre los cuales se definen relaciones de
jerarquía:
Árbol Binario
Definición y propiedades
Operaciones de recorrido (In-Orden, Pre-Orden, Post-Orden y Por
Niveles)
Árbol Binario de Búsqueda
Características
Implementación
2
Agenda
Introducción
Conceptos básicos
Árboles Binarios
3
Concepto de Árbol
Longitud, profundidad y altura
Relaciones entre nodos
Definición
Propiedades
Operaciones de recorrido
Condiciones efectivas para la búsqueda
INTRODUCCIÓN
Modelos lineales vs. jerárquicos
Lasestructuras de datos lineales permiten describir
conjuntos de datos que mantienen entre ellos
relaciones de sucesión (o de predecesión).
Los Árboles permiten representar estructuras
jerárquicas entre conjuntos de datos.
4
P.e. : lista de clientes de una empresa, trabajos en la
cola de impresión, etc.
P.e. : estructura de directorios, árbol genealógico,
expresionesaritméticas, etc
INTRODUCCIÓN
Estructuras jerárquicas
En ocasiones los datos de una colección mantienen
relaciones de tipo jerárquico, que no es posible
expresar con una representación lineal.
P.e.1 : colección de directorios
$HOME
eda
librerías
estructuras
5
aplicaciones
util
figuras
hospital
INTRODUCCIÓN
Estructuras jerárquicas
P.e.2: el Árbol que semuestra a continuación representa la
expresión aritmética (((a*b)+(c+d))*(e-f))
*
+
-
*
a
6
+
b
c
e
d
f
INTRODUCCIÓN
Estructuras jerárquicas
Los Árboles permiten procesos de búsqueda con coste
sublineal
P.e.: coste de buscar el dato “300” en la colección de
enteros {100, 50, 200,25, 75, 150, 300}
Usando una lista
Usando un Árbol
Es necesariorecorres todos
los elementos en el peor de
los casos
100
50
Coste lineal
25
200
75
150
¿ cuánto cuesta así ?
7
300
CONCEPTOS BÁSICOS
Definición de Árbol
Un Árbol es una estructura jerárquica que se puede definir
por medio de un conjunto de nodos (uno de los cuales es
distinguido como la raíz del Árbol) y un conjunto de aristas
tal que:
Cualquier nodo H,a excepción del raíz, está conectado por
medio de una arista a un único nodo P. Se dice que P es el nodo
padre y H el hijo
8
Un nodo sin hijos se denomina hoja
Un nodo que no es hoja se denomina nodo interno
CONCEPTOS BÁSICOS
Definición de Árbol
Ejemplo:
Nodo raíz: A
Nodos hojas:
{D, M, N, F, J, K, L}
Nodos internos:
{A, B, E, I, C, G, H}
9CONCEPTOS BASICOS
Longitud, profundidad y altura
En un árbol hay un único camino desde la raíz a cada nodo
El número de aristas que componen un camino se denomina
longitud del camino
Profundidad de un nodo: longitud del camino que va desde
la raíz a ese nodo
Se dice que todos los nodos que están a la misma profundidad
están en el mismo nivel
Altura de unnodo: longitud del camino que va desde ese
nodo hasta la hoja más profunda bajo él
10
La profundidad de la raíz es 0
Altura de un árbol = Altura de la raíz
CONCEPTOS BÁSICOS
Ejercicio
a)
b)
c)
d)
e)
f)
g)
11
Ejercicio 1:
¿Cuántas aristas tiene un
árbol con N nodos?
¿Longitud de A a D?
¿Longitud de C a K?
¿Longitud de B a N?
¿Longitud de B a B?¿Profundidad de A, B, C
y F?
¿Altura de B, C, I, F y del
árbol?
CONCEPTOS BASICOS
Relaciones entre nodos
Los nodos que tienen el mismo padre son hermanos
Si hay un camino desde el nodo u hasta el nodo v,
u es un ascendiente de v
v es un descendiente de u
Si u != v, entonces
12
u es un ascendiente propio de v
v es un descendiente propio de u...
Regístrate para leer el documento completo.