Pages: [1]   Go Down
Print
Author Topic: Alcune domande ultimo compito  (Read 1261 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
musma
Matricola
*
Offline Offline

Gender: Male
Posts: 82


« on: 24-04-2010, 22:34:19 »

Ho alcuni dubbi sull'ultimo compito.

Ecco la prima.

Qual è il numero massimo di nodi interni che un albero rossonero con b-altezza 3 può avere?

a) 7
b) 15
c) 31
d) 63


Qual è la risposta esatta. E come avete ragionato?
« Last Edit: 24-04-2010, 22:36:01 by musma » Logged
Yaroth
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 445



« Reply #1 on: 24-04-2010, 23:43:54 »

Giusto!! avendo risposto alle due di notte ieri non avevo ragionato bene, con B-altezza ci si riferisce all'altezza nera dell'albero Wink
« Last Edit: 25-04-2010, 09:21:16 by Yaroth » Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #2 on: 25-04-2010, 00:08:09 »

io a dire il vero ho la vaga impressione che sia la d.
la domande chiede il numero massimo, quindi pensiamo il nostro albero completo, e con i livelli di colore alternati partendo dal nero che è il colore della radice. Dopo di che potremmo avere in tutto altri tre livelli rossi, e due neri prima di arrivare alle foglie (nere) che non consideriamo. Il che vuol dire in tutto sei livelli, e visto che il numero di nodi e 2^n, e per avere i nodi interni basta togliere la radice, avremmo (2^n)-1= (2^6) -1= 64-1=63=D.
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!
Spaccossa
Apprendista Forumista
**
Offline Offline

Posts: 215



« Reply #3 on: 25-04-2010, 00:21:35 »

io a dire il vero ho la vaga impressione che sia la d.
la domande chiede il numero massimo, quindi pensiamo il nostro albero completo, e con i livelli di colore alternati partendo dal nero che è il colore della radice. Dopo di che potremmo avere in tutto altri tre livelli rossi, e due neri prima di arrivare alle foglie (nere) che non consideriamo. Il che vuol dire in tutto sei livelli, e visto che il numero di nodi e 2^n, e per avere i nodi interni basta togliere la radice, avremmo (2^n)-1= (2^6) -1= 64-1=63=D.

confermo quanto detto da cocks, l'esempio cè l'hai nel libro a pag 232. guarda tutto il ramo sinistro del primo dell'albero (a)
Logged
Pages: [1]   Go Up
Print
Jump to: