Implémentation Java IntervalTree DeleteNode

Question

J'ai besoin d'une implémentation IntervalTree ou RangeTree en Java et j'ai du mal à en trouver une avec support de suppression de travail.

Il en existe une version intégrée à sun.jvm.hotspot.utilities.IntervalTree , mais le deleteNode dans la superclasse RBTree indique:

/**
 * 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.
 */

Essayer de supprimer des noeuds d'une arborescence lève l'exception:

  

Le noeud final max n'a pas été mis à jour   correctement

Dans quelle mesure serait-il difficile d'implémenter correctement la fonctionnalité delete dans une sous-classe de sun.jvm.hotspot.utilities.IntervalTree? Ou existe-t-il une autre implémentation de l'arbre d'intervalle qui l'implémente déjà correctement?

Actuellement, j'efface l'arbre et je le re-peuple chaque fois qu'il y a une suppression, ce qui est loin d'être idéal (note: la définition de DEBUGGING = false dans l'arborescence RBTree accélère considérablement les choses).

Answer 1

J'ai fini par modifier le sun.jvm.hotspot.utilities.IntervalTree pour conserver un ensemble de nœuds supprimés. Lors d'une recherche, j'exclus tous les éléments de cet ensemble. Ce n’était pas idéal, mais c’était beaucoup plus facile que d’avoir " real " suppression fonctionne. Une fois que l'ensemble supprimé est devenu trop volumineux, je reconstruis l'arbre.

Answer 2

Ce projet a une implémentation de RangeTree qui pourrait vous être plus utile. Les forfaits solaires peuvent convenir à une utilisation rapide et délicate, mais je ne recommanderais pas de construire quoi que ce soit d’important en les utilisant. Sun ne peut pas les maintenir stables.

Answer 3

Je ne connais pas vos exigences exactes, mais un arbre de segment non statique pourrait fonctionner pour vous. Si tel est le cas, consultez logiciel de gestion de la mise en forme , plus précisément le SegmentTree forfait . Il a la fonctionnalité de suppression dont vous avez besoin.

Si vous décidez de lancer le vôtre, puis-je vous suggérer de l'ouvrir au sourcing? Je suis surpris qu'il n'y ait pas déjà un arbre d'intervalle ouvert et facile disponible.

Answer 4

l'implémentation ac # est basée sur une arborescence AVL augmentée @ http://code.google.com/ p / intervaltree / . la traduction en java ne devrait pas être trop difficile.

Answer 5

J'ai trouvé une implémentation à code source ouvert avec suppression, mais des efforts sont nécessaires pour la rendre entièrement fonctionnelle.

Il s’agit d’un module de projet plus vaste à code source ouvert Gephi , mais voici le sources et javadoc . Si vous voulez un pot, vous pouvez installer Gephi, et il se trouve dans:

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

La méthode de suppression utilisée ici supprime tous les intervalles qui se chevauchent avec l’intervalle d’entrée (au lieu de seulement l’intervalle d’entrée). Cependant, j’ai trouvé dans l’information que certaines méthodes privées suppriment un nœud spécifique (qui stocke un intervalle). Les méthodes de recherche privées renvoient également des nœuds.

Donc, je pense qu'avec un peu d'effort, il est possible de refactoriser le code et d'avoir ceci - la fonction 'supprimer un intervalle spécifique'. Le moyen le plus rapide et le plus sale serait simplement de rendre publiques les méthodes privées / la classe Node. Mais puisqu'il s'agit d'un projet open source, il pourrait peut-être évoluer à l'avenir vers une bonne implémentation standard de l'arbre d'intervalle.