Come mantenere minimo e massimo il tempo di O (1) in un albero di ricerca binario bilanciato, senza muovere intorno con i puntatori?

L'accise 3-7 nel "Manuale Algorithm Design" libro dice:Come mantenere minimo e massimo il tempo di O (1) in un albero di ricerca binario bilanciato, senza muovere intorno con i puntatori?

Supponiamo di avere accesso a una struttura di dati dizionario equilibrata, che sostiene ognuno di ricerca operazioni, inserimento, cancellazione, minimo, massimo, successore e il predecessore in O (log n) time. Spiegare come modificare le operazioni di inserimento ed eliminazione in modo che continuino a prendere O (log n) ma ora minimo e massimo richiedono O (1) tempo. (Suggerimento: pensare in termini di utilizzo delle operazioni di dizionario astratte, invece di pasticciare in giro con puntatori e simili.)

Senza i suggerimenti, credo che questa domanda è abbastanza facile.

Ecco la mia soluzione:

per l'albero, ho appena mantenere un puntatore min punta sempre al minimo, e un altro indice di massima che punta sempre al massimo.

Quando si inserisce x, confronto solo il tasto min. Con x.key, if min.key > x.key, then min = x; e lo faccio anche per il massimo, se necessario.

Quando si elimina x, if min==x, then min = successor(x); if max==x, then max = predecessor(x);

Ma il suggerimento dice che non posso pasticciare in giro i puntatori e simili. La mia soluzione è in discussione con i puntatori?

Se non è possibile utilizzare punti extra, come posso ottenere O (1) per il minimo e il massimo?

Grazie

fonte

2012-03-07 Jackson Tale

La mia ipotesi è, la soluzione è quella che chiedi nella domanda, dal momento che cambi il 'insert' e' cancella le operazioni, ma mantenendole su O (log n) perché ciò che fai è O (log n) del vecchio 'insert' /' delete' più O (log n) per 'successor' o' predecessore', che rimane su O (log n) in totale. E non stai giocando con i puntatori qui, perché in realtà mantieni il valore 'min' e' max'. – stryba

@stryba, l'ho pensato anch'io. Ma hanno bisogno di chiarimenti. –

Non sono chiaro sulla parte "mucking with pointers". La mia ipotesi è che non si debba puntare ai valori massimi/minimi precedenti e piuttosto usare il successore ecc. – stryba

La risposta è la stessa che darei - che non stai pasticciano con i puntatori , stai solo memorizzando i valori min/max.

Così, tanto per essere più sicuri :)

fonte

2012-03-07 16:19:34

sei sicuro? Ho solo paura che un giorno un'intervistatore mi faccia questa domanda, ma ho risposto in modo sbagliato. –

@Jackson: Ancora una volta, ** confidenza ** :) Questo è più importante per un colloquio rispetto alla tua capacità di risolvere i puzzle degli algoritmi sciocchi, comunque –

Io non credo che si possa ottenere O (1) sia per il massimo e mininum.

Ad ogni modo, il libro vuole scoprire da solo binary heaps. Non guardare il link se vuoi farlo da solo. Considera solo questo suggerimento: "La radice dell'albero contiene sempre il valore minimo" (o il valore massimo se vuoi "massimo" essere O (1)).

fonte

2012-03-07 14:04:32

gli heap binari sono buoni suggerimenti. ma la cosa è che la domanda nel libro diceva "ora minimo e massimo richiede O (1) tempo", se si usa l'heap, allora sarà come quello che hai detto, non possiamo ottenere O (1) per entrambi a lo stesso tempo. Sei sicuro dei tuoi suggerimenti? –

Sì, il mio suggerimento funziona solo per min o max, non per entrambi. Non vedo che puoi ottenere entrambi senza modificare la tua struttura. O (1) significa "in un numero fisso di operazioni". Significa che min e max dovrebbero essere vicini alla parte superiore dell'albero, il che non funziona se si desidera mantenere O (log n) per inserimento/eliminazione. –

pensi che i tuoi suggerimenti su questa accisa possano essere in qualche modo sbagliati? –

È possibile ottenere log (N) il tempo per l'aggiornamento/cancellare e costante di tempo per ottenere il/massimo valore minimo utilizzando Min-Max Heaps

fonte

2012-03-07 15:09:06 silviupop

Non credo che 'delete' debba essere limitato al minimo e al massimo, quindi in un Min-Max-Heap,' delete' includerebbe una ricerca O (N). –

userei due heap binari: un minimo e un mucchio max. In ognuno di essi viene memorizzata metà degli elementi e in questo modo è possibile accedere a max e min in O (1). L'heap minimo contiene la metà con gli elementi più piccoli e il massimo accumula la metà con gli elementi più grandi. Le operazioni di inserimento/cancellazione sarebbero ancora tutte O (log n). Quando si inserisce un nuovo elemento è sufficiente verificare su quale heap deve andare.

fonte

2012-03-07 19:06:28

Memorizzare due valori, il massimo e il minimo. Questi devono essere controllati e potenzialmente aggiornati ad ogni eliminazione. Se viene eliminato un minimo, chiamare il successore, aggiornare il minimo ed eliminare il vecchio elemento.Inserito, confronta il nuovo oggetto con min/max, se sostituisce un aggiornamento il minimo/massimo di conseguenza

fonte

2014-06-18 02:48:44 Shivi

Come mantenere minimo e massimo il tempo di O (1) in un albero di ricerca binario bilanciato, senza muovere intorno con i puntatori?

risposta

Problemi correlati