INGENIERIA EN SISTEMAS COMPUTACIONALES
MATERIA:
Lenguajes y Autómatas II
ASESOR:
Dr. Miguel Ángel Macías García
ALUMNO: Nº DE CONTROL.
Mario Hernández Tenorio 13380926
UNIDAD ACADÉMICA: FECHA:
SOTO LA MARINA 23/Agosto/2019
pág. 1
DEFINICIÓN
Arboles
Los árboles son contenedores que permiten organizar un conjunto de objetos en
forma jerárquica. Ejemplos típicos son los diagramas de organización de las
empresas o instituciones y la estructura de un sistema de archivos en una
computadora. Los arboles sirven para representar formulas, la descomposición de
grandes sistemas en sistemas más pequeños en forma recursiva y aparecen en
forma sistemática en muchísimas aplicaciones de la computación científica. Una
de las propiedades más llamativas de los arboles es la capacidad de acceder a
muchísimos objetos desde un punto de partida o raíz en unos pocos pasos. Por
ejemplo, en mi cuenta poseo unos 61,000 archivos organizados en unos 3500
directorios a los cuales puedo acceder con un máximo de 10 cambios de directorio
(en promedio unos 5).
Sorprendentemente no existe un contenedor STL de tipo árbol, si bien varios de
los otros contenedores (como conjuntos y correspondencias) están implementados
internamente en términos de árboles. Esto se debe a que en la filosofía de las STL
el árbol es considerado o bien como un subtipo del grafo o bien como una entidad
demasiado básica para ser utilizado directamente por los usuarios.
Los árboles son las estructuras de datos no lineales y dinámicas de datos más
importantes del área de computación. Dinámicas, puesto que las mismas pueden
cambiar tanto de forma como de tamaño durante la ejecución del programa. No
lineales, puesto que cada elemento del árbol puede tener más de un sucesor. Los
árboles balanceados o AVE son la estructura de datos más eficiente para trabajar
con la memoria principal —interna— del procesador, mientras que los árboles B y.
especialmente la versión B+, representan la estructura de datos más eficiente para
trabajar en memoria secundaria o externa.
pág. 2
Un árbol se puede definir como una estructura jerárquica aplicada sobre una
colección de elementos u objetos llamados nodos, uno de los cuales es conocido
como raíz. Además se crea una relación o parentesco entre los nodos dando lugar
a términos como padre. Hijo, hermano, antecesor, sucesor, ancestro, etcétera.
Formalmente se define un árbol de tipo T como una estructura homogénea
resultado de la concatenación de un elemento de tipo T con un número finito de
árbol les disjuntos, llamados subárboles. Una forma particular de árbol es el árbol
vacío.
Los árboles son estructuras recursivas, ya que cada subárbol es a su vez un árbol.
ELEMENTOS
La estructura tipo árbol tiene ciertas características y propiedades que la
distinguen. A continuación se presentan las más importantes:
a) Todo árbol que no es vacío tiene un único nodo raíz.
b) Un nodo X es descendiente directo de un nodo Y, si el nodo X es apuntado por
el nodo Y En este caso es común utilizar la expresión X es hijo de Y.
c) Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta al nodo Y. En
este caso es común utilizar la expresión X es padre de Y.
d) Se dice que todos los nodos que son descendientes directos —hijos— de un
mismo nodo —padre—- son hermanos.
e) Todo nodo que no tiene ramificaciones —hijos——, se conoce con el nombre de
terminal u hoja.
f) Todo nodo que no es raíz ni terminal u hoja se conoce con el nombre de interior.
g) Grado es el número de descendientes directos de un determinado nodo.
pág. 3
h) Grado del árbol es el máximo grado de todos los nodos del árbol.
I) Nivel es el número de arcos que deben ser recorridos para llegar a un
determinado nodo. Por definición la raíz tiene nivel 1.
j) Altura del árbol es el máximo número de niveles de todos los nodos del árbol.
Raíz: El nodo superior de un árbol.
Hijo: Un nodo conectado directamente con otro cuando se aleja de la raíz.
Padre: La noción inversa de hijo.
Hermanos: Un conjunto de nodos con el mismo padre.
Descendiente: Un nodo accesible por descenso repetido de padre a hijo.
Ancestro: Un nodo accesible por ascenso repetido de hijo a padre.
Hoja (llamado menos comúnmente nodo externo): Un nodo sin hijos.
Nodo interno: Un nodo con al menos un hijo.
Grado: Número de subárboles de un nodo.
Brazo: La conexión entre un nodo y otro.
Camino: Una secuencia de nodos y brazos conectados con un nodo
descendiente.
Nivel: El nivel de un nodo se define por 1 + (el número de conexiones entre
el nodo y la raíz).
Altura de un nodo: La altura de un nodo es el número de aristas en el
camino más largo entre ese nodo y una hoja.
Altura de un árbol: La altura de un árbol es la altura de su nodo raíz.
Profundidad: La profundidad de un nodo es el número de aristas desde la
raíz del árbol hasta un nodo.
Bosque: Un bosque es un conjunto de árboles n ≥ 0 disjuntos.
Rama: Una ruta del nodo raíz a cualquier otro nodo.
Longitud de camino interno y externo
Se define la longitud de camino del nodo X como el número de arcos que se
deben recorrer para llegar desde la raíz hasta el nodo X. Por definición la raíz
pág. 4
tiene longitud de camino 1, sus descendientes directos longitud de camino 2 y así
sucesivamente. Considere el árbol de la figura 6.2. El nodo B tiene longitud de
camino 2, el nodo I longitud de camino 4 y el nodo H longitud de camino 3.
Longitud de camino interno
La longitud de camino interno (LCI) del árbol es la suma de las longitudes de
camino de todos los nodos del árbol. Esta medida es importante porque permite
conocer los caminos que tiene el árbol. Se calcula por medio de la siguiente
fórmula:
Donde i representa el nivel del árbol, h su altura y n el número de nodos en el nivel
j. La LCI del árbol de la figura 6.2 se calcula de esta forma:
LCI= * 1+2*2+5*3+4*4=36
Ahora bien, la media de la longitud de camino interno (LCIM) se calcula dividiendo
la LCI entre el número de nodos del árbol (n). La media es importante porque
pág. 5
permite conocer, en promedio, el número de decisiones que se deben tomar para
llegar a un determinado nodo partiendo desde la raíz. Se expresa:
La LCIM del árbol de la figura 6.2 se calcula como se muestra a continuación:
LCIM = 36/3 = 3
Longitud de camino externo
Para definir la longitud de camino externo de un árbol es necesario primero
explicar los conceptos de árbol extendido y nodo especial.
Un árbol extendido es aquel en el que el número de hijos de cada nodo es igual al
grado del árbol. Si alguno de los nodos del árbol no cumple con esta condición,
entonces deben incorporarse al mismo tantos nodos especiales como se requiera
para llegar a cumplirla.
Los nodos especiales tienen como objetivo remplazar las ramas vacías o nulas, no
pueden tener descendientes y normalmente se representan con la forma de un
cuadrado.
En la figura 6.3 se presenta el árbol extendido de la figura 6.2. El número de nodos
especiales de este árbol es 25.
Se puede definir ahora la longitud de camino externo (LCE) de un árbol como la
suma de las longitudes de camino de todos los nodos especiales del árbol. Se
calcula por medio de la siguiente fórmula:
pág. 6
Donde j representa el nivel del árbol, h su altura y ne1 el número de nodos
especiales en el nivel I. Observe que i comienza desde 2, puesto que la raíz se
encuentra en el nivel 1 y no puede ser un nodo especial.
La LCE del árbol de la figura 6.3 se calcula de esta manera:
LCE= 1*2+1 *3 11 *4 12*5=109
Ahora bien, la media de la longitud de camino externo (LCEM) se calcula
dividiendo la LCE entre el número de nodos especiales del árbol (ne). Observe el
lector la siguiente fórmula:
E indica el número de arcos que se deben recorrer en promedio para llegar,
partiendo desde la raíz, a un nodo especial cualquiera del árbol.
La LCEM del árbol de la figura 6.3 se calcula de la siguiente manera:
pág. 7
LCEM = 109/25 = 4.36
El siguiente ejemplo clarificará los conceptos de longitud de camino interno y
externo.
Dado el árbol general de la figura 6.4 y el árbol extendido de la figura 6.5 se
calcula la longitud de camino interno:
pág. 8
RECORRIDOS
Una vez que se crea el árbol binario, se pueden realizar otras operaciones sobre
sus elementos: recorrer todos los nodos, insertar un nuevo nodo, eliminar alguno
de los existentes o buscar un valor determinado.
Una de las operaciones más importantes que se realiza en un árbol binario es el
recorrido de los mismos. Recorrer significa visitar los nodos del árbol en forma
ordenada, de tal manera que todos los nodos del mismo sean visitados una sola
vez. Existen tres formas diferentes de efectuar el recorrido y todas ellas de
naturaleza recursiva; éstas son:
a) Recorrido en preorden
1. Visitar la raíz
2. Recorrer el subárbol izquierdo
3. Recorrer el subárbol derecho
h) Recorrido en inorden
1. Recorrer el subárbol izquierdo
2. Visitar la raíz
3. Recorrer el subárbol derecho
c) Recorrido en posorden
1. Recorrer el subárbol izquierdo
pág. 9
2. Recorrer el subárbol derecho
3. Visitar la raíz
TIPOS DE ARBOLES
ÁRBOLES BALANCEADOS: Cuando se estudiaron los árboles binarios de
búsqueda se mencionó que es una estructura sobre la cual se pueden realizar
eficientemente las operaciones de búsqueda. inserción y eliminación. Sin
embargo, si el árbol crece o decrece descontroladamente, el rendimiento puede
disminuir considerablemente. El caso más desfavorable se produce cuando se
inserta un conjunto de claves ordenadas en forma ascendente o descendente.
ÁRBOLES BINARIOS: Un árbol ordenado es aquel en el cual la distribución de
las ramas sigue un cierto orden. Los árboles ordenados de grado 2 son de
especial interés en el área de la computación porque permiten representar la
información relacionada con la solución de muchos problemas. Estos árboles son
conocidos con el nombre de árboles binarios.
En un árbol binario cada nodo puede tener como máximo dos subárboles y éstos
se distinguen entre sí como el subárbol izquierdo y el subárbol derecho, según su
ubicación con respecto al nodo raíz.
ARBOLES MULTICAMINOS: Los diferentes tipos de árboles binarios estudiados
hasta el momento fueron desarrollados para funcionar en la memoria principal de
la computadora. Sin embargo, existen muchas aplicaciones en las que el volumen
de información es tal, que los datos no caben en la memoria principal y es
necesario almacenarlos, organizados en archivos. en dispositivos de
pág. 10
almacenamiento secundario. Esta organización de archivos debe ser
suficientemente adecuada corno para recuperar los datos en forma eficiente.
Árboles-B: Los árboles-B son una generalización de los árboles balanceados.
Éstos representan básicamente un método para almacenar y recuperar
información en medios externos. Fueron propuestos por Bayer y McCreight en
1970. Su nombre árboles-B nunca fue explicado por los autores, aunque muchos
sostienen que B proviene de Bayer, uno de sus inventores. En este tipo de
árboles, un grupo de nodos recibe el nombre de página. En cada página se
almacena la información de un grupo de nodos y se identifica por medio de una
clave o llave.
Arboles- B+: Los árboles-B+ se han convertido en la técnica más utilizada para la
organización de archivos indizados. La principal característica de estos árboles es
que toda la información se encuentra en las hojas, mientras que los nodos raíz e
interiores almacenan claves que se utilizan como índices. Debido a esta
característica de los árboles-B, todos los caminos desde la raíz hasta cualquiera
de los datos tienen la misma longitud.
Arboles 2-4: Los árboles 2-4 son una variante de los árboles multicaminos. Éstos
se caracterizan porque cada uno de sus nodos pueden tener máximo 4 hijos y
todos los nodos externos —hojas—- están al mismo nivel. Es decir, en estos
árboles se debe garantizar el tamaño y la altura de los mismos.
APLICACIONES REALES DE UN ÁRBOL
Los árboles son estructuras no lineales y dinámicas empleadas en muchas
aplicaciones computacionales, en especial en la construcción de compiladores, en
minería de datos, lingüística computacional.
Un árbol impone una estructura jerárquica sobre una colección de objetos.
Ejemplos claros de utilización de árboles se presentan tanto dentro como fuera del
área de computación (índices de libros, árboles genealógicos, etc.); en Informática
pág. 11
constituyen una de las estructuras más utilizadas, con aplicaciones que van desde
los árboles sintácticos utilizados para la representación y/o interpretación de
términos de un lenguaje o expresiones aritméticas.
En general, se usarán árboles siempre que se quiera representar información
jerarquizada, cuando esta converja en un solo punto.
Las aplicaciones de los arboles binarios son muy variadas ya que se les puede
utilizar para representar una estructura en la cual es posible tomar decisiones con
dos opciones en distintos puntos.
pág. 12
REFERENCIAS:
OSVALDO CAIRÓ, SILVIA GUARDATI. (2006). ESTRUCTURAS DE DATOS
Tercera edición. México: McGRAW-HILL/INTERAMERICANA EDITORES, S.A. DE
C.V..
Bottazzi, Cristian. Costarelli, Santiago.. (0). Algoritmos y Estructuras de Datos.
Universidad Nacional del Litoral: s/n.
pág. 13
