El número máximo de nodos en un árbol binario de profundidad $k$ es $2^{k}-1$ , $k \geq1$ .

Question

Me confunde esta afirmación

El número máximo de nodos en un árbol binario de profundidad $k$ es $2^k-1$ , $k \geq1$ .

¿Cómo es posible que esto sea cierto? Digamos que tengo el siguiente árbol

    1
   / \
  2   3

Aquí la profundidad del árbol es 1. Por lo tanto, según la fórmula, será $2^1-1 = 1$ . Pero tenemos $3$ nodos aquí. Estoy realmente confundido con esto de la profundidad.

¿Alguna aclaración?

Answer 1

Debe ser $2^{k+1}-1$ . La prueba es la siguiente: En un árbol binario completo, tienes 1 raíz, 2 hijos de esa raíz, 4 nietos, 8 nietos y así sucesivamente. Por tanto, el número total de nodos es la suma de las series geométricas:

$$1+2+4+8+\dots +2^{k} = \frac{2^{k+1}-1}{2-1}=2^{k+1}-1$$

donde $k$ es la profundidad (es decir, para $k=0$ tenemos 1 nodo).

Answer 2

Te respondes a ti mismo en la pregunta.

El número de nodos es igual a $2^{k}-1$ donde $k≥1$ . Así que el nivel mínimo es 1, no 0.

Por lo tanto, el ejemplo es correcto porque tiene 2 niveles de profundidad: $2^{2}-1 = 3$

Answer 3

Un árbol binario podría hacerse recibiendo mercancías, y trabajando hacia abajo hasta encontrar una ranura vacía para ella.

El primer elemento se llama "1". El segundo objeto, suponiendo que sea mayor que el primero, se llama "11". El tercer objeto que entra se llama, digamos, "110", lo que significa que es mayor que "1", pero menor que "11". A medida que llegan objetos, adquieren direcciones como ésta. El siguiente objeto podría ser más pequeño que "1", por lo que es "10".

La profundidad del árbol es simplemente la cadena más larga registrada, por lo que la profundidad del árbol del párrafo anterior es 3 (es decir, los dígitos de "110").

El total de nombres posibles, es entonces los números binarios de '1' a '111', donde '111' es la longitud del nombre más largo (o profundidad). Esto equivale a $2^d-1$ donde $d$ es la profundidad. En un árbol real, no todas las partes están ocupadas, por lo que la población es inferior al máximo que podría contener.

Answer 4

Suponemos que la raíz de un árbol binario está en el nivel 1, por lo que en su árbol mencionado, la profundidad es 2 no 1, por lo que (2 a la potencia 2 ) - 1 = 3 nodos.

Answer 5

De acuerdo con su fórmula. la profundidad no es igual a 1 aquí. profundidad comienza a partir de 1 en adelante. y el nivel del árbol comienza a partir de 0. Así que aquí la profundidad es 2. tomas 2^2 - 1 = 3 nodos. aquí k = 2.

En algunos libros encontrarás la profundidad a partir de 1 y el nivel del árbol a partir de 0 y en otros libros lo encontrarás al revés. Pero de donde has sacado esta fórmula aquí la profundidad empieza desde 1 (es decir, la profundidad mínima puede ser 1)