Sign in to follow this  

What's the name of this data structure?

This topic is 3483 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I need a data structure that sorts 'chunks' in a tree but keeps the elements in order in arrays - similar to a b-tree but the branch nodes do not contain any elements (just the left/right decision data); all the elements are in the leaf nodes and are in order. Does such a beast have a specific name? e.g.
                             9
                           /                             /                              /                               /                                /                                 /                                  4              14
                    / \             /                    /   \           /                     /     \         /                      /       \       /                   [0..4]    [5..9] [10..14] [15..19]


ug, source tags don't preserve line-endings?
             9
      4              14
[0..4] [5..9] [10..14] [15..19]

Share this post


Link to post
Share on other sites
Thank you!

A search for segtree came up empty, and I wasn't sure if they were the same thing or not.


I can guarantee that the leaf node elements have non-overlapping intervals, is an interval-tree still the best thing?

[Edited by - Shannon Barber on July 5, 2008 1:51:20 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this