Pages: 1 [2] 3   Go Down
Print
Author Topic: come si dimostra il numero massimo di nodi ad altezza h?  (Read 7729 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
equivoco
Matricola
*
Offline Offline

Posts: 69


« Reply #15 on: 18-12-2012, 12:48:03 »

non sono sicuro che non ho fatto errori, ma ho preso l'insert di un albero rosso nero, e su carta ho creato l'albero scorrendo il codice passo passo alla fine mi restano 2 nodi rossi
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #16 on: 18-12-2012, 13:16:46 »

ma se esiste per ogni coppia di nodi un arco si forma il ciclo che contraddice l'ipotesi del grafo aciclico... quindi solo per esclusione punterei alla b) ma non l'ho capita proprio...il cervello si rifiuta  testate !!!!!!
Se ho inteso bene le parole, prova questo grafo:

 A-->B--->C--->D--->A 

 così qualunque coppia di nodi ha un solo arco ma forma il ciclo! se togli D--->A hai l'aciclicità ma non soddisfi la condizione "per ogni coppia" perchè la coppia di nodi A-D non ha archi!

Per la 13 se è vera la a) allora la d) è vera pure! l'ho scelta per questo :p ... mah....

Per la 15 mi pare troppo .... ma resta il dubbio di come calcolarlo!!!! io ho fatto questo ragionamento:
Ho preso l'es a lezione di fondere le k liste cn complessità tot nlogk .... 
avendo 4 liste ho fatto nlog4=2n  boh
Potresti postare questo esempio fatto a lezione?
Logged
Andrea2990
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 235



WWW
« Reply #17 on: 18-12-2012, 13:20:03 »

2 nodi rossi anche a me, bastava inserire come nei classici alberi binari di ricerca e aggiustare di volta i colori dei nodi secondo le varie regole e i vari casi. Insomma, InsertFixUp.
Logged
Il Capitano
Apprendista Forumista
**
Offline Offline

Posts: 409


« Reply #18 on: 18-12-2012, 14:55:33 »

2 nodi rossi anche a me, bastava inserire come nei classici alberi binari di ricerca e aggiustare di volta i colori dei nodi secondo le varie regole e i vari casi. Insomma, InsertFixUp.

Io ho inserito cosi:

                               1
                      3              5
                 2        4

Non dovrebbe essere soltanto il 3 il nodo rosso? Perchè la radice è nera e le foglie (2,4,5) pure...
Logged
TheSpecialOne
Apprendista Forumista
**
Offline Offline

Posts: 232



« Reply #19 on: 18-12-2012, 15:00:32 »

2 nodi rossi anche a me, bastava inserire come nei classici alberi binari di ricerca e aggiustare di volta i colori dei nodi secondo le varie regole e i vari casi. Insomma, InsertFixUp.

Io ho inserito cosi:

                               1
                      3              5
                 2        4

Non dovrebbe essere soltanto il 3 il nodo rosso? Perchè la radice è nera e le foglie (2,4,5) pure...

Anche io ho fatto questo ragionamento..
Logged
equivoco
Matricola
*
Offline Offline

Posts: 69


« Reply #20 on: 18-12-2012, 15:07:34 »

ci sono le rotazioni
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #21 on: 18-12-2012, 15:09:57 »

si ci sono le rotazioni.. comunque domanda numero 8? è la c?
Logged
nairi
Apprendista Forumista
**
Offline Offline

Posts: 185



« Reply #22 on: 18-12-2012, 15:18:26 »


Non dovrebbe essere soltanto il 3 il nodo rosso? Perchè la radice è nera e le foglie (2,4,5) pure...

Raga ma le foglie sono I NIL !!!!!!!!!!!!!!!!!!!!

 Quindi secondo me sono 2 i nodi rossi ma non ne ho la certezza assoluta!!!! Pensate anche alla b-altezza e quindi alla 5° proprietà!
 
Logged
Raro89
Apprendista Forumista
**
Offline Offline

Posts: 121



« Reply #23 on: 18-12-2012, 15:26:29 »

Ho cercato di capire meglio al domanda inserendo i nodi ad uno ad uno seguendo l'ordine dato e ovviamente facendo le opportune rotazioni,  il risultato è stato questo grafo:

                     3
               2           5
          1             4

con 2 nodi rossi (2,5) e 2 nodi neri(1,4) più ovviamente la radice ed i nodi NIL
Logged
Andrea2990
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 235



WWW
« Reply #24 on: 18-12-2012, 15:38:59 »

Quote
si ci sono le rotazioni.. comunque domanda numero 8? è la c?
Qualcuno lo sa?
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #25 on: 18-12-2012, 15:45:33 »

Quote
si ci sono le rotazioni.. comunque domanda numero 8? è la c?
Qualcuno lo sa?
Anche tu nel dubbio vero Andrea? Cheesy
Logged
Raro89
Apprendista Forumista
**
Offline Offline

Posts: 121



« Reply #26 on: 18-12-2012, 15:46:39 »

dalle slide del prof, capitolo 9-slide 17, sembra intuirsi sia la c,
perchè dice che il tempo totale per ordinare i 5 gruppi per ceeling(n/5) è cn...
poi non so forse sbaglio io nell'interpretare la domanda e relativa spiegazione delle slide
Logged
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #27 on: 18-12-2012, 15:48:32 »

dalle slide del prof, capitolo 9-slide 17, sembra intuirsi sia la c,
perchè dice che il tempo totale per ordinare i 5 gruppi per ceeling(n/5) è cn...
poi non so forse sbaglio io nell'interpretare la domanda e relativa spiegazione delle slide
nelle slide del prof c'è il select?
Logged
Raro89
Apprendista Forumista
**
Offline Offline

Posts: 121



« Reply #28 on: 18-12-2012, 15:49:13 »

il tempo totale per ordinare i 5 gruppi per ceeling(n/5)

scusate mi sono spiegato male, dice che il tempo per ordinare i 5 elementi del gruppo deve essere ripetuto per tutti i gruppi, ovvero ceeling (n/5) volte
Logged
equivoco
Matricola
*
Offline Offline

Posts: 69


« Reply #29 on: 18-12-2012, 15:50:52 »

secondo me il tempo per ordinare il gruppi è O(1) esattamente 7 confronti e quindi la risposta è c
Logged
Pages: 1 [2] 3   Go Up
Print
Jump to: