performance - 効率的な比較操作を可能にする値の範囲を格納するためのデータ構造

Question

重複しない整数の範囲を格納できるデータ構造を探しており、特定の範囲がデータ構造に存在するかどうかを比較しています。

たとえば、（0,9）、（10,19）、（30,29）を格納した後、ある時点で、範囲（1,11）がカバーされているかどうかを確認したい場合、アルゴリズムは次のようになります。 「はい」ですが、範囲（15,25）の場合、指定された範囲がカバーされていないため、アルゴリズムは「いいえ」を返します。

よろしくお願いします。

Answer 1

重複しない範囲の整数を扱っているので、単純なBSTでうまくいくと思います（厳密なO（logN）パフォーマンスが必要な場合は、AVLやRBツリーのようにバランスが取れています）。

間隔[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

間隔をすばやく保存および検索するように設計された間隔ツリーデータ構造を探している可能性があります。