Programacion- arboles

EDAs Jerárquicas
Á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}

9CONCEPTOS 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...