Pages: [1]   Go Down
Print
Author Topic: dubbio su alberi RB  (Read 1523 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Neds
Matricola
*
Offline Offline

Gender: Male
Posts: 36


« on: 12-02-2010, 12:01:12 »

abbiamo questo esercizio:
sia T un albero RB con n nodi. qual'è la complessità del miglior algoritmo possibile per trasformare T in un albero binario di ricerca?

a O(1)
b O(log n)
c O(n)
d O(n log n)

qual'è la risposta esatta?io sono indeciso tra la a e la c. sono più convinto che sia la c perchè basta togliere i colori a tutti i nodi
secondo voi?
 
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #1 on: 12-02-2010, 12:21:37 »

io credo la a perchè è già un albero binario di ricerca.
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!
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #2 on: 12-02-2010, 12:35:42 »

io credo la a perchè è già un albero binario di ricerca.

secondo me è pure la a..i colori non hai bisogno di toglierli..basta non considerarli proprio  pray
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
leviadragon
Apprendista Forumista
**
Offline Offline

Posts: 217


WWW
« Reply #3 on: 12-02-2010, 13:40:39 »

colorare tutti i nodi rossi in nero...

immagino sia O(n)

sbaglio?
Logged

www.darkzero.altervista.org <-- se vi piace mettetela come homepage

Link Immagine


--gratuitamente ricevete,gratuitamente date--
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #4 on: 12-02-2010, 14:09:34 »

non è detto che devi trasformare tutti i nodi di rosso in nero..i bst non hanno colore tra gli attributi
siccome l'albero rb è un bst già di suo, se non consideri totalmente il colore e le relative 5 proprietà da mantenere hai un albero binario di ricerca..

quindi a mio parere in O(1) hai risolto
Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
Psycho
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 497



« Reply #5 on: 12-02-2010, 14:12:06 »

per fare un esempio pratico:
prendi il codice degli alberi rb rimuovi i controlli sulle proprietà dei colori e dell'altezza nera e hai ottenuto un bst.
« Last Edit: 12-02-2010, 14:14:05 by Psycho » Logged

Segnate le date, cancellate gli altri impegni, chiudete i libri e i quaderni e per un attimo accorgetevi che la vita non è piatta ma può essere... 3d!
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #6 on: 12-02-2010, 15:44:39 »

Quote
per fare un esempio pratico:
prendi il codice degli alberi rb rimuovi i controlli sulle proprietà dei colori e dell'altezza nera e hai ottenuto un bst.
tanto è vero che nel algoritmo del bt devi aggiungere soltanto poche righe che ti permettano di rispettare le 5 proprietà.

Quote
colorare tutti i nodi rossi in nero...

immagino sia O(n)
Se la domanda è decontestualizzata... si è O (n)! O perchè i nodi rossi sono al più n/2, quindi non possiamo dire che è anche omega(n).
Se invece ti riferivi all'esercizio, come dice Psyco, non hai bisogno di ricolorare, ne tanto meno di eliminare il campo colore, sono solo informazioni in più che non ti danno nessun fastidio, almeno se parliamo di costi.
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!
Neds
Matricola
*
Offline Offline

Gender: Male
Posts: 36


« Reply #7 on: 12-02-2010, 17:23:57 »

 ok
grazie
Logged
Vincenzo Cutello
Administrator
Forumista
*****
Offline Offline

Gender: Male
Posts: 600


« Reply #8 on: 15-02-2010, 09:26:22 »

La domanda si può riscrivere in questo modo: "Cosa bisogna fare per trasformare una Ferrari in una automobile?"

Da non confondere con la domanda:
"Cosa bisogna fare per fare in modo che una Ferrari non sia più una Ferrari ma una semplice automobile?"
Logged
Pages: [1]   Go Up
Print
Jump to: