¿Por qué la altura mínima de un árbol binario

En mi clase de Java, estamos aprendiendo sobre la complejidad de diferentes tipos de colecciones.

Pronto hablaremos de árboles binarios, sobre los que he estado leyendo. El libro establece que la altura mínima de un árbol binario es , pero no ofrece más explicaciones.$\log_2(n+1) - 1$

¿Alguien puede explicar por qué?

Un árbol binario tiene 1 o 2 hijos en nodos no hoja y 0 nodos en nodos hoja. Deje que haya nodos en un árbol y tenemos que organizarlos de tal manera que todavía formen un árbol binario válido.$n$

Sin probar, estoy afirmando que para maximizar la altura, los nodos dados deben estar dispuestos linealmente, es decir, cada nodo no hoja debe tener solo un hijo:

                              O 1
                              |
                              O 2
                              |
                              O 3
                              |
                              O 4
                              |
                              O 5
                              |
                              O 6
                              |
                              O 7
                              |
                              O 8

Aquí, la fórmula para calcular la relación de altura en términos de número de nodos es sencilla. Si es la altura del árbol, entonces h = n - 1 .$h$$h = n-1$

Ahora, si intentamos construir un árbol binario de nodos con altura mínima (siempre reducible a un árbol binario completo), tenemos que empaquetar tantos nodos como sea posible en los niveles superiores, antes de pasar al siguiente nivel. Entonces, el árbol toma la forma del siguiente árbol:$n$

                              O
                              |1
                              |
                       O------+-----O
                       |2           |3
                       |            |
                   O---+---O    O---+----O
                   |4      |5    6        7
                   |       |
               O---+--O    O
                8      9    10

Comencemos con un caso particular, .$n = 2^m - 1$

Sabemos que,

$$2^0 + 2^1 + 2^2 + ... + 2^{m-1} = 2^m - 1$$

Además, es fácil demostrar que, un nivel puede tener como máximo 2 i nodos en ella.$i$$2^i$

Usando este resultado en la suma anterior, encontramos que para cada nivel , de 0 a m , existe un término correspondiente 2 i - 1 en la expansión de 2 m - 1 . Esto implica que un árbol binario completo de 2 m - 1 nodos está completamente lleno y tiene una altura, h ( 2 m - 1 ) = m - 1 , donde h ( n ) = altura de un árbol binario completo con n nodos.$i$$0$$m$$2^{i-1}$$2^m - 1$$2^m - 1$$h(2^m-1) = m-1$$h(n) =$$n$

Usando este resultado, , ya que el árbol con 2 m - 1 nodos está completamente lleno y, por lo tanto, un árbol con ( 2 m - 1 ) + 1 = 2 m nodos tiene que acomodar el nodo adicional en el siguiente nivel m , aumentando la altura en 1 de m - 1 a m .$h(2^m) = m$$2^m-1$$(2^m-1)+1 = 2^m$$m$$m-1$$m$

Hasta ahora hemos demostrado, h ( 2 m + 1 ) = m + 1 así como, h ( 2 m + 1 - 1 ) =

$$h(2^m) = m,$$ $$h(2^{m+1}) = m+1$$ $$h(2^{m+1} -1) = m$$

Por lo tanto, m ≤ h ( n ) < m + $\forall n \in \mathbb{Z}, 2^m \leq n < 2^{m+1}$

$$m \leq h(n) < m+1$$

Pero, tomando log (base 2) en ambos lados, m = ⌊ log 2 ( n )

$$m \leq \log_2(n) < m+1$$ $$m = \lfloor \log_2(n) \rfloor$$

Por lo tanto, h ( n ) = m = ⌊ log 2 ( n ) $\forall n, n \in [2^m, 2^{m+1})$

$$h(n) = m = \lfloor \log_2(n) \rfloor$$

Y podemos generalizar este resultado usando la inducción.$\forall n \in \mathbb{Z}$

$\log_2(n+1)-1$$n$$\log_2(n)$$n$

$n$

$4$$1+1\cdot2+1\cdot2\cdot2+1\cdot2\cdot2\cdot2$$3$

$$\text{nodes}=1+2+2^{2}+2^{3}+...+2^{\text{depth}}=\sum_{k=0}^{\text{depth}} 2^{k}=\frac{1-2^{\text{depth}+1}}{1-2}.$$

$$\text{nodes}=2^{\text{depth}+1}-1,$$ $$\begin{eqnarray} \text{nodes}+1&=&2^{\text{depth}+1}\\ \log_{2}(\text{nodes}+1)&=&\log_{2}(2^{\text{depth}+1})=\text{depth}+1\\ \log_{2}(\text{nodes}+1)-1&=&\text{depth}. \end{eqnarray}$$

Para mantener la altura mínima, es fácil ver que necesitamos completar todos los niveles, excepto posiblemente el último. ¿Por qué? de lo contrario, podríamos subir los nodos del último nivel a espacios vacíos en los niveles superiores.

Ahora, imagine que tengo un número no especificado de frijoles y le doy un grano a la vez y le pido que construya un árbol binario con la altura mínima posible. Puede que me quede sin frijoles cuando llenes el último nivel por completo o al menos tengas un frijol en el último nivel. Digamos que tienes la altura de tu árbol h en este punto.

$$2^{0}+2^{1}+2^{2}+2^{3}+\dots+2^{h}=2^{h+1}-1 \leq n\,.$$ $$h = \lg(n+1)-1\,.$$