CAP5 Aplicaciones De Estructuras De Datos Árboles

Pontificia Universidad Católica del Perú
Facultad de Ciencias e Ingeniería
Especialidad de Ingeniería Informática
Curso: Algoritmia
Capítulo 5: Aplicaciones de Estructuras de Datos

Profesor:
Mag. Fernando Alva Manchego
2014-2
1

Árboles
2

Definición
Raíz
A

C

B
E

F
L

G
M

H

I

D
K

J

subárbol

N
subárbol

subárbol
3

Árboles Binarios
4

Definición
• Árboles con grado 2
– Cada nodopuede tener 2 hijos como máximo

Raíz
A
C

B
D

Terminologia:
 hijo izquierdo
 hijo derecho
 información

E

F

5

Operaciones en Árboles Binarios
•
•
•
•
•
•
•
•
•

Crear árbol
Verificar si el árbol está vacío
Imprimir elementos del árbol
Determinar la altura del árbol
Buscar un elemento
Buscar el padre de un elemento
Insertar un elemento a la izquierda de otro elemento
Insertar un elemento a laderecha de otro elemento
Finilizar un árbol

6

Recorrido de Árboles Binarios
• Recorrer un árbol visitando cada nodo una única
vez genera una secuencia lineal de nodos
– Listado de todos los elementos
– Búsqueda de un elemento

• Tres formas de recorrer árboles binarios en
función del orden en que se visitan los nodos:
– Pre-orden
– En-orden
– Post-orden
7

Recorrido de Árboles Binarios
•Pre-orden: se visita primero el nodo raíz y después
los subárboles izquierdo en pre-orden y derecho en
pre-orden

8

Recorrido de Árboles Binarios
•

En-orden: se visita el subárbol izquierdo en-orden,
el nodo raíz y el subárbol derecho en-orden

9

Recorrido de Árboles Binarios
•

Post-orden: se visita el subárbol izquierdo en postorden, el subárbol derecho en post-orden y el nodo
raíz, en eseorden

10

Recorrido de Árboles
• Otras formas:
– Búsqueda/recorrido en amplitud
– Búsqueda/recorrido en profundidad

• Independiente del tipo de árbol
• Tradicionalmente de izquierda a derecha

11

Recorrido de Árboles
• En amplitud: un nivel cada vez

12

Recorrido de Árboles
• En profundidad: una rama del árbol cada vez
(= pre-orden)

13

Ejercicio: Recorrido de Árboles
Para el siguiente árbol,muestre cuáles serían las salidas para
los recorridos en amplitud y profundidad (pre-orden)

14

Recorrido de Árboles:
Implementación
•

En profundidad = pre-orden
–

Usar una pila (explícita o implícitamente)

15

Recorrido de Árboles:
Implementación
•

En amplitud, ¿cómo se implementaría?

•

COLA:
Si el nodo raíz es diferente de NULL, entra en la cola
Mientras la cola no esté vacía
Seretira/vista el primero de la cola
Si ese nodo tiene hijos, ellos entran en la cola

16

Recorrido de Árboles:
Implementación
• En amplitud

17

Ejercicio: Amplitud vs. Profundidad
• Use las estrategias para buscar el nodo F
– ¿Cuál es mejor en términos de nodos visitados y de
memoria?

18

Árboles Binarios de
Búsqueda
19

Definición
• Un árbol binario con raíz R es u árbol binario de
búsqueda (ABB)si:
– La llave (información) de cada nodo del subárbol
izquierdo de R es menor que la llave del nodo R
(en orden alfabético, por ejemplo)
– La llave de cada nodo del subárbol derecho de R es
mayor que la llave del nodo R
– Los subárboles izquierdo y derecho también son
ABBs
20

ABB: Ejemplos
R2

R1
D

D

A

A

F

B
C

E

Es ABB

G

B

F
C

E

G

No es
ABB

21

ABB: ¿Por qué son buenos?
• Parabuscar en un ABB
– En cada nodo, se compara el elemento buscado con
el elemento actual:
• Si es menor, se recorre el subárbol izquierdo
• Si es mayor, se recorre el subábol derecho

– Se desciende verticalmente hasta as hojas, en el
pero caso, sin pasar por más de un nodo en el
mismo nivel
– Por lo tanto, en el peor caso, la búsqueda pasa por
tantos nodos como fuese la altura del árbol
22

ABB:Ejemplo de Búsqueda
• Busque el elemento E en los siguientes árboles:
R2

R1
D

D
B
A

A

F
C

E

Es ABB

3 consultas

G

B

F
C

E

G

No es
ABB

6 consultas
23

ABB: ¿Por qué son buenos?

• ¡Búsquedas muy rápidas!
– En promedio: O (log n)
– Peor caso: O (n)

24

ABB: Representación
Raíz

Raíz

D
ABB vacío
F

B
A

C

G

25

ABB: Operaciones
• Deben considerar el orden de los elementos del...