ARBOL TEORIA 1

Vista previa del material en texto

ÁRBOLES
CONTENIDO
1. CONCEPTOS BÁSICOS
2. ÁRBOLES GENERALES
3. ÁRBOLES BINARIOS
4. IMPLEMENTACIÓN DE UN ÁRBOL
5. ÁRBOL BINARIO DE BÚSQUEDA
6. APLICACIONES
1. CONCEPTOS BÁSICOS
DEFINICIÓN
Un árbol es una estructura de datos jerárquica
aplicada sobre una colección de elementos u objetos
(nodos).
Los arboles representan las estructuras no lineales y
dinámicas de datos más importantes en
computación:
• Dinámicas porque las estructuras de árbol pueden
cambiar durante la ejecución de un programa.
• No lineales, puesto que a cada elemento del árbol
pueden seguirle varios elementos.
Cada dato reside en un nodo, y se utiliza la
terminología de árbol genealógico.
Ejemplo
DEFINICIÓN
TERMINOLOGÍA
− Nodo raíz: Todo árbol que no es
vacio, tiene un único nodo raíz ·(A).
− Nodo hijo: Un nodo B es hijo de un
nodo A si B es sucesor directo de A (B
es apuntado por A)
− Nodo padre: Un nodo A es padre de
un nodo B si A es predecesor directo
B (A apunta a B)
− Nodos hermanos: son sucesores
directos de un mismo nodo. Hijos de
un mismo padre (B y C).
− Nodo hoja: Nodo sin hijos (D,E,G,H)
− Nodo interior: no es raíz ni hoja (F).
A
CB
D E
F
G H
TERMINOLOGÍA
− Grado: es el número de sucesores
directos de un determinado nodo. El
grado del árbol será entonces el
máximo grado de todos los nodos del
árbol. (2).
− Bosque: Es una colección de dos o
mas árboles.
− Todos los nodos tienen un solo padre
excepto el nodo raíz (no tiene padre).
− Camino: Es el recorrido que enlaza
nodos consecutivos. (secuencia de
nodos tales que cada uno es hijo del
anterior). (A , C, F).
A
CB
D E
F
G H
− Longitud del camino: Número de
aristas que tiene
− Rama; camino que termina en un hoja
(C, F, H).
− Nivel: Cada nodo tiene asociado un
numero de nivel que es la longitud del
camino desde la raíz hasta el nodo
especificado. Raíz tiene nivel 0. (F = 2).
− Antecesor: un nodo es antecesor de
otro si hay un camino del primero al
segundo
− Descendiente: un nodo es
descendiente de otro si hay un camino
del segundo al primero
A
CB
D E
F
G H
TERMINOLOGÍA
− Subárbol: Un nodo y todos sus descendientes
A
CB
D E F
G H
TERMINOLOGÍA
− Altura de un árbol: Número de niveles (mayor
nivel +1)
EJEMPLO: ÁRBOL GENEALÓGICO DE MARÍA
El árbol es ordenado:
•El primer subárbol corresponde al padre
•El segundo subárbol corresponde a la madre
Otras definiciones
BOSQUE (FLORESTA): Es una colección de dos o más 
árboles disjuntos.
• Disjuntos significa que no hay nodos en común entre dos 
árboles cualesquiera del bosque
• De un árbol se obtiene un bosque al quitarle la raíz, si tiene 
dos hijos o más.
• De un bosque se obtiene un árbol al añadirle un nodo que 
sea raíz de todos los árboles que lo conforman.
2. ÁRBOLES GENERALES
ÁRBOLES GENERALES
También llamados n-arios o multicampo.
Son árboles con grado mayor a 2
Se utilizan para representar organizaciones jerárquicas, 
conde cada nodo tiene un número variable de hijos.
ÁRBOLES GENERALES: RECORRIDO
RECORRIDO EN PROFUNDIDAD O VERTICAL:
Se visita primero la rama más a la izquierda (desde el 
nodo raíz hasta el nodo hoja).
Luego se visitan las ramas de izquierda a derecha (cada 
nodo se visita solo una vez)
ÁRBOLES GENERALES: RECORRIDO
RECORRIDO EN ANCHURA O POR NIVELES:
Se visitan los nodos nivel por nivel a partir del nodo 
raíz (nivel 0)
En cada nivel se visitan los nodos de izquierda a 
derecha.
3. ÁRBOLES BINARIOS
ÁRBOLES BINARIOS
Un árbol binario es un árbol ordenado, a lo sumo de 
grado 2, es decir, cada nodo puede tener 0, 1 o 2 
hijos (subárbol izquierdo y subárbol derecho).
Al ser ordenado, importa el orden de los subárboles, 
es necesario especificar cuál es el hijo izquierdo y 
cuál el hijo derecho.
X
Y Z
Padre o Raíz
Subárbol Izquierdo Subárbol Derecho
EJEMPLO DE ÁRBOL BINARIO
Un árbol binario de decisión para ordenar tres
elementos A, B y C.
• Nodo interno: preguntas con respuesta si/no
• Nodos hoja: decisiones
ÁRBOL BINARIO EQUILIBRADO
Un árbol binario puede estar equilibrado o no
equilibrado. Para que un árbol binario este equilibrado
cada uno de sus sub árboles debe cumplir:
|altura(subárbol izq) – altura(subárbol der) <=1
A
B C
D E F G
Árbol Binario Equilibrado
A
B
C D
E
F
Árbol Binario No-Equilibrado
ÁRBOL BINARIO COMPLETO
En un árbol binario completo, cada nodo, excepto los
del último nivel, tiene dos hijos.
Si H es la altura y N el número de nodos, se cumple:
N = 2^H - 1
En el siguiente ejemplo, N=7, H=3:
7 = 2^3 -1
A
B C
D E F G
RECORRIDO DE UN ÁRBOL BINARIO
Los recorridos de un árbol binario se clasifican de acuerdo 
al momento en que se visita la raíz del árbol y sus 
subárboles izquierdo y derecho.
Existen tres recorridos:
Preorden:
Inorden:
Posorden:
RAIZ IZQUIERDO DERECHO
IZQUIERDO RAIZ DERECHO
IZQUIERDO DERECHO RAIZ
RECORRIDO DE UN ÁRBOL BINARIO
1. Preorden (NID) u orden previo: La raíz se procesa 
antes que los subárboles izquierdo y derecho.
Pasos: 
1. Recorrer la raíz (N) 
2. Recorrer el subárbol izquierdo (I)
3. Recorrer el subárbol derecho (D)
Algoritmo:
Si A no es vacío entonces 
inicio
ver los datos de la raíz de T
preorden (subárbol izquierdo del raíz de T)
preorden (subárbol derecho del raíz de T)
fin.
Ejemplo:
A
B C
D E F G
1
2
3 4
5
6 7
Recorrido PreOrden:
A B D E C F G
RECORRIDO DE UN ÁRBOL BINARIO
2. Recorrido en inorden (IND) u orden simétrico:
Procesa primero el subárbol izquierdo, después la raíz 
y a continuación el subárbol derecho. El significado “in” 
es que la raíz se procesa entre los subárboles. 
Si el árbol no está vacío, los pasos son:
1. Recorrer todo el subárbol Izquierdo (I)
2. Visitar el Nodo Raíz (N)
3. Recorrer todo el subárbol Derecho (D)
ALGORITMO:
Si el árbol no esta vacío entonces
inicio 
inorden (subárbol izquierdo del raíz de T)
ver los datos de la raíz de T
inorden (subárbol derecho del raíz de T)
Fin 
2
5
1
7
4
8
10
12
Primero
se resuelve 
este lado
2
3
4
5
6
8
9
10
1 7 5 4
Ahora resuelve este lado
8 12 10
Recorrido : = 1 7 5 4 2 8 12 10
RECORRIDO DE UN ÁRBOL BINARIO
3. Recorrido posorden (IDN) u orden posterior: procesa 
el nodo raíz (pos) después de que los subárboles izquierdo 
y derecho se han procesado. Se comienza situándose en la 
hoja más a la izquierda y se procesa. A continuación se 
procesa el subárbol derecho. Por último, se procesa el 
nodo raíz. 
Si el árbol no está vacío, los pasos son:
1. Recorrer el subárbol izquierdo (I)
2. Recorrer el subárbol derecho (D)
3. Recorrer el nodo Raíz (N)
ALGORITMO:
Si el árbol no esta vacío entonces
inicio 
posorden (subárbol izquierdo del raíz de T)
posorden (subárbol derecho del raíz de T)
ver los datos de la raíz de T
Fin 
Ejemplos
A
B C
D E F G
1 2
3
4 5
6
7
Recorrido: D E B F G C A
+
*
A B
^
/
c d
3.5
1
3
2
4
6
5
8
7
9
Recorrido: A B * C D / 3.5 ^ +
4. IMPLEMENTACIÓN DE ÁRBOLES 
Los arboles pueden ser construidos con estructuras
estáticas y dinámicas:
• Las estáticas son arreglos, registros y conjuntos.
• Las dinámicas están representadas por listas.
Las implementaciones con estructuras estáticas, con
arreglos, serán vistas en el siguiente capítulo, como
un caso particular de la representación de Grafos.
Acá veremos la implementación con una estructura
dinámica, con una lista enlazada. Cada nodo del
árbol será un objeto de la clase nodo.
IMPLEMENTACIÓN DE LOS ÁRBOLES
En un árbol general cada nodo puede poseer un número 
indeterminado de hijos. La implementación de los nodos en este 
caso se realiza de la siguiente manera: como no se sabe de 
antemano cuantos hijos tiene un nodo en particular se utilizan dos 
referencias, una a su primer hijo (a la izquierda) y otra a su 
hermano más cercano (a la derecha). La raíz del árbol 
necesariamente tiene la referencia a su hermano como null. 
IMPLEMENTACIÓN DE ÁRBOLES GENERALES
Todo árbol general, implementado como se vio en la anteriordiapositiva, puede representarse como un árbol binario, con solo 
girar 45 grados las aristas horizontales. Las propiedades de los 
árboles binarios se cumplen en los árboles generales. 
La transformación de una árbol general G en árbol binario W, 
requiere los pasos siguientes:
1. La raíz del árbol W es la misma que del árbol G.
2. El nodo raíz (nivel 0) se une con su hijo más a la izquierda.
3. El hijo más a la izquierda se una con sus nodos hermanos, de 
izquierda a derecha.
4. Se repiten los pasos 2 y 3 para cada nodo de cada nivel del 
árbol: 1, 2, 3, etc. (en cada nivel se va de izquierda a derecha)
5. Se giran 45 grados las aristas horizontales.
TRANSFORMACIÓN DE ÁRBOLES GENERALES EN 
BINARIOS
Ejemplo:
TRANSFORMACIÓN DE ÁRBOLES GENERALES EN 
BINARIOS
Transformación de un bosque (floresta) en árbol binario:
TRANSFORMACIÓN DE ÁRBOLES GENERALES EN 
BINARIOS
IMPLEMENTACIÓN DE ÁRBOLES 
BINARIOS CON UNA LISTA ENLAZADA
NODO: se representa con un objeto, que tiene 3 
campos:
hizq: contiene la dirección del hijo izquierdo
hder: contiene la dirección del hijo derecho
dato: almacena el elemento (dato) 
Hijo 
derecho
Hijo 
izquierdo
IMPLEMENTACIÓN DE ÁRBOLES 
BINARIOS CON UNA LISTA ENLAZADA
Ejemplo:
5. ÁRBOL BINARIO DE BÚSQUEDA 
ÁRBOL BINARIO DE BÚSQUEDA
Los árboles binarios se adaptan muy bien para
buscar elementos de forma eficiente.
Para ello, todos los elementos se almacenan en el
árbol ordenados:
- Todos los descendientes izquierdos de un nodo
(subárbol izquierdo) son menores que él
- Todos los descendientes derechos de un nodo
(subárbol derecho) son mayores que él
En este caso, la búsqueda es O(log n) en el caso
promedio, si el árbol está equilibrado y si las hojas
están aproximadamente a la misma profundidad
• La utilidad de los árboles binarios de búsqueda reside en que si
buscamos cierta componente, podemos decir en qué mitad del
árbol se encuentra comparando solamente con el nodo raíz.
• Los nodos de un árbol binario de búsqueda se pueden
enumerar en orden creciente siguiendo un recorrido en inorden.
• Una mejora de los árboles de búsqueda consiste en añadir un
campo clave en cada nodo y realizar las búsquedas
comparando los valores de dichas claves en lugar de los
valores del campo contenido.
ÁRBOL BINARIO DE BÚSQUEDA
6. APLICACIONES DE ÁRBOLES 
Los árboles tienen muchas aplicaciones, por
ejemplo:
• organizar adecuadamente la información,
• construir un árbol genealógico,
• numerar capítulos y secciones de un libro,
• análisis de circuitos,
• representación de estructuras de fórmulas
matemáticas
• organización de datos en bases de datos
• representación de la estructura sintáctica en
compiladores
APLICACIONES DE LOS ÁRBOLES
GRACIAS