[Tech] [OT] Btree

[Franco Bagnoli]

On Mon, 10 Dec 2001, Massimiliano Masi wrote:

> Salve !!!
>
> Sono ottissimo pero':
>
> per scuola ho bisogno di fare una relazione sulla quantita' di nodi
> in un albero binario.
>
> Facendo delle statisctiche, mi viene fuori:

se l'albero è perfettamente bilanciato il risultato è facile da ottenere:

livello     albero                   n. nodi

   0            o                        1
               / \
   1          o   o                      2
              |\  |\
   2          o o o o                    4

.....
   n          [snip]                     2^n

per cui: numero totale nodi = \sum_{i=0}^n 2^i = 2^{n+1}-1
di cui 2(n+1)-1  esterni


detto cazzate?

Ciao.
-- 
Franco Bagnoli (franchino) <bagnoli@dma.unifi.it>
Dipartimento di Matematica Applicata "G. Sansone" - Universita' di Firenze
Via S. Marta, 3 I-50139 Firenze, Italy. Tel. +39 0554796422, fax: +39 055471787
GPG Key fingerprint = 169D 9EA5 8FD3 7EDA E43A  9830 255F BCEC 0D63 3728