Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: Daréios89 on 04-10-2010, 11:45:47



Title: Sistema d'esercitazione e alberi binari
Post by: Daréios89 on 04-10-2010, 11:45:47
In una domanda del genere:

Quote
Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (43, 46, 19, 12, 47, 18, 3, 10, 2, 5).
Individuare il corretto output di una visita Postorder del suddetto albero dopo aver effettuato l'operazione Delete(T,10)

Non so come inserire bene le chiavi, io so che in un albero binario per ogni nodo, gli elementi più piccoli stanno a sinistra e gli altri a destra, ma come faccio a capire esattamente da dove iniziare?
Come fate voi?
Mi confondo nello stabilire cosa mettere nella radice, perchè poi quelli più grandi vanno a destra per dire...e quindi non posso mettere l'elemento più grande dell'insieme..come fate voi?


Title: Re:SIstema d'esercitazione e alberi binari
Post by: kry84 on 04-10-2010, 13:29:24
Devi inserirli in ordine di lettura: il primo elemento dell'array sarà la tua radice, gli altri li sistemi di conseguenza.
 .wink


Title: Re:Sistema d'esercitazione e alberi binari
Post by: Daréios89 on 04-10-2010, 13:34:47
Scusa ma non ho tutto chiaro:

Quote
Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (16, 30, 18, 50, 27, 40, 1, 49, 19).
Individuare il corretto output di una visita Preorder del suddetto albero dopo aver effettuato l'operazione Delete(T,27)

 

L'albero ha 9 nodi, e se non l'ho costruito male ha nell'ultimo livello due nodi figli del nodo più a sinistra, però qui come devo fare?

Cioè in radice metto 16, poi 30 e 18 sono entrambi più grandi, quindi ocsa gli metto a sinistra?
Non ho capito...

Mentre invece non ho capito quelli sulla procedura partition, cioè a dire il vero, non ho ben capito come funziona e cosa fa la procedura partition.. .poverinoi


Title: Re:Sistema d'esercitazione e alberi binari
Post by: kry84 on 04-10-2010, 13:51:31
Prova a dare un'occhiata a questo post:
http://forum.sdai.unict.it/index.php?topic=8310.15



Title: Re:Sistema d'esercitazione e alberi binari
Post by: Riki Chardo on 11-10-2010, 20:08:07
Scusa ma non ho tutto chiaro:

Quote
Sia dato un albero binario di ricerca, T, costruito mediante l'inserimento delle seguenti chiavi, in ordine di arrivo (16, 30, 18, 50, 27, 40, 1, 49, 19).
Individuare il corretto output di una visita Preorder del suddetto albero dopo aver effettuato l'operazione Delete(T,27)

 

L'albero ha 9 nodi, e se non l'ho costruito male ha nell'ultimo livello due nodi figli del nodo più a sinistra, però qui come devo fare?

Cioè in radice metto 16, poi 30 e 18 sono entrambi più grandi, quindi ocsa gli metto a sinistra?
Non ho capito...

Mentre invece non ho capito quelli sulla procedura partition, cioè a dire il vero, non ho ben capito come funziona e cosa fa la procedura partition.. .poverinoi

caro Daréios te  lo spiego in modo semplice e conciso cercando di fare un esempio un po grafico.

inseriamo in ordine
16, 30, 18, 50, 27, 40, 1, 49, 19
si parte dal 16 se l'albero è nullo bisogna mettere la radice quindi 16 alla radice

16

adesso 30
il 30 è piu grande quindi lo mettiamo a destra

     16
       \
       30

tocca al 18
il 18 va confrontato con 16 ed è piu grande quindi procedi continuando a fare i confronti verso destra
confrontiamo dunque il 18 con il 30.. è piu piccolo quindi andiamo a sinistra

         16
            \
             30
              /
            18

50

50-16 maggiore -> destra
50-30 maggiore -> destra

non appena trovi uno spazio vuoto lungo il tuo cammino inserisci l'elemento.

16
  \
  30
   /\
18 50

e cosi via spero di essere stato kiaro.


Title: Re:Sistema d'esercitazione e alberi binari
Post by: Daréios89 on 11-10-2010, 20:27:49
Aaaaaah ecco dove sbagliavo, non scendevo nell'albero.... :boh
Ora credo proprio di si....grazie  .wink