Почему API Java Collections API не имеет реализации дерева

Ответ 1

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

Я думаю, что причина в том, что никто не придумал хороший API для деревьев, которые оба

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

(И где вы остановитесь? Дерево? Двоичное дерево? N-арное дерево? DAG? График?)

Стоит отметить, что ни коллекции Apache Commons, ни коллекции Google (aka Guava) не имеют API дерева. Тем не менее, есть активная проблема Guava по этой теме - http://code.google.com/p/guava-libraries/issues/detail?id=174 - так ясно, по крайней мере, некоторые люди согласны с вашей точкой зрения.

UPDATE

Начиная с версии 15.0, у Guava теперь есть поддержка дерева в виде классов TreeTraverser и BinaryTreeTraverser. Но это может быть не то, что вы ожидаете. По правде говоря, эти классы фактически не реализуют структуру данных дерева. Вместо этого вы должны сделать это в параметре общего типа. Кроме того, классы Traverser даже избегают делать предположения о API-интерфейсах типа node. Они делают это, будучи абстрактными классами, и требуют, чтобы подтип конкретного traverser реализовал операции, которые опросили дерево; например для получения node детей.

FWIW, TreeMap и TreeSet не являются "древовидными API". Это древовидные реализации API Map и Set. Публикация полностью скрыта публичными API-интерфейсами, что делает эти два класса совершенно непригодными для использования в качестве деревьев общего назначения.

Ответ 2

ИМХО, теоретически, Tree не является типом коллекции, это всего лишь тип реализации. Я имею в виду, что существуют абстрактные коллекции, такие как Set (неупорядоченный набор записей), List (упорядоченный набор записей), Map (два набора записей с отношениями между ними), и есть их реализации: массив, список (например, ArrayList и LinkedList), HashSet и т.д., Все они имеют свои преимущества и недостатки. Таким образом, Tree - это только одна из реализаций (например, для списков), которая может дать вам (грубо) более быстрый поиск, чем массив, но без доступа по индексу.

Кстати, на Java есть TreeMap ( "реализация NavigableMap на основе Red-Black tree" ) и TreeSet ( "Навигационная навигация на основе TreeMap." ) в Java.

Ответ 3

java.util.TreeMap - это реализация Red и Black Tree.