J'ai besoin d'un Intervaltree ou implémentation de RangeTree en Java et j'ai du mal à en trouver un avec Support de suppression fonctionnelle.
Il y a un intégré à Sun.jvm.hotspot.avalities.Intervaltree , mais le Suppression méthode dans la superclasse RBTREE STATS: P>
/** * 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. */
5 Réponses :
Ce projet a une implémentation de Rangètre qui pourrait être davantage utilisée pour vous. Les paquets Sun Sun pourraient être ok pour un usage rapide et sale, mais je ne recommanderais pas de construire quoi que ce soit important de s'appuyer sur eux. Le soleil peut ne pas les garder stables.
Merci pour le lien, Yishai. Je regarde les docs Olvai.sourceforge.net/tj / TJ-Javadoc-Public / TreeJuxtaposataire / ... et ne voyez aucun moyen d'obtenir une liste de nœuds pour une plage ou de modifier l'arborescence une fois créée. On dirait également qu'il y a des fuites de dépendance sur le projet d'interface graphique qu'ils l'utilisent. Je suppose que cela est très spécifique aux besoins de ce projet, et non à un régime à usage général. Avez-vous utilisé cette implémentation?
@Sam, non je ne l'ai pas utilisé. C'était juste l'alternative que je pouvais trouver. Comme il est open source, cela pourrait vous donner une meilleure base pour commencer avec la sous-classement de la mise en œuvre du soleil.
Je ne connais pas vos exigences exactes, mais un arbre de segment non statique peut fonctionner pour vous. Si tel est le cas, consultez Gestion de la mise en page SW , plus précisément la segmenttree Paquet . Il a la fonctionnalité Supprimer dont vous avez besoin.
Si vous décidez de rouler le vôtre, pourriez-je suggérer d'ouvrir l'approvisionnement? Je suis surpris qu'il n'y ait pas déjà d'arbre d'intervalle ouvert et facile à intervalles.
J'ai fini par modifier le sun.jvm.hotspot.utilité.Intervaltree pour maintenir un ensemble de nœuds supprimés. Lorsque vous effectuez une recherche, j'exclue les éléments de cet ensemble. Pas idéal, mais c'était beaucoup plus facile que d'obtenir une «vraie» suppression de travail. Une fois que l'ensemble supprimé devient trop grand, je reconstruit l'arbre.
Il y a une implémentation AC # basée sur un arbre AVL augmenté @ http://code.google.com/ p / intervaltree / . La traduction de Java ne devrait pas être trop difficile.
J'ai trouvé une implémentation open-source avec suppression, mais elle ne fait aucun effort pour le rendre pleinement fonctionnel.
C'est un module de projet open-source plus grand Gephi , mais voici le Sources et Javadoc . Si vous voulez un jar, vous pouvez installer Gephi, et c'est dans: la méthode de suppression là-bas, supprime tous les intervalles qui se chevauchent avec l'intervalle d'entrée (au lieu de simplement l'entrée ). Cependant, j'ai trouvé dans les sorcies qu'il existe des méthodes privées qui retirent un nœud spécifique (qui stocke un intervalle). De plus, les méthodes de recherche privées renvoient des nœuds. Donc, je pense que avec un peu d'effort, il est possible de refroidir le code et d'avoir cette fonctionnalité «Supprimer l'intervalle spécifique». La manière la plus rapide et la plus sale serait de rendre les méthodes privées / la classe de nœuds du public. Mais puisqu'il s'agit d'un projet open source, il pourrait peut-être évoluer à l'avenir dans une bonne implémentation standard d'arborescence d'intervalle.