Java: бинарное дерево поиска

Question

Учитывая мое недавнее (довольно успешно) вопрос:

Algorithmic issue: determining "user sessions"

Я уверен, что способ ее решения чисто является использование сбалансированного бинарного дерева (что дало бы a n log m решение проблемы, где, к счастью, m будет довольно маленьким, даже крошечным, по сравнению с n), как намекнул один из ответов (ответ, который поставляется с некоторыми псевдо- код).

Мой вопрос прост: у Java API по умолчанию есть самобалансирующееся дерево?

Если нет, знаете ли вы о какой-либо реализации такого дерева (Apache, коллекции Google, что-нибудь)?

Если ничего не подходит, как было бы лучшим деревом для реализации такого сбалансированного двоичного дерева?

Answer 1

java.util.TreeSet - это сбалансированная реализация дерева. Он гарантирует время доступа O (logn) путем изменения древовидной структуры, когда это необходимо, поэтому оно не будет вырождено в список.

Главный вопрос: какие операции вам нужны из этого дерева, и если TreeSet поддерживает их.