Do you know a good implementation of a (binary) segment tree in Java?
thanks zPesk, but this is R-Tree I want a btree implementation which is pretty small.
talg
2009-04-25 19:26:41
A:
If you have access to CLRS, it has an in-depth discussion on implementing an interval tree data structure.
Wouldn't an interval tree serve also as a segment tree, where the segment endpoints are the bounds of the interval, or is there some specific property to the segment tree which is left out?
codekaizen
2009-04-25 20:23:45
I am not sure, since I'm new to the topic, just segment tree seems much simpler to implement and fits the problem I need to solve
talg
2009-04-25 20:31:52
the wikipedia page notes indictae that the segment/interval trees a similar but different. for eacample "The segment tree is less efficient than the interval tree for range queries in one dimension, due to its higher storage requirement: O(nlogn) against the O(n) of the interval tree. The importance of the segment tree is that the segments within each node’s canonical subset can be stored in any arbitrary manner [7]."
ShuggyCoUk
2009-04-28 12:30:02
+1
A:
This has been implemented within the open source Layout Management SW Package project
Here is a link to the sub package
You might find the code useful. I have neither verified it nor run it and I cannot find the license the code is provided under from a quick search of the code and website so Caveat Emptor.
You may be able to contact the authors but the last activity appears to have been August 2008.
ShuggyCoUk
2009-04-28 12:49:19