x
a
e
y
b
q
v
w
f
u
o
Definición, propiedades, recorridos

Investiga lo siguiente:
 DOM—Document Object Model
▪ Para XML
▪ Para HTML
 Árbol de decisión
XML
<numeros>
<numero> 1 </numero>
<numero> 2 </numero>
<numero> 3 </numero>
<numero> 4 </numero>
</numeros>

Almacenamiento eficiente
 AVL, B+

Toma de decisiones
 Árboles de decisión

Representación de jerarquías
 Categorización, juegos

Representación de documentos
 XML

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.

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 libre en que uno de los vértices se
distingue de los demás.
r
x
z
y

Porción de un árbol inducida por los
descendientes de un nodo.
a
Sub-árbol
enraizado
en c
c
b
d
e

Nodo sin hijos.
r
x
z
y
a
b

Nodo que no es hoja.

¿Formalización?
r
x
z
y
a
b

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
Profundidad de x= 1
Altura= 3
r
x
z
y
a
b

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 es ancestro de y
y es descendiente de x
x
z
y
a
b

Un nodo es ancestro y descendiente de sí
mismo.
 Ancestro propio
 Descendiente propio

Nodos con el mismo padre
r
x
z
y
a
b
7
3
8
6
5
9
4
10
12
11
1
•Raíz
•Hojas
•Nodos internos
2
•Padres/hijos
•Ancestros/
descendientes
•Profundidad
•Altura

3 conjuntos de nodos
x
 Raíz
 Sub-árbol izquierdo
a
e
 Sub-árbol derecho
y

0 a 2 hijos
b
q
 Hijo izquierdo e hijo derecho
v
w
f
u
o

Hijo ausente
x

Árbol vacío
 No contiene nodos

Completo
 Cada nodo
▪ O es hoja
▪ O tiene 2 hijos
a
e
y
b
q
v
w
f
u
o

Por el orden de inserción, el árbol puede
desbalancearse
 La búsqueda degenera en búsqueda secuencial

Solución
 Utilizar árboles balanceados (AVL)

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”

En profundidad (DFS)
 Pre-orden
▪ Raíz—hijo izquierdo—hijo derecho
 In-orden
 Post-orden
 Conversos

En anchura (BFS)
Visitar la raíz
Recorrer en pre-orden el sub-árbol izquierdo
Recorrer en pre-orden el sub-árbol derecho
x
a
z
e
s
y
b
m
n
q
w
t
v
f
u
o
Recorrer en in-orden el sub-árbol izquierdo
Visitar la raíz
Recorrer en in-orden el sub-árbol derecho
x
a
e
y
b
q
v
w
f
u
o
Recorrer en post-orden el sub-árbol izquierdo
Recorrer en post-orden el sub-árbol derecho
Visitar la raíz
x
a
e
y
b
q
v
w
f
u
o



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
y
b
q
z
m
w
n
e
t
s
v
f
u
o


¿Qué es un árbol?
¿Qué propiedades tiene?

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
Volver
Descargar

Árboles - Dra. Sara Elena Garza V.