IntervalTree DeleteNode Implementazione Java

Question

Ho bisogno di un'implementazione IntervalTree o RangeTree in Java e ho difficoltà a trovarne uno con supporto per la cancellazione funzionante.

Ce n'è uno integrato in sun.jvm.hotspot.utilities.IntervalTree , ma deleteNode negli stati della superclasse RBTree:

/**
 * FIXME: this does not work properly yet for augmented red-black
 * trees since it doesn't update nodes. Need to figure out exactly
 * from which points we need to propagate updates upwards.
 */

Cercare di eliminare i nodi da un albero finisce per generare l'eccezione:

  

L'endpoint massimo del nodo non è stato aggiornato   correttamente

Quanto sarebbe difficile implementare correttamente la funzionalità delete in una sottoclasse di sun.jvm.hotspot.utilities.IntervalTree? Oppure esiste un'altra implementazione di Interval Tree che lo implementa correttamente?

Attualmente sto solo cancellando l'albero e ripopolarlo ogni volta che c'è una cancellazione, che è tutt'altro che ideale (nota: impostare DEBUGGING = false nell'RBTree ha velocizzato le cose tremendamente).

Answer 1

Ho finito per modificare il sun.jvm.hotspot.utilities.IntervalTree per mantenere un insieme di nodi eliminati. Quando eseguo una ricerca, escludo qualsiasi elemento in questo set. Non è l'ideale, ma è stato molto più semplice che ottenere "reali". cancellazione funzionante. Quando il set eliminato diventa troppo grande, ricostruisco l'albero.

Answer 2

Questo progetto ha un'implementazione RangeTree che potrebbe esserti più utile. I pacchetti Sun potrebbero essere ok per un uso rapido e sporco, ma non consiglierei di costruire qualcosa di importante affidandoti a loro. Sun potrebbe non mantenerle stabili.

Answer 3

Non conosco i tuoi esatti requisiti, ma un albero dei segmenti non statico potrebbe funzionare per te. In tal caso, dai un'occhiata a SW di gestione del layout , in particolare il SegmentTree pacchetto . Ha la funzione di rimozione che ti serve.

Se decidi di fare il tuo, potrei suggerire di acquistarlo apertamente? Sono sorpreso che non sia già disponibile un Interval Tree aperto e semplice.

Answer 4

esiste un'implementazione ac # basata su un albero AVL aumentato @ http://code.google.com/ p / intervaltree / . la traduzione in java non dovrebbe essere troppo difficile.

Answer 5

Ho trovato un'implementazione open source con eliminazione, ma è necessario un certo sforzo per renderla perfettamente funzionante.

È un modulo di un più ampio progetto open source Gephi , ma ecco i fonti e javadoc . Se vuoi un barattolo puoi installare Gephi, ed è in:

/gephi/modules/org-gephi-data-attributes-api.jar

Il metodo di eliminazione lì, rimuove tutti gli intervalli che si sovrappongono con l'intervallo di input (anziché solo quello di input). Tuttavia, ho scoperto nei soruces che ci sono metodi privati ??che rimuovono un nodo specifico (che memorizza un intervallo). Anche i metodi di ricerca privati ??restituiscono nodi.

Quindi penso che con un po 'di sforzo sia possibile riformattare il codice e avere questa funzione' elimina intervallo specifico '. Il modo più veloce e più sporco sarebbe quello di rendere pubblici i metodi privati ??/ la classe Node. Ma dal momento che è un progetto open source, forse potrebbe evolversi in futuro in una buona implementazione standard dell'albero degli intervalli.