Progettare algoritmo

[matteo1095]

Salve ragazzi mi sto preparando per l'esame e stavo provando a fare questo esercizio però non ho un idea chiara su come svolgerlo. Io pensavo di visitare l'albero con una visita in-order (simmetrica), mettere il risultato in un array e poiché (se non sbaglio) l`array dopo la visita in-order dovrebbe essere ordinato in modo crescente se non lo è significa che ci sono errori e allora lo riordino.
Io pensavo di fare una cosa del genere ma questo non impiega certamente O(n) e non sono poi così sicuro che sia una cosa fattibile.. avete suggerimenti

[SuperStep]

non devi ordinare l'albero. Come c'e' scritto devi ordinare solo _due_ elementi fuori posto.

Io farei una ricerca ricorsiva InOrder dove passerei il riferimento ad una classe che tiene traccia degli elementi fuori posto finche' trovati < 2, altrimenti si ferma.

Quando si ferma controllare se trovati == 2.

Se trovati == 2 invertire trovato[0] con trovato[1].

[edit]

il tempo nel caso peggiore come in questo caso e' O(n). Altrimenti e' O(numero-attraversamenti).

Poi devi sommare il tempo di scambio. che per inciso e' scambio(1).

quindi:
peggiore = O(n) + scambio(1).
migliore = O(2) + scambio(1).

[matteo1095]

SuperStep non riesco a capire una cosa come faccio a fargli capire che ad esempio l 80 è fuori posto in quanto rispetto al 20 è in posizione giusta ma rispetto il 40 e la radice no. Questi abr non mi sono chiari

[SuperStep]

mmm... effettivamente non avevo dato sguardo a questa cosa.

Dal grafico possiamo capire che l'albero e' non ordinato poiche' un discendente del figlio sinistro e' piu' grande del nodo in considerazione (80 > 40).

Mentre dall'altra parte abbiamo che un discendente del figlio destro e' piu' piccolo del nodo in considerazione (30 < 50).

Allora esistono degli algoritmi chiamati inOrder Traversal, che in particolare ti fanno attraversare tutto l'albero per cercare gli elementi in ordine: http://en.wikibooks.org/wiki/A-level_Co ... inary_tree

una soluzione efficiente che ho trovato a questo url: http://www.geeksforgeeks.org/a-program- ... st-or-not/ (soluzione 3)

che ti evita di fare avanti ed indietro e quella di utilizzare due variabili MIN e MAX. Faccio un esempio utilizzando un pivout che chiamo MIN e MAX sostituito al valore dell'elemento root.

facciamo le cose Step By Step:

Siamo al nodo root, quindi MIN:50, MAX:50 andiamo in order, per ogni elemento ovviamente controllo se si trova a sinistra che sia piu' piccolo del padre, se si trova a destra che sia piu' grande del padre.

Codice: Seleziona tutto

andando a sinistra di 50 siamo sul nodo 40. 40 > MAX? no OK! (MAX: 50)
andiamo a sinistra di 40  siamo sul nodo 20. 20 > MAX? no OK! (MAX: 50)
andiamo a sinistra di 20 siamo sul nodo 10. 10 > MAX? no Ok! (MAX: 50)
10 non ha figli. saliamo su nodo 20
andiamo a destra di 20 siamo sul nodo 80. 80 > MAX? si -> salvare nodo 80 come primo match.
80 non ha figli saliamo sul nodo 20
saliamo sul nodo 40
andiamo a destra del nodo 40 siamo sul nodo 45. 45 > MAX? no OK! (MAX: 50)
45 non ha figli saliamo sul nodo 40
saliamo sul nodo 50.

Stessa cosa per gli elementi a destra della radice.

Il metodo 4 suggerito nel link di sopra, riporta una soluzione di spostare gli elementi in un array usando il metodo In-Order Traversal, dopo di che controllare se l'array e' ordinato. Se non e' ordinato cercare di prendere gli elementi fuori posto.

In questo caso avremmo un array del tipo

Codice: Seleziona tutto

10, 20, 80, 40, 45, 50, 100, 30

ovviamente gli elementi fuori posto sono 80 e 30.

Pero' in questo caso la durata e'
O(n) + P(n) + scambio(1)

O(n) = inOrder Traversal
P(n) = isInOrder Array