Árbol binario completo – Part 1

Sabemos que un árbol es una estructura de datos no lineal. No tiene limitación en el número de niños. Un árbol binario tiene una limitación ya que cualquier Node del árbol tiene como máximo dos hijos: un hijo izquierdo y otro derecho.

¿Qué es un árbol binario completo?

Un árbol binario completo es un tipo especial de árbol binario en el que todos los niveles del árbol se llenan por completo, excepto los Nodes de nivel más bajo que se llenan desde la izquierda tanto como sea posible.

Alguna terminología del árbol binario completo:

• Raíz : Node en el que ningún borde proviene del padre. Ejemplo -Node A
• Hijo : el Node que tiene algún borde entrante se llama hijo. Ejemplo: los Nodes B, H son hijos de A y D respectivamente.
• Hermano : los Nodes que tienen el mismo padre son hermanos. Ejemplo: J, K son hermanos ya que tienen el mismo padre E.
• Grado de un Node : número de hijos de un padre en particular. Ejemplo: el grado de A es 2 y el grado de H es 1. El grado de L es 0.
• Nodes internos/externos : los Nodes hoja son Nodes externos y los Nodes no hoja son Nodes internos.
• Nivel : cuente los Nodes en una ruta para llegar a un Node de destino. Ejemplo: el nivel del Node H es 3 ya que los Nodes A, D y H forman la ruta.
• Altura : número de aristas para llegar al Node de destino, la raíz está a la altura 0. Ejemplo: la altura del Node E es 2, ya que tiene dos aristas desde la raíz.

Propiedades del árbol binario completo:

• Se dice que un árbol binario completo es un árbol binario apropiado donde todas las hojas tienen la misma profundidad.
• En un árbol binario completo, el número de Nodes en la profundidad d es 2 ^d . 
• En un árbol binario completo con n Nodes, la altura del árbol es log(n+1) .
• Todos los niveles excepto el último nivel están completamente llenos.

Árbol binario perfecto vs Árbol binario completo:

Un árbol binario de altura ‘h’ que tiene el número máximo de Nodes es un árbol binario  perfecto .
Para una altura h dada , el número máximo de Nodes es 2 ^h+1 -1 .

Un árbol binario completo de altura h es un árbol binario propio hasta la altura h-1 , y en el último nivel los elementos se almacenan en orden de izquierda a derecha.

Ejemplo 1:

La altura del árbol binario dado es 2 y el número máximo de Nodes en ese árbol es n= 2 ^h+1 -1 = 2 ²⁺¹ -1 = 2 ³ -1 = 7 .
Por lo tanto, podemos concluir que es un árbol binario perfecto .
Ahora, para un árbol binario completo, está lleno hasta la altura h-1, es decir; 1, y los elementos del último nivel se almacenan en orden de izquierda a derecha. Por lo tanto, también es un árbol binario completo. Aquí está la representación de los elementos cuando se almacenan en una array

En la array, todos los elementos se almacenan continuamente.

Ejemplo 2:

La altura del árbol binario dado es 2 y el número máximo de Nodes que debería haber allí es 2 ^h+1 – 1 = 2 ²⁺¹ – 1 = 2 ³ – 1 = 7 . 
Pero el número de Nodes en el árbol es 6 . Por lo tanto, no es un árbol binario perfecto .
Ahora, para un árbol binario completo, está lleno hasta la altura h-1, es decir; 1 y el elemento del último nivel se almacenan en orden de izquierda a derecha. Por lo tanto, este es un árbol binario completo . Almacene el elemento en una array y será como;

Ejemplo 3:

La altura del árbol binario es 2 y el número máximo de Nodes que puede haber allí es 7, pero solo hay 5 Nodes, por lo que no es un árbol binario perfecto .
En el caso de un árbol binario completo, vemos que en el último nivel los elementos no se llenan de izquierda a derecha. Así que no es un árbol binario completo .

Los elementos de la array no son continuos.

Árbol binario completo vs árbol binario completo:

Para un árbol binario completo, cada Node tiene 2 hijos o 0 hijos.

Ejemplo 1:

En el árbol binario dado, no hay ningún Node que tenga el grado 1, ya sea 2 o 0 hijos para cada Node, por lo tanto, es un árbol binario completo .

Para un árbol binario completo, los elementos se almacenan nivel por nivel y no desde el extremo izquierdo del último nivel. Por lo tanto, este no es un árbol binario completo . La representación de la array es:

Ejemplo 2:

En el árbol binario dado, no hay ningún Node que tenga el grado 1. Cada Node tiene un grado de 2 o 0. Por lo tanto, es un árbol binario completo .

Para un árbol binario completo, los elementos se almacenan nivel por nivel y se rellenan desde el extremo izquierdo del último nivel. Por lo tanto, este es un árbol binario completo . A continuación se muestra la representación de array del árbol:

Ejemplo 3:

En el árbol binario dado, el Node B tiene un grado 1 que viola la propiedad del árbol binario completo, por lo que no es un árbol binario completo.

Para un árbol binario completo, los elementos se almacenan nivel por nivel y se rellenan desde el extremo izquierdo del último nivel. Por lo tanto, este es un árbol binario completo . La representación de array del árbol binario es:

Ejemplo 4:
 

En el árbol binario dado, el Node C tiene un grado 1 que viola la propiedad de un árbol binario completo, por lo que no es un árbol binario completo.

Para un árbol binario completo, los elementos se almacenan nivel por nivel y se rellenan desde el extremo izquierdo del último nivel. Aquí el Node E viola la condición. Por lo tanto, este no es un árbol binario completo . 

Creación de Árbol Binario Completo:

Sabemos que un árbol binario completo es un árbol en el que excepto el último nivel (digamos l ) todos los demás niveles tienen ( 2l ) Nodes y los Nodes están alineados de izquierda a derecha.
Se puede representar mediante una array. Si el padre es el índice i, entonces el hijo izquierdo está en 2i+1 y el hijo derecho está en 2i+2 .

Algoritmo:

Para la creación de un árbol binario completo , necesitamos una estructura de datos de cola para realizar un seguimiento de los Nodes insertados.

Paso 1: inicialice la raíz con un nuevo Node cuando el árbol esté vacío.

Paso 2: si el árbol no está vacío, obtenga el elemento frontal 

• Si el elemento frontal no tiene un elemento secundario izquierdo, establezca el elemento secundario izquierdo en un nuevo Node
• Si el hijo derecho no está presente, configure el hijo derecho como un nuevo Node

Paso 3: si el Node tiene ambos elementos secundarios, sáquelo de la cola.

Paso 4: Poner en cola los nuevos datos.

Ilustración:

Considere la siguiente array:

1. El primer elemento será la raíz (valor en el índice = 0 )

A se toma como raíz

2. El siguiente elemento (en el índice = 1 ) quedará a la izquierda y el tercer elemento (índice = 2 ) será el hijo derecho de la raíz

B como hijo izquierdo y D como hijo derecho

3. el cuarto (índice = 3 ) y el quinto elemento (índice = 4 ) serán el hijo izquierdo y derecho del Node B

E y F son hijos izquierdo y derecho de B

4. El siguiente elemento (índice = 5 ) será hijo izquierdo del Node D

G se convierte en hijo izquierdo del Node D

Así es como se crea el árbol binario completo.

Implementación: para la implementación de la construcción de un árbol binario completo a partir del recorrido de orden de nivel se proporciona en esta publicación .

Aplicación del árbol binario completo:

• Ordenar montón
• Estructura de datos basada en clasificación de montón

Verifique si un árbol binario dado está completo o no: siga esta publicación para verificar si el árbol binario dado está completo o no.