Java: збалансований двійковий дерево пошуку - java, api, binary-tree

Враховуючи моє нещодавнє (кілька успішне) питання:

Алгоритмічна проблема: визначення "сесій користувача"

Я досить впевнений, що шлях до його вирішення чисто - це використання збалансованого бінарного дерева (яке дало б n log m вирішення проблеми, де на щастя м буде досить маленьким, навіть крихітним, у порівнянні з н), начебто натякнута на одну з відповідей (відповідь, яка поставляється з деяким псевдокодом).

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

Якщо ні, чи знаєте ви про будь-яку реалізацію такого дерева (Apache, колекції Google, що-небудь)?

Якщо ніщо не виглядає придатним, що б було найкраще дерево, щоб почати з такого збалансованого бінарного дерева?

Відповіді:

java.util.TreeSet є збалансованою реалізацією дерева. Це гарантує час доступу O (logn), змінюючи структуру дерева, коли це необхідно, тому воно не вироджується в список.

Головне питання: які операції вам потрібні з цього дерева і якщо TreeSet підтримує їх.