Estructura de Datos Lineales
Arboles
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
1
Introducción
• Las estructuras array y listas son estructuras
de datos lineales. A cada elemento le
correspondía siempre un siguiente
elemento.
• Los Arboles y Grafos son estructuras de
datos no lineales puesto que pueden tener
diferentes siguientes elementos, y también
se conocen como estructuras multi enlazadas
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
2
Terminología básica
• Un árbol es un conjunto, de vértices y
arcos que satisfacen ciertos requerimientos.
Un vértice es un objeto simple (conocido
también como nodo) que puede tener un
nombre, además de cierta información; un
arco es la unión entre dos vértices.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
3
Terminología básica
• Una ruta, en un árbol, es una lista de
diferentes vértices en la que los vértices
consecutivos se conectan por medio de
arcos dentro del árbol. Uno de los nodos del
árbol se identifica como raíz (root).
• Existe exactamente una ruta entre la raíz y
un nodo.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
4
Terminología básica
• Esta
definición implica que no existen
direcciones en los arcos, normalmente pensamos
en los arcos como cualquier punto más allá de la
raíz.
• Cada nodo, excepto la raíz, tiene exactamente un
nodo arriba de él (padre) así, los nodos que se
encuentran directamente abajo de algún nodo se
denominan hijos.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
5
Terminología básica
• Los nodos que no tienen hijos se conocen
como hojas o nodos terminales. Así, un
nodo con al menos un hijo es un nodo no
terminal.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
6
Definición recursiva
• Base. Un nodo sencillo n es un árbol (árbol
trivial). Decimos que n es es la raíz de ese
árbol de un sólo nodo.
• Inducción. Sea v un nuevo nodo y sean T1,
T2, ..., Tk uno o más árboles con raíces c1,
c2, ..., ck, respectivamente.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
7
Definición recursiva
• Requerimos que ningún nodo aparezca más
de una vez en los árboles Ti's; y por
supuesto, v, siendo un "nuevo" nodo, no
puede estar en ninguno de estos árboles.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
8
Definición recursiva
• Generamos un nuevo árbol T de v y T1, T2,
..., Tk de la siguiente forma:
a) Hacemos v la raíz de T
b) Adicionamos un arco de v a cada c1, c2, ..., ck,
haciendo a cada uno de estos últimos un hijo de la
raíz v. Otra forma de ver este paso es que hemos
hecho a v el padre de cada una de las raíces de los
árboles T1, T2, ..., Tk.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
9
Árboles ordenados, orientados y libres
• Un árbol es ordenado cuando el orden de
los subárboles es importante; cuando no se
considera un orden para los subárboles, el
árbol es orientado. En este último caso, si la
dirección de los arcos se ignora, el árbol es
libre.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
10
Árboles ordenados, orientados y libres
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
11
Subárboles
• En un árbol T, un nodo n, junto con todos
sus descendientes, es llamado un subárbol
de T. El nodo n es la raíz de este subárbol.
• Cada nodo es una raíz de un subárbol
formado por él y los nodos debajo de él.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
12
Subárboles
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
13
Nivel, altura y longitud de ruta
• Los nodos en un árbol lo dividen en niveles: el
nivel de un nodo es el número de nodos en la ruta
de ese nodo hasta la raíz (sin incluirlo a él mismo).
• La altura de un árbol es el nivel máximo entre
todos los nodos del árbol.
• La longitud de ruta de un árbol es la suma de
los niveles de todos los nodos en el mismo
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
14
Árbol dirigido
• Un árbol es dirigido si cada nodo tiene una
dirección hacia algún otro nodo sin contener
ciclos.
• Un árbol es dirigido por la raíz si existe un
sólo vértice r llamado raíz, con un grado de
conectividad de entrada id(r) = 0 y para el
resto de los vértices v del árbol id(v) = 1.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
15
Anexo B
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
16
Árbol binario
• Un árbol binario es un conjunto finito de
elementos que, o está vacío, o está formado
de tres partes: la primera parte consiste en
un elemento denominado raíz; las otras dos
partes son, por sí mismas, árboles binarios,
denominados
subárbol
izquierdo
y
subárbol derecho.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
17
Anexo B
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
18
Árbol binario
• Estos subárboles pueden estar vacíos. Cada
elemento de un árbol binario se denomina
nodo.
• En un árbol binario, generalmente se
cumple que, para cada nodo: los hijos
izquierdos de un nodo son menores a él y
los hijos derechos de un nodo son mayores
a él.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
19
Árbol binario
• Recursivamente definimos un árbol binario:
Base. El árbol vacío es un árbol binario
Inducción. Si r es un nodo, y T1 y T2 son
árboles binarios, entonces, existe un árbol
binario con raíz r, un subárbol izquierdo T1
y un subárbol derecho T2.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
20
Propiedades
Existe exactamente una ruta que une cualquier par
de nodos en un árbol
Un árbol con N nodos tiene N - 1 arcos
Un árbol binario con N nodos internos tiene N + 1
nodos externos
La longitud de ruta externa de cualquier árbol
binario con N nodos internos es 2N veces más
grande que la longitud de ruta interna
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
21
Definiciones
• Cuando un árbol binario tiene exactamente
cero o dos subárboles es llamado árbol
estrictamente binario, de otra forma, es un
árbol de Knuth.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
22
Definiciones
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
23
Definiciones
• Un árbol binario estricto de altura d es
balanceado cuando cada hoja en el árbol
está en el nivel d o d - 1.
• Un árbol binario estricto de altura d es
completamente balanceado si todas sus
hojas o nodos terminales se encuentran en el
nivel d.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
24
Definiciones
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
25
Definiciones
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
26
Bosques
• Un bosque es un conjunto de árboles
disjuntos, y puede ser transformado en un
árbol de Knuth con el algoritmo siguiente:
1.Ligar las raíces de los árboles del bosque y
seleccionar a la raíz del árbol a la izquierda
como la raíz del nuevo árbol
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
27
Bosques
2.Ligar a todos los hermanos de cada padre
3.Retirar todas las ligas de un padre a sus
hijos excepto la del hijo de la izquierda
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
28
Anexo B
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
29
Anexo B
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
30
Anexo B
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
31
Anexo B
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
32
Operaciones en árboles binarios
• INFO(p). Regresa el contenido de n.
• LEFT(p). Regresa un apuntador al hijo izquierdo
de n.
• RIGHT(p). Regresa un apuntador al hijo derecho
de n.
• FATHER(p). Regresa un apuntador al padre de n.
• BROTHER(p). Regresa un apuntador al hermano
de n.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
33
Operaciones en árboles binarios
• ISLEFT(p). Regresa un valor verdadero
(TRUE) si n es un hijo izquierdo.
• ISRIGHT(p). Regresa un valor verdadero
(TRUE) si n es un hijo derecho.
• MAKETREE(x). Crea un nuevo árbol
binario formado por un solo nodo con
información x y regresa un apuntador a ese
nodo.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
34
Operaciones en árboles binarios
• SETLEFT(p,x). Recibe un apuntador p a
un nodo de un árbol binario que no tenga
hijo izquierdo. Crea un nuevo hijo izquierdo
a ese nodo con información x.
• SETRIGHT(p,x). Recibe un apuntador p a
un nodo de un árbol binario que no tenga
hijo derecho. Crea un nuevo hijo derecho a
ese nodo con información x.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
35
Anexo A
 Programa 54
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
36
Recorrido de árboles
• Recorrer un árbol es un método de visitas
de sus nodos con el objeto de sistematizar
la recuperación de la información
almacenada en los mismos.
• Los
recorridos
pueden
practicarse
sistematizando la visita de los subárboles.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
37
Recorrido de árboles. Preorder
Función Preorder
{
Se visita el nodo
Si el subárbol izquierdo existe y no se ha
visitado: llamar a Preorder
Si el subárbol derecho existe y no se ha
visitado: llamar a Preorder
Regresar
}
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
38
Recorrido de árboles. Inorder
Función Inorder
{
Si el subárbol izquierdo existe y no se ha
visitado: llamar a Inorder
Se visita el nodo
Si el subárbol derecho existe y no se ha
visitado: llamar a Inorder
Regresar
}
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
39
Recorrido de árboles. Postorder
Función Postorder {
Si el subárbol izquierdo existe y no se ha
visitado: llamar a Postorder
Si el subárbol derecho existe y no se ha
visitado: llamar a Postorder
Se visita el nodo
Regresar
}
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
40
Anexo B
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
41
Borrado de nodos
• Para borrar cualquier nodo de un árbol
binario, se debe de colocar en su lugar el
nodo que está más a la izquierda del
subárbol derecho o el nodo que está más a
la derecha del subárbol izquierdo.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
42
Anexo B
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
43
Balanceo de Árboles
• Cuando un árbol se desbalancea es
necesario realizar una serie de rotaciones
que acomoden la nueva raíz y se genere un
árbol balanceado.
• Primero, es necesario saber cuándo un árbol
se ha desbalanceado. Para ello es necesario
llevar una ponderación en cada nodo a
medida que se insertan nuevos elementos.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
44
Árbol balanceado
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
45
Balanceo de Árboles
• Así, si un nodo no tiene hijos o tiene ambos,
su ponderación será de 0. Si tiene el hijo
izquierdo, pero no el derecho, se le restará a
su ponderación un 1. Si tiene el hijo
derecho, pero no el izquierdo, se le sumará
a su ponderación un 1. Así, cuando un nodo
tenga una ponderación mayor a 1 o menor a
-1, ese nodo se encuentra desbalanceado.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
46
Balanceo de Árboles
• Cuatro rotaciones (depende del pivote)
– Rotación sencilla izquierda
– Rotación sencilla derecha
– Rotación doble izquierda
– Rotación doble derecha
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
47
Anexo B
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
48
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
49
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
50
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
51
Anexo A




