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

Posts: 95


« Reply #15 on: 22-05-2010, 17:29:57 »

Buon pomeriggio, anche io trovo delle difficoltà nella costruzione degli alberi, qualcuno potrebbe chiarirmi le idee?
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #16 on: 22-05-2010, 17:35:04 »

Inserimento:
Code:
        20
     /        \
   7           44
    \        /      \
    15     32      50
      \       \     /
      16      34  45
               /  \
             33  42
LeftRotate(T,44):
Code:
        20
     /        \
   7            50
    \           /     
    15      44     
      \      /  \   
      16  32  45 
            /   
          34
          / \
       33  42
-il 45 è il famoso eventuale figlio a cui va garanita la peternità (nella left è il figlio sinistro del perno), diventa figlio destro del nodo di rotazione.

PostOrder
Code:
16 15 7 33 42 34 32 45 44 50 20

scusate tanto per la grafica!
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!
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #17 on: 22-05-2010, 17:44:09 »

@Federik il 45 o il 50 non possono precedere il 44 nell'albero, visto che non lo precedono nell'array di inserimento. Credo che tu abbia sbagliato nel suo inserimento.
@207 cosa non ti è chiaro? la procedura di inserimento in ordine d'arrivo?
devi inserire scorrere l'array e inserire man mano nell'albero il nodo nel posto giusto. Qual è? beh devi confrontare ricorsivamente il valore del nodo da inserire con la root, e scendere nel sottoalbero di sinistra se è minore (n< root) di destra se è maggiore(n>root). E così ripetere nel sottoalbero in cui si scende, finchè la root del sottoalbero in questione non ha figli, è una foglia. L'inserimento prenderà sempre posto come foglia. Per questo se precede un numero nell'array, non può essere un suo successore.
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!
207
Matricola
*
Offline Offline

Posts: 95


« Reply #18 on: 22-05-2010, 17:53:01 »

Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (48, 1, 27, 17, 2, 24, 9, 26, 25).
Individuare il corretto output di una visita Preorder del suddetto albero dopo aver effettuato l'operazione LeftRotate(T,2)

Come si costruisce questo?
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #19 on: 22-05-2010, 18:05:02 »

inserimento:
Code:
         48
        /
      1
        \
         27
        /
      17
     /  \
   2  24
  /       \
 9        26
           /
          25
LeftRotate(T,2)
Code:
         48
        /
      1
        \
         27
        /
      17
     /   \
   9   24
    \      \
     2     26
           /
          25
PreOrder:
Quote
48 1 27 17 9 2 24 26 25
ti ricordo che nel PREorder la radice PREcede il proprio sottoalbero destro e sinistro nella visualizzazione.

Dimmi cosa non ti è chiaro spiegarti tutto qui è davvero difficile. L'esercizio comprende tre procedure, inserimento, rotate e visita.
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!
207
Matricola
*
Offline Offline

Posts: 95


« Reply #20 on: 22-05-2010, 18:16:26 »

L'esercizio di prima l'avevo capito dopo che l'ho postato, cmq grazie, invece non mi è chiara la rotazione destra di questo esercizio:

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

Questo è l'albero che ho costruito:

Code:

                                                                          7
                                                                        /  \
                                                                       6   36
                                                                            /  \
                                                                          20 49
                                                                            \   /
                                                                           28 45
                                                                           /
                                                                         24

Non riesco a ruotare correttamente.
« Last Edit: 22-05-2010, 18:27:24 by 207 » Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #21 on: 22-05-2010, 18:24:00 »

la rotazione destra l'ho descritta un pò più su. Comunque:
il 36 scende di un livello, il 49 suo figlio destro diventa padre del nodo di rotazione(che è suo figlio sinistro). Il vecchio padre di 36 è ora padre di 49. I sottoalberi sinistro del nodo di rotazione(36) e destro del nodo perno (49) rimangono tali. Mentre il nodo figlio sinistro del perno, diventa ora figlio destro di 36.
Chiaro adesso!?
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!
207
Matricola
*
Offline Offline

Posts: 95


« Reply #22 on: 22-05-2010, 18:31:58 »

Quasi chiaro, ma potresti postare l'albero dopo la rotazione per favore.
Logged
Federik88
Matricola
*
Offline Offline

Gender: Female
Posts: 96



« Reply #23 on: 22-05-2010, 19:13:03 »

@Federik il 45 o il 50 non possono precedere il 44 nell'albero, visto che non lo precedono nell'array di inserimento. Credo che tu abbia sbagliato nel suo inserimento.

Grazie cock86 per aver disegnato e spiegato l'esercizio, ora mi sono chiarita le idee. Non avevo sbagliato l'inserimento ma mi son confusa in altro. Provo a far altri esercizi per vedere se il tutto mi è chiaro nono  Grazie ancora!
« Last Edit: 22-05-2010, 19:16:59 by Federik88 » Logged
Federik88
Matricola
*
Offline Offline

Gender: Female
Posts: 96



« Reply #24 on: 22-05-2010, 19:50:05 »

credo che dopo la rotazione l'albero sia così :


                          7
                        /    \
                     6       49
                             /   \
                           20    36
                             \       \
                            28      45
                             /
                           24
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #25 on: 22-05-2010, 20:15:19 »

credo che dopo la rotazione l'albero sia così :


                          7
                        /    \
                     6       49
                             /   \
                           20    36
                             \       \
                            28      45
                             /
                           24
ehm.. no no!
il 36 (e tutto il suo sotto albero) diventa figlio sinistro del 49. Così:
                          7
                        /    \
                     6       49
                              /  \
                           36   45
                           /
                        20
                          \
                          28
                          /
                       24
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!
207
Matricola
*
Offline Offline

Posts: 95


« Reply #26 on: 23-05-2010, 15:27:41 »

La rotazione dell'albero va fatta a sinistra non a destra, l'output del preorder è:
7 6 20 36 28 24 49 45
Potreste postarlo correttamente?
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #27 on: 23-05-2010, 15:50:00 »

cpsì:
           7
          /   \
        6   20
                 \
                 36
                  /  \
               28   49
               /         \
             24        45

e l'output:
7 6 20 36 28 24 49 45
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!
207
Matricola
*
Offline Offline

Posts: 95


« Reply #28 on: 23-05-2010, 15:53:05 »

Adesso è chiaro!!
Logged
cock86
Forumista Eroico
*****
Offline Offline

Posts: 2.014


OM


« Reply #29 on: 23-05-2010, 15:56:08 »

comunque adesso la rotazione è a destra (come richiedeva l'esercizio) prima l'avevamo fatta a sinistra!
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!
Pages: 1 [2] 3 4   Go Up
Print
Jump to: