Sign in to follow this  
Shannon Barber

What's the name of this data structure?

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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this