Embed Size (px)
Citation preview
ÁRBOL CON RAÍZ : DEFINICIÓN Sea A un conjunto y T una relación en A .
Se dice que T es un árbol si posee un vértice vo en A con
la propiedad de que existe una única trayectoria de vo
hacia cualquier otro vértice de A pero no existe una
trayectoria de vo a vo.
Notación:
Se dice que T es un árbol con raíz y se denota (T, vo)
vo se denomina raíz del árbol T
Cualquier otro elemento de A es un vértice en T.
Observación:
T se representa por su Digrafo Unidad 4: Grafos y Arboles _ 2º parte
35
EJEMPLO
36
v2
v1
v0v3
v4
v5
v6
v7
v8
v11v9
v10
DISEÑO DE UN ÁRBOL CON RAÍZ
3
Unidad 4: Grafos y Arboles _ 2º parte
◦ Se ubica a la raíz vo , de la cual se dirá que esta en el
nivel 0.
◦ Ninguna arista entra a vo pero pueden salir varias, que se
trazan hacia abajo. Los vértices terminales de las aristas
que comienzan en vo son los vértices del nivel 1
◦ Cada vértice del nivel 1 no tienen otras aristas que
entren en él, pero cada uno de estos vértices pueden
tener varias aristas que salen de él. Se trazan las aristas
que salen del nivel 1 hacia abajo y terminan en vértices
que estarán en el nivel 2
◦ Y asi sucesivamente con cada nivel….
◦ .
EJEMPLO
38
v2v1
v0
v3
v4 v5v6
v7v8
v9
v11v10
MAS DEFINICIONES
39
El nivel de un nodo está dado por el número de aristas que deben
ser recorridos para llegar a él desde el vértice raíz.
La altura de un árbol es el nivel más grande del mismo.
Un vértice X se dice padre de otro vértice Y cuando existe una
trayectoria de longitud 1 que sale de X y termina en Y, el que a su
vez se dice hijo de X. Por ejemplo vo se dice padre de todos los
vértices del nivel 1
Los vértices hijos del mismo padre se dicen hermanos
Un vértice X se dice descendiente de otro Y cuando existe una
trayectoria de cualquier longitud que comienza en X y termina en Y.
En ese caso se dice que Y es antecesor de X
Un vértice se dice hoja cuando no tiene hijos
Un árbol se dice ordenado cuando los hijos de cada vértice están
linealmente ordenados de izquierda a derecha
PROPIEDADES DE LOS ÁRBOLES
Sea (T, vo) un árbol con raíz. Entonces:
a) No existen ciclos en T.
b) vo es la única raíz en T.
c) Cada vértice en T distinto de vo tiene grado
interno (grado de entrada) uno y vo tiene
grado interno cero.Unidad 4: Grafos y Arboles _ 2º parte
40
TEOREMA 1:
DEMOSTRACIÓN
41
Un
ida
d 4
: Gra
fos y A
rbo
les _
2º p
arte
a)
Suponga que existe un ciclo q en T, que comienza y
termina en v.
Por definición de árbol existe una trayectoria p de vo a
v.
Entonces q p (composición de p con q) es una
trayectoria de vo a v diferente de p, lo que contradice la
definición de árbol.
La contradicción proviene de haber supuesto la
existencia del ciclo q. Por lo tanto , no existen ciclos
en T
b)
Supongamos que existe otra raíz de T llamada v’o ,
entonces existe una trayectoria p de v’o a vo y
considerando que vo es raiz, una trayectoria q de vo
a v’o
Entonces q p (composición de p con q) es un ciclo
de v’o a v’o, lo que, por definición, es imposible.
Entonces se concluye que vo es la única raíz.
Demostración de c): queda para el alumnoUnidad 4: Grafos y Arboles _ 2º parte
42
Sea (T, vo) un árbol con raíz sobre un conjunto A.
a) T es una relación arreflexiva :
(a,a) T , a A
b) T es asimétrica:
a, b A , (a,b)T (b,a) T
c) T es atransitiva:
a, b,c A , (a,b)T (b,c)T (a,c)T
Unidad 4: Grafos y Arboles _ 2º parte
43
TEOREMA 2:
SU
BÁ
RB
OL
Sea (T,vo) un árbol con raíz sobre A y sea v A.
Sea B el conjunto que consta de v y todos sus hijos.
Sea T(v) el árbol obtenido de T de la siguiente
manera: se eliminan todos los vértices que no sean
hijos de v y todas las aristas que comienzan o
terminan en un vértice de este tipo. Se obtiene el
siguiente resultado
Si (T, vo) es un árbol con raíz y vT, entonces T(v)
también es un árbol con raíz v.
Se dice que T(v) es el subárbol de T que comienza
en v.
44
TEOREMA 3
45
v1
vo
v3
v4 v5
v2
v6 v7
v8 v9
v1
0
v11
v1
2
v1
3
v1
3
v1
8
v1
9
v2
0
v1
4
v1
5
v1
6
v1
7
T(v1)
T(v8)
T(v7)
T(v2)
46
Sea nN.
Un árbol T es un n-árbol (o árbol n-ario) si cada vértice
tiene a lo sumo n hijos.
Se dice que T es un n-árbol Completo si todos los
vértices de T, distintos de las hojas, tienen exactamente n hijos.
Árboles binarios Un árbol T es un árbol binario si cada vértice tiene a lo
sumo 2 hijos
Un árbol T es un árbol binario completo si cada vértice
exactamente 2 hijos
Árboles n-arios
EJEMPLOS
47
Un
ida
d 4
: Gra
fos y A
rbo
les _
2º p
arte
3-ario 2-ario o binario binario completo
Los árboles binarios son muy importantes, ya que existen métodos eficientes
para implementarlos y hacer búsquedas en ellos.
Además es posible reorganizar cualquier árbol con raíz como un árbol binario
ÁRBOL BINARIO POSICIONAL
Cada vértice tiene a lo sumo 2 hijos los
cuales tienen una posición definida: izquierda
o derecha.
ÁRBOLES ETIQUETADOS
Para muchos usos de los árboles en las ciencias de la
computación, es útil etiquetar los vértices o aristas de
un digrafo.
Los arboles binarios etiquetados sirven, por ejemplo,
para representar operaciones binarias.
48
+
a b
a+b
x y
xy
p q
pq
PROCEDIMIENTO PARA ENCONTRAR EL ÁRBOL ETIQUETADO DE UNA EXP. ALGEBRAICA
49
◦ Se etiqueta la raíz con el operador principal de la expresión.
◦ Se etiqueta a los hijos izquierdo y derecho de la raíz
mediante el operador principal de las expresiones para los
argumentos de la izquierda y derecha, respectivamente.
◦ Si un argumento es cte o variable, se lo utiliza para etiquetar
el vértice descendiente que corresponde.
◦ Se continúa con este proceso hasta concluir con la expresión
EJEMPLO
50
Un
ida
d 4
: Gra
fos y A
rbo
les _
2º p
arte
El siguiente árbol corresponde a la expresión
(3 – (2 * x)) + ((x – 2) + (3 + x))
+
- +
3 * - +
2 x 32x x
EJERCICIO PARA EL ALUMNO
51
Un
ida
d 4
: Gra
fos y A
rbo
les _
2º p
arte
Confeccionar el árbol correspondiente a las siguientes
expresiones algebraicas y responder
a) ¿Cuál es la altura de cada uno de ellos?
b) Los vértices hojas pueden estar etiquetados con
operadores?
c) Dar el nivel de cada operación en ambos casos
BÚSQUEDA EN ÁRBOLES BINARIOS POSICIONALES
Llamamos así al proceso mediante el cual se
visita cada vértice de un árbol en un orden
específico
Sea T un árbol binario posicional con raíz v.
Designaremos con vI al hijo izquierdo y con vD al
hijo derecho, donde uno o ambos pueden estar
ausentes. Entonces, si existe vI, el subárbol T(vI)
es el subárbol izquierdo de T y si existe vD, el
subárbol T(vD) es el subárbol derecho de T Unidad 4: Grafos y Arboles _ 2º parte
52
BÚSQUEDA EN PREORDEN
Sea T un árbol binario posicional con raíz v:
Paso 1: Visitar v (anotar)
Paso 2: Si existe vI, entonces aplicar este algoritmo a
T(vI)
Paso 3: Si existe vD, entonces aplicar este algoritmo a
T(vD)
Paso 4: Fin del algoritmo
53
BÚSQUEDA EN ENTREORDEN
Sea T un árbol binario posicional con raíz v:
Paso 1: Si existe vI, entonces aplicar este algoritmo a
T(vI)
Paso 2: Visitar v
Paso 3: Si existe vD, entonces aplicar este algoritmo a
T(vD)
Paso 4: Fin del algoritmo
Unidad 4: Grafos y Arboles _ 2º parte
54
BÚSQUEDA EN POSTORDEN
Sea T un árbol binario posicional con raíz v:
Paso 1: Si existe vI, entonces aplicar este algoritmo a
T(vI)
Paso 2: Si existe vD, entonces aplicar este algoritmo a
T(vD)
Paso 3: Visitar v
Paso 4: Fin del algoritmo
Unidad 4: Grafos y Arboles _ 2º parte
55
EJEMPLO
56
Un
ida
d 4
: Gra
fos y A
rbo
les _
2º p
arte
Sea T el árbol binario posicional etiquetado cuyo
digrafo es el siguiente:
A
F G
C
K LIH
D
B
E
J
El recorrido en preorden genera la siguiente sucesión:A B D H E I J C F K G L
El recorrido en entreorden genera la siguiente sucesión:H D B I E J A F K L C L G
El recorrido en posorden genera la siguiente sucesión:H D I J E B K F L G C A
NOTACIONES PREFIJAS (O POLACA) , INFIJAS Y POSFIJAS
57
Un
ida
d 4
: Gra
fos y A
rbo
les _
2º p
arte
Cuando se aplica el algoritmo de búsqueda en
preorden a un árbol correspondiente a una expresión
algebraica, el resultado de la búsqueda se llama
forma prefija (o polaca) de la expresión algebraica
dada.
Si se aplican los algoritmos de entreorden y
postorden, se obtienen las notaciones infija y
posfija, respectivamente, de la expresión algebraica.
La primera es la más usada. La segunda tiene el
inconveniente de necesitar paréntesis para evitar
ambigüedades
EJEMPLO
58
Un
ida
d 4
: Gra
fos y A
rbo
les _
2º p
arte
Obtener las
expresiones prefija,
infija y posfija
correspondiente al
siguiente árbol
/
+ -
* 2
x
1
Z 3
El recorrido en preorden genera la forma prefija de la expresión:
/ + x 1 – * z 3 2El recorrido en entreorden genera la forma infija de la expresión :
(x + 1) / ((z * 3) – 2)El recorrido en postorden genera la forma posfija de la expresión :
x 1 + z 3 * 2 – /
ENLACES DE INTERES
http://es.wikipedia.org/wiki/Teor%C3%ADa_de_los_grafos
http://es.wikipedia.org/wiki/%C3%81rbol_de_expansi%C3%B3n
http://decsai.ugr.es/~jfv/ed1/tedi/cdrom/docs/arb_BB.htm
http://sistemas.itlp.edu.mx/tutoriales/estru1/54.htm
http://mate.cucei.udg.mx/matdis/6arb/6arb2.htm
80
