IntervalTree DeleteNode Implementación de Java

Question

Necesito una implementación de IntervalTree o RangeTree en Java, y tengo problemas para encontrar una con soporte de eliminación de trabajo.

Hay un built-in de uno en sun.jvm.hotspot.utilities.IntervalTree, pero el método deleteNode en los estados superclase 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. 
*/ 

Tratando de eliminar nodos de un árbol termina lanzando la excepción:

Nodo de el punto final máximo no se actualizó correctamente

¿Qué tan difícil sería pr Operly implementar la funcionalidad delete en una subclase de sun.jvm.hotspot.utilities.IntervalTree? ¿O hay otra implementación de Interval Tree que ya implementa esto correctamente?

Actualmente estoy acabando con el árbol y volviéndolo a poblar cada vez que hay una eliminación, que está lejos de ser ideal (nota: establecer DEBUGGING = false en el RBTree aceleró enormemente).

Answer 1

Terminé modificando el sun.jvm.hotspot.utilities.IntervalTree para mantener un conjunto de nodos eliminados. Al hacer una búsqueda, excluyo cualquier elemento en este conjunto. No es ideal, pero esto fue mucho más fácil que trabajar con eliminación "real". Una vez que el conjunto eliminado se vuelve demasiado grande, reconstruyo el árbol.

Answer 2

tiene una implementación de RangeTree que podría ser más útil para usted. Los paquetes solares podrían estar bien para un uso rápido y sucio, pero no recomendaría construir algo importante dependiendo de ellos. Sun no puede mantenerlos estables.

Answer 3

No conozco sus requisitos exactos, pero un árbol de segmentos no estático podría funcionar para usted. Si es así, eche un vistazo a Layout Management SW, específicamente el SegmentTree package. Tiene la función de eliminar que necesita.

Si decides enrollar el tuyo, ¿podría sugerirte abrirlo? Me sorprende que ya no haya un Árbol de Intervalos abierto y fácil.

Answer 4

hay una implementación de C# basada en un árbol AVL aumentado @http://code.google.com/p/intervaltree/. la traducción a Java no debería ser demasiado difícil.

Answer 5

Encontré una implementación de código abierto con eliminación, pero requiere un poco de esfuerzo para que sea completamente funcional.

Es un módulo del proyecto de código abierto más grande Gephi, pero aquí están los sources y javadoc. Si quieres un frasco puede instalar el Gephi, y está en:

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

El método de eliminación allí, elimina todos los intervalos se solapan con el intervalo de entrada (en lugar de sólo la entrada de uno). Sin embargo, encontré en las versiones que hay métodos privados que eliminan un nodo específico (que almacena un intervalo). Además, los métodos de búsqueda privados devuelven nodos.

Así que creo que con un poco de esfuerzo es posible refactorizar el código y tener esto: función 'borrar intervalo específico'. La manera más rápida y sucia sería simplemente hacer que los métodos privados/clase de nodo sean públicos. Pero dado que es un proyecto de código abierto, tal vez podría evolucionar en el futuro hacia una buena implementación estándar del árbol de intervalos.