Treap con le chiavi implicite

Question

C'è una struttura di dati denominata treap:. Quello è un albero binario di ricerca randomizzati, che è anche un mucchio sul generati casualmente cosiddette "priorità"

C'è una variazione di questa struttura, dove le chiavi sono implicite, non sono memorizzati nella struttura, ma consideriamo l'indice ordinata del nodo nell'albero come chiave di questo nodo. Abbiamo bisogno di memorizzare dimensioni di sottostruttura in ogni nodo, invece di chiave. Questa tecnica ci permette di pensare a treap come una sorta di matrice, che supporta un sacco di funzionamento in O (log N) tempo:. Inserimento, cancellazione, reversione del sottoarray, cambiando su intervalli e così via

so un po 'su questa struttura, ma non così tanto. Ho cercato di google, ma ho trovato solo un sacco di articoli su treap in sé, ma nulla di questo "treap implicito" / "elenco indicizzato". Ho anche non so il suo nome, perché la mia lingua madre non è l'inglese e lettura ho ascoltato usato il termine originario di struttura, non originale inglese termine. Questo termine nativo può essere tradotto direttamente in inglese come "Treap sui tasti impliciti" o "albero cartesiano sui tasti implicite".

Qualcuno mi può punto l'articolo su questa struttura o mi dica il suo nome originale? Grazie.

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

UPD:. Qualche spiegazione in più sulla struttura Sto cercando

Si consideri un treap consueto con priorità e chiavi scelti casualmente, che sono dati utente effettivi memorizzati nella struttura. Poi Immaginiamo abbiamo qualche altra informazione utente memorizzate in ogni nodo, e le chiavi non sono altro che le chiavi di ricerca. Il passo successivo è il calcolo e mantenere la dimensione sottostruttura in ogni nodo: dobbiamo aggiornare questo parametro dopo ogni Merge / Split / aggiungere / rimuovere, ma permette di trovare, per esempio, elemento Kth dell'albero in O (log N) tempo.

Quando abbiamo dimensioni sottoalbero in ciascun nodo, possiamo buttare via le chiavi e immaginare che treap rappresenta una matrice di dati utente in ordine simmetrico. indice di campo di ciascun elemento può essere facilmente calcolata dimensioni sottoalbero. Ora possiamo aggiungere / rimuovere un elemento nel mezzo della matrice o dividere questo array - il tutto in O (log N) tempo

.

Possiamo anche rendere il funzionamento "multiplo" - per esempio, aggiungere un valore costante a tutti gli elementi della nostra "allineamento". Per implementare ciò, dobbiamo rendere questa operazione ritardato, aggiungere un parametro in ogni nodo che rappresenta una costante ritardo che deve essere "dopo" aggiunto a tutti gli elementi della sottomatrice di questo nodo, e "push" I cambiamenti al basso come necessario. Aggiungendo una costante di subarray o pittura (marcatura) sottoarray può essere fatta ritardare in questo modo, come invertendo la sottomatrice (qui le informazioni ritardato nel nodo del bit "sottomatrice deve essere invertita"), e così via.

UPD2: frammento di - pezzo della piccola quantità di informazioni che ho trovato. Non notare cirillico :) Parole "с неявным ключом" significa in traduzione diretta "con il tasto implicito".

Answer 1

È possibile trovare questa struttura dati nel lavoro di Kaplan e Verbin sull'ordinamento permutazioni firmati da inversioni (pagina 7, punto 3.1): http://www.math.jussieu.fr/~fouquet/ENSEIGNEMENT/PROJETS/kaplan.pdf .

Answer 2

L'idea chiave (senza giochi di parole!) In treaps è quello di utilizzare le chiavi, che sono randomizzati. Se si rimuove le chiavi, non vedo come si può avere un Treap: quindi forse ho frainteso la tua domanda. O forse si fa riferimento l'alternativa al treaps, randomizzati albero binario di ricerca . Entrambe le strutture di dati utilizzano la stessa idea che si può raggiungere la media complessità nel caso assicurandosi i vostri sguardi albero come un albero di media (al posto di un caso patologico).

Con i treaps, si esegue questa operazione utilizzando le priorità casuali e il bilanciamento.

Con randomizzati alberi binari, la casualità è incluso solo durante la costruzione: cioè, quando si inserisce un nodo albero T, ha probabilità 1 / (dimensioni (T) + 1) per essere alla radice, dove la dimensione (T) è il numero di nodi di T; e naturalmente se il nodo non è inserito alla radice, si continua ricorsivamente finché non viene aggiunto. (Vedi articoli mia C. Martinez per uno studio dettagliato di questi alberi.)

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

Se questo non è quello che cercate, forse si potrebbe condividere alcune informazioni aggiuntive è: ha fatto il tuo chiunque docente menzione che potrebbe aver lavorato su questa struttura, dove ha fatto qui questo docente e ciò che la sua / vostra nazionalità. Potrebbe non sembrare, ma conoscendo la tua lingua madre potrebbe essere un indizio importante, come si può generalmente piolo giù algoritmi / strutture dati ad un determinato paese che ha avuto origine esso.

Answer 3

Forse siete alla ricerca di un corda (forma complessa di stringa) modificato per le vostre esigenze per le operazioni di ritardo. La cosa interessante è che non è una questione aperta per quanto riguarda le corde proprio qui adesso .

Answer 4

Non credo ci sia un nome per quella struttura di dati dal momento che è semplicemente una combinazione di due concetti ortogonali. È possibile utilizzare i tasti impliciti in questo modo con qualsiasi struttura dati ad albero auto-bilanciamento.

Si potrebbe desiderare di dare un'occhiata al alberi capro espiatorio, dato che usano le dimensioni sottostruttura già per il riequilibrio e non richiedono alcun overhead per-nodo.