On Thu 31-05-12 14:04:23, John Stultz wrote:So roughly the naive approach listed in the wikipedia link is what I'm using here.On 05/31/2012 01:48 PM, Jan Kara wrote:Wikipedia has a good description of Interval trees:On Fri 25-05-12 12:17:34, John Stultz wrote:Although I'm not sure your interval tree description doesn't matchI suspect range-tree isn't a totally accurate name, but IWell, interval tree is a data structure for tracking a set of
couldn't quite make out the difference between range trees
and interval trees, so I just picked one to call it. Do
let me know if you have a better name.
possibly overlapping intervals. Range tree is a data structure tracking
points allowing for fast queries on a set of points contained in a given
range (gets useful and interesting when dimension> 1). Your data structure
is neither so it would be good to have a different name. OTOH there are so
many data structures that it's hard to find a reasonable unused name ;)
what I'm trying to provide. Could you clarify why that doesn't
match?
http://en.wikipedia.org/wiki/Interval_tree
For example they are tertiary trees.
Ah. I see the issue you're concerned about!Ok, but then you should define where an interval that is intersectingSo for my usage in the volatile range code, I don't want+I think you should document here that the added range must not intersect
+/**
+ * range_tree_add - Add a node to a range tree
+ * @root: range tree to be added to
+ * @node: range_tree_node to be added
+ *
+ * Adds a node to the range tree.
with any other range in the tree.
intersecting or overlapping ranges added, but I didn't feel it was
necessary to add this restriction to my rangetree code as well,
since someone might want to store overlapping ranges.
other intervals ends up sorted...