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

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

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

Answer 4

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

Answer 5

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

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

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

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

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