Árbol binario completo: un árbol binario es un árbol binario completo si todos los niveles están completamente llenos, excepto posiblemente el último nivel y el último nivel tiene todas las teclas lo más a la izquierda posible
Los siguientes son ejemplos de árboles binarios completos
18 años
/ \
15 30
/ \ / \
40 50 100 40
- ¿Cuál sería un ejemplo de un problema de programación que sería difícil si no fuera posible sin el uso de array?
- ¿Qué son los treaps con claves implícitas?
- ¿Es así como se elimina de un árbol de búsqueda binario cuando un padre tiene dos subárboles?
- Cómo usar la primera búsqueda en profundidad en un laberinto
- ¿Qué es una explicación intuitiva de MapReduce?
18 años
/ \
15 30
/ \ / \
40 50 100 40
/ \ /
8 7 9
Suponga que la altura del árbol = h. entonces # niveles (L) = h + 1.
entonces el máximo de nodos posibles en el árbol binario completo es cuando todos los niveles están completamente llenos
en el nivel rrot, es decir, el nivel 1 #nodes = 1 = 2 ^ 0
en el nivel 2 #nodes = 2 = 2 ^ 1
en el nivel 3 #nodes = 4 = 2 ^ 2
en el nivel 4 #nodes = 8 = 2 ^ 3
en el nivel 5 #nodes = 16 = 2 ^ 4
.
.
.
.
.
en el nivel h #nodes = 2 ^ (h-1)
en el nivel h + 1 #nodos = 2 ^ h
total = 2 ^ 0 + 2 ^ 1 + 2 ^ 2 + 2 ^ 3 + ……… + 2 ^ (h-1) + 2 ^ h
====> 1 + 2 + 4 + 8 + ……………………………………. + 2 ^ h
por lo tanto, el número dado de nodos en el árbol binario completo debe ser como máximo = total
es decir, n <= total
n <= 1 + 2 + 4 + 8 + ……………………………………. + 2 ^ h
n <= 2 ^ (h + 1)
n <= 2 ^ L (becoz, L = h + 1)
log2 (n) <= L
L> = log2 (n)
L = techo (log2 (n))
