IntervalTree DeleteNode Java Implementation

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

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

Answer 3

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

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

Answer 4

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

Answer 5

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

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

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

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

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