Java: arbre binaire équilibré

Question

Compte tenu de ma récente (un certain succès) question:

Algorithmic issue: determining "user sessions"

Je suis assez sûr que la façon de le résoudre est proprement d'utiliser un arbre binaire équilibré (ce qui donnerait n log m solution au problème, où heureusement le m va être très petit, même minuscule, comparé au n), comme suggéré par l'une des réponses (réponse qui vient avec un peu de pseudo code).

Ma question est simple: ne l'API Java par défaut ont un arbre autoéquilibré?

Sinon, savez-vous de toute mise en œuvre d'un tel arbre (Apache, collections Google, quoi que ce soit)?

Si rien ne semble approprié, quel serait le meilleur arbre pour commencer à mettre en œuvre un tel arbre binaire équilibré?

Answer 1

java.util.TreeSet est une mise en œuvre d'arbre équilibré. Il garantit le temps d'accès O (logn) en modifiant la structure de l'arbre si nécessaire, afin qu'il ne dégénère pas en une liste.

La principale question est: quelles opérations vous avez besoin de cet arbre et si TreeSet les prend en charge.