Altura del árbol binario

Question

Necesito una fórmula general para calcular la altura mínima del árbol binario y la altura máxima del árbol binario. (no es el árbol de búsqueda binario)

Answer 1

Piensa cómo puede cambiar la estructura del árbol.

Por ejemplo, si el árbol está completamente desequilibrado, este es el peor de los casos: cada nodo tendrá exactamente un hijo. En el mejor de los casos, el árbol se completa de forma equilibrada y cada nodo tiene dos hijos.

Dado que suena como tarea, la dejo allí.

Answer 2

La altura máxima es n y la altura min (es decir, un árbol binario perfecto) es el (base 2 log (n + 1)) - 1

Answer 3

Si tiene N elementos, la altura mínima de un binario el árbol será log2 (N) +1.

Para un árbol binario completo, la altura máxima será N/2.

Para un árbol binario no completa, la altura máxima será de N.

Answer 4

En primer lugar puede haber alguna diferencia en cuanto a cómo la informática calcula la altura de un árbol, frente a la altura manera se determina en discreta matemáticas (teoría de grafos), esto puede ser debido a la existencia de datos en cualquier nodo (o vertice), mientras que en matemáticas, es un enfoque teórico puro.

Así que tal vez sea mejor que aclare cuál necesita.

En matemáticas discretas, los árboles se clasifican como árboles m-ary, por lo que un árbol bin-ary es un árbol 2-aria. También a cualquier altura dada, puede haber a lo sumo 2^h = L (hojas). Esto es importante de notar, ya que confirma que la raíz está en la altura cero, por lo tanto 2^0 = 1 hoja ... 1 vértice ... la raíz.

n vértices Así dadas, la altura de un árbol está dada por la fórmula n = 2^(h + 1) - 1

Puesto que usted está buscando h, usted tiene que tomar el log2 de ambos lados de la fórmula n = 2^(h + 1) - 1

Para un árbol binario completo, la altura máxima es log2 (n + 1) = log2 (2^(h + 1)) esta es igual al techo (log2 (n + 1) - 1) = h

Para un árbol binario no completo, la altura máxima = (n - 1) por lo tanto, si tiene n vértices, la raíz debe restarse para obtener la altura máxima, debido a la fórmula anterior (2^h = L)

Para alturas mínimas, extrapole de las reglas anteriores.

Answer 5

La altura mínima es h = techo (log (n + 1)/log (2) -1) para cualquier árbol binario.

Answer 6

Si una raíz puede tener cualquier número de hojas de hasta 2 (0,1,2) entonces:

• La altura máxima es n-1. Este es el caso cuando su árbol tiene una sola hoja. Ningún nodo tiene más de una rama.
• La altura mínima es [log2 (n)] donde [x] es la parte entera de x.

Para obtener una altura mínima, cada raíz debe tener tantas ramas como sea posible. En este caso, notará que para n = 1, height = 0; para n = 2 a n = 3, altura = 1; para n = 4 a n = 7, altura = 2; para n = 8 para n = 15, altura = 3 etc.

este modo se puede observar que, para cada n, existe ap tal que:

2^p < = n < 2^(p + 1) yp = altura, por lo que height = [log2 (n)]

Answer 7

N - número de nodos.
H - altura del árbol binario.

completa Binary Tree:
Luego, con la altura H N sería estar entre:

2^H <= N <= (2^(H+1) - 1) 

Por lo tanto, la solución de esta desigualdad; obtenemos:

H <= lg(N) and H >= (lg(N+1) - 1) 

De ahí que por fin tenemos:

H = floor(lg(N)) = ceil((lg(N+1) - 1)) //as H is integer 

(lg: log de base 2)

Binary Tree (no necesariamente completar):

Max height = N; 

Min Height = floor(lg(N)) = ceil((lg(N+1) - 1)) 

Obtenemos altura mínima cuando se completa el árbol binario.

Answer 8

Con n-nodes, la altura máxima posible es floor(log(n)) = ceil (log(n+1))-1.

Con n-nodes, la altura mínima posible es n-1.