Se dovessi farlo, probabilmente utilizzerei un albero bilanciato (ad esempio, AVL o rosso-nero) in cui ogni nodo tiene traccia delle dimensioni del suo sottoalbero sinistro (e tieni traccia del dimensione complessiva). Questo fungerebbe da indice in un buffer circolare che memorizza i dati stessi.

Quindi, quando arriva un nuovo oggetto, trovi il valore più vecchio nel buffer circolare. Cerca quel nodo nell'albero ed eliminalo [ O(log N) complessità]. Mentre scorri l'albero per eliminarlo, aggiorni il conteggio in ogni nodo, per indicare quale sottostruttura si sta riducendo.

Sovrascrivi quel nodo nel buffer circolare con il nuovo valore. Inserisci un nodo nell'albero per il nuovo valore [anche O(log N) complessità]. Di nuovo, mentre si scende la struttura per inserire il nuovo valore, si aggiornano i conteggi nei nodi per indicare la nuova dimensione della sottostruttura.

Trova la mediana attraverso l'albero - inizia dal nodo radice. Controlla la dimensione del sottoalbero sinistro per determinare se la mediana si trova nel sotto-albero sinistro o destro. Viaggia lungo l'albero fino a raggiungere la mediana. Poiché la profondità dell'albero è proporzionale al log N, questa operazione è anche O(log N) .

Questo lascia un dettaglio secondario: l'albero userà tipicamente l'allocazione dinamica. Tuttavia, è possibile evitare che si tratti di un problema abbastanza facilmente: pre-allocare un blocco di spazio per tutti i nodi dell'albero necessari. Costruiscile in (per esempio) un elenco collegato di nodi liberi. Quando hai bisogno di allocare un nodo, prendi sempre quello dalla testa della lista. Quando hai bisogno di liberare un nodo, basta aggiungerlo all'inizio della lista.

Una volta che il tuo albero è "pieno", basterà semplicemente aggiungere un nodo alla lista e riutilizzarlo immediatamente per creare il nuovo nodo. La "lista collegata" in pratica agirà come un puntatore a quel nodo solo quando è libero.

Questa è una raffinatezza dell'idea di Jerry Coffin.

• Utilizza un albero quasi bilanciato, in cui tutti i nodi risiedono direttamente nel buffer circolare.
• Inizializza con valori fittizi, in modo che la dimensione rimanga costante per tutto il tempo.
• Utilizza left , right e parent puntatori (o indici) in ciascun nodo.
• Archivia e gestisci rank in ogni nodo.
• Invece di rimuovere un inserimento di un elemento, sostituirlo sostituendolo semplicemente cambiando il valore.
• Dopo la sostituzione, l'albero di solito non è più ordinato.
• Utilizza le rotazioni per ripristinare l'ordine, ad esempio
  • C'è sempre al massimo un nodo che viola l'ordine.
  • L'albero mantiene la sua proprietà RB o AVL.

Fare ciò è sicuramente più veloce della rimozione e dell'inserimento di nodi. Quando sei fortunato, il nodo si sposta solo poche volte. Con una probabilità del 50%, il vecchio e il nuovo elemento appartengono allo stesso semipiano, ecc.

Le rotazioni devono essere ideate e questo può essere un po 'complicato, in quanto è necessario ripristinare l'ordine e anche mantenere l'albero bilanciato allo stesso tempo.

Suppongo che tu possa guadagnare un fattore quattro in questo modo, ma è solo una supposizione.