Albero binomiale
Un albero binomiale è un albero ordinato definito ricorsivamente nel seguente modo: l'albero binomiale B 0 {\displaystyle B_{0}} è costituito da un singolo nodo, 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à: i suoi nodi sono esattamente 2 k {\displaystyle 2^{k}} , la sua altezza è esattamente k {\displaystyle k} , 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} la sua radice ha grado k {\displaystyle k} ed inoltre tale grado è maggiore del grado di ogni altro nodo.
Un albero binomiale è un albero ordinato definito ricorsivamente nel seguente modo:
- l'albero binomiale è costituito da un singolo nodo,
- l'albero binomiale è costituito da due alberi binomiali collegati assieme in modo che la radice di uno dei due alberi binomiali sia figlio sinistro della radice dell'altro.
Un generico albero binomiale è caratterizzato da alcune proprietà:
- i suoi nodi sono esattamente ,
- la sua altezza è esattamente ,
- i suoi nodi a profondità sono esattamente , con
- la sua radice ha grado ed inoltre tale grado è maggiore del grado di ogni altro nodo.
Grado massimo
[modifica | modifica wikitesto]Il massimo grado di ogni nodo di un albero binomiale con nodi è .
Bibliografia
[modifica | modifica wikitesto]- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduzione agli algoritmi. Jackson Libri, 2003, ISBN 88-256-1421-7.
