Árbol binario perfecto – Part 1

¿Qué es un árbol binario perfecto?

Un árbol binario perfecto es un árbol binario en el que cada uno de los Nodes internos tiene exactamente dos Nodes secundarios y todos los Nodes hoja están situados en el mismo nivel del árbol.

En otras palabras, se puede decir que cada nivel del árbol está completamente ocupado por los Nodes.

Ejemplos de árbol binario perfecto: 

Un árbol con solo el Node raíz también es un árbol binario perfecto.     

El siguiente árbol no es un árbol binario perfecto porque el último nivel del árbol no está completamente lleno.

Propiedades de un árbol binario perfecto:

• Grado: El grado de un Node de un árbol se define como el número de hijos de ese Node. Todos los Nodes internos tienen un grado de 2. Los Nodes hoja de un árbol binario perfecto tienen un grado de 0.
• Número de Nodes hoja: si la altura del árbol binario perfecto es h , entonces el número de Nodes hoja será 2 ^h porque el último nivel está completamente lleno.
• Profundidad de un Node: La profundidad promedio de un Node en un árbol binario perfecto es Θ(ln(n)) .
• Relación entre Nodes hoja y Nodes no hoja: Nº de Nodes hoja = Nº de Nodes no hoja +1.
• Número total de Nodes: Un árbol de altura h tiene un total de Nodes = 2 ^h+1 – 1 . Cada Node del árbol está lleno. Entonces, el número total de Nodes se puede calcular como 2 ⁰ + 2 ¹ + . . . + ^2h = ^2h+1 – 1.
• Altura del árbol: La altura de un árbol binario perfecto con N número de Nodes = log(N + 1) – 1 = Θ(ln(n)) . Esto se puede calcular utilizando la relación que se muestra al calcular el número total de Nodes en un árbol binario perfecto.

Compruebe si un árbol es un árbol binario perfecto o no:

• Encuentre la profundidad de cualquier Node (en el árbol de abajo encontramos la profundidad del Node más a la izquierda). Sea esta profundidad d .
• Ahora recorra recursivamente el árbol y verifique las siguientes dos condiciones.
  • Cada Node interno debe tener ambos hijos no vacíos.
  • Todas las hojas están a la profundidad d

Para obtener más información al respecto, consulte el artículo artículo: Comprobar si un árbol binario dado es perfecto o no