Treap con chiavi implicite

Question

C'è una struttura di dati chiamata treap: si tratta di un albero di ricerca binario randomizzato, che è anche un mucchio di cosiddette "priorità" generate casualmente.

C'è una variazione di questa struttura, dove le chiavi sono implicite, non sono memorizzate nell'albero, ma consideriamo l'indice ordinato del nodo nell'albero come la chiave di questo nodo. Abbiamo bisogno di memorizzare la dimensione della sottostruttura in ogni nodo anziché la chiave. Questa tecnica ci consente di pensare a treap come una sorta di array, che supporta molte operazioni nel tempo O (log N): inserimento, cancellazione, reversione di subarray, cambio di intervallo e così via.

Conosco un po 'di questa struttura, ma non così tanto. Ho provato a google, ma ho trovato solo un sacco di articoli su Treap, ma nulla su questa "lista implicita"/"elenco indicizzato". Non conosco nemmeno il suo nome, perché la mia lingua madre non è l'inglese e la lezione che ho ascoltato usava il termine nativo di struttura, non il termine originale inglese. Questo termine nativo può essere tradotto direttamente in inglese come "Treap on the implicit keys" o "Cartesian tree on the implicit keys".

Qualcuno può indicarmi l'articolo su questa struttura o dirmi il suo nome originale? Grazie.

P.S. Scusa se il mio inglese non era abbastanza comprensibile.

UPD: Qualche spiegazione in più sulla struttura che sto cercando.

Considera un consueto trionfo con priorità e chiavi scelti a caso, che sono dati utente reali memorizzati nell'albero. Immaginiamo di avere qualche altra informazione utente memorizzata in ogni nodo, e le chiavi non sono altro che le chiavi di ricerca. Il passo successivo è il calcolo e il mantenimento della dimensione del sottostrato in ogni nodo: dobbiamo aggiornare questo parametro dopo ogni unione/divisione/Aggiungi/Rimuovi, ma ci permette di trovare, per esempio, l'elemento Kth dell'albero in O (log N) tempo.

Quando abbiamo le dimensioni di sottostruttura in ogni nodo, possiamo gettare via le chiavi e immaginare che treap rappresenti una serie di dati utente in attraversamento inorder. L'indice di matrice di ciascun elemento può essere facilmente calcolato da dimensioni di sottostruttura. Ora possiamo aggiungere/rimuovere un elemento nel mezzo della matrice o dividere questo array - tutto in tempo O (log N).

Possiamo anche eseguire un'operazione "multipla", ad esempio aggiungere un valore costante a tutti gli elementi del nostro "array". Per implementare questa operazione, dobbiamo ritardare questa operazione, aggiungere un parametro in ogni nodo che rappresenta una costante ritardata che deve essere "successivamente" aggiunta a tutti gli elementi del sottoarray di questo nodo e "spingere" le modifiche verso l'alto come necessario. Aggiungendo una costante al sottoarray o alla pittura (marcatura) il subarray può essere ritardato in questo modo, invertendo il subarray (qui le informazioni ritardate nel nodo nel bit "subarray deve essere invertito"), e così via.

UPD2: Ecco il numero code snippet - parte della piccola quantità di informazioni che ho trovato. Non notare cirillico :) Le parole "с неявным ключом" significano nella traduzione diretta "con chiave implicita".

Answer 1

È possibile trovare questa struttura dati nel documento di Kaplan e Verbin sull'ordinamento delle permute firmate mediante inversioni (pagina 7, sezione 3.1): http://www.math.jussieu.fr/~fouquet/ENSEIGNEMENT/PROJETS/kaplan.pdf.

Answer 2

L'idea chiave (no pun intended!) In treaps è l'uso di chiavi, che sono randomizzate. Se rimuovi le chiavi, non vedo come si possa avere un trionfo: quindi forse ho frainteso la tua domanda. O forse ti stai riferendo all'alternativa a treaps, l'albero di ricerca binario randomizzato . Entrambe le strutture dati utilizzano la stessa idea che è possibile raggiungere la complessità del caso medio assicurandosi che il proprio albero assomigli ad un albero medio (invece che a un caso patologico).

Con i treap, lo si fa utilizzando priorità e bilanciamento casuali.

Con alberi binari randomizzati, la casualità è inclusa solo durante la costruzione: ovvero, quando si inserisce un nodo nell'albero T, ha probabilità 1/(dimensione (T) + 1) di essere alla radice, dove la dimensione (T) è il numero di nodi di T; e, naturalmente, se il nodo non è inserito nella radice, si continua in modo ricorsivo fino a quando non viene aggiunto. (Vedi articoli il mio C. Martinez per uno studio dettagliato di questi alberi.)

Questa struttura dati si comporta esattamente come un tracing, ma utilizza un meccanismo diverso che non richiede chiavi.

Se questo non è quello che stavi cercando, forse potresti condividere alcune informazioni aggiuntive: il tuo docente ha menzionato qualcuno che avrebbe potuto lavorare su questa struttura, dove hai fatto questo docente e quale/tua nazionalità. Potrebbe non sembrare così, ma conoscere la tua lingua nativa potrebbe essere un indizio importante in quanto puoi in genere abbattere algoritmi/strutture dati in un paese specifico che l'ha originato.

Answer 3

Non penso che ci sia un nome per quella struttura dati poiché è semplicemente una combinazione di due concetti ortogonali. Potresti usare chiavi implicite come questa con praticamente qualsiasi struttura di dati ad albero autoequilibrante.

Si potrebbe voler dare un'occhiata agli alberi di capro espiatorio, poiché usano già le dimensioni del sottostrato per il ribilanciamento e non richiedono alcun overhead per nodo.

Answer 4

Forse stai cercando uno Rope (forma di stringa complessa) modificato in base alle tue esigenze per le operazioni in ritardo. La cosa interessante è che esiste una domanda aperta riguardante le corde right here right now.