performance - 用于存储允许高效比较操作的值范围的数据结构

Question

我正在寻找一种允许存储非重叠整数范围的数据结构并比较某个范围是否存在[被]数据结构[覆盖]。

例如，在我存储 (0,9),(10,19),(30,29) 之后，稍后我想检查范围 (1,11) 是否被覆盖，在这种情况下算法给出"is"，而对于范围 (15,25)，算法给出“否”，因为给定范围未涵盖。

非常感谢。

Answer 1

由于您处理的是非重叠整数范围，我认为一个简单的 BST 就可以完成这项工作(像 AVL 或 RB 树一样平衡，以防您需要严格的 O(logN) 性能)

对于区间 [a-b]构建以“a​​”为键的树。节点结构类似于:

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

为了搜索:

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));
}