Implementación de Árboles Binarios

Vista previa del material en texto

Nombre del alumno: Antony Arturo García Pérez
Matrícula: 2020690020
Carrera: Licenciatura en Ciencia de Datos
Nombre de la materia: Algoritmos y Estructura de Datos
Nombre del docente: Carlos Basulto González
Implementación de Árboles Binarios
Sabinas, Coahuila							13/12/2020
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. En un árbol binario cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
Existen tipos de árboles binarios que suelen usarse para fines específicos, como:
· Árbol binario de búsqueda
· Árbol de Fibonacci
Implementación en C
Un árbol binario puede declararse de varias maneras. Algunas de ellas son:
Estructura con manejo de memoria dinámica, siendo el puntero que apunta al árbol de tipo tArbol:
typedef struct nodo {
 int clave;
 struct nodo *izdo, *dcho;
}Nodo;
Estructura con arreglo indexado:
typedef struct tArbol
{
 int clave;
 tArbol hIzquierdo, hDerecho;
} tArbol;
tArbol árbol[NUMERO_DE_NODOS];
En el caso de un árbol binario casi-completo (o un árbol completo), puede utilizarse un sencillo arreglo de enteros con tantas posiciones como nodos deba tener el árbol. La información de la ubicación del nodo en el árbol es implícita a cada posición del arreglo. Así, si un nodo está en la posición i, sus hijos se encuentran en las posiciones 2i+1 y 2i+2, mientras que su padre (si tiene), se encuentra en la posición truncamiento ((i-1)/2) (suponiendo que la raíz está en la posición cero). Este método se beneficia de un almacenamiento más compacto y una mejor localidad de referencia, particularmente durante un recorrido en pre orden. La estructura para este caso sería por tanto:
int árbol[NUMERO_DE_NODOS];
Los árboles binarios representan una de las estructuras de datos más importantes en computación; por su dinamismo, la no linealidad entre sus elementos, y por su sencilla programación.
Para un árbol en general como el que se muestra en la figura anterior, se han configurado algunos pasos que se deben ejecutar para convertir ese árbol general en un árbol binario. Consideremos un árbol en general, los pasos por aplicar para lograr la conversión del árbol en general a un árbol binario son los siguientes:
1. Deben enlazarse los hijos de cada nodo en forma horizontal, (los hermanos). 
2. Debe enlazarse en forma vertical el nodo padre con el hijo que se encuentra más a la izquierda; además debe eliminarse el vínculo de ese padre con el resto de sus hijos. 
3. Debe rotarse el diagrama resultante aproximadamente cuarenta y cinco grados hacia la izquierda; para obtener el árbol binario correspondiente.
Se muestra la aplicación de esos pasos para el árbol mostrado antes. El árbol después de aplicar el paso uno es:
Árbol obtenido después de aplicar los pasos dos y tres:
Una de las grandes utilidades y ventajas de los arboles binarios son su gran ahorro de energía y tiempo a la hora de ordenar números o datos deseados, siendo que además esta es una de las maneras más fáciles de hacerlo, también posee una gran ventaja frente a otros métodos a la hora de buscar algún número o dato deseado, por lo que en áreas como en la Ciencia de Datos donde se manejan grandes volúmenes de datos, esta representa una gran herramienta, además de que gracias a este nivel tan alto de búsqueda y ordenamiento, en el área de la Inteligencia Artificial se pueden crear modelos e inteligencias que aprendan o busquen cierto elemento de manera autónoma mucho más rápido
Conclusión
Al concluir esta actividad pude comprender los beneficios y utilidades que tienen los árboles binarios dentro de los campos de la Ciencia de Datos y de La Inteligencia Artificial, así como entendí las implementaciones que estos tienen. Pienso que es muy importante poder comprender este tipo de herramientas ya que así si en algún momento de nuestra vida se nos presenta algún problema podamos recurrir a nuestros conocimientos en este tema
Referencias
· http://www.sites.upiicsa.ipn.mx/estudiantes/academia_de_informatica/estructura_y_rd/docs/u3/Conversi%C3%B3n%20de%20%C3%A1rboles%20generales%20en%20%C3%A1rboles%20binarios.pdf
· http://delta.cs.cinvestav.mx/~adiaz/anadis/BinTree.pdf
· Euler, L. (1736). «Solutio problematis ad geometriam situs pertinentis». Commentarii Academiae Scientiarum Imperialis Petropolitanae 8. 128-140.
· Erdős, P. ; Gallai, T. (1960). «Graphs with prescribed degree of vertices». Mat. Lapok 11. 264–274..
· Havel, V. (1955). «A remark on the existence of finite graphs.». Časopis Pest. Mat. 80. 477–480..