Il mantenimento di un ordinamento efficiente in cui è possibile inserire gli elementi “in mezzo” qualsiasi due altri elementi l'ordine?

https://cs.stackexchange.com/questions/14708

16-10-2019
|

Domanda

Immaginate Ho un ordinamento su un mucchio di elementi in questo modo:

entrare descrizione dell'immagine qui

Quando una freccia $ X \ Y leftarrow $ significa $ X .

Al fine di rispondere in modo efficiente a domande come $ A \ stackrel {?} {<} D $, una sorta di etichettatura o di dati struttura è richiesto. Ad esempio, è possibile numerare i nodi da sinistra a destra, e quindi si può semplicemente fare integer confronto per rispondere alla domanda: {?} $ A \ stackrel {<} D \ implica 1 <4 \ implica T $. Sarebbe simile a questa:

entrare descrizione dell'immagine qui

Se il numero è l'ordinamento, e la lettera è solo un nome.

Ma cosa succede se si ha bisogno di inserire elementi "tra" gli altri due elementi in ordine, in questo modo:

entrare descrizione dell'immagine qui

Come si può mantenere un tale ordinamento? Con semplice numerazione, si esegue nel problema che non ci sono numeri interi "tra" $ 2,3 $ per l'uso.

Soluzione

Questo è noto come il "ordine di manutenzione" problema . C'è una soluzione relativamente semplice utilizzando $ O (1) $ tempo ammortizzato per entrambe le query e inserti. Ora, da "relativamente semplice", voglio dire che bisogna capire alcuni blocchi di costruzione, ma che una volta arrivati ??quelli, il resto non è difficile da vedere.

http://courses.csail.mit.edu/6.851/ spring12 / conferenze / L08.html

L'idea di base è una struttura di dati a due livelli. Il livello superiore è come la soluzione albero AVL da Realz Slaw, ma

I nodi sono direttamente etichettati con le stringhe di bit di lunghezza $ O (\ lg n) $ con un ordine che corrisponde al fine nell'albero. Confronto assume quindi costante di tempo
Un albero con un minor numero di rotazioni di un albero AVL è utilizzato, come un albero o di capro espiatorio di un albero di peso bilanciato, in modo relabellings avvengono meno frequentemente.

Il livello di fondo è le foglie dell'albero. Tale livello utilizza la stessa lunghezza di etichette, $ O (\ lg n) $, ma vale solo $ O (\ lg n) $ articoli in ogni foglia in un semplice legata lista. Questo ti dà abbastanza bit extra per etichettare in modo aggressivo.

Foglie diventi troppo grande o troppo piccolo ogni $ O (\ lg n) $ inserti, inducendo un cambiamento nel livello più alto, che prende $ O (\ lg n) $ tempo ammortizzato ($ \ Omega (n) $ peggiore tempo -case). Ammortizzato, questo è solo $ O (1) $.

Esistono

molto più complesso di strutture per l'esecuzione di aggiornamenti a $ O (1) $ tempo nel caso peggiore.

Altri suggerimenti

