CODEWITHSUNDEEP
performancealgorithmdata-structures
cpp_noname
cpp_noname

Reputation: 2071

Data Structure for storing ranges of values that allows efficient comparision operation

I am looking for a data structure that allows storing non-overlapping ranges of integers and comparing whether a certain range exists[is covered] in[by] the data structure.

For example, after I store (0,9),(10,19),(30,29), at some point later I want to check if the range (1,11) is covered, in which case the algorithm gives a "yes" whereas with the range (15,25) the algorithm gives a "no" as the given range is not covered.

Many thanks in advance.

Upvotes: 2

Views: 301

Answers (2)

srbhkmr
srbhkmr

Reputation: 2104

Since you're dealing with non-overlapping ranges of integers, I think a simple BST could do the job(balanced like AVL or RB-tree, in case you want strict O(logN) performance)

For intervals [a-b] Build the tree keeping 'a' as the key. Node structure would be something like:

struct node{
int left;
int right;
struct node*left;
struct node*right;
};

In order to search:

bool SearchOverlap(node* root, interval I){
if(!root)
    return false;
if(I.right < root->left)
    SearchOverlap(root->left, I);
else if(I.left > root->right)
    SearchOverlap(root->right, I);
else if(I.left > root->left && I.right < root->right)
    return true;
else if(I.left < root->left && I.right < root->right)
    return SearchOverlap(root->left, new Interval(I.left, root->left));
else if(I.left > root->left && I.right > root->right)
    return SearchOverlap(root->right, new Interval(root->right, I.right));
}

Upvotes: 2

amit
amit

Reputation: 178531

You might be looking for the Interval Tree data structure, which is designed to store and search for intervals fast.

Upvotes: 1

Related Questions