Albero binomiale

Un albero binomiale è un albero ordinato definito ricorsivamente nel seguente modo:

1. l'albero binomiale ${\displaystyle B_{0}}$ è costituito da un singolo nodo,
2. l'albero binomiale ${\displaystyle B_{k}}$ è costituito da due alberi binomiali ${\displaystyle B_{k-1}}$ collegati assieme in modo che la radice di uno dei due alberi binomiali sia figlio sinistro della radice dell'altro.

Alberi binomiali di grado rispettivamente 0, 1, 2 e 3. Il primo albero è costituito da un solo nodo, il secondo è l'unione di alberi binomiali di grado 0, il terzo è costituito dall'unione di due alberi di grado 2. Il terzo albero è definito ricorsivamente in modo analogo.

Un generico albero binomiale ${\displaystyle B_{k}}$ è caratterizzato da alcune proprietà:

1. i suoi nodi sono esattamente ${\displaystyle 2^{k}}$,
2. la sua altezza è esattamente ${\displaystyle k}$,
3. i suoi nodi a profondità ${\displaystyle i}$ sono esattamente ${\displaystyle {\binom {k}{i}}}$, con ${\displaystyle i=0,1,...,k}$
4. la sua radice ha grado ${\displaystyle 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 ${\displaystyle n}$  nodi è ${\displaystyle lg(n)}$ .

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduzione agli algoritmi. Jackson Libri, 2003, ISBN 88-256-1421-7.

  Portale Informatica

  Portale Matematica