D4rkAng3l
30-06-2008, 11:34
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
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