Есть ли дерево, которое может ранжировать объект?

Я закодировал дерево двоичной статистики Red Black, чтобы получить ранг произвольного объекта, сопоставимого с другими объектами в дереве Red Black. Интересно, существует ли класс API, который обеспечивает те же функциональные возможности.Есть ли дерево, которое может ранжировать объект?

Было бы неплохо, если бы присвоен ранг, у класса есть функция, чтобы вернуть объект этого ранга внутри дерева.

Обратите внимание, что Red-black BST позволяет эти две операции в log (n) времени, где n это количество объектов в дереве.

источник

2013-07-15 fodon

Вы имеете в виду, что вы реализовали дерево статистики заказа? Я не думаю, что они находятся в Java stdlib. –

java.util.TreeSet использует красно-черное дерево, реализованное с помощью java.util.TreeMap. http://en.wikipedia.org/wiki/Java_collections_framework – sara

Как люди обычно оценивают объекты в динамически сформированной структуре данных, например дереве? – fodon

В стандартном API нет дерева статистики заказа. TreeMap, в частности, не имеет методов поиска ранга ключа или нахождения ключа по рангу в O (log n) времени.

Это не похоже на обычные библиотеки дополнений (коллекции Apache Commons, Google Guava) также имеют дерево статистики заказа.

источник

2013-07-15 15:17:35 Joni

Команда guava google, похоже, работает над ней на основе электронной почты. – fodon

-1

Вы заново изобрели колесо. Вы можете использовать TreeMap<YourClassAsKey, Long>, так как TreeMap снабжен красным черным BST, и мы e значение Long в качестве счетчика.

С его Javadoc: реализация NavigableMap на основе

Красно-черное дерево.

источник

2013-07-15 15:11:38

Что происходит, когда вы добавляете ключ в середине. Нужно ли увеличивать все долги больше, чем ключ? Если да, то каким образом процесс log (n) добавляет ключ? Red-Black BST добавляет в log (n) время.Существует смысл изобретать «пневматическую шину», даже если колесо находится вокруг. – fodon

@fodon Что вы подразумеваете под * Нужно ли увеличивать все длинные, превышающие ключ? *. –

Как вы предлагаете решить проблему поиска ранга произвольного ключа (не обязательно ключа в наборе ключей в TreeMap)? – fodon

-1

Да есть TreeMap:

Красно-черное дерево реализации NavigableMap основе. Карта сортируется в соответствии с естественным порядком ее ключей или Компаратором, предоставленным при создании карты, в зависимости от того, какой конструктор используется.

Эта реализация обеспечивает гарантированное время регистрации журнала (n) для операций containsKey, get, put и remove. Алгоритмы являются адаптацией к тем, которые применяются в работе Cormen, Leiserson и «Rivest's Introduction to Algorithms».

Было бы хорошо, если бы присвоили звание, класс имеет функцию возвращать объект этого ранга в дереве.

Интерфейс NavigableMap (реализован TreeMap) предлагает такие методы, как floorKey и ceilingKey.

источник

2013-07-15 15:11:48 assylias

Какая из проблем, которые я поставил, решает ли это в log (n) времени? – fodon

@fodon Я неправильно понял вашу потребность. Вы можете поместить объекты как ключи и фиктивные значения. Затем вы можете вызвать 'map.headMap(). Size()' для получения ранга (не уверен, что это O (log (n))). Но я не уверен, как вы получите доступ к n-му элементу с помощью этой методологии. – assylias

Да, это хорошая идея. Было бы интересно узнать, является ли это процессом log (n), чтобы найти size() в headmap() – fodon

Отъезд http://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html.

Профессор Sedgewick назвал деревья RedBlack, поэтому, скорее всего, это правильная реализация RedBlack BST. Он также имеет ранг (работает в O (lgN)). (Я бы не стал писать собственную версию, если она поддерживает удаление). Это, по крайней мере, хорошая рекомендация. (Не в java.util alas)

источник

2015-02-23 16:39:45

Есть ли дерево, которое может ранжировать объект?

ответ

Смежные вопросы