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

Question

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

Алгоритмическая проблема: определение «пользовательских сессий»

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

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

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

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

Answer 1

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

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