[algoritmo] Operazioni su albero AVL

[D4rkAng3l]

Ciao,
ho questo esercizio di un vecchio compito d'esame:

Dato un albero AVL con n chiavi e un intero k <= n, rea-
lizzare un algoritmo che restituisca l'elemento che occupa la k-esima posizione nella sequenza ordinata delle chiavi.
ATTENZIONE: l'esercizio sarµa valutato solo se corre-
dato da adeguata descrizione del funzionamento dell'algoritmo, in base ai seguenti
parametri: correttezza, e±cienza e analisi di complessitµa.

La mia idea è la seguente ed essendo differente dalle 3 proposte dal professore vi chiedo se secondo voi è corretta.

Nell'albero AVL gli elementi vengono inseriti e mantenuti in determinate posizioni in base al valore delle loro chiavi.

Il mio algoritmo sarà una funzione che come parametri prende di input avrà un albero AVL (puntatore alla radice per esempio) ed un valore intero k minore del numero dei nodi.
Come output mi restituirà l'elemento che occupa la k-esima posizione (il puntatore al nodo con chiave k).

Gli alberi AVL sono alberi binari di ricerca quindi posso trovare facilmente il minimo scorrendo fino al nodo all'estrema sinistra (vabbè la tecnica standard per trovare il nodo).

A questo punto il minimo occuperà la posizione 1 nella sequenza ordinata in base ai valori delle chiavi. Effettuo per k volte l'estrazione del successore e quello sarà il k-esimo elemento da restituire (restituisco allora il puntatore a quel nodo)...

Cioè per esempio se k=3

Trovo il minimo e salto al successore del minimo (che è per definizione il secondo nodo più piccolo), a questo punto salto al successore di tale nodo, salto ancora al successore del precedente nodo: ho trovato il nodo in posizione k=3 nella sequenza ordinata in base alla chiave.

Per quanto riguarda la correttezza credo che sia banalmente giustificabile per costruzione in quanto partendo dal minimo che è l'elemento in posizione 1 della sequenza ordinata per costruzione di volta in volta salto al successore che per definizione è l'elemento minimo più grande del nodo in questione presente nell'albero. Volendo forse lo potrei anche dimostrare per induzione ma mi pare non ce ne sia bisogno.

Per quanto riguarda la complessità: Visto che l'albero è AVL quindi bilanciato in altezza la ricerca del minimo impiegherà tempo O(log(n)) operazioni per arrivare fino al nodo del minimo e poi k salti al successore che credo che nel caso peggiore sia k=log(n) quindi la complessità totale sarebbe O(log(n)) anche se non vorrei dire cavolate....comunque eventualmente non fosse così sarebbe sempre O(k*log(n)) = O(log(n))

Ci può stare? Secondo voi la mia soluzione può essere considerata corretta.

Grazie
Andrea

[gugoXX]

La complessita' del tuo algoritmo e'
O(n/2 log n), ovvero O( n log n)

In quanto alla meglio quando vuoi il primo, hai O(log n)
quando invece vuoi l'ultimo hai O(n log n)
In media appunto O(n/2 Log(n)) = O(n log n);

[D4rkAng3l]

Originariamente inviato da gugoXX

La complessita' del tuo algoritmo e'
O(n/2 log n), ovvero O( n log n)

In quanto alla meglio quando vuoi il primo, hai O(log n)
quando invece vuoi l'ultimo hai O(n log n)
In media appunto O(n/2 Log(n)) = O(n log n);

Si...lui chiede sempre la stima del caso peggiore...quindi per te è corretto? me lo avrebbero dato buono?

[gugoXX]

Io ti direi che non e' sufficiente. O meglio, il criterio di efficienza non e' superato.

Costerebbe di meno svolgere l'albero interamente in una array e andare a cercare la i-esima posizione all'interno dell'array svolto, con complessita' O(N) che e' quella per costruire l'array.

Tip: Come faresti a dire quanti elementi contiene l'albero?
Occorre contarli uno ad uno.
Riesci a trovare un modo per contarli in ordine? (Nell'ordine logico di successione dei valori)

[D4rkAng3l]

Originariamente inviato da gugoXX

Io ti direi che non e' sufficiente. O meglio, il criterio di efficienza non e' superato.

Costerebbe di meno svolgere l'albero interamente in una array e andare a cercare la i-esima posizione all'interno dell'array svolto, con complessita' O(N) che e' quella per costruire l'array.

Tip: Come faresti a dire quanti elementi contiene l'albero?
Occorre contarli uno ad uno.
Riesci a trovare un modo per contarli in ordine? (Nell'ordine logico di successione dei valori)

Capito,
quella era una delle 3 soluzioni che aveva scritto il mio proff però nel testo non chiedeva un limite in complessità per garantire una certa efficienza...a volte la chiede, altre volte no