Pages: 1 2 [3] 4   Go Down
Print
Author Topic: dubbio su un possibile errore in un esercizio sugli Alberi binari di ricerca  (Read 5374 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
mafalda
Apprendista Forumista
**
Offline Offline

Posts: 430


CЯΣDΣЯCI SΣMPЯΣ, ΛЯЯΣПDΣЯSI MΛI!


« Reply #30 on: 25-05-2010, 15:48:38 »

Segnalo errore:

Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo
(15, 7, 19, 38, 37, 21, 10, 2, 39, 27, 48).
Individuare il corretto output di una visita Preorder del suddetto albero dopo aver effettuato l'operazione Insert(T,23).
Erano presenti più di 12 (forse 15) quadrati dove inserire le chiavi dell'albero.
Logged

...๔єςเ, ๔єςเ, ๔єςเ...
bluegirl
Apprendista Forumista
**
Offline Offline

Posts: 360



« Reply #31 on: 26-05-2010, 11:28:21 »

Come si dovrebbe costruire l'albero dopo la LefttRotate e rightRotate??Io l'ho sbagliato


1)Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (49, 14, 19, 27, 42, 39, 20, 13, 48, 25, 11).
Individuare il corretto output di una visita Postorder del suddetto albero dopo aver effettuato l'operazione LeftRotate(T,19)



2)Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (31, 15, 36, 27, 49, 10, 18, 17, 48, 9, 7).
Individuare il corretto output di una visita Postorder del suddetto albero dopo aver effettuato l'operazione RightRotate(T,15)

Credevo di aver capito dopo le spiegazioni qui sul forum ed invece...
« Last Edit: 26-05-2010, 11:31:06 by bluegirl » Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #32 on: 26-05-2010, 11:40:32 »

Allora quando fai una rotazione su un nodo, se la rotazione e Right (risp Left) immagina i nodi iscritti in una circonferenza e li fai girare in senso orario (risp antiorario). Prova ad immaginare come viene, l'unico nodo che cambia paternità e emisfero (figlio destro/sinistro) quello che sta al centro della circonferenza(c fig.1a e b fig.1b) che diventa figlio destro (risp sinistro) del nodo di rotazione.

fig. 1____________________________
       a)                                    b)               |
       x          left(T,x)               y                 |
     /   \        ---->                   / \                |
    a    y       right(T,y)           x   c              |
         / \      <----                 / \                  |
        b  c                            a   b                |
                                                                |
                                                                |
________________________________|
Spero di non averti confuso le idee. Anzi spero che adesso sia più chiaro.
Visto così l'idea della circonferenza diventa poco intuibile, ma prova a ridisegnartelo. E a vedere girare tutti i nodi e quello che sta al centro segue il giro e si trova attaccato dall'emisfero opposto e con un altro padre.

prova a rifare i tuoi esempi caso mai vediamo anche di risolvere quelli!!!
 
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!
bluegirl
Apprendista Forumista
**
Offline Offline

Posts: 360



« Reply #33 on: 26-05-2010, 16:33:52 »

Aspè...ti posto un altro esercizio vediamo se ho capito...

Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (12, 3, 49, 32, 5, 18, 25, 34, 48, 7, 46).
Individuare il corretto output di una visita Postorder del suddetto albero dopo aver effettuato l'operazione LeftRotate(T,12)

Albero:                   12
                         /            \
                      3                49
                         \               /
                          5           32
                             \         /    \
                              7     18      34
                                      \         \
                                     25      48
                                              /
                                           46


Dopo la rotazione dovrebbe essere così?
                               49             
                             /       \
                       32             12
                        /              /   \
                       3           18    34
                         \            \       \
                           5        25      48
                            \                    /
                              7                 46       
                                             
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #34 on: 26-05-2010, 18:14:57 »

no no! non devi scambiare il 12 con il 49!
                              49
                             /    \
                        12        34
                      /    \           \
                   3      32          48
                    \       /            /
                     5    18        46
                      \        \
                       7      25
viene così.
il 12 scende a sinistra, il 49 sale e come figlio sinistro prende il 12 (che era suo padre). Il 32 cambia emisfero(ramo), dobbiamo dargli un padre, diventa figlio destro del 12(nodo di rotazione).

