Relación entre el número de Nodes y la altura del árbol binario

Requisito previo: estructura de datos del árbol binario 
En este artículo, discutiremos varios casos de relación entre el número de Nodes y la altura del árbol binario. Antes de comprender este artículo, debe tener una idea básica sobre los árboles binarios y sus propiedades. 
La altura del árbol binario es el camino más largo desde el Node raíz hasta cualquier Node hoja del árbol. Por ejemplo, la altura del árbol binario que se muestra en la Figura 1(b) es 2, ya que la ruta más larga desde el Node raíz al Node 2 es 2. Además, la altura del árbol binario que se muestra en la Figura 1(a) es 4. 

Árbol binario: 
en un árbol binario, un Node puede tener un máximo de dos hijos. 

Cálculo de la altura mínima y máxima a partir del número de Nodes: 
si hay n Nodes en el árbol binario, la altura máxima del árbol binario es n-1 y la altura mínima es floor(log2n) . 

Por ejemplo, el árbol binario sesgado a la izquierda que se muestra en la Figura 1(a) con 5 Nodes tiene una altura de 5-1 = 4 y el árbol binario que se muestra en la Figura 1(b) con 5 Nodes tiene una altura de piso (log25) = 2. 
 

Cálculo del número mínimo y máximo de Nodes desde la altura: 
si el árbol binario tiene una altura h , el número mínimo de Nodes es h+1 (en el caso de un árbol binario sesgado hacia la izquierda y hacia la derecha). 

Por ejemplo, el árbol binario que se muestra en la Figura 2(a) con altura 2 tiene 3 Nodes. 
Si el árbol binario tiene una altura h, el número máximo de Nodes será cuando todos los niveles estén completamente llenos. El número total de Nodes será 2^0 + 2^1 + …. 2^h = 2^(h+1)-1. 
Por ejemplo, el árbol binario que se muestra en la Figura 2(b) con altura 2 tiene 2^(2+1)-1 = 7 Nodes. 

Árbol de búsqueda binaria: 
en un árbol de búsqueda binaria, el hijo izquierdo de un Node tiene un valor menor que el padre y el hijo derecho tiene un valor mayor que el padre. 

Cálculo de la altura mínima y máxima a partir del número de Nodes: 
si hay n Nodes en un árbol de búsqueda binaria, la altura máxima del árbol de búsqueda binaria es n-1 y la altura mínima es ceil (log2n). 

Cálculo del número mínimo y máximo de Nodes a partir de la altura: 
si el árbol de búsqueda binario tiene una altura h , el número mínimo de Nodes es h+1 (en el caso de un árbol de búsqueda binario sesgado hacia la izquierda y hacia la derecha). 
Si el árbol de búsqueda binaria tiene una altura h , el número máximo de Nodes será cuando todos los niveles estén completamente llenos. El número total de Nodes será 2^0 + 2^1 + …. 2^h = 2^(h+1)-1. 

Todas las reglas en BST son las mismas que en el árbol binario y se pueden visualizar de la misma manera. 

Que-1. La altura de un árbol es la longitud del camino más largo desde la raíz hasta la hoja. El número máximo y mínimo de Nodes en un árbol binario de altura 5 son: 
(A) 63 y 6, respectivamente 
(B) 64 y 5, respectivamente 
(C) 32 y 6, respectivamente 
(D) 31 y 5, respectivamente 

Solución: De acuerdo con la fórmula discutida, 
número máximo de Nodes = 2^(h+1)-1 = 2^6-1 =63. 
número mínimo de Nodes = h+1 = 5+1 = 6. 

Que-2. ¿Cuál de las siguientes alturas no es posible para un árbol binario con 50 Nodes? 
(A) 4 
(B) 5 
(C) 6 
(D) Ninguno 

Solución: De acuerdo con la fórmula discutida, 
Altura mínima con 50 Nodes = piso (log250) = 5. Por lo tanto, la altura 4 no es posible.