Instituto Tecnológico
de Reynosa
Tecnologías de la Información y la
comunicación (TIC’s)
Investigación:
Aplicaciones de los Arboles
Integrantes:
1.- Alberto Flores Castillo
2.- Juan Manuel Avelino Hdz.
3.- Jorge Luis García Sierra
Materia: Matemáticas Discretas II.
Catedrático: Lic.: María de los Ángeles Rocha
Sánchez.
Cd. Reynosa Tamps., 12 de abril de 2011
APLICACIONES DE ARBOLES EN LA COMPUTACIÓN.
INTRODUCCIÓN
Los árboles representan las estructuras no lineales y dinámicas de datos más
importantes en computación. Los árboles pueden ser construidos con estructuras
estáticas y dinámicas. Las estáticas son arreglos, registros y conjuntos, mientras
que las dinámicas están representadas por listas.
Un árbol es 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.
Existen diferentes formas de representación de un árbol, entre las más comunes
se tienen las siguientes: Mediante círculos y flechas, Mediante paréntesis
anidados, Mediante notación decimal de Dewey. Algunas veces se incluye entre
los árboles el árbol nulo vacío, el cual, es un árbol sin nodos que se representa
mediante la letra.
Cualquier nodo del árbol podría tener un número arbitrario de nodos hijos, a esto
se le conoce como un árbol general, como se muestra en la siguiente figura. Si se
limita el número de nodos hijos para cada nodo del árbol, digamos a un número n
> 2 (llamado la aridad del árbol), entonces el árbol de aridad n es llamado n-ario.
La terminología que por lo regular se utiliza para el manejo de árboles es la
siguiente:
-HIJO. X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice
que X es descendiente directo de Y.
-PADRE. X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que
X es antecesor de Y.
-HERMANO. Dos nodos serán hermanos si son descendientes directos de un
mismo nodo.
-HOJA. Se le llama hoja o terminal a aquellos nodos que no tienen
ramificaciones.
-NODO INTERIOR. Es un nodo que no es raíz ni terminal.
-GRADO. Es el número de descendientes directos de un determinado nodo.
-GRADO DEL ÁRBOL Es el máximo grado de todos los nodos del árbol.
-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.
-ALTURA. Es el máximo número de niveles de todos los nodos del árbol.
-PESO. Es el número de nodos del árbol sin contar la raíz.
-LONGITUD DE CAMINO. Es el número de arcos que deben ser recorridos para
llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y
sus descendientes directos longitud de camino 2 y así sucesivamente.
ORDEN DE LOS NODOS. Generalmente los árboles de un nodo se ordenan de
izquierda a derecha. Si no se toma en cuenta el orden de los nodos hijos, entonces
se habla de un árbol no ordenado.
APLICACIÓN DE ÁRBOLES EN LAS ÁREAS DE COMPUTACIÓN
De las estructuras de datos de tipo Árbol, la especie más utilizada es el Árbol
Binario de Búsqueda. Los principales tipos de árboles binarios de búsqueda son
los AVL, B* y balanceado.
Los árboles binarios de búsqueda se utilizan para localizar en forma rápida un
elemento almacenado en ese árbol, a partir de una clave. Son una forma de
implementar arreglos asociativos o mapas, en donde se almacenan elementos que
son pares <clave, valor>.
En las bases de datos relacionales, para poder localizar en forma rápida un
registro de una taba a partir de una clave, se utilizan objetos asociados a las tablas
llamados índices. Estos índices son árboles binarios de búsqueda almacenados en
el disco, que a partir de una clave indican dónde se encuentra el registro
correspondiente en la tabla.
Otro ejemplo de la utilización de árboles binarios de búsqueda son los
diccionarios. A partir de una palabra, se realiza una búsqueda en el árbol para
saber si está incluida en el conjunto, y si existe, se obtienen sus datos asociados
(por ejemplo, si es un verbo, un sustantivo, un artículo, etc.).
En Teoría de Compiladores, durante la fase de análisis del código fuente, los
analizadores léxico, sintáctico y semántico utilizan tablas de símbolos, en donde
se almacenan las palabras clave y las palabras reservadas y sus atributos,
implementadas (por lo general) como árboles binarios de búsqueda.
En síntesis, se utiliza un árbol binario de búsqueda cuando se desea almacenar en
una estructura de datos cierta información, a la cual luego se desea acceder en
forma rápida a partir de una clave.
La representación gráfica de un árbol binario es la siguiente:
Representación en Memoria
Hay dos formas tradicionales de representar un árbol binario en memoria:
* Por medio de datos tipo punteros también conocidos como variables
dinámicas o listas.
* Por medio de arreglos.
Sin embargo la más utilizada es la primera, puesto que es la más natural para
tratar este tipo de estructuras.
Los nodos del árbol binario serán representados como registros que contendrán
como mínimo tres campos. En un campo se almacenará la información del nodo.
Los dos restantes se utilizarán para apuntar al subárbol izquierdo y derecho del
subárbol en cuestión.
Cada nodo se representa gráficamente de la siguiente manera:
Clasificación de Arboles Binarios
Existen cuatro tipos de árbol binario:.
* A. B. Distinto.
* A. B. Similares.
* A. B. Equivalentes.
* A. B. Completos.
A continuación se hará una breve descripción de los diferentes tipos de árbol
binario así como un ejemplo de cada uno de ellos.
A. B. DISTINTO
Se dice que dos árboles binarios son distintos cuando sus estructuras son
diferentes. Ejemplo:
A. B. SIMILARES
Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la
información que contienen sus nodos es diferente. Ejemplo:
A. B. EQUIVALENTES
Son aquellos arboles que son similares y que además los nodos contienen la
misma información. Ejemplo:
A. B. COMPLETOS
Son aquellos arboles en los que todos sus nodos excepto los del último nivel,
tiene dos hijos; el subárbol izquierdo y el subárbol derecho.
Recorridos.
El recorrido en un árbol binario permite rescatar los datos en formas diferentes.
Aunque existen varias maneras de hacerlo, aquí se verán las más conocidas:
inorden, preorden, postorden.
Una de los recorridos más usados (inorden) es el que rescata los datos en forma
ordenada (de menor a mayor).
La técnica que usualmente se usa para hacer el recorrido, es ir almacenando los
datos en una estructura lineal: Cola, Lista o Pila.
El criterio para escoger una de las tres depende del problema, pero generalmente
los criterios generales son los siguientes:
Cola: los datos quieren ser vistos en el mismo orden en el cual fueron
recorridos y la cola pasa a ser un instrumento de almacenamiento de "corto
plazo" : (almacenar , ver , vaciar ).
Lista: los datos necesitan ser almacenados y se requieren operaciones en
donde es necesario acceder a los datos en cualquier posición.
Pila: se necesita que los datos se almacenen en forma de pila, pasando a ser un
instrumento de almacenamiento de "corto plazo".
De aquí en adelante, las implementaciones de recorrido serán usando una Cola,
ya que los problemas que vienen, requieren los datos en forma ordenada.
Definición de Recorridos
Inorden: recorrer en inorden el subárbol izquierdo, visitar el elemento de la
raíz y luego recorrer en inorden el subárbol derecho.
Preorden: visitar el elemento de la raíz, recorrer en preorden el subárbol
izquierdo y luego recorrer en preorden el subárbol derecho.
Postorden: recorrer en postorden el subárbol izquierdo, luego recorrer en
postorden el subárbol derecho y finalmente visitar el elemento de la raíz.
