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

Gender: Female
Posts: 96



« on: 21-05-2010, 18:30:32 »

Salve a tutti,
cortesemente qualcuno potrebbe chiarirmi un mio dubbio.
Facendo gli esercizi proposti nella sezione Esercitazione del Sistema di esercitazione online, mi è capitato il seguente esercizio:

"Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (32, 41, 37, 15, 5, 8, 6, 44, 29).
Individuare il corretto output di una visita Preorder del suddetto albero dopo aver effettuato l'operazione Delete(T,) "


Mi chiedevo, ma dentro il metodo Delete non manca il valore della chiave da eliminare? O mi sto confondendo io?

Grazie a chiunque mi toglierà il dubbio.

Un  buon pomeriggio
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #1 on: 21-05-2010, 19:58:16 »

manca manca! mi sembra di aver letto da qualche parte che il prof abbia chiesto di segnalare (se non errò via mail o a lezione) eventuali "bug" riscontrati nel sistema di esercitazione.
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!
Simone Faro
Moderator
Matricola
*****
Offline Offline

Gender: Male
Posts: 67


WWW
« Reply #2 on: 22-05-2010, 09:04:22 »

Bug eliminato.
Grazie per la segnalazione
Il Prof
Logged

________________________________
Simone Faro, Ph.D.
Dipartimento di Matematica e Informatica
Università di Catania
________________________________
bluegirl
Apprendista Forumista
**
Offline Offline

Posts: 360



« Reply #3 on: 22-05-2010, 09:45:03 »

A proposito di alberi binari di ricerca...ho un dubbio sulla risoluzione di un esercizio:

Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (25, 7, 44, 49, 20, 5, 24, 30).
Individuare il corretto output di una visita Postorder del suddetto albero dopo aver effettuato l'operazione RightRotate(T,44).


Mi costruisco l'albero:
                                                   25
                                                /       \
                                             7         44
                                             / \          \
                                           5  20       49
                                                   \
                                                 24
                                                    \
                                                    30


Come si dovrebbe fare il RightRotate su 44???
Logged
LexaIdo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 110



« Reply #4 on: 22-05-2010, 09:51:25 »

A proposito di alberi binari di ricerca...ho un dubbio sulla risoluzione di un esercizio:

Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (25, 7, 44, 49, 20, 5, 24, 30).
Individuare il corretto output di una visita Postorder del suddetto albero dopo aver effettuato l'operazione RightRotate(T,44).


Mi costruisco l'albero:
                                                   25
                                                /       \
                                             7         44
                                             / \          \
                                           5  20       49
                                                   \
                                                 24
                                                    \
                                                    30


Come si dovrebbe fare il RightRotate su 44???
credo che il 30 dovrebbe essere figlio sinistro di 44, è più grande di 25 quindi deve stare a destra... e così si può effettuare la rotazione 
Logged
Federik88
Matricola
*
Offline Offline

Gender: Female
Posts: 96



« Reply #5 on: 22-05-2010, 10:33:29 »

si, ha ragione LexaIdo, il 30 dovrebbe essere figlio sinistro del 44, e così facendo la rotazione è poi possibile, perchè per poter fare la rotazione destra sulla chiave 44 è necessario che esista un suo figlio sinistro

Ragazzi ho da proporvi un'altro dubbio.  Mi è capitato il seguente esercizio:

Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (7, 8, 20, 11, 10, 41, 36, 46, 42, 6, 37).
Individuare il corretto output di una visita Postorder del suddetto albero dopo aver effettuato l'operazione Delete(T,41)


E dopo il testo vi era una sola possibile cassella per l'output. Ma L'output non dovrebbe essere più lungo di una sola chiave?  A me è risultato così: 6, 10, 11, 37, 36, 46, 42, 20, 8, 7
Logged
bluegirl
Apprendista Forumista
**
Offline Offline

Posts: 360



« Reply #6 on: 22-05-2010, 10:49:08 »

Frederick il tuo output dovrebbe essere corretto...cmq ci sarà un'altro bug?Invece io ho problemi nel rotateRight o RotateLeft...non ho capito una cosa: ma perchè sposto il 30?si va a prendere la foglia più a destra?ed il nuovo albero come diventerebbe?
« Last Edit: 22-05-2010, 10:59:43 by bluegirl » Logged
LexaIdo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 110



« Reply #7 on: 22-05-2010, 11:10:35 »

l'albero all'inizio è così:
                                                   25
                                                /       \
                                             7          44
                                            / \        /    \
                                          5  20    30   49
                                                  \
                                                  24

poi effettuando la rotazione destra sul 44 dovrebbe diventare così:
                                                     25
                                                  /       \
                                                7         30
                                               / \           \
                                             5  20         44
                                                    \           \
                                                    24        49
Logged
Federik88
Matricola
*
Offline Offline

Gender: Female
Posts: 96



« Reply #8 on: 22-05-2010, 11:16:49 »

ciao bluegirl, scusa se ti correggo ma il mio nome è Federik o se preferisci Federica, Frederik credo sia il nick di un altro nostro collega, lo dico per evitare la confusione tra noi due data la somiglianza tra i due nick.

