Algoritmos y Estructuras de Datos (VJ1215)

La altura máxima sería n - 1. Correspondería a un árbol en el que n - 1 nodos tienen un solo hijo.

La altura mínima correspondería a un árbol en el que todos los nodos, excepto los que estuviesen a la máxima profundidad, tuviesen dos hijos. Su valor exacto se obtiene calculando el logaritmo en base 2 de n y truncando el resultado a 0 digitos decimales. Eso lo podemos expresar como floor(log₂(n)).

Por ejemplo, para cualquier n tal que 16 ≤ n < 32, se cumple 4 ≤ log₂(n) < 5 y la altura mínima sería floor(log₂(n)) = 4. Eso correspondería a un árbol que tenga un nodo a profundidad 0, dos a profundidad 1, cuatro a profundidad 2, ocho a profundidad 3 (hasta ahí, eso sumaría 15 nodos) y el resto a profundidad 4. Todos los nodos a profundidad entre 0 y 3 tendrían dos hijos y los nodos a profundidad 4 serían las hojas.