5 tipos de árboles binarios en la estructura de datos explicados

Un árbol binario es una estructura de datos de árbol no lineal que contiene cada nodo con un máximo de 2 hijos. El nombre binario sugiere el número 2, por lo que cualquier árbol binario puede tener un hijo izquierdo y derecho.

Un puntero representa un árbol binario en el nodo superior, generalmente conocido como la raíz del árbol. Cada nodo en un árbol binario contiene datos, un puntero al hijo izquierdo y un puntero al hijo derecho. Los punteros se utilizan para implementar un árbol binario. El puntero raíz denota el primer nodo en el árbol. Para crear un árbol binario, primero debe crear un nodo.

Después de familiarizarse conlo que es un árbol binario en la estructura de datos , también necesita conocer las operaciones básicas realizadas en un árbol binario.Puede realizar funciones como insertar un elemento, eliminar un elemento, buscar un elemento y recorrer el árbol binario.

Cualquierárbol binario en la estructura de datos se usa de dos maneras diferentes en computación.En primer lugar, se utilizan para acceder a los nodos en función de etiquetas o valores específicos vinculados con cada nodo. En segundo lugar, se utilizan como representaciones de datos con una estructura ramificada relevante.

Antes de pasar por variostipos de árboles binarios , primero familiaricémonos con la terminología utilizada en un árbol binario.

Nodo: contiene un valor de datos en un árbol binario.

Raíz: el nodo superior de cualquier árbol binario se denomina raíz de un árbol.

Tamaño: Denota el número de nodos en un árbol binario.

Nodo padre: Un nodo en un árbol binario con un hijo.

Nodo hijo: es un nodo que se origina a partir de un nodo padre que se aleja de la raíz del árbol binario.

Nodo interno: Es un nodo con al menos un hijo en un árbol binario.

Nodo hoja: Es un nodo sin hijo.Es alternativamente un nodo externo.

Profundidad de un árbol de nodos: Se calcula en el contexto de un nodo en particular.Se conoce como el número de aristas desde un nodo particular hasta la raíz.

Longitud del camino interno de un árbol: Se refiere a la suma de los niveles de cada nodo interno en un árbol binario.

Longitud del camino externo de un árbol: Se define como la suma de los niveles de cada nodo externo en un árbol binario.

Altura del nodo en un árbol: Es el número de aristas desde un nodo específico hasta el nodo hoja más profundo del árbol binario.La altura de la raíz siempre será mayor que la de otros nodos en el árbol binario.

Ahora veamos los detalles de 5tipos de árboles binarios.

Tipos de árbol binario

1. Árbol binario completo

Esteárbol binario en la estructura de datos también se conoce con los nombres de árbol binario propio y árbol binario estricto.Es uno de lostipos más fundamentales de árbol binario en la estructura de datos.Un árbol binario completo se define como un árbol binario en el que cada nodo debe tener dos o ningún hijo.

Alternativamente, se caracteriza como un árbol binario en el que cada nodo consta de dos hijos, excepto los nodos hoja. Los nodos en los que se almacena la dirección del nodo raíz se denominan nodos hijos de la raíz. Esos nodos desprovistos de hijos se denominan nodos hoja.

Debe recorrer todos los nodos para verificar si un árbol es un árbol binario. El código devolverá "Falso" si algún nodo tiene un hijo. Devolverá "Verdadero" si todos los nodos tienen 0 o 2 hijos.

Estas son las propiedades de un árbol binario completo:

• El número de nodos hoja es igual al número de nodos internos + 1. Por ejemplo, si el número de nodos internos es 4, el número de nodos hoja es igual a 5.
• El número máximo de nodos y el número de nodos en un árbol binario son iguales. Se representa como 2h+1 -1.
• El número mínimo de nodos en un árbol binario completo es 2h-1.
• La altura mínima de un árbol binario completo es log 2 (n+1) – 1.
• La altura máxima de un árbol binario completo es h = (n+1)/2.

2. Árbol binario perfecto

Un árbol binario perfecto es uno de esostipos de árboles binarios en los que cada nodo debe tener 0 o 2 hijos, y el nivel de cada nodo hoja debe ser el mismo.En otras palabras, los árboles binarios perfectosen la estructura de datos se definen como aquellos árboles en los que todos los nodos interiores poseen dos ramas y aquellos nodos sin ramas (nodos hoja) existen en el mismo nivel.

