Árbol binario en estructura de datos: propiedades, tipos, representación y beneficios

Entre los diferentes tipos de estructuras de datos se encuentran los árboles binarios que tienen más usos que la mayoría de los otros tipos. Sus aplicaciones más notables incluyen programación peer-to-peer, búsqueda, criptografía, enrutadores de red con mayor ancho de banda que otros y videojuegos en 3D. Ahora discutiremos en detalle qué son los árboles binarios en la ciencia de datos, cuáles son sus tipos y cómo se representan.

¿Qué son los árboles binarios?

Si ha trabajado en árboles normales antes o incluso conoce sus conceptos básicos, sabrá que no hay restricciones en lo que respecta a la cantidad de elementos secundarios que se permite que los diferentes nodos tengan en estos árboles. Los árboles binarios son un poco diferentes en este sentido. Cada padre o nodo en árboles binarios puede tener un máximo de solo dos hijos.

Todos los nodos en un árbol binario tienen tres componentes principales:

• un elemento de datos
• una referencia correcta
• una referencia izquierda

El nodo que se encuentra en la parte superior del árbol se denomina nodo raíz. Los nodos padres son aquellos que tienen hijos. Los nodos secundarios y los nodos principales están conectados entre sí a través de referencias. Los nodos que no tienen hijos se denominan nodos hoja.

Es claramente evidente que los nodos en los árboles binarios pueden tener un hijo, dos hijos o ningún hijo. Los árboles binarios no son estructuras de datos lineales como colas, matrices, pilas y listas vinculadas. En cambio, son estructuras de datos jerárquicas.

Echa un vistazo a: Ideas de proyectos de ciencia de datos para principiantes

Propiedades importantes de los nodos en árboles binarios

Una mejor comprensión de estas propiedades lo ayudará a aprovechar al máximo esta discusión sobre árboles binarios. La profundidad de los diferentes nodos se define como el número de nodos que existen en el camino que conecta la raíz con un nodo en particular. Es por eso que la profundidad del nodo raíz es 0. Por otro lado, la altura de los diferentes nodos en un árbol binario es el número de nodos que se encuentran en el camino que conecta un nodo particular con el nodo raíz. Es por eso que la altura de los nodos hoja es 0.

Como puede ver claramente, la profundidad de un nodo se mide comenzando desde el nodo raíz y luego descendiendo hasta llegar a ese nodo. Por otro lado, cuando se trata de calcular la altura, comenzamos en el nodo en cuestión y luego viajamos hacia el nodo raíz. Las dos veces, empezamos en 0. Hay gente que también mide la altura y la profundidad desde 1 y no desde 0, lo cual no está mal y es justo lo que prefieren diferentes personas.

Ahora, la profundidad máxima de un nodo se define como la profundidad de un árbol binario. De manera similar, la altura máxima de un nodo se define como la altura de un árbol binario. Entonces, la altura y la profundidad de un árbol binario son siempre las mismas.

Más información: estructuras de datos y algoritmos en Python

¿Qué es un árbol de búsqueda binaria?

Un árbol de búsqueda binario es el más común de todos los otros tipos de árboles binarios. Es un árbol binario especializado que viene con propiedades que son diferentes y más útiles que cualquier otra forma de árbol binario. ¿Qué es exactamente un árbol de búsqueda binario o BST? Tal como sugiere su nombre, un árbol de búsqueda binaria se utiliza para buscar datos en el árbol.

Un BST viene con propiedades que le permiten facilitar búsquedas eficientes. Un BST es un árbol binario que tiene la clave del nodo que es menor y mayor que los nodos del subárbol derecho y los nodos del subárbol izquierdo, respectivamente.

Representación de árboles binarios

1. Representación vinculada

Los árboles binarios en representación enlazada se almacenan en la memoria como listas enlazadas. Estas listas tienen nodos que no están almacenados en ubicaciones de memoria adyacentes o vecinas y están vinculados entre sí a través de la relación padre-hijo asociada con los árboles.

En esta representación, cada nodo tiene tres partes diferentes:

• puntero que apunta hacia el nodo derecho,
• puntero que apunta hacia el nodo izquierdo,
• elemento de datos

Esta es la representación más común. Todos los árboles binarios constan de un puntero raíz que apunta en la dirección del nodo raíz. Cuando vea un nodo raíz que apunta hacia nulo o 0, debe saber que se trata de un árbol binario vacío. Los punteros derecho e izquierdo almacenan la dirección de los hijos derecho e izquierdo del árbol.

2. Representación secuencial

Aunque es más simple que la representación vinculada, su ineficiencia lo convierte en una representación de árbol binario menos preferida de los dos. La ineficiencia radica en la cantidad de espacio que requiere para el almacenamiento de diferentes elementos del árbol. La representación secuencial utiliza una matriz para el almacenamiento de elementos de árbol.

El número de nodos que tiene un árbol binario define el tamaño de la matriz que se utiliza. El nodo raíz del árbol binario se encuentra en el primer índice de la matriz. El índice en el que se almacena un nodo en particular definirá los índices en los que se almacenarán los elementos secundarios derecho e izquierdo del nodo. Un árbol vacío tiene nulo o 0 como su primer índice.

Tipos de árboles binarios

1. Árboles binarios completos: Los árboles binarios completos son aquellos árboles binarios cuyos nodos tienen dos hijos o ninguno. En otras palabras, un árbol binario se convierte en un árbol binario completo cuando, aparte de las hojas, todos sus otros nodos tienen dos hijos.
2. Árboles binarios completos: Los árboles binarios completos son aquellos que tienen todos sus diferentes niveles completamente llenos. La única excepción a esto podría ser su último nivel, cuyas teclas están predominantemente a la izquierda. Un montón binario a menudo se toma como ejemplo de un árbol binario completo.
3. Árboles binarios perfectos: Los árboles binarios perfectos son árboles binarios cuyas hojas están presentes al mismo nivel y cuyos nodos internos tienen dos hijos. Un ejemplo común de un árbol binario perfecto es un árbol genealógico ancestral.
4. Árboles binarios degenerados patológicos: Los árboles degenerados son aquellos árboles binarios cuyos nodos internos tienen un hijo. Sus niveles de rendimiento son similares a las listas enlazadas. Obtenga más información sobre los tipos de árbol binario.

Leer: Las seis estructuras de datos más utilizadas en R

Beneficios de los árboles binarios

1. Una forma ideal de ir con la forma jerárquica de almacenar datos
2. Reflejar las relaciones estructurales que existen en el conjunto de datos dado
3. Haga que la inserción y la eliminación sean más rápidas que las listas y matrices vinculadas
4. Una forma flexible de almacenar y mover datos
5. Se utilizan para almacenar tantos nodos como sea posible.
6. Son más rápidos que las listas enlazadas y más lentos que las matrices cuando se trata de acceder a los elementos.

Conclusión

En este blog, hemos discutido qué son los árboles binarios en las estructuras de datos, así como sus tipos, sus representaciones y sus beneficios. Los dos usos principales de los árboles son para buscar y almacenar datos y, por lo tanto, son parte integral del estudio de la ciencia de datos y sus campos relacionados.

Si tiene curiosidad por aprender sobre árboles binarios en estructuras de datos, ciencia de datos, consulte el Programa PG Ejecutivo en Ciencia de Datos de IIIT-B y upGrad, creado para profesionales que trabajan y ofrece más de 10 estudios de casos y proyectos, talleres prácticos prácticos, tutoría con expertos de la industria, 1 a 1 con mentores de la industria, más de 400 horas de aprendizaje y asistencia laboral con las mejores empresas.