EDIT[Perdonate l'errore]
                           49
                           /   
                        12       
                      /    \       
                   3        32         
                    \       /   \         
                     5    18    34
                      \      \       \
                       7     25      48
                                       /
                                      46
Non so per quale motivo ma avevo trattato il figlio 32 (34 per intenderci) come figlio di 49. Svista grafica credo!!!
« Last Edit: 29-05-2010, 17:38:42 by cock86 » 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!
bluegirl
Apprendista Forumista
**
Offline Offline

Posts: 360



« Reply #35 on: 26-05-2010, 18:19:44 »

ok...grazie cmq per la pazienza
« Last Edit: 26-05-2010, 18:24:05 by bluegirl » Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #36 on: 26-05-2010, 21:41:41 »

spero solo che sia serivita per te ed altri!
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!
Federik88
Matricola
*
Offline Offline

Gender: Female
Posts: 96



« Reply #37 on: 28-05-2010, 22:24:41 »

mi potreste dire se ho scritto in maniera corretta l'albero dopo la rotazione? Inserisco per prima il testo dell'esercizio:

Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (17, 46, 33, 40, 18, 3, 26, 30).
Individuare il corretto output di una visita Postorder del suddetto albero dopo aver effettuato l'operazione RightRotate(T,46)


ed ecco l'albero da me costruito dopo la rotazione:

                                 17
                               /      \
                            3          33
                                          \
                                          46
                                        /
                                     40
                                   /
                                 18
                                    \
                                       26
                                          \
                                          30

é corretto? Incrocio le dita... nono
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #38 on: 28-05-2010, 22:54:26 »

devo darti una brutta notizia: l'albero viene così

            17
           /   \
         3     33
               /    \
           18      46
              \      /
              26 40
             /
          30

hugh!
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!
Federik88
Matricola
*
Offline Offline

Gender: Female
Posts: 96



« Reply #39 on: 28-05-2010, 23:12:31 »

mannaggia... 

inizialmente anch'io avevo pensato alla tua stessa soluzione poi però l'ho modificata in quella che ho postato precedentemente, perchè riguardando l'albero originale:

              17
             /    \
          3        46
                   /
                33
              /     \
           18      40
            \
            26
              \
              30

 ho pensato che affinchè rimanesse valida la parentela del 18 come figlio più piccolo del 33, e poi a sua volta come figlio più piccolo del 36, allora il 18 dovesse essere messo a sinistra del 40 in modo da risultare piu piccolo sia del 46 che del 33 come detto precedentemente. Ma forse è sbagliato tutto questo ragionamento?

La cosa strana è che, dopo l'esercizio chiedeva una visita credo Preorder che mi è risultata giusta con l'albero da me fatto, ovvero 17,3,33,46, 40,18,26,30

Sono un pò confusa
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #40 on: 28-05-2010, 23:25:14 »

Quote
La cosa strana è che, dopo l'esercizio chiedeva una visita credo Preorder che mi è risultata giusta con l'albero da me fatto, ovvero 17,3,33,46, 40,18,26,30
e questa è giusta?! cioè il sistema ti da questa soluzione? ma mi sembra che sia sbagliata  
a me viene (17, 3, 33, 18, 26, 30, 46, 40)
comunque il ragionamento che hai fatto era giusto in parte, cioè garantire che il 18 (in quanto figlio sinistro) rimanga più piccolo di 33 è giusto. Che rimanga più piccolo del 46 lo manteniamo anche se gliel'ho assegniamo come fratello destro. Inoltre dobbiamo mantenere che il 40 sia il precedente del 46 (cioè il figlio più a destra del sottoalbero sinistro). Nel tuo albero dice che il precedente del 46 è il 30. E non va per niente bene. perchè ci sono il 33 e il 40.
Prova a fare una visita inorder, non ti viene ordinato.
« Last Edit: 28-05-2010, 23:47:22 by cock86 » 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!
Federik88
Matricola
*
Offline Offline

Gender: Female
Posts: 96



« Reply #41 on: 28-05-2010, 23:47:37 »

purtroppo dopo aver controllato la soluzione e aver visto che coincideva con la mia , ho dimenticato di scriverla nel quaderno e sono passata all'esercizio successivo,mi sembra di ricordare che la soluzione fosse quella da me indicata prima ma è giusto un ricordo ed il problema è che non sono sicura nemmeno che la visita richiesta fosse la Preorder, ricordo solo che avevo notato che la mia soluzione coincideva con quella del sistema, e dato che la mia soluzione a occhio riguarda una visita preorder sono risalita da qui alla soluzioni vista. Ma forse ricordo male, o li per lì ho letto male credendo che la mia soluzione fosse corretta

Cmq mi sa che hai ragione tu, avevo dimenticato di mantenere il prev del 46, ovvero il 40 come hai detto tu, e quindi la mia soluzione da cui si capisce che è errata Sad
Grazie per il chiarimento ^_^
Logged
bluegirl
Apprendista Forumista
**
Offline Offline

Posts: 360



« Reply #42 on: 29-05-2010, 10:06:48 »

Federik ho svolto il tuo esercizio ed anche a me risulta come cock e la visita Preorder dovrebbe risultare così: 17,3,33,18,26,30,46,40.

Per non sbagliare più questi esercizi ti conviene tenere a mente il grafico che mi ha fatto sopra lo stesso cock
Logged
Federik88
Matricola
*
Offline Offline

Gender: Female
Posts: 96



« Reply #43 on: 29-05-2010, 11:35:33 »

grazie bluegirl per l'ulteriore conferma 

Spero di riuscire a capirli questi esercizi, ora seguirò i tuoi consigli e guarderò il grafico da te consigliato ^_^
Logged
jos90
Apprendista Forumista
**
Offline Offline

Posts: 171



« Reply #44 on: 19-09-2011, 16:32:12 »

Scusate mi stavo rileggendo le vostre discussioni e mi pare di aver capito che quando si presenta un'operazione di rightRotate si fa diventare l'elemento x (es. rightRotate(46) ) il primo figlio destro del suo figlio sinistro (33) e si collegano a lui gli eventuali nodi al di sotto di quest'ultimo nodo (33), giusto?


              17
             /    \
          3        46
                   /
                33
              /     \
           18      40
            \
            26
              \
              30
Logged

Perchè non pensi di non capire, quando capisci di non pensare?
Pages: 1 2 [3] 4   Go Up
Print
Jump to: