Forum Ubuntu-it

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

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).

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

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. 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 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