En este tutorial, aprenderá sobre la estructura de datos de árbol. Además, aprenderá sobre los diferentes tipos de árboles y las terminologías utilizadas en árbol.
Un árbol es una estructura de datos jerárquica no lineal que consta de nodos conectados por bordes.
Un árbol
¿Por qué Tree Data Structure?
Otras estructuras de datos como matrices, listas enlazadas, pila y cola son estructuras de datos lineales que almacenan datos de forma secuencial. Para realizar cualquier operación en una estructura de datos lineal, la complejidad del tiempo aumenta con el aumento del tamaño de los datos. Pero no es aceptable en el mundo computacional actual.
Las diferentes estructuras de datos de árbol permiten un acceso más rápido y fácil a los datos, ya que es una estructura de datos no lineal.
Terminologías de árboles
Nodo
Un nodo es una entidad que contiene una clave o valor y apunta a sus nodos secundarios.
Los últimos nodos de cada ruta se denominan nodos hoja o nodos externos que no contienen un enlace / puntero a los nodos secundarios.
El nodo que tiene al menos un nodo hijo se denomina nodo interno .
Borde
Es el enlace entre dos nodos cualesquiera.
Nodos y bordes de un árbol
Raíz
Es el nodo más alto de un árbol.
Altura de un nodo
La altura de un nodo es el número de bordes desde el nodo hasta la hoja más profunda (es decir, el camino más largo desde el nodo hasta un nodo hoja).
Profundidad de un nodo
La profundidad de un nodo es el número de bordes desde la raíz hasta el nodo.
Altura de un árbol
La altura de un árbol es la altura del nodo raíz o la profundidad del nodo más profundo.
Altura y profundidad de cada nodo en un árbol.
Grado de un nodo
El grado de un nodo es el número total de ramas de ese nodo.
Bosque
Una colección de árboles disjuntos se llama bosque.
Creando bosque a partir de un árbol
Puede crear un bosque cortando la raíz de un árbol.
Tipos de árbol
- Árbol binario
- Árbol de búsqueda binaria
- Árbol AVL
- Árbol B
Cruce de árboles
Para realizar cualquier operación en un árbol, debe llegar al nodo específico. El algoritmo de recorrido de árbol ayuda a visitar un nodo requerido en el árbol.
Para obtener más información, visite el cruce de árboles.
Aplicaciones de árbol
- Los árboles de búsqueda binaria (BST) se utilizan para comprobar rápidamente si un elemento está presente en un conjunto o no.
- Heap es un tipo de árbol que se utiliza para ordenar montones.
- En los enrutadores modernos se usa una versión modificada de un árbol llamado Tries para almacenar información de enrutamiento.
- Las bases de datos más populares utilizan B-Trees y T-Trees, que son variantes de la estructura de árbol que aprendimos anteriormente para almacenar sus datos.
- Los compiladores utilizan un árbol de sintaxis para validar la sintaxis de cada programa que escribe.
