Come salvare la memoria quando si memorizzano le informazioni sul colore in Alberi rosso-nero?

Mi sono imbattuto in questa domanda in uno dei corsi sugli algoritmi di Coursera e mi sono reso conto che non ho idea di come farlo. Ma ancora, ho qualche idea a riguardo. La prima cosa che mi viene in mente è stata l'utilizzo di bit set ottimizzati (come Java BitSet) per ottenere il nodo di mappatura key -> color. Quindi, tutto ciò di cui abbiamo bisogno è allocare un set di un bit per l'intero albero e usarlo come fonte di informazioni sul colore. Se non ci sono elementi duplicati nell'albero, dovrebbe funzionare.Come salvare la memoria quando si memorizzano le informazioni sul colore in Alberi rosso-nero?

Sarebbe felice di vedere le idee di altri su questo compito.

fonte

2013-04-18 Vladimir Kostyukov

Utilizzare il bit meno significativo di uno dei puntatori nel nodo per memorizzare le informazioni sul colore. I puntatori del nodo dovrebbero contenere anche indirizzi sulla maggior parte delle piattaforme. Vedere i dettagli here.

fonte

2013-04-18 16:36:26

Hai assolutamente ragione che questo è l'approccio più comune. Tuttavia, in Java, questo non è possibile poiché Java non espone i bit dei suoi puntatori. L'OP potrebbe usare Java, anche se non sono sicuro che sia così. – templatetypedef

@templatetypedef La domanda non ha preso di mira esplicitamente Java, ha semplicemente menzionato una struttura dati simile a quella di Java, quindi potrebbe essere o non essere il caso. –

Giusto, non intendevo Java come obiettivo ma mi aspettavo una soluzione portatile (senza questi dettagli nudi metall). Ad ogni modo, non riesco nemmeno a capire questa risposta. @AlexeyFrunze, potresti spiegare l'idea più dettagliata (ad esempio in C e puntatori a 4 byte)? –

Un'opzione consiste nell'utilizzare un albero che richiede meno contabilità, ad es. a splay tree. Tuttavia, in particolare gli splay tree non sono molto utili per l'iterazione (sono molto più utili alla ricerca casuale), quindi potrebbero non essere adatti per il dominio in cui stai lavorando.

Puoi anche usarne uno BitSet per l'intero albero rosso-nero in base alla posizione del nodo, ad es la radice è il bit 0, il ramo sinistro della radice è il 1 ° bit, il ramo destro è il 2 ° bit, il ramo sinistro del ramo sinistro è il 3 ° bit, ecc; in questo modo non dovrebbe importare se ci sono elementi duplicati. Mentre attraversi l'albero, prendi nota della posizione in cui ti trovi.

È molto più efficiente in termini di spazio utilizzare un bitet per l'albero invece di assegnare un valore booleano a ciascun nodo; ogni booleano prenderà almeno un byte e può occupare una parola a seconda dell'allineamento, mentre il bitset occuperà solo un bit per nodo (più 2x bit per rappresentare un albero massimo sbilanciato dove il ramo più corto è la metà della lunghezza di il ramo più lungo).

fonte

2013-04-18 16:53:07

basta modificare l'albero BST. Per il nodo nero, non notare. E per il nodo rosso, scambia il suo bambino sinistro e figlio destro. In questo caso, un nodo può essere giustificato in rosso o in nero in base a se il figlio destro è più grande del figlio sinistro.

fonte

2015-07-26 02:49:54 icystar

Questo non funziona con nodi che non hanno due nodi figlio. –

Certo che lo fa: basta controllare se l'un nodo si trova nel posto sbagliato. Se ci sono nodi zero, non c'è nulla da verificare poiché non diamo mai al nodo Null un collegamento rosso. – lwassink

Invece di utilizzare la proprietà booleana su un figlio, potremmo definire un nodo rosso come quello che ha un figlio nel posto sbagliato.

Se andiamo in questo modo tutti i nodi foglia sono garantiti per essere neri e dovremmo scambiare il genitore con il fratello (rendendolo rosso) quando si inserisce un nuovo nodo.

fonte

2017-07-27 10:58:18

Come salvare la memoria quando si memorizzano le informazioni sul colore in Alberi rosso-nero?

risposta

Problemi correlati