Pages: [1]   Go Down
Print
Author Topic: Alberi RB  (Read 1449 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Daniele
Matricola
*
Offline Offline

Posts: 81


« on: 04-03-2010, 18:44:42 »

 RB con n>1 elementi e con uno solo rosso. Segnare quella giusta.
      a) Il nodo rosso è figlio della radice
      b) Il nodo rosso non ha nodi figli
      c) Le foglie (nil) dell'albero sono tutte allo stesso liv
      d) Il sottoalbero DX ha altezza diversa del sottoalbero SX

Perché le foglie nill sono tutte allo stesso livello?

Un albero di questo tipo non è RB?

                     O
                    /  \
                  O    nil
                /    \
             nil    nil
Logged
Innuendo85
Apprendista Forumista
**
Offline Offline

Posts: 222



« Reply #1 on: 04-03-2010, 19:09:58 »

L'hai ricopiata da questo post  http://forum.sdai.unict.it/index.php?topic=7018.15 ...vero?  Purtroppo,il nostro collega l'ha scritta male (me lo ricordo bene,perchè quel compito l'ho fatto anch'io!) 
La domanda esatta è la seguente: Sia T un albero RB con n>1 elementi e con uno solo rosso.Quale delle seguenti affermazioni è SICURAMENTE FALSA?

a) Il nodo rosso è figlio della radice
b) Il nodo rosso non ha nodi figli
c) Le foglie (nil) dell'albero sono tutte allo stesso liv
d) Il sottoalbero DX ha altezza diversa del sottoalbero SX

Come vedi,ora la domanda è ben diversa! Cosa risponderesti,adesso?
Logged

You can be anything you want to be, just turn yourself into anything you think that you could ever be...Be free with your tempo, be free, be free...Surrender your ego - be free, be free to yourself...
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #2 on: 04-03-2010, 20:59:06 »

la risposta errata è la C. Perchè l'albero rossonero deve mantenere la proprietà della b altezza, quindi nel lato in cui sta il nodo rosso, le foglie nil saranno ad un livello in più. Di contro in qualche caso le altre possone essere vere.
La a è banalmente vera se al secondo livello mettiamo il nodo rosso.
La b non vuol dire niente, possiamo creare sia un albero dove il nodo ha figli, che un albero in cui non ne ha.
La d infine è vera se il nodo rosso sta a destra, falsa se sta a sinistra.
Vi sottolineo l'aggettivo SICURAMENTE perchè vuol dire che non esiste un caso in cui è vera, cioè quanto ho dimostrato in precedenza. Spero di essere stato chiaro.
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Daniele
Matricola
*
Offline Offline

Posts: 81


« Reply #3 on: 05-03-2010, 14:35:09 »

Grazie 
Logged
kri
Apprendista Forumista
**
Offline Offline

Posts: 233


« Reply #4 on: 06-03-2010, 22:03:15 »

La d infine è vera se il nodo rosso sta a destra, falsa se sta a sinistra.
Vi sottolineo l'aggettivo SICURAMENTE perchè vuol dire che non esiste un caso in cui è vera, cioè quanto ho dimostrato in precedenza. Spero di essere stato chiaro.

Aspetta, scusa, non sto capendo: la risposta non dice "il sottoalbero di dx ha altezza maggiore/ minore del sx"
ma dice diversa, quindi non è sinonimo di dire che le foglie non sono allo stesso livello???
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #5 on: 07-03-2010, 00:02:54 »

Quote
"il sottoalbero di dx ha altezza maggiore/ minore del sx"
ma dice diversa
hai ragione! io avevo considerato maggiore! ma poco importa. Così anzi la d sarebbe sempre vera. E la domanda chiede quale è sicuramente falsa. Chiaro?
Logged

Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Pages: [1]   Go Up
Print
Jump to: