title: Albero binomiale
text: # Albero binomiale
  
  Un albero binomiale è un albero ordinato definito ricorsivamente nel seguente modo:
  
  * l'albero binomiale $B_{0}$ è costituito da un singolo nodo,
  * l'albero binomiale $B_{k}$ è costituito da due alberi binomiali $B_{k-1}$ collegati assieme in modo che la radice di uno dei due alberi binomiali sia figlio sinistro della radice dell'altro.
  
  Un generico albero binomiale $B_{k}$ è caratterizzato da alcune proprietà:
  
  * i suoi nodi sono esattamente $2^{k}$,
  * la sua altezza è esattamente $k$,
  * i suoi nodi a profondità $i$ sono esattamente ${\binom {k}{i}}$, con $i=0,1,...,k$
  * la sua radice ha grado $k$ ed inoltre tale grado è maggiore del grado di ogni altro nodo.
  
  ## Grado massimo
  
  Il massimo grado di ogni nodo di un albero binomiale con $n$ nodi è $lg(n)$.
  
  