En este contexto, el nivel de un nodo es la distancia o altura desde el nodo raíz. Puede considerar un árbol binario perfecto como un árbol binario completo en el que el último nivel también está completamente ocupado.

Aprendacursos de ciencia de datosen línea de las mejores universidades del mundo.Obtenga programas Executive PG, programas de certificados avanzados o programas de maestría para acelerar su carrera.

3. Árbol binario completo

Un árbol binario completo es uno de esos tipos de árboles binarios en la estructura de datos en los que todos los niveles del árbol están completamente llenos.El último nivel del árbol binario puede o no estar completamente lleno. Sin embargo, cada nodo debe ubicarse en la posición más a la izquierda en el último nivel del nodo. Los nodos deben incluirse desde la izquierda.

Son uno de lostipos esenciales de árboles binarios porque ofrecen la mejor relación entre el número de nodos y la altura de un árbol.

Estas son las propiedades clave de un árbol binario completo:

• El número máximo de nodos es 2 h+1 – 1.
• El número mínimo de nodos es de 2 h .
• La altura mínima es log 2 (n+1) – 1.

4. Árbol binario equilibrado

En árboles binarios balanceados, la altura de un árbol es log 2 del número total de nodos. Suponga que la altura del árbol es h y el número total de nodos del árbol es n. La ecuación para calcular la altura es h = log(n). La diferencia máxima de altura entre un subárbol derecho y un subárbol izquierdo debe ser "1".

La diferencia puede tener otros valores como 0 y -1. Estos tipos de árboles binarios también se denominan árboles AVL.Uno de los ejemplos más conocidos de árboles binarios equilibrados es el árbol rojo-negro.

Puede implementar el siguiente código para ejecutar un árbol binario equilibrado.

Nodo de clase privada {

valor int privado;

Nodo privado a la izquierda;

derecho de nodo privado;

}

public boolean isBalanced(Nodo n) {

si (altura del árbol balanceado (n) > -1)

devolver verdadero;

falso retorno;

}

público int altura del árbol equilibrado (nodo n) {

si (n == nulo)

devolver 0;

int h1 = balanceartreeHeight(n.derecha);

int h2 = balanceartreeHeight(n.left);

si (h1 == -1 || h2 == -1)

devolver -1;

si (Math.abs(h1 – h2) > 1)

devolver -1;

si (h1 > h2)

devuelve h1 + 1;

devuelve h2 + 1;

}

Consulte nuestros programas de ciencia de datos de EE. UU.

5. Árbol binario degenerado

Un árbol binario degenerado es uno de lostipos de árbol binario de búsqueda menos utilizados .Es un árbol binario en el que cada nodo tiene un solo hijo, es decir, un hijo izquierdo o derecho. Ningún nodo debe tener hijos tanto izquierdo como derecho.

Lea nuestros artículos populares de ciencia de datos de EE. UU.

Conclusión

Es esencial comprenderqué es un árbol binario en la estructura de datos si desea usarlo para varias aplicaciones.La implementación de diferentes funciones en árboles binarios puede ayudarlo a organizar y almacenar datos de manera eficiente.

El estudio de múltiples tipos de árboles binarios lo ayuda a realizar operaciones de manera más efectiva en la complejidad del tiempo. Los fundamentos de la ciencia de datos, incluidala estructura de datos de árbol binario, lo ayudan a comenzar su viaje de ciencia de datos fácilmente.Posteriormente, puede trabajar en proyectos avanzados de ciencia de datos para mejorar sus habilidades y su cartera.

Comience con su viaje de aprendizaje automático en upGrad

Si desea aprender Data Science, puede seguir el programa de Maestría en Ciencias en Data Science de upGrad . Este curso de 24 meses imparte habilidades como Python, implementar modelos de ML, procesamiento de BD con Spark, análisis predictivo y estadísticas, y modelos de ML supervisados ​​y no supervisados. El curso es adecuado para gerentes ambiciosos, graduados de MBA, ingenieros y profesionales en varios dominios.

Completar este curso lo ayudará a trabajar como ingeniero de datos, analista de big data, ingeniero de aprendizaje automático y científico de datos.