Ejemplo 1 (Balanceo)
Programa 55-a
Programa 55-b
Programa 55-c
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
52
Árboles binarios Entretejidos o
Enhebrados
• Dada la importancia de los árboles ligados,
conviene desarrollar algoritmos no recursivos
para manipularlos y estudiar las exigencias de
tiempo y espacio de dichos algoritmos.
• Al cambiar las ligas nil en ligas especiales
(entretejidas), es posible realizar recorridos,
inserciones y eliminaciones sin recurrir a una pila
o a la recursión.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
53
Árboles Entretejidos
• En un árbol binario entretejido a la derecha,
cada liga derecha nil se reemplaza por una
liga especial con el sucesor del nodo bajo la
transversal en orden, llamada entretejido
derecho.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
54
Árboles Entretejidos
• Usando este tipo de árbol nos será fácil
hacer una transversal en orden del mismo,
pues lo único que se requiere es seguir una
liga o entretejido ordinario para hallar el
siguiente nodo que se visitará.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
55
Árboles Entretejidos
• En un árbol entretejido izquierdo se
sustituye cada liga izquierda nil con una
liga especial con el predecesor del nodo
bajo la transversal en orden.
• Si se tienen ambos entretejidos, el resultado
se conoce como árbol binario totalmente
entretejido.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
56
Árboles Entretejidos
 Figura 33
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
57
Árboles de Expresión
• Un árbol de expresión se construye a partir
de los operandos y operadores simples de
una expresión (aritmética o lógica),
colocando los operandos simples como las
hojas de un árbol binario y los operadores
como los nodos interiores.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
58
Árboles de Expresión
• En cada operador binario, el subárbol
izquierdo contiene todos los operandos y
operadores simples en el operando
izquierdo del operador dado, y el subárbol
derecho contiene todo lo del operando
derecho.
• En un operador unitario, un subárbol estará
vacío.
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
59
Árboles de Expresión
• Se acostumbra escribir algunos operadores
unitarios a la izquierda de sus operandos,
como ‘-’ (negación unitaria) o bien las
funciones estándar como log() y cos().
• Otros se escriben a la derecha, entre ellos la
función factorial ( )!, o la que asume el
cuadrado de un número: ( )2
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
60
Árboles de Expresión
 Figura 34
 Figura 35
 Figura 36
UNIVERSIDAD DEL CAUCA - PIS
Ing. Miguel Angel Niño Zambrano
EDII
61
Descargar

Arboles - Universidad del Cauca