Ciao volevo chiedere se è possibile accedere all’ i-esimo elemento di un set in O(1) o O(logN).
Ho provato ad usare gli iteratori ma non sono riuscito a fare meglio di O(N). Esiste un modo oppure è impossibile? Grazie
Quale altre operazioni devi fare?
Esistono strutture che ti permettono di accedere all’iesimo elemento, modificarlo, oppure inserire un elemento in posizione X, come richiesto in Vasi 2 .
Avevo avuto un’ idea proprio per risolvere quel problema, volevo provare ad usare un set dato che per risolverlo serve un bbst e il set è un bbst.
L’unico problema che ho incontrato è quello di conoscere il valore nell’ i-esima posizione di un set in un tempo veloce
Si lo so è solo che volevo provare a “barare” e utilizzare i set che sono già implementati senza dover implementare da solo un bbst
I set si basano sulle chiavi tu devi basarti sulla posizione e quindi sulla grandezza dei sottoalberi.
Io personalemente ho scritto una versione modificata dell’AVL per risolvere vasi 2. Non nego che la logica e l’implementazione sono poco amichevoli.