Talk:Interval tree

How to insert to centered tree?

Can someone please give an algoritm to insert a element into a centered tree? LostBoy256 (talk) 14:59, 11 February 2020 (UTC)

Complexity

The centered interval tree requires O(n^2) storage, worst case, when intervals intersect all nodes. For example: {(1, 10), (17, 29), (31, 38), (30, 40), (15, 24), (0, 50), (-10, 60), (5, 45)}

As I understand it the centered interval tree has O(n) storage requirements, not O(n^2). Any given interval is stored in only one node of the tree because all intervals that overlap $x_{\textrm {center}}$ are in that node. The nodes reachable by $S_{\textrm {left}}$ and $S_{\textrm {right}}$ are those that do not overlap $x_{\textrm {center}}$. So, it follows that any single interval appears in only one node. --300Baud (talk) 03:37, 16 March 2021 (UTC)

Different algorithms

This link, http://www.dgp.toronto.edu/~jstewart/378notes/22intervals/ describes a completely different approach, I think.

This look like what is what is called Segment Tree here on WP, in reality there is not much of a distinction. Especially since the naive interval tree described in this article is very inefficient.Carewolf (talk) 21:34, 15 October 2012 (UTC)

Interval tree example

I don't think the interval tree example [[1]] is correct. Each node in the interval tree should contain the maximum of all the interval highs of all of its children nodes. The code shown will simply put the high point of the interval in each node, and not update the maximum values in all of its ancestor nodes. —Preceding unsigned comment added by 68.165.106.2 (talk) 18:18, 25 September 2008 (UTC)

Agree! The Java code is some what incorrect as you say. I'm not familiar with Java and would like to rewrite the code in C which taking the maximun into account. - Justin545 (talk) 12:59, 28 November 2014 (UTC)

tree

About querying a tree: so there is a binary search for each node.. that gives O(log^2 n + m) query time.. how is O(log n + m) achieved?

Never mind, I corrected the description. There is no binary search involved, just a simple enumeration.

---

Actually there is a binary search involved - according to the description, we need to first search S_center (sorted by beginnings) to find the greatest beginning smaller than x. THEN we enumerate.

So the algorithm as presented is indeed O((log n)^2 + m). It can be augmented with additional O(n log n) storage to get back to the O(log n + m): you can keep a separate array of sorted beginnings, and for each beginning x, keep a list of its indices in each of the (log n) sorted S_center lists reached when traversing the main tree with query=x. Basically, you can pre-process and save the results of the binary searches mentioned above.

216.239.45.4 (talk) 22:16, 20 October 2009 (UTC)emilp

Rewrite by Breuwi

Interesting: it seems Breuwi [rewrote this article], replacing it with what looks like an entirely different datastructure (solving the same problem). The references at the bottom probably don't make much sense anymore now. I wonder how this kind of issue is generally fixed. --Raboof 14:01, 21 February 2007 (UTC)

No, it's fundamentally the same data structure but has been made more complicated than necessary. —Pqrstuv 05:35, 28 June 2007 (UTC)

I think you're stretching 'fundamentally the same' to extremes here :) --Raboof 21:48, 2 December 2007 (UTC)

Can I recommend putting the "Alternate structure" first? - it is by far the simpler implementation, and is the one given in CLR. I cannot see that the more complex implementation adds much. -- random visitor, 22 July 2007

In favor ;) --Raboof 21:48, 2 December 2007 (UTC)

Breuwi also added the note This alternate algorithm is not what is normally referred to as an "interval tree." a 'unreferencedsection' marker. As this algorithm is the one mentioned in the first reference of this article, which is a relatively authorative source, I'm removing both and making the reference more explicit. --Raboof 21:50, 2 December 2007 (UTC)

Alternative implementation

It's not at all obvious to me how to use a balanced tree in the alternative implementation when generalised to more than one dimension. The rotations of the tree (required for balancing) will mess up the dividing-in-alternate-dimensions by giving child nodes to inappropriate parents.

I'm not sure that design scales to higher dimensions - Special:Contributions/198.37.18.99 added that comment and subsequent editors extended it. I'll make the wording somewhat less strong. --Raboof 22:30, 2 December 2007 (UTC)

Reference

It'd be nice to be able to point readers to good datastructures/algorithms for storing and searching though recurring calendar items, as this is a related use case --Raboof 13:05, 5 October 2007 (UTC)

What is the reference for the "Alternative Data Structure"? Is an author inventing this one? I think Wikipedia articles are supposed to refer to established methods. In this case the method has no name and no asymptotic running time. —Preceding unsigned comment added by 149.169.152.14 (talk) 19:41, 9 October 2007 (UTC)

• The so-called 'Alternative Data Structure' is the one originally in the article, before the rewrite I mentioned above. This is the one described by the first reference. --Raboof 21:19, 2 December 2007 (UTC)

ITIM

I was looking for a data structure that allowed one to query with a point and return whether the point was in any of the intervals in the data structure--that is, without caring which or how many intervals contained it. Is there a simpler or more efficient data structure for solving such a problem efficiently? Erik Carson (talk) 21:02, 6 April 2011 (UTC)

• I did see Segment tree, but even that is overkill as it queries for which segments (intervals) contain the point rather than simply whether any of them do. Erik Carson (talk) 21:07, 6 April 2011 (UTC)
• Both structures described in this article can do that, you should simply stop search after it discovers the first matching interval. -- X7q (talk) 21:08, 6 April 2011 (UTC)

Please add graphic example

I'm a visual thinker and would pick up the concept much quicker if you included a picture or two. Better yet, an animation. StuRat (talk) 00:12, 30 April 2014 (UTC)

Asymptotic optimality of trivial solution

The article says, "The trivial solution is to visit each interval and test whether it intersects the given point or interval, which requires Θ(n) time, where n is the number of intervals in the collection. Since a query may return all intervals, for example if the query is a large interval intersecting all intervals in the collection, this is asymptotically optimal." But this seems wrong since you could return all the intervals without actually visiting each interval. Maybe the caller of the function would still have to visit all the intervals but maybe not. For instance, maybe all that is of interest is the number of intervals in the query.

Typo in overlap test?

The overlap test formula here has, I think, a typo. It reads:

{\displaystyle a_{0}<b_{1}} and {\displaystyle a_{1}>b_{0}} {\displaystyle a_{1}>b_{0}}

when it should read:

{\displaystyle a_{0}<b_{1}} and {\displaystyle a_{1}>b_{0}} {\displaystyle a_{1}<b_{0}}

Or maybe I don't understand it well?

Higher dimensional augmented trees

The "Higher dimensions" section does not cite any sources, and it's unclear to me how to use such nested interval trees constructed from the augmented red-black trees described in CLRS. I can't find any mention of such a structure in the literature either. Gyorgy.Kurucz (talk) 11:52, 20 November 2022 (UTC)