Árbol binario | Conjunto 2 (Propiedades)

Hemos discutido la Introducción al Árbol Binario en el set 1 . En esta publicación, se analizan las propiedades de un árbol binario. 

1) El número máximo de Nodes en el nivel ‘l’ de un árbol binario es 2 ^l . 
Aquí el nivel es el número de Nodes en la ruta desde la raíz hasta el Node (incluyendo la raíz y el Node). El nivel de la raíz es 0. 
Esto se puede probar por inducción. 
Para raíz, l = 0, número de Nodes = 2 ⁰ = 1 
Suponga que el número máximo de Nodes en el nivel ‘l’ es 2 ^l 
Dado que en el árbol binario cada Node tiene como máximo 2 hijos, el siguiente nivel tendría el doble de Nodes, es decir 2 * 2 ^litros 

2) El número máximo de Nodes en un árbol binario de altura ‘h’ es 2 ^h – 1 . 
Aquí, la altura de un árbol es el número máximo de Nodes en el camino de la raíz a la hoja. La altura de un árbol con un solo Node se considera como 1. 
Este resultado se puede derivar del punto 2 anterior. Un árbol tiene Nodes máximos si todos los niveles tienen Nodes máximos. Entonces, el número máximo de Nodes en un árbol binario de altura h es 1 + 2 + 4 + .. + 2 ^h-1 . Esta es una serie geométrica simple con h términos y la suma de esta serie es 2 ^h – 1. 
En algunos libros, la altura de la raíz se considera 0. En esta convención, la fórmula anterior se convierte en 2 ^h+1 – 1 

3) En un Árbol Binario con N Nodes, la altura mínima posible o el número mínimo de niveles es Log ₂ (N+1).
Debe haber al menos un elemento en cada nivel, por lo que la altura no puede ser mayor que N. Un árbol binario de altura ‘h’ puede tener un máximo de 2 ^h – 1 Nodes (propiedad anterior). Entonces el número de Nodes será menor o igual a este valor máximo.

N <=  2h - 1
2h >= N+1
log2(2h) >= log2(N+1)           (Taking log both sides)
hlog22 >= log2(N+1)       (h is an integer)
h  >= | log2(N+1) |

Entonces la altura mínima posible es | registro ₂ (N+1) |

4) Un árbol binario con hojas L tiene al menos | Log ₂ L |+ 1 niveles.  
Un árbol binario tiene el número máximo de hojas (y un número mínimo de niveles) cuando todos los niveles están llenos. Deje que todas las hojas estén en el nivel l, entonces lo siguiente es cierto para el número de hojas L. 

L   <=  2l-1  [From Point 1]
l =   | Log2L | + 1 
where l is the minimum number of levels.

5) En el árbol binario donde cada Node tiene 0 o 2 hijos, el número de Nodes hoja es siempre uno más que los Nodes con dos hijos .

L = T + 1
Where L = Number of leaf nodes
T = Number of internal nodes with two children
Proof:
No. of leaf nodes (L) i.e. total elements present at the bottom of tree = 
2h-1 (h is height of tree)
No. of internal nodes = {total no. of nodes} - {leaf nodes} = 
{ 2h - 1 } - {2h-1} = 2h-1 (2-1) - 1 = 2h-1 - 1
So , L = 2h-1
     T = 2h-1 - 1
Therefore L = T + 1
Hence proved

6) En un árbol binario no vacío, si n es el número total de Nodes y e es el número total de aristas, entonces e = n-1 

Cada Node en un árbol binario tiene exactamente un padre con la excepción del Node raíz. Entonces, si n es el
número total de Nodes, entonces n-1 Nodes tienen exactamente un padre. Solo hay un borde entre cualquier hijo y su
padre. Entonces el número total de aristas es n-1. 

Ver Handshaking Lemma and Tree para una prueba.
En el próximo artículo sobre la serie de árboles, discutiremos diferentes tipos de árboles binarios y sus propiedades .