Pages: 1 [2]   Go Down
Print
Author Topic: Aggiunta di elemento in heap  (Read 3451 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« Reply #15 on: 27-09-2011, 15:12:56 »

Perfetto...
Logged
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #16 on: 27-09-2011, 15:24:54 »

Quote
perchè dobbiamo guardare solamente ad altezza massima che sarebbe il livello sotto la radice
No....l' altezza massima si trova scendendo più giù....più vai sotto più aumenta l' altezza.

Tu dici? Io so che le foglie hanno altezza 0, la radice altezza massima.

http://en.wikipedia.org/wiki/Tree_%28data_structure%29#Terminology
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #17 on: 27-09-2011, 15:27:35 »

Infatti intendevo l' altezza dell' albero.

Per quanto riguarda l'altezza h di un albero binario è data dalla massima profondità raggiunta dalle sue foglie. Quindi, l'altezza misura la massima distanza di una foglia dalla radice dell'albero.


            O
         /      \
      O         O
    /   \      /   \
  O     O  O     O

Qual è l' altezza di questo albero?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
flashato90
Apprendista Forumista
**
Offline Offline

Posts: 122


WWW
« Reply #18 on: 27-09-2011, 15:31:57 »

Quote
perchè dobbiamo guardare solamente ad altezza massima che sarebbe il livello sotto la radice
No....l' altezza massima si trova scendendo più giù....più vai sotto più aumenta l' altezza.

Tu dici? Io so che le foglie hanno altezza 0, la radice altezza massima.

http://en.wikipedia.org/wiki/Tree_%28data_structure%29#Terminology

Ecco! Io intendevo proprio quello... quindi credevo che siccome dovemamo trovare un determinato nodo ad altezza massima (esclusa la radice) ... l'altezza massima (non dell'albero)... era quella riguardante i nodi nel livello sotto la radice e quindi bastava vedere se era rosso il nodo root.left(); oppure root.right(); ... per questo io credevo fosse O(1)...
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #19 on: 27-09-2011, 17:07:01 »

Quote
quindi credevo che siccome dovemamo trovare un determinato nodo ad altezza massima (esclusa la radice) ...

Eh no perchè dice di trovare se esiste un nodo rosso alla massima altezza, ma la massima altezza è ovviamente riferita all' altezza dell' albero. 
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #20 on: 27-09-2011, 17:08:55 »

Quote
quindi credevo che siccome dovemamo trovare un determinato nodo ad altezza massima (esclusa la radice) ...

Eh no perchè dice di trovare se esiste un nodo rosso alla massima altezza, ma la massima altezza è ovviamente riferita all' altezza dell' albero. 

intendiamo quindi "il nodo rosso piu' vicino possibile alla radice", giusto?
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #21 on: 27-09-2011, 20:24:09 »

Quote
intendiamo quindi "il nodo rosso piu' vicino possibile alla radice", giusto?

Secondo me no, correggimi se sbaglio:

                   1
               /       \
            2            3
         /      \       /   \
      4         5     6    7
    /   \      /  \
  8     9  10  11..................

Il nodo 2, ha altezza pari a 2, il nodo 4, ha altezza 1 e il nodo 8 ha altezza pari a 0. Ci sei?
Quindi nel nostro quesito(che hai risolto) si chiede di determinare se c' è un nodo rosso alla massima altezza, si intenderà dell' albero. I nodi 2 e 3 non sono alla massima altezza, l' altezza massima dell' albero è quella delle foglie, quindi dovremo cercarlo tra i nodi 8, 9, 10, 11....
Cosa ne pensi?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Misa
Matricola
*
Offline Offline

Posts: 57



« Reply #22 on: 27-09-2011, 20:57:59 »

Secondo me no, correggimi se sbaglio:

                   1
               /       \
            2            3
         /      \       /   \
      4         5     6    7
    /   \      /  \
  8     9  10  11..................

Il nodo 2, ha altezza pari a 2, il nodo 4, ha altezza 1 e il nodo 8 ha altezza pari a 0. Ci sei?

si, ci sono.... la radice ha h=3, i nodi 2 e 3 hanno h=2 i nodi 4,5,6,7 h=1, etc.

visto che ci chiede il nodo rosso alla massima altezza, mi sembra dobbiamo scendere in ordine...
nodo 1, nodi 2 e 3, nodi 4,5,6 e 7....

potrei sbagliarmi. meglio che vada a riposare, mi gira la testa Cheesy
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #23 on: 27-09-2011, 22:26:51 »

Si si la mia era una spiegazione data a flashato90 che non aveva ben chiaro come funzionasse l' altezza, concordo invece sul tuo metodo di risoluzione.
In bocca al lupo per domani ragazzuoli..
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: 1 [2]   Go Up
Print
Jump to: