"La "clasificación de los árboles y sus aplicaciones"

INSTITUTO TECNOLÓGICO DE COMITÁN Ingeniería Sistemas Computacionales Asignatura: Estructura de Datos Docente: Gladys Valdés Colunga Tema: "La clasificación de los árboles y sus aplicaciones" Presenta: Luis Enrique Díaz Sánchez-21700169 Comitán de Domínguez, Chiapas; a 13 de octubre de 2023.

Introducción

En este trabajo, exploraremos la fascinante estructura de datos no lineales conocida como "árbol". Los árboles se utilizan para representar información con relaciones jerárquicas entre sus elementos, como registros, árboles genealógicos y tablas de contenidos. En particular, nos sumergiremos en un tipo especial de árbol: el "árbol binario", que se implementa fácilmente en computadoras, a pesar de su aparente restricción. Sin embargo, nuestro viaje no se limitará al mundo de los árboles binarios. También profundizaremos en conceptos clave, como la terminología asociada con los árboles, los árboles binarios complementarios, los árboles binarios de búsqueda y las operaciones de búsqueda e inserción en árboles binarios de búsqueda. Además, exploraremos árboles más generales y cómo representarlos en computadoras, así como la interesante relación entre los árboles generales y los árboles binarios. Este trabajo te llevará a través de un emocionante viaje a través del mundo de las estructuras de datos jerárquicas, revelando su utilidad y versatilidad en una variedad de aplicaciones.

Arboles

(wikipedia, 2022)

(CÓMPUTO, 2022)

Una estructura de datos de árbol se puede definir de forma recursiva (localmente) como una colección de nodos (a partir de un nodo raíz), donde cada nodo es una estructura de datos con un valor, junto con una lista de referencias a los nodos (los hijos), con la condición de que ninguna referencia esté duplicada ni que ningún nodo apunte a la raíz.

son considerados las estructuras de datos no lineales y dinámicas de datos muy importantes del área de computación.

(CÓMPUTO, 2022)

(wikipedia, 2022)

les llama estructuras dinámicas, porque las mismas pueden cambiar tanto de forma como de tamaño durante la ejecución del programa.

En ciencias de la computación y en informática, un árbol es un tipo abstracto de datos (TAD) ampliamente usado que imita la estructura jerárquica de un árbol, con un valor en la raíz y subárboles con un nodo padre, representado como un conjunto de nodos enlazados.

(CÓMPUTO, 2022)

son muy utilizados en informática como un método eficiente para búsquedas grandes y complejas.

(CÓMPUTO, 2022)

(CÓMPUTO, 2022)

Casi todos los sistemas operativos almacenan sus archivos en árboles o estructuras similares a árboles.

Y estructuras no lineales porque cada elemento del árbol puede tener más de un sucesor

Arboles

Datos importantes de los Árboles

propiedades importantes

(Blog, 2022)

(wikipedia, 2022)

• Nodos: Se le llama Nodo a cada elemento que contiene un Árbol.
• Nodo Raíz: Se refiere al primer nodo de un Árbol, Solo un nodo del Árbol puede ser la Raíz.
• Nodo Padre: Se utiliza este termino para llamar a todos aquellos nodos que tiene al menos un hijo.
• Nodo Hijo: Los hijos son todos aquellos nodos que tiene un padre.
• Nodo Hermano: Los nodos hermanos son aquellos nodos que comparte a un mismo padre en común dentro de la estructura.
• Nodo Hoja: Son todos aquellos nodos que no tienen hijos, los cuales siempre se encuentran en los extremos de la estructura.
• Nodo Rama: Estos son todos aquellos nodos que no son la raíz y que ademas tiene 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 brazos entre el nodo y la raíz).
• Altura de un nodo: La altura de un nodo es el número de brazos 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 brazos desde la raíz del árbol hasta un nodo.
• Bosque: Un bosque es un conjunto de árboles n ≥ 0 disjuntos.

Arboles

Recorrido sobre Árboles

Búsquedas no informadas

(Blog, 2022)

(Blog, 2022)

Las búsquedas no informadas son aquellas en que se realiza el viaje por todo el árbol sin tener una pista de donde pueda estar el dato deseado. Este tipo de búsquedas también se conocen como búsquedas a ciegas. A este tipo de escenarios en los cuales las búsquedas de hacen a ciegas los conocemos como búsquedas no informadas.

Los recorridos son algoritmos que nos permiten recorrer un árbol en un orden especifico, los recorridos nos pueden ayudar encontrar un nodo en el árbol, o buscar una posición determinada para insertar o eliminar un nodo. Básicamente podemos catalogar las búsqueda en dos tipos, las búsqueda en profundidad y las búsquedas en amplitud. pertenecen a las búsquedas no informadas. Búsqueda en profundidad Recorrido Pre-orden: El recorrido inicia en la Raíz y luego se recorre en pre-orden cada unos de los sub-árboles de izquierda a derecha. Esta definición puede ser un poco compleja de entender por lo que mejor les dejo la siguiente imagen.

(Blog, 2022)

Recorrido Pre-orden: El recorrido inicia en la Raíz y luego se recorre en pre-orden cada unos de los sub-árboles de izquierda a derecha.

(Blog, 2022)

Recorrido in-orden: Se recorre en in-orden el primer sub-árbol, luego se recorre la raíz y al final se recorre en in-orden los demas sub-árboles

(Blog, 2022)

Recorrido Pos-orden: Se recorre el pos-orden cada uno de los sub-árboles y al final se recorre la raíz.

Arboles

clasificacion

Árboles Binarios.

Árboles B (Árboles de búsqueda multicamino autobalanceados)

Árbol de búsqueda binario auto-balanceable.

Árbol de segmento.

Árboles AVL.

Árboles Multicamino.

Árbol AA.

Árboles Rojo-Negro.

(wikipedia, 2022

conclusion

En Conclusión, un árbol binario se define como un conjunto finito de elementos llamados nodos. Al emplear una terminología que evoca relaciones familiares, podemos comprender de manera más clara las relaciones entre los nodos de un árbol. Es importante destacar que la implementación de un árbol en una computadora es un proceso accesible y eficiente, lo que nos permite aprovechar todo su potencial en diversas aplicaciones. A lo largo de este trabajo, hemos explorado conceptos fundamentales como la raíz de un árbol, los nudos que lo componen, y la distinción entre nodos sucesores y nodos terminales. Estos elementos forman la base para comprender en profundidad las estructuras de datos jerárquicas y su utilidad en la resolución de problemas en la informática y más allá. En última instancia, hemos revelado que los árboles binarios son solo el punto de partida en un mundo de posibilidades y aplicaciones más amplias en el ámbito de las estructuras de datos no lineales. La comprensión de estos conceptos nos permite explorar y aprovechar el potencial de los árboles en contextos diversos, desde la organización de información hasta la optimización de algoritmos.

Referencias

Blog, O. B. (07 de octubre de 2022). Estructura de datos – Árboles. Obtenido de https://www.oscarblancarteblog.com/2014/08/22/estructura-de-datos-arboles/ CÓMPUTO, L. R. (07 de octubre de 2022). ESTRUCTURAS DE DATOS. Obtenido de Unidad VII. Árboles: https://www.uv.mx/personal/ermeneses/files/2021/08/Clase8-Arboles.pdf wikipedia. (07 de octubre de 2022). Árbol (informática). Obtenido de https://es.wikipedia.org/wiki/%C3%81rbol_(inform%C3%A1tica)

¡Gracias!