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

Question

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

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

提前谢谢了。

Answer 1

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

对于间隔 [ab] 构建以“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));
}

Answer 2

您可能正在寻找间隔树数据结构，它旨在快速存储和搜索间隔。