4 tipos de árboles en la estructura de datos explicados: propiedades y aplicaciones

¿Qué es un árbol en la estructura de datos?

Un árbol es un tipo de estructura de datos que representa datos jerárquicos. Tiene una estructura no lineal que consiste en nodos conectados por bordes. Entre los otros tipos de estructuras de datos que realizan operaciones en una estructura de datos lineal, la complejidad aumenta con el aumento del tamaño de los datos. Sin embargo, la estructura de datos de árbol proporciona un acceso más rápido a los datos que no son lineales. Disponibilidad de los diversos tipos de estructuras de datos y los algoritmos asociados a ellos, el desempeño de tareas se ha convertido en una forma fácil y eficiente.

Algunas terminologías asociadas con los árboles en la estructura de datos son:

• Nodo : el nodo es una entidad en una estructura de datos de árbol que contiene una clave o un valor y punteros a sus nodos secundarios.
• Nodo secundario: un nodo secundario es el descendiente de cualquier nodo.
• Nodos de hoja: los nodos que no tienen ningún nodo secundario y son el nodo más inferior de un árbol. También se denominan nodos externos.
• Raíz : Es el punto más alto de un árbol.
• Nodo interno : el nodo que tiene al menos un nodo hijo.
• Borde: Un borde se refiere a la conexión entre dos nodos en un árbol.
• Altura de un nudo: Número de aristas desde el nudo hasta la hoja más profunda.
• Profundidad de un nodo : Número de aristas desde la raíz hasta el nodo.
• Altura de un árbol : Altura del nodo raíz.
• Grado de un nodo : Número total de ramas a ese nodo.
• Bosque: Una colección de árboles disjuntos.

tipos de arbol

1. Árbol binario

El árbol binario es un tipo de estructura de datos de árbol donde cada nodo principal tiene un máximo de dos nodos secundarios. Como sugiere el nombre, binario significa dos, por lo tanto, cada nodo puede tener 0, 1 o 2 nodos. En la Figura 1 se muestra una estructura de datos de árbol binario . El nodo 1 del árbol contiene dos punteros, uno para cada nodo secundario. El nodo 2 nuevamente tiene dos punteros cada uno para los dos nodos secundarios. Mientras que los nodos 3, 5 y 6 son nodos de hoja y, por lo tanto, tienen punteros nulos en las partes izquierda y derecha.