Per quanto riguarda l'esercizio sulla RotateRight, il 30 dovrebbe trovarsi a sinistra del 44 proprio per inserimento, e non per qualche spostamento. Perchè partendo dalla radice, il 30 è maggiore di 25, per cui scendi alla sua destra e arrivi al 44, il 30 è più piccolo del 44 e allora scendi alla sua sinistra e lo collochi come suo figlio sinistro, ed ecco che hai inserito così il 30 nell'albero.

Poi per poter fare la rotazione destra del 44, prendi il suo figlio sinistro, in questo caso il 30, e ques'ultimo prenderà il posto del 44, mentre il 44 dovrebbe essere spostato alla destra "del nuovo padre" 30 , prendendo il posto del 49, e il 49 credo che dovrebbe diventare figlio destro di 44. Ma non sono sicura di questi ultimi due spostamenti che ti ho indicato.

Ti rappresento l'albero così come io l'ho pensato dopo la rotazione, anche se non sono sicura che sia giusto:
 
                                                    25
                                                  /       \
                                                7         30
                                               / \           \
                                             5  20         44
                                                    \           \
                                                    24        49
Logged
Federik88
Matricola
*
Offline Offline

Gender: Female
Posts: 96



« Reply #9 on: 22-05-2010, 11:24:06 »

ho perso tempo a scrivere il mio post precedente che non mi ero accorta che già LexaIdo ci aveva indicato l'albero dopo la rotazione, grazie per l'indicazione . Dato che avevo il dubbio di aver fatto gli spostamenti in modo corretto, vedendo che il mio albero coincide con il suo inizio a pensare che magari i miei ragionamenti erano giusti.  nono
Logged
bluegirl
Apprendista Forumista
**
Offline Offline

Posts: 360



« Reply #10 on: 22-05-2010, 11:36:55 »

Grazie ad entrambi  , vado a fare altri esercizi con la rotazione.
Chiedo scusa a Federik88 per l'errore nel nick
Logged
Federik88
Matricola
*
Offline Offline

Gender: Female
Posts: 96



« Reply #11 on: 22-05-2010, 11:44:16 »

ma figurati, te l'ho detto solo per evitare di fare confusione  . Mi rimetto anch'io a fare un altro pò di esercizi.
Logged
LexaIdo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 110



« Reply #12 on: 22-05-2010, 11:46:37 »

ho perso tempo a scrivere il mio post precedente che non mi ero accorta che già LexaIdo ci aveva indicato l'albero dopo la rotazione, grazie per l'indicazione . Dato che avevo il dubbio di aver fatto gli spostamenti in modo corretto, vedendo che il mio albero coincide con il suo inizio a pensare che magari i miei ragionamenti erano giusti.  nono
se 2 indizi fanno una prova abbiamo scritto giusto  ok comunque non sarei mai riuscito a spiegarlo meglio di come hai fatto tu 
Grazie ad entrambi  , vado a fare altri esercizi con la rotazione.
prego 
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #13 on: 22-05-2010, 12:16:44 »

mentre leggevo il post avevo vosto l'errore con Frederick eh eh per una volta che non risponde!
Comunque ho visto che avete risposto tuttavia questa è la mia risposta...
la rotazione è richiamata sul 44 (nodo di rotazione). Prima cosa dobbiamo vedere se è possibile e quindi il 44 deve avere un figlio sinistro (che diventerà suo padre). Il 30 è figlio sinistro. Procediamo.
Come si opera nella rotazione destra? come se avessimo collegato i nostri nodi tramite dei fili rigidi, prendi il figlio sinistro(30) del nodo di rotazione (44), usiamolo come perno della rotazione e immaginiamo di portarlo ad un livello superiore, il nodo di rotazione (44) padre del perno (30) scende e diventa suo figlio destro (44 figlio di 30). Colleghiamo il vecchio padre (25) del nodo di rotazione (44) come padre del nodo perno (30) (25 è ora padre di 30). Il figlio destro del nodo di rotazione rimane tale (così come il sinistro del nodo perno se ci fosse stato, sarebbe rimasto figlio sinistro). Nel nostro esempio abbiamo finito.
Ma nella rotazione avremmo dovuto garantire una paternità all' eventuale figlio destro del nodo perno. Sarebbe semplicemente diventato figlio sinistro del nodo di rotazione. E quindi se è chiaro dovremmo trovarci qui:
Code:
      25
     /    \
   7      30
  / \        \
 5  20      44
       \        \
        24      49
Federik88 e LexaIdo avevano già detto giusto!
« Last Edit: 22-05-2010, 17:35:46 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 #14 on: 22-05-2010, 17:17:37 »

Grazie per la conferma cock86 

Facendo un'altro esercizio mi è venuto un dubbio su come dovrebbe venire l'albero dopo la rotazione. Ecco il testo:
Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (20, 7, 15, 44, 32, 50, 45, 34, 33, 42, 16).
Individuare il corretto output di una visita Postorder del suddetto albero dopo aver effettuato l'operazione LeftRotate(T,44).

Io l'ho fatto così l'albero , ma son sicura che sia sbagliato

                                               20
                                            /        \
                                        7            50
                                        \               /
                                        15            45
                                          \            /
                                           16       44
                                                       /
                                                      32
                                                         \
                                                           34
                                                            /  \
                                                         33    42
                                                            
« Last Edit: 22-05-2010, 17:22:59 by Federik88 » Logged
Pages: [1] 2 3 4   Go Up
Print
Jump to: