Stavo facendo da tutor a uno studente che ha trovato questo compito. Richiede fondamentalmente una struttura dati con le seguenti caratteristiche:
Questa struttura dati esiste anche?
L'indizio per trovare la giusta struttura dati qui è che i requisiti ( diversi dai requisiti di spazio e accessibilità diretta ) sono quelli di un albero binario. Questo mi ha fatto pensare a come potresti modificare un albero binario per farlo soddisfare i requisiti.
Quello che puoi fare è serializzare in modo efficace in un array una traversata del primo ordine di un albero binario che memorizza un 1 o 0 per la presenza di ciascun elemento nell'insieme, o per i nodi non fogliari la presenza di uno qualsiasi dei nodi figlio. L'inserimento richiede quindi che i bit O (log n) siano impostati su 1, la cancellazione richiede che i bit O (log n) siano copiati da un nodo di trasmissione e che la massima sia una ricerca binaria. L'accesso diretto è ancora possibile perché i nodi foglia hanno lo stesso formato del vettore bit, ignorando i primi bit (n-1).
Esempio: n = 8, con gli elementi 2, 3, 4 e 6 impostati:
1 11 1110 01110100
^ root: some values are in the set
^^ second level: values present in both first and second halves
^^^^ third level: quarters 1,2, and 3 have members, but the final quarter is empty
^^^^^^^^ leaves, essentially the same as the bit vector described in the question.
Leggi altre domande sui tag data-structures complexity