Figura 1: Una representación de un árbol binario ( https://www.javatpoint.com/binary-tree ).

Propiedades de un árbol binario

• El número máximo de nodos en cada nivel de I es 2 i .
• La altura del árbol en la Figura 1 es 3, lo que significa que el número máximo de nodos será (1+2+4+8) =15.

• En la altura h, el número máximo de nudos posibles es (20 + 21 + 22+….2h) = 2h+1 -1.

• A la altura h, el número mínimo de nodos posibles es igual a h+1.

• Un número mínimo de nodos representará un árbol con la altura máxima y viceversa.

Incluso los árboles binarios se pueden dividir en los siguientes tipos de árboles:

• Árbol binario completo: Es un tipo especial de árbol binario. En esta estructura de datos de árbol, cada nodo padre o un nodo interno tiene dos hijos o ningún nodo hijo.
• Árbol binario perfecto: en este tipo de estructura de datos de árbol , cada nodo interno tiene exactamente dos nodos secundarios y todos los nodos hoja están al mismo nivel.
• Árbol binario completo: se parece al árbol binario completo con algunas diferencias.
• Cada nivel está completamente lleno.
• Los nudos de las hojas se inclinan hacia la izquierda del árbol.
• No es un requisito que el último nodo hoja tenga el hermano correcto, es decir, un árbol binario completo no tiene que ser un árbol binario completo.
• Árbol degenerado o patológico: estos árboles tienen un solo hijo a la izquierda o a la derecha del nodo padre.
• Árbol binario sesgado: es un árbol patológico o degenerado en el que el árbol está dominado por los nodos izquierdos o los nodos derechos. Por lo tanto, hay dos tipos de árboles binarios sesgados, es decir, árbol binario sesgado a la izquierda o sesgado a la derecha.
• Árbol binario equilibrado: la diferencia entre la altura del subárbol izquierdo y derecho para cada nodo es 0 o 1.

2. Árbol de búsqueda binaria

Estas estructuras de árbol no son lineales y un nodo está conectado a varios nodos. El nodo se puede conectar como máximo a dos nodos secundarios. Se llama árbol de búsqueda binaria porque:

• Cada nodo tiene un máximo de dos nodos secundarios.
• Se puede usar para buscar un elemento en 0 (log (n)) tiempo y, por lo tanto, se conoce como árbol de búsqueda.

Figura: Un ejemplo de un árbol de búsqueda binario ( https://www.tutorialspoint.com/data_structures_algorithms/binary_search_tree.htm )

Las propiedades de un árbol de búsqueda binaria son:

• El valor en todos los nodos de un subárbol izquierdo debe ser menor que el valor en el nodo raíz.
• El valor en todos los nodos de un subárbol derecho debe ser mayor que el valor en el nodo raíz.

3. Árbol AVL

Los árboles AVL son los tipos o variantes de un árbol binario. Consiste en propiedades tanto del binario como de un árbol de búsqueda binario. Inventados por Adelson Velsky Lindas, estos árboles se autoequilibran, lo que significa que la altura del subárbol izquierdo y del subárbol derecho está equilibrada. Este equilibrio se mide en términos de un factor de equilibrio.

Factor de equilibrio:

• Es la diferencia entre el subárbol izquierdo y el subárbol derecho.
• El valor de un factor de equilibrio debe ser 0, -1 o 1. Por lo tanto, cada nodo de un árbol AVL debe constar de un valor de factor de equilibrio, es decir, 0, -1 o 1.
• Factor de equilibrio = (Altura del subárbol izquierdo - Altura del subárbol derecho)
• Se dice que un árbol AVL es un árbol equilibrado si el factor de equilibrio de cada nodo está entre -1 y 1.

Los valores de los nodos distintos de -1, a 1 en un árbol AVL representarán un árbol desequilibrado que debe equilibrarse.

• Si un nodo tiene un factor de equilibrio de 1, significa que el subárbol izquierdo está un nivel más alto que el subárbol derecho.
• Si un nodo tiene un factor de equilibrio de 0, significa que la altura del subárbol izquierdo y el subárbol derecho es igual.
• Si un nodo tiene un factor de equilibrio de -1, significa que el subárbol derecho está un nivel por encima del subárbol izquierdo o que el subárbol izquierdo está un nivel por debajo del subárbol derecho.

4. Árbol B

B Tree es una forma más generalizada de un árbol de búsqueda binaria. También se conoce como el árbol m way de altura equilibrada, donde m es el orden del árbol. Cada nodo del árbol puede tener más de una clave y más de dos nodos secundarios. En el caso de un árbol binario, los nodos hoja pueden no estar al mismo nivel. Sin embargo, en el caso de un Árbol B, todos los nodos hoja deben estar al mismo nivel.

Propiedades de un árbol B:

• Las claves se almacenan en orden creciente para cada nodo x.
• Existe un valor booleano "x.leaf" en cada nodo, lo cual es cierto si x es una hoja.
• Los nodos internos deben tener como máximo claves "n-1", donde n es el orden del árbol. También debe tener un puntero para cada niño.
• Todos los nodos tendrán como máximo n hijos y al menos n/2 hijos, excepto el nodo raíz.
• Los nodos de las hojas del árbol tienen la misma profundidad.
• El nodo raíz tendrá un mínimo de 1 clave y al menos dos hijos.
• Si n ≥ 1, entonces para cualquier árbol B de clave n de altura h y grado mínimo t ≥ 2, h ≥ logt (n+1)/2.

Aplicaciones

• El árbol de búsqueda binaria se puede aplicar para buscar un elemento en un conjunto de elementos.
• Los árboles de montón se utilizan para la ordenación de montón.
• Los enrutadores modernos usan un tipo de árbol llamado Tries para almacenar información de enrutamiento.
• Los B-Trees y los T-Trees son utilizados principalmente por bases de datos populares para almacenar sus datos.
• Los compiladores utilizan un árbol de sintaxis para validar la sintaxis de cada programa escrito.

Conclusión

Las estructuras de datos proporcionan una forma organizada de almacenar los datos para una gestión sencilla y un manejo eficaz. Existen varios tipos de estructuras de datos para diferentes tipos de datos. Basado en el tipo de datos que necesitan ser almacenados, es elegido por el usuario.

Los árboles son tipos de tales estructuras de datos donde se puede almacenar el tipo jerárquico de datos. Los datos se almacenan en los nodos que a veces almacenan la referencia para otros nodos llamados nodos secundarios.

Según la cantidad de nodos secundarios, los árboles se pueden clasificar en varios tipos, como se menciona en el artículo. Según la disposición de los nodos en los tipos de árbol, cada estructura de árbol tiene propiedades asociadas. Con los diferentes tipos de operaciones que pueden realizar las diferentes clases de árboles, este tipo de estructura de datos ha encontrado aplicaciones en algoritmos de clasificación y almacenamiento de datos.

Un programa Executive PG en desarrollo de software: especialización en desarrollo de pila completa, curado por upGrad & IIIT-Bangalore, puede ayudarlo a mejorar su perfil y asegurar mejores oportunidades de empleo como programador.