Alve a tutti ragazzi, ho il seguente dubbio, sto realizzando una libreria in C per ricerca inserimento e rimozione da un albero binario rosso nero, chiaramente ogni nodo ha una chiave ed un valore. Ora alla libreria volevo aggiungere la possibilità di ricercare ad esempio il 5° elemento più grande secondo un altra chiave, le mie idee erano due, quella di tenere in memoria un array che viene aggiornato man mano in base all'inserimento nell'albero, quindi usando delle realloc ogni volta, inoltre ho anche pensato che se l'utente vuole cancellare un elemento dall'albero, devo farlo anche nel array, il che significa scorrerlo eliminare, shiftare e ri-allocare per liberare quella cella "doppia" dovuta alla eliminazione e allo shift. Tutto questo però ha un bel costo computazionale, l'inserimento nell'albero é log n + la ri-allocazione dell'array che suppongo ogni volta che aggiungo un elemento costa(n + 1), per un totale O(n^2 log n). Mentre l'eliminazione + shift riesco a farlo in O(n logn), mentre poi ri-allocare di nuovo suppongo costi (n - 1), quindi O(n^2 log n). Però in questo modo, usando una selezione deterministica ottengo il k-esimo elemento dall'array in O(n).
La mia seconda idea invece era quella portarmi dietro una variabile che indica il numero di nodi totali, poi quando l'utente vuole ricercare il k-esimo elemento, alloco memoria pari al numero di nodi, supponiamo n, poi inizio una visita dell'albero aggiungendo i nodi all'array che mi costa O(n), infine lancio la selezione deterministica, per un totale di O(n^2). Secondo voi quale potrebbe essere la soluzione migliore, ne esistono di migliori? Aggiungo anche che devo farlo senza usare le strutture dinamiche aumentate, quindi ho a disposizione solo questo array per la ricerca k-esima, e l'albero binario rosso nero.
Grazie a tutti in anticipo