ÁrbolesDefinición, propiedades, recorridos

x

a

q

y b

w

e

v u

f o

Entrando en el tema…

Investiga lo siguiente: DOM—Document Object Model▪ Para XML▪ Para HTML

Árbol de decisión<numeros> <numero> 1 </numero> <numero> 2 </numero> <numero> 3 </numero> <numero> 4 </numero></numeros>

XML

Aplicaciones de los árboles

Almacenamiento eficiente AVL, B+

Toma de decisiones Árboles de decisión

Representación de jerarquías Categorización, juegos

Representación de documentos XML

¿Qué es un árbol?

Estructura de datos jerárquica

Formalmente Grafo acíclico y no dirigido▪ Si es conectado Árbol libre▪ Si es desconectado Bosque

Vértices de un árbol nodos.

Árbol libre (Cormen p. 1086)

Bosque (Cormen p. 1086)

¿?

Equivalencias (trabajo en equipo)

G es un árbol libre.

Cualesquiera dos vértices en G están conectados por un camino simple único.

Si se remueve una arista de E, el grafo queda desconectado.

|E|=|V|-1

G es acíclico.

Si se agrega una arista a E, el grafo contiene un ciclo.

Árbol con raíz

Árbol libre en que uno de los vértices se distingue de los demás.

r

x

z

y

Sub-árbol enraizado en un nodo

Porción de un árbol inducida por los descendientes de un nodo.

a

b c

d e

Sub-árbol

enraizado en c

Hoja

Nodo sin hijos.

r

x a b

z

y

Nodo interno

Nodo que no es hoja.

¿Formalización?

r

x a b

z

y

Profundidad y altura

Profundidad de un nodo Tamaño del camino desde la raíz hasta

el nodo

Altura Tamaño ▪ del camino simple más largo ▪ desde la raíz hasta una hoja

r

x a b

z

yProfundidad de x= 1

Altura= 3

Ancestro

Nodo c en la ruta de la raíz hacia otro nodo d. d sería descendiente de c Padre—ancestro inmediato Hijo—descendiente inmediato

r

x a b

z

y

x es ancestro de yy es descendiente

de x

Ancestro y descendiente

Un nodo es ancestro y descendiente de sí mismo. Ancestro propio Descendiente propio

Hermanos

Nodos con el mismo padre

r

x a b

z

y

Ejercicio

7

3 10 4

8

5

12

6

9

11 2

1

• Raíz• Hojas• Nodos internos

• Padres/hijos• Ancestros/ descendiente

s

• Profundidad• Altura

Árboles binarios

3 conjuntos de nodos Raíz Sub-árbol izquierdo Sub-árbol derecho

0 a 2 hijos Hijo izquierdo e hijo derecho

x

a

q

y b

w

e

v u

f o

Árboles binarios

Hijo ausente

Árbol vacío No contiene nodos

Completo Cada nodo ▪ O es hoja ▪ O tiene 2 hijos

x

a

q

y b

w

e

v u

f o

Árboles binarios de búsqueda

Por el orden de inserción, el árbol puede desbalancearse La búsqueda degenera en búsqueda

secuencial

Solución Utilizar árboles balanceados (AVL)

Árboles binarios de búsqueda (ABB)

Sobre ellos podemos aplicar búsqueda binaria

El “chiste” Tener los datos estratégicamente acomodados

Para ello Hijos izquierdos Menores Hijos derechos Mayores Raíz “Intermedio”

Ejemplo

Recorridos

En profundidad (DFS) Pre-orden▪ Raíz—hijo izquierdo—hijo derecho

In-orden Post-orden Conversos

En anchura (BFS)

Pre-orden

Visitar la raízRecorrer en pre-orden el sub-árbol

izquierdoRecorrer en pre-orden el sub-árbol

derecho

x

a

q

y b

w

m

tn

z e

s v u

f o

Pre-orden

In-orden

Recorrer en in-orden el sub-árbol izquierdo

Visitar la raízRecorrer en in-orden el sub-árbol

derecho

x

a

q

y b

w

e

v u

f o

In-orden

Post-orden

Recorrer en post-orden el sub-árbol izquierdo

Recorrer en post-orden el sub-árbol derecho

Visitar la raíz

x

a

q

y b

w

e

v u

f o

Post-orden

Recorridos Conversos

Visitan primero el sub-árbol derecho En casos no binarios, sería de

derecha a izquierda Recorridos

Pre-orden converso In-orden converso Pos-orden converso

x

a

q

y b

w

m tn

z e

s v u

f o

azeybmnts uv qwfo

Niveles

¿Qué es un árbol? ¿Qué propiedades tiene?

Tarea (puntos extra)

Dos opciones Representar un documento XML como

árbol▪ Extraer las propiedades vistas en clase

Crear un grafo a partir de una red social▪ Extraer las propiedades vistas en clase

Tipos de estructuras

Lineal

Jerárquica

Red

Sin relaciónVolver