5 tipos de árboles binarios explicados [con ilustraciones]

En informática, varias estructuras de datos ayudan a organizar los datos en diferentes formas. Entre ellos, los árboles son estructuras de datos abstractas ampliamente utilizadas que simulan una estructura de árbol jerárquica. Un árbol generalmente tiene un valor raíz y subárboles que están formados por los nodos secundarios de sus nodos principales. Los árboles son estructuras de datos no lineales.

Una estructura de datos de árbol general no tiene limitación en la cantidad de nodos secundarios que puede contener. Sin embargo, este no es el caso con un árbol binario. Este artículo aprenderá sobre una estructura de datos de árbol específica: árbol binario y tipos de árbol binario .

¿Qué es la estructura de datos de árbol binario?

Un árbol binario es una estructura de datos no lineal de tipo árbol con un máximo de dos hijos para cada padre. Cada nodo en un árbol binario tiene una referencia izquierda y derecha junto con el elemento de datos. El nodo en la parte superior de la jerarquía de un árbol se denomina nodo raíz. Los nodos que contienen otros subnodos son los nodos principales.

Un nodo padre tiene dos nodos hijos: el hijo izquierdo y el hijo derecho. Hashing, enrutamiento de datos para el tráfico de red, compresión de datos, preparación de montones binarios y árboles de búsqueda binarios son algunas de las aplicaciones que utilizan un árbol binario.

Terminologías asociadas con árboles binarios y tipos de árboles binarios

• Nodo: Representa un punto de terminación en un árbol.
• Raíz: el nodo superior de un árbol.
• Padre: cada nodo (aparte de la raíz) en un árbol que tiene al menos un subnodo propio se llama nodo padre.
• Niño: Un nodo que proviene directamente de un nodo principal cuando se aleja de la raíz es el nodo secundario.
• Nodo hoja: Estos son nodos externos. Son los nodos que no tienen hijo.
• Nodo interno: como sugiere el nombre, estos son nodos internos con al menos un hijo.
• Profundidad de un árbol: el número de aristas desde el nodo del árbol hasta la raíz.
• Altura de un Árbol: Es el número de aristas desde el nudo hasta la hoja más profunda. La altura del árbol también se considera la altura de la raíz.

Como ahora está familiarizado con la terminología asociada con el árbol binario y los tipos de árbol binario, es hora de comprender los componentes del árbol binario . Consulte nuestros cursos de ciencia de datos para aprender en profundidad sobre la estructura y los componentes binarios.

Componentes del árbol binario

Hay tres componentes de árbol binario . Cada nodo de árbol binario tiene estos tres componentes asociados. Se convierte en un concepto esencial para que los programadores entiendan estos tres componentes del árbol binario:

1. elemento de datos
2. Puntero al subárbol izquierdo
3. Puntero al subárbol derecho

Fuente

Estos tres componentes del árbol binario representan un nodo. Los datos residen en el medio. El puntero izquierdo apunta al nodo secundario, formando el subárbol izquierdo. El puntero derecho apunta al nodo secundario a su derecha, creando el subárbol derecho.

Leer: Principales preguntas de cálculo aproximado y métodos informativos para la ciencia de datos

Tipos de árboles binarios

Hay varios tipos de árboles binarios , y cada uno de estos tipos de árboles binarios tiene características únicas. Aquí están cada uno de los tipos de árboles binarios en detalle:

1. Árbol binario completo

Es un tipo especial de árbol binario que tiene cero hijos o dos hijos. Significa que todos los nodos en ese árbol binario deben tener dos nodos secundarios de su nodo principal o el nodo principal es en sí mismo el nodo hoja o el nodo externo.

En otras palabras, un árbol binario completo es un árbol binario único donde cada nodo excepto el nodo externo tiene dos hijos. Cuando tiene un solo hijo, dicho árbol binario no será un árbol binario completo. Aquí, la cantidad de nodos hoja es igual al número de nodos internos más uno. La ecuación es como L=I+1, donde L es el número de nodos hoja e I es el número de nodos internos.

Aquí está la estructura de un árbol binario completo:

2. Árbol binario completo

Un árbol binario completo es otro tipo específico de árbol binario en el que todos los niveles del árbol están completamente llenos de nodos, excepto el nivel más bajo del árbol. Además, en el último o el nivel más bajo de este árbol binario, cada nodo posiblemente debería residir en el lado izquierdo. Aquí está la estructura de un árbol binario completo:

3. Árbol binario perfecto

Se dice que un árbol binario es "perfecto" si todos los nodos internos tienen estrictamente dos hijos, y cada nodo externo u hoja está al mismo nivel o profundidad dentro de un árbol. Un árbol binario perfecto con altura 'h' tiene 2h – 1 nodo. Aquí está la estructura de un árbol binario perfecto:

4. Árbol binario equilibrado

Se dice que un árbol binario está 'equilibrado' si la altura del árbol es O(logN), donde 'N' es el número de nodos. En un árbol binario equilibrado, la altura de los subárboles izquierdo y derecho de cada nodo debe variar como máximo en uno. Un árbol AVL y un árbol rojo-negro son algunos ejemplos comunes de estructura de datos que pueden generar un árbol de búsqueda binario equilibrado. Aquí hay un ejemplo de un árbol binario balanceado:

5. Árbol binario degenerado

Se dice que un árbol binario es un árbol binario degenerado o un árbol binario patológico si cada nodo interno tiene un solo hijo. Dichos árboles son similares a una lista enlazada en cuanto al rendimiento. Aquí hay un ejemplo de un árbol binario degenerado:

Beneficios de un árbol binario

• La operación de búsqueda en un árbol binario es más rápida en comparación con otros árboles
• Solo dos recorridos son suficientes para proporcionar los elementos en orden ordenado
• Es fácil recoger los elementos máximos y mínimos.
• El recorrido de gráficos también usa árboles binarios
• Es posible convertir diferentes expresiones de postfijo y prefijo usando árboles binarios

Lea también: Árboles de decisión en el aprendizaje automático: funciones, clasificación, pros y contras

Conclusión

El árbol binario es uno de los árboles más utilizados en la estructura de datos. Cada uno de los tipos de árboles binarios tiene sus características únicas. Estas estructuras de datos tienen requisitos específicos en informática aplicada. Esperamos que este artículo sobre tipos de árboles binarios haya sido útil. upGrad ofrece varios cursos en ciencia de datos, aprendizaje automático, big data y más.

Si tiene curiosidad por aprender sobre ciencia de datos, consulte el Programa ejecutivo PG 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, tutoría con expertos de la industria, 1 -on-1 con mentores de la industria, más de 400 horas de aprendizaje y asistencia laboral con las mejores empresas.