Java: balanced binary search tree
Given my recent (somewhat successful) question:
Algorithmic issue: determining "user sessions"
I'm pretty sure that the way to solve it cleanly is to use a balanced binary tree (which would give an n log m solution to the problem, where thankfully the m is going to be quite small, even tiny, compared to the n), like hinted by one of the answer (answer which comes with some pseudo-code).
My question is simple: does the default Java API have a self-balancing tree?
If not, do you know of any implementation of such a tree (Apache, Google collections, anything)?
If nothing looks suitable开发者_如何学运维, what would be the best tree to start with to implement such a balanced binary tree?
java.util.TreeSet
is a balanced tree implementation. It guarantees O(logn) access time by modifying tree structure when necessary, so it won't degenerate into a list.
The main question is: what operations you need from that tree and if TreeSet
supports them.
精彩评论