¿Por qué un árbol binario completo de $n$ las hojas tienen $2n-1$ ¿Nodos?

Question

Un árbol binario completo se define como un árbol en el que cada nodo tiene $2$ o $0$ niños.

Diversas fuentes han descrito la relación entre los nodos y las hojas como $2n-1$ donde $n$ es el número de hojas. Sin embargo, no he podido encontrar una descripción de cómo esta relación fue derivada.

Answer 1

Cualquier árbol binario completo puede verse como la estructura de un torneo de eliminación simple con $n$ equipos correspondientes a las hojas. En cada juego que no sea una hoja, el perdedor se va a casa y el ganador pasa a la siguiente ronda. Hay un campeón final, que gana el juego de raíz, por lo que debe haber $(n-1)$ los nodos no-hoja ya que todos los demás equipos pierden exactamente una vez. Por lo tanto, $n + (n-1) = 2n-1$ nodos en conjunto.

Answer 2

Un árbol binario perfecto (completo y pleno) siempre tiene $2^m$ hojas para algunos $m$ . ¿Cuántos nodos tendrá? Bueno, tendrá $1$ raíz, y $2$ hijos de la raíz, y $4$ total de hijos de esos hijos, y así sucesivamente, hasta el $2^m$ hojas. Así que habrá $$ 1 + 2 + 4 + 8 + \cdots + 2^m = \sum_{i = 0}^m 2^i $$ nodos totales en un árbol binario perfecto con $2^m$ hojas. Ahora hay una fórmula estándar que $$ \sum_{i = 0}^m 2^i = 2^{m+1} - 1. $$ Si empezamos diciendo que $n = 2^m$ es el número de hojas, entonces $2^{m+1} -1$ nodos es lo mismo que $2\cdot 2^m - 1 = 2n - 1$ nodos, que es la fórmula solicitada en la pregunta.

Answer 3

Bueno, empieza con el nodo padre. Si sólo tienes un nodo, que es una hoja, y $2(1) - 1 = 1$ . Esta ecuación implica que cada vez que se añada una hoja más, el número total de nodos aumentará en 2.

Ahora añadir dos hijos significa quitar una hoja (el padre era una hoja) y añadir dos nuevas hojas, lo que da un total de una nueva hoja. Estás añadiendo dos nodos de una hoja extra, así que resulta que esta ecuación funciona.

Answer 4

Un gráfico sigue una propiedad básica

$$\text{Sum of degrees of all nodes }= 2 \times\text{number of edges}$$

Ahora bien, como se trata de un árbol binario completo se deduce:

1. Las hojas son los únicos nodos con grado $1$ que haya $n$ de ellos
2. La raíz es el único nodo con grado $2$ , hay $1$ raíz
3. Todos los nodos internos tienen grado $3$ que haya $x$ de ellos

Dado que el árbol es también un gráfico, utilizando la propiedad básica se obtiene

$$n\times 1 + 1\times2 + x\times3 = 2 \times\text{number of edges}$$

Para calcular el número de aristas:

Considera que cada nodo, excepto el nodo raíz, tiene exactamente una arista padre y cada arista es alguna arista padre. Así que el número total de aristas es el número de aristas padre que es igual al número de nodos que tienen un padre, es decir $n+x$ (el nodo raíz no tiene padre)

Por lo tanto, la ecuación se convierte en $$n + 2 + 3x = 2\times(n+x)$$ De donde \begin{align}x = n-2\\ \text{Total number of nodes} &= n + 1 + x &+1\text{ is for root node}\\ &= n + 1 + n-2 = 2n-1\end{align}

Answer 5

Intenta eliminar un nodo hoja... tienes que eliminar la arista que lo soporta, y luego fusionar las dos aristas adyacentes a esa arista (eliminando así un segundo nodo) para volver a tener un árbol binario completo. Así que el número de nodos y aristas es de la forma $2n + k$ . El árbol trivial tiene $1$ hoja y ninguna arista y un nodo... por lo que el número de nodos debe ser siempre $2n-1$ y el número de aristas debe ser siempre $2n-2$ .