Heap, numero nodi di altezza h

YmirYmir Posts: 183
edited January 2016 in Algoritmica e laboratorio
Uhm, mi sfugge qualcosa... ^^'
Convincetemi che, come dice il Cormen, in qualunque heap di n elementi vi sono al più HVZfgYt.png nodi di altezza h.

Comments

  • MindFlyerMindFlyer Posts: 436
    edited January 2016
    Questo esercizio mi ha spiazzato un po', finché sono andato a vedere la definizione che dà di altezza. E' una definizione a cui non ero abituato: l'altezza di un nodo è la lunghezza del cammino discendente più lungo che parte dal nodo stesso. Insomma è la distanza della foglia più lontana del sottoalbero pendente da quel nodo. Ergo tutte le foglie hanno altezza 0, tutti i genitori di una foglia hanno altezza 1, etc.

    Data questa definizione, è facile contare esattamente i nodi ad altezza 0, ovvero le foglie: sono [tex]\lceil n/2\rceil[/tex]. Questo è sostanzialmente ciò che dice l'esercizio 6.1-7, che avrai fatto (altrimenti cazzo! cioè, volevo dire: altrimenti fallo!). Quindi vedi già che la formula è vera per h=0. Il resto segue per induzione e qualche conticino...
  • YmirYmir Posts: 183
    Nella seconda edizione che ho non c'è l'esercizio che nella terza è 6.1-7... ma ora ho pure la terza!
    Comunque graziee!
  • MindFlyerMindFlyer Posts: 436
    Come grazie? Lasci a me il privilegio di scrivere la gaia soluzione? Che gentile!! -.-

    Facciamo vedere prima che le foglie sono davvero [tex]\lceil n/2\rceil[/tex]. Questo è vero non solo per gli alberi binari bilanciati, ma per tutti gli alberi binari in cui c'è al più un nodo con un solo figlio! Supponiamo prima che tutti i nodi abbiano 0 o 2 figli. Quelli con 0 figli li chiamiamo foglie, e diciamo che sono [tex]f[/tex]. Quelli con 2 figli li chiamiamo interni, e diciamo che sono [tex]i[/tex]. Dunque [tex]n=f+i[/tex]. Notiamo che in questo caso [tex]n[/tex] dev'essere dispari.

    Adesso contiamo il numero di archi dell'albero in due modi diversi. Sia questo numero [tex]a[/tex]. Abbiamo che [tex]a=n-1[/tex], perché si tratta di un albero. Infatti, immaginiamo di togliere una foglia alla volta, col suo rametto attaccato, come se l'albero fosse una margherita. Insieme ad ogni foglia si toglie un rametto, finché resta solo la radice. A quel punto abbiamo tolto [tex]n-1[/tex] nodi e [tex]a-1[/tex] archi (e abbiamo scoperto che non ci ama, tanto per cambiare). Quindi i nodi totali devono essere [tex]a+1[/tex].

    Un altro modo di contare gli archi è questo: le foglie hanno un arco incidente, mentre i nodi interni hanno 3 archi incidenti, tranne la radice che ne ha 2. La somma delle incidenze nodo-arco è quindi [tex]f+3(i-1)+2[/tex]. In questo modo abbiamo contato ogni arco esattamente due volte (perché ogni arco è incidente a esattamente due nodi), e quindi abbiamo [tex]a=\frac{f+3i-1}{2}[/tex]. Uguagliando le due espressioni di [tex]a[/tex], abbiamo [tex]n-1=\frac{f+3i-1}{2}[/tex].
    Ricordando che [tex]i=n-f[/tex] e sostituendo, viene fuori che [tex]f=\frac{n+1}{2}[/tex]. Siccome [tex]n[/tex] è dispari, abbiamo equivalentemente [tex]f=\lceil n/2\rceil[/tex].

    Supponiamo adesso che ci sia esattamente un nodo con un figlio, e che quindi [tex]n[/tex] sia pari. Togliendo questo unico figlio si rimane con un albero che ha lo stesso numero di foglie (una foglia va via, ma il suo genitore diventa foglia!), e [tex]n-1[/tex] nodi, i quali hanno tutti 0 o 2 figli. Per quanto detto sopra, sappiamo che qui le foglie sono [tex]f=\frac{(n-1)+1}{2}=\frac n2[/tex]. Poiché [tex]n[/tex] è pari, questo è uguale a [tex]\lceil n/2\rceil[/tex].

    Forti di questo lemma, passiamo al problema principale. Lo facciamo per induzione sull'altezza dell'albero. Per altezza 0, ovvero per l'albero che consiste della sola radice-foglia, la verifica è banale. Supponiamo adesso che l'albero sia alto un po' più di Leonardo DiCaprio, e vediamo che, grazie al lemma, i nodi di altezza [tex]h=0[/tex], ovvero le foglie, sono esattamente [tex]\lceil n/2\rceil=\lceil n/2^{h+1}\rceil[/tex]. Quindi ok. Adesso togliamo tutte le foglie, restando così con un albero bilanciato di [tex]n-\lceil n/2\rceil = \lfloor n/2\rfloor[/tex] nodi. Per ipotesi induttiva, i nodi ad altezza [tex]h'[/tex] in questo albero sono al più [tex]\left\lceil\frac{\lfloor n/2\rfloor}{2^{h'+1}}\right\rceil \leqslant \left\lceil\frac{n/2}{2^{h'+1}}\right\rceil= \lceil n/ 2^{h'+2}\rceil[/tex]. Ora osserviamo che nell'albero originario questi nodi hanno altezza [tex]h=h'+1[/tex], perché qui c'è un livello di foglie in più. Sostituendo, abbiamo che i nodi a livello [tex]h[/tex] sono al più (per via di quel [tex]\leqslant[/tex]) [tex]\lceil n/2^{h+1}\rceil[/tex], come volevamo.
  • YmirYmir Posts: 183
    edited January 2016
    Uhm non intendevo che dovessi scrivere la dimostrazione... ho scritto grazie ringraziandoti di avermi fatto capire come aveva contato per arrivare a quella congettura ^^'

    Beh, ormai che l'hai scritta, posso guardarla dopo averla fatta. Grazie anche di questo ahaha

    ... poverino, guarda quanto hai scritto °-°
Sign In or Register to comment.