[Tech] [OT] Btree

[Franco Bagnoli]

On Tue, 11 Dec 2001, Massimiliano Masi wrote:

> Ciao !!!
>
> On Mon, Dec 10, 2001 at 11:25:26PM +0100, Franco Bagnoli wrote:
> > se l'albero è perfettamente bilanciato il risultato è facile da ottenere:
>
> Infatti.
> Mettiamo pero' che il tree sia un avl o un albero non bilanciato.
> Nel primo caso mi aspetto che i mediani siano zero, invece dalla simulazione
> mi vengono:
> 			Interni		mediani		esterni
> AVL			30%		10%		60%
>
> Btree (non bal)		33%		50%		17%
>
> (sempre che non abbia sbagliato il programma che genera/conta/fa la stat) :)

io sono alquanto arrugginito, mi ripeti la definizione di mediani? peerché
dovrebbero essere 0 su un AVL (che se mi ricordo bene dovrebbe
approssimare un albero perfettamente bilanciato)?

Inoltre, almeno per l'albero bilanciato, gli esterni seguono una legge di
crescita (con il numero di livelli n) diversa da quelli interni

numero totale ~ 2^n
numero esterni ~ 2*n

per cui le percentuali dipendono da n, non tendono ad un limite.

Viceversa, per un albero completamente sbilanciato tutti i nodi sono
esterni.

Secondo me dovresti fare il grafico dei numeri con n.

Comunque si dopvrebbe riuscire a fare il calcolo anche delle fluttuazioni,
solo che mi ci vuole un po' di tempo, ora sto preparando la lezione di
domani.

-- 
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