Построение дерева из упорядоченного списка

Question

В java, im, создающем SortedSet из списка, который всегда будет упорядочен (но это только тип ArrayList). Я полагаю, что добавление их один за другим будет иметь довольно низкую производительность (например, для дерева AVL), так как ему придется многократно изменять порядок дерева.

Мой вопрос в том, как должен Я создаю этот комплект? таким образом, чтобы как можно быстрее построить сбалансированное дерево?

конкретной реализации я планировал с помощью был либо IntRBTreeSet или IntAVLTreeSet из http://fastutil.dsi.unimi.it/docs/it/unimi/dsi/fastutil/ints/IntSortedSet.html

после написания этого, я думаю, что низкая производительность не повлияет на меня слишком много в любом случае (слишком малое количество данных), но им по-прежнему заинтересованы в том, как это будет сделано в общем случае.

Answer 1

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

1. найти средний элемент списка
2. вставить его в набор
3. повторить для обоих подсписков слева и справа от среднего элемента

Answer 2

Красно-черные деревья - хороший выбор для общего случая, и у них очень быстрые вставки. См. Chris Okasaki's paper для элегантной и быстрой реализации. Библиотека Functional Java имеет общий класс Set, который поддерживается красно-черным деревом, реализованным в соответствии с этой статьей.

Answer 3

У вас проблема с производительностью с простым подходом просто вставлять элементы по мере их поступления?

Если нет, не оптимизируйте.

Answer 4

Созданный в TreeSet (http://java.sun.com/j2se/1.4.2/docs/api/java/util/TreeSet.html) класс использует красно-черное дерево, поскольку оно поддерживает дерево (и, было отмечено, красно-черные деревья довольно быстры для вставок). Вот good info на деревьях Red-Black (у них нет проблемы типичной реализации двоичного дерева при вставке данных, которые в основном упорядочены).

Если вы имеете дело с огромными наборами данных (достаточно большими, чтобы требовать поддержки на основе дисков или значительного обмена файлами подкачки), то B + Tree - очень хороший вариант (см. JDBM для Java-базирующейся версии B + Tree - он не реализует Set, но может быть использован таким образом, если это необходимо).

В зависимости от того, как ваше приложение действительно использует эти данные, вам может потребоваться рассмотреть библиотеку GlazedLists и сделать ваши списки «живыми». Если все, что вы делаете, это статический анализ, то это может быть излишним, но это абсолютно фантастический способ работать со списком данных. Определенно стоит прочитать.

Answer 5

При обсуждении использования набора мне приходит в голову, что, возможно, проблема может быть переформулирована. Зачем использовать Set вообще? Если вы просто хотите проверить членство и сортировать исходный список, выполните двоичный поиск объекта - это будет так же быстро (и, вероятно, быстрее), чем любое n-дерево, которое вы можете себе представить, и это не так сложно код.

Итак, представьте интерфейс OrderedListSet, который просто обертывает объект списка Подкласс. Пока компаратор, используемый для заказа списка, также используется для двоичного поиска, это должно быть довольно прямолинейным.

Все операции с множеством начнутся с вызова getIndex (Object ob), после чего в списке будет выполнено соответствующее действие.