Как найти ранг элемента в TreeSet

Question

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

Спасибо

РЕДАКТИРОВАТЬ: Я думаю, что вы можете сделать это с помощью tailset, т.е. сравните размер исходного набора с размером хвоста. Насколько эффективен хвост?

Answer 1

TreeSet не обеспечивает эффективный метод ранга. Я подозреваю (вы можете подтвердить, посмотрев на его источник), что TreeSet даже не содержит каких-либо дополнительных битов информации (то есть количества элементов в левом и правом поддеревьях каждого узла), что нужно будет выполнять такие запросы в O (log (n)) время. Так что, похоже, не существует быстрого способа найти ранг элемента TreeSet.

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

Answer 2

Согласно источнику реализации Sun JDK6, tailSet(E).size() перебирает набор хвостов и подсчитывает элементы, поэтому этот вызов равен O (размер набора хвостов).

Answer 3

Нет другого пути, кроме Iterator.

Отредактировано:

Попробуйте это:

treeSet.higher(treeSet.first());

Это должно дать второй элемент TreeSet.Я не уверен, что это более оптимизировано, чем просто использование Iterator.