Albero binomiale

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 albero binomiale è un albero ordinato definito ricorsivamente nel seguente modo:

  1. l'albero binomiale B 0 {\displaystyle B_{0}} è costituito da un singolo nodo,
  2. l'albero binomiale B k {\displaystyle B_{k}} è costituito da due alberi binomiali B k − 1 {\displaystyle 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 {\displaystyle B_{k}} è caratterizzato da alcune proprietà:

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