Talk:Interval tree

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Start	rated as start-Class on the assessment scale
Mid	rated as mid-importance on the assessment scale

Contents 1 tree 2 Rewrite by Breuwi 3 Alternative implementation 4 Reference

[edit] 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.

[edit] 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)

[edit] 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)

[edit] 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)