Al posto di semplice numerazione, si potrebbe diffondersi i numeri su una grande gamma (costante di dimensioni), come ad esempio integer minimo e massimi di un intero CPU. Poi si può continuare a mettere i numeri "in mezzo" dalla media dei due numeri circostanti. Se i numeri diventano troppo affollate (ad esempio si finisce con due interi adiacenti e non v'è alcun numero in mezzo), si può fare una sola volta rinumerazione dell'intero ordinamento, ridistribuendo i numeri in modo uniforme su tutta la gamma.

Naturalmente, è possibile eseguire nella limitazione che tutti i numeri all'interno della gamma della grande costante vengono utilizzati. In primo luogo, questo non è un di solito un problema, dal momento che il numero intero di dimensioni su una macchina è abbastanza grande in modo che se si ha più elementi che probabilmente non sarebbe entrare nella memoria in ogni caso. Ma se si tratta di un problema, si può semplicemente rinumerare con un più grande numero intero-range.

Se l'ordine di ingresso non è patologica, questo metodo potrebbe ammortizzare i renumberings.

Risposta query

Un semplice confronto intero può rispondere alla query $ \ left (X \ stackrel {?} {<} Y \ right) $.

Ora query sarebbe molto rapida ($ \ mathcal {O} \ left (1 \ right) $) se si utilizza interi della macchina, in quanto è un semplice confronto intero. Usando una gamma più ampia richiederebbe interi più grandi, e il confronto avrebbe preso $ \ mathcal {O} \ left (\ log {| integer |} \ right). $

inserimento

In primo luogo, si manterrebbe la lista collegata dell'ordinamento, ha dimostrato nella domanda. Inserimento qui, dato i nodi per posizionare il nuovo elemento di mezzo, sarebbe $ \ mathcal {O} \ left (1 \ right) $.

Etichettatura il nuovo elemento di solito essere veloce $ \ mathcal {O} \ left (1 \ right) $ perché si sarebbe calcolare il nuovo Numeber facilmente facendo la media dei numeri circostanti. Di tanto in tanto si potrebbe a corto di numeri "in mezzo", che farebbe scattare il $ \ mathcal {O} \ left (n \ right) $ procedura di rinumerazione tempo.

Evitare rinumerazione

È possibile utilizzare carri invece di numeri interi, in modo che quando si ottengono due numeri interi "adiacenti", hanno possono essere in media. Così si può evitare la rinumerazione di fronte a due galleggianti interi: basta dividere a metà. Tuttavia, alla fine del tipo virgola mobile si esaurirà di accuratezza, e due galleggianti "adacent" non sarà in grado di essere media (la media dei numeri circostanti probabilmente sarà pari ad uno dei numeri circostanti).

È possibile utilizzare allo stesso modo un intero "decimale", dove si mantiene due interi per un elemento; uno per il numero e uno per il decimale. In questo modo, si può evitare di rinumerazione. Tuttavia, l'intero decimale finirà troppo pieno.

Utilizzando una lista di numeri interi o di bit per ciascuna etichetta può evitare del tutto la rinumerazione; questo è fondamentalmente equivale all'utilizzo numeri decimali con lunghezza illimitata. Il confronto sarebbe stato fatto lessicografico, ed i tempi di confronto aumenterà alla lunghezza delle liste coinvolte. Tuttavia, questo può sbilanciare l'etichettatura; alcune etichette potrebbero richiedere solo un numero intero (senza decimali), altri potrebbero avere un elenco di lunga durata (decimali lunghi). Questo è un problema, e rinumerazione può aiutare anche qui, ridistribuendo la numerazione (qui elenchi di numeri) in modo uniforme su una gamma scelta (campo di qui forse significa lunghezza delle liste) in modo che dopo un tale rinumerazione, le liste sono tutti della stessa lunghezza .

Questo metodo in realtà è effettivamente utilizzato in questo algoritmo ( implementazione href="https://code.google.com/p/transitivity-utils/">, relevant ); nel corso dell'algoritmo, un ordinamento arbitrario deve essere mantenuta e gli usi autore interi e rinumerazione per realizzare questo.

Cercando di attenersi ai numeri rende il vostro spazio chiave un po 'limitato. Si potrebbe utilizzare lengt variabileh stringhe invece, utilizzando logica di confronto "a" < "ab" < "B". Ancora due problemi restano da risolvere A. Le chiavi potrebbero diventare arbitrariamente lungo B. Lungo confronto chiavi potrebbe diventare costoso

È possibile mantenere un albero Key-less AVL o simili.

E 'avrebbe funzionato come segue: L'albero mantiene un ordinamento sui nodi proprio come un albero AVL normalmente lo fa, ma invece del tasto determinare dove il nodo "deve" mentire, non ci sono chiavi, e si deve esplicitamente Inserire il nodi "dopo" altro nodo (o in altre parole "tra" due nodi), dove "dopo" significa che viene dopo di attraversamento in ordine dell'albero. L'albero sarà quindi mantenere l'ordine per voi, naturalmente, e sarebbe anche bilanciare, a causa della AVL incorporato nelle rotazioni. Ciò manterrà tutto uniformemente distribuita automaticamente.

inserimento

Oltre all'inserimento regolare nella lista, come dimostrato nella domanda, manterrebbe un albero AVL separata. Inserimento alla lista stessa è $ \ mathcal {O} \ left (1 \ right) $, come si deve il "prima" e "dopo" i nodi.

tempo inserimento nella struttura è di $ \ mathcal {O} \ left (\ log {n} \ right) $, lo stesso che l'inserimento di un albero AVL. Inserimento implica avere un riferimento al nodo che si desidera inserire dopo, ed è sufficiente inserire il nuovo nodo nella sinistra del nodo più a sinistra del figlio destro; questa posizione è "prossimo" in ordine dell'albero (che è accanto a l'attraversamento in ordine). Poi fanno i tipici rotazioni AVL per riequilibrare l'albero. Si può fare un'operazione simile per "Inserisci prima"; questo è utile quando è necessario inserire qualcosa nella all'inizio della lista, e non v'è alcun nodo "prima" del nodo.

Risposta query

Per rispondere alle domande di $ \ left (X \ stackrel {?} {<} Y \ right) $, è sufficiente trovare tutti gli antenati di $ X $ e $ Y $ nella struttura, e si analizza la posizione di dove nella struttura antenati divergono; quella che diverge verso "sinistra" è il minore dei due.

Questa procedura richiede $ \ mathcal {O} \ left (\ log {n} \ right) $ tempo a salire l'albero alla radice e di ottenere le liste degli antenati. Se è vero che questo sembra più lento di confronto intero, la verità è, è lo stesso; solo che il confronto intero su una CPU è delimitata da una grande costante per renderlo $ \ mathcal {O} \ left (1 \ right) $; se abbondare questa costante, è necessario mantenere multipli interi ($ \ mathcal {O} \ left (\ log {n} \ right) $ interi in realtà) e fare la stessa $ \ mathcal {O} \ left (\ log { n} \ right) $ confronti. In alternativa, è possibile "legata" l'altezza dell'albero di una quantità costante, e "barare" allo stesso modo la macchina fa con numeri interi: ora query sembreranno $ \ mathcal {O} \ left (1 \ right) $