Java-реализация IntervalTree DeleteNode

Question

Мне нужна реализация IntervalTree или RangeTree в Java, и у меня возникли проблемы с поиском ее с работающей поддержкой удаления.

Есть встроенный в sun.jvm.hotspot.utilities.IntervalTree , но метод deleteNode в состояниях суперкласса 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.
 */

Попытка удалить узлы из дерева приводит к исключению:

Максимальная конечная точка узла не была обновлена правильно

Насколько сложно было бы правильно реализовать функциональность delete в подклассе sun.jvm.hotspot.utilities.IntervalTree? Или есть другая реализация Interval Tree, которая уже реализует это правильно?

В настоящее время я просто стираю дерево и перезаполняю его каждый раз, когда происходит удаление, что далеко от идеала (примечание: установка DEBUGGING = false в RBTree значительно ускорила процесс).

Answer 1

В итоге я изменил sun.jvm.hotspot.utilities.IntervalTree, чтобы сохранить набор удаленных узлов. При выполнении поиска я исключаю любые элементы из этого набора. Не идеально, но это было намного проще, чем работать с «настоящим» удалением. Как только удаленный набор становится слишком большим, я перестраиваю дерево.

Answer 2

Этот проект имеет реализацию RangeTree, которая может быть более полезной для вас. Солнечные пакеты могут быть хороши для быстрого и грязного использования, но я бы не рекомендовал создавать что-то важное, полагаясь на них. Солнце может не поддерживать их стабильность.

Answer 3

Я обнаружил реализацию с открытым исходным кодом с удалением, но для того, чтобы сделать ее полностью функциональной, нужно приложить некоторые усилия.

Это модуль более крупного проекта с открытым исходным кодом Gephi , но вот sources и javadoc . Если вы хотите банку, вы можете установить Gephi, и он находится в:

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

Метод delete позволяет удалить все интервалы, перекрывающиеся с входным интервалом (а не только с входным). Однако я обнаружил, что существуют частные методы, которые удаляют определенный узел (который хранит один интервал). Также частные методы поиска возвращают узлы.

Так что я думаю, что с небольшими усилиями можно реорганизовать код и получить такую ​​функцию - «удалить определенный интервал». Самый быстрый и самый грязный способ - сделать общедоступные классы private / Node. Но поскольку это проект с открытым исходным кодом, возможно, в будущем он может превратиться в хорошую стандартную реализацию дерева интервалов.

Answer 4

есть реализация c #, основанная на расширенном дереве AVL @ http://code.google.com/p/intervaltree/. перевод на Java не должен быть слишком сложным.

Answer 5

Я не знаю ваших точных требований, но нестатическое дерево сегментов может работать на вас. Если это так, взгляните на SW Layout Management SW , в частности пакет SegmentTree . Он имеет функцию удаления вам нужно.

Если вы решите свернуть свой собственный, могу ли я предложить открыть его? Я удивлен, что уже нет открытого и простого дерева интервалов.