Pages: [1]   Go Down
Print
Author Topic: Alberi Binari: Sistema di esercitazione  (Read 1574 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
milos224
Forumista
***
Offline Offline

Posts: 830


« on: 29-09-2011, 16:46:57 »

Per quanto riguarda il sistema di esercitazione non so fare questo tipo di esercizio.

Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (30, 28, 35, 49, 10, 19, 9, 2).
Individuare il corretto output di una visita Preorder del suddetto albero dopo aver effettuato l'operazione RightRotate(T,30).

So cos'è una visita in Preorder,Inorder,e PostOrder ma non so cosa voglia dire il resto dell'esercizio, ovvero l'inserimento delle chiavi in ordine di arrivo,e il RightRotate(T,30). Inoltre l'esercizio ha delle varianti: l'ultima parte può cambiare. Al posto di RightRotate trovo a volte LeftRotate( ), Insert ( ) e Delete ( ). Qualcuno che mi illumini?

L'output in questo caso è il seguente: 28,10,9,2,19,30,35,49.
Logged
jos90
Apprendista Forumista
**
Offline Offline

Posts: 171



« Reply #1 on: 29-09-2011, 17:37:20 »

L'inserimento delle chiavi in ordine di arrivo consiste nel creare un albero binario scrivendo una alla volta le chiavi così come ti sono date, ed essendo binario devi scegliere se le chiavi successive siano da mettere o come figli sinistri o figli destri di un'altra determinata chiave, questo lo puoi fare confrontandola nuova chiave con la chiave preesistente vedendo se è piu piccola o piu grande, per esempio:

Code:
(prima chiave quindi la radice di                                     30                      
quest'albero binario di ricerca)                                      /    \
(figlio sinistro perchè è piu piccolo di 30)                     28   35 (perchè è piu grande)
                                                                                 /         \ (piu grande di 30 e 35 quindi..)
                                                                             10         49
                                                                              \
(nel caso del 19 esisteva già                                   19
 una piu piccola di 28..)    (..ma essendo piu grande diventa suo figlio destro)

Insomma l'albero viene

Code:
                30                      
                /    \
             28      35
             /           \
          10           49
        /     \
       9     19
      /
    2

Spero di essere stato chiaro, non credo d'aver fatto gaf in quanto così gli esercizi mi risultano XD
Per quanto riguardano i RightRotate e LeftRotate ci sono decine di discussioni, se capisci l'inserimento credo ti verrà piu facile comprendere questi due algoritmi, che d'altronde non sarò capace di spiegarti ma ti metterò solo confusione in testa.. per questo ti rimando a http://forum.sdai.unict.it/index.php?topic=8217.0 quest'altro topic che mi è stato molto utile, per insert si tratta di inserire nello stesso modo in cui hai creato l'albero una nuova chiave, per delete invece rimuoverla e collegare gli eventuali nodi al padre della chiave rimossa!
« Last Edit: 29-09-2011, 17:40:36 by jos90 » Logged

Perchè non pensi di non capire, quando capisci di non pensare?
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #2 on: 30-09-2011, 11:30:16 »

L'inserimento delle chiavi in ordine di arrivo consiste nel creare un albero binario scrivendo una alla volta le chiavi così come ti sono date, ed essendo binario devi scegliere se le chiavi successive siano da mettere o come figli sinistri o figli destri di un'altra determinata chiave, questo lo puoi fare confrontandola nuova chiave con la chiave preesistente vedendo se è piu piccola o piu grande, per esempio:

Code:
(prima chiave quindi la radice di                                     30                      
quest'albero binario di ricerca)                                      /    \
(figlio sinistro perchè è piu piccolo di 30)                     28   35 (perchè è piu grande)
                                                                                 /         \ (piu grande di 30 e 35 quindi..)
                                                                             10         49
                                                                              \
(nel caso del 19 esisteva già                                   19
 una piu piccola di 28..)    (..ma essendo piu grande diventa suo figlio destro)

Insomma l'albero viene

Code:
                30                      
                /    \
             28      35
             /           \
          10           49
        /     \
       9     19
      /
    2

Spero di essere stato chiaro, non credo d'aver fatto gaf in quanto così gli esercizi mi risultano XD
Per quanto riguardano i RightRotate e LeftRotate ci sono decine di discussioni, se capisci l'inserimento credo ti verrà piu facile comprendere questi due algoritmi, che d'altronde non sarò capace di spiegarti ma ti metterò solo confusione in testa.. per questo ti rimando a http://forum.sdai.unict.it/index.php?topic=8217.0 quest'altro topic che mi è stato molto utile, per insert si tratta di inserire nello stesso modo in cui hai creato l'albero una nuova chiave, per delete invece rimuoverla e collegare gli eventuali nodi al padre della chiave rimossa!

Per l'inserimento si procede allo stesso modo come se sto inserendo un altro elemento? E per la rimozione? Se in questo caso volessi togliere il 19?
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #3 on: 30-09-2011, 12:35:35 »

Il 19 è una foglia quindi può essere rimosso senza modificare altro.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #4 on: 30-09-2011, 15:11:28 »

Il 19 è una foglia quindi può essere rimosso senza modificare altro.
Che cretino che sono, volevo dire il 10..
Logged
jos90
Apprendista Forumista
**
Offline Offline

Posts: 171



« Reply #5 on: 30-09-2011, 16:31:53 »

si lo puoi rimuovere e i figli di 10 diventano figli di 28
Logged

Perchè non pensi di non capire, quando capisci di non pensare?
milos224
Forumista
***
Offline Offline

Posts: 830


« Reply #6 on: 30-09-2011, 16:52:16 »

si lo puoi rimuovere e i figli di 10 diventano figli di 28
e 19 che è minore di 28 diventa lo stesso un figlio destro?
Logged
jos90
Apprendista Forumista
**
Offline Offline

Posts: 171



« Reply #7 on: 01-10-2011, 11:28:18 »

Credo che non ci sia nessuno spostamento ulteriore se non quello dell'associazione dei figli in corrispondenza di com'erano prima del delete.. a te risulta in questo modo?
Logged

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