用於存儲值的範圍的數據結構，其允許有效的對比操作

Question

我尋找其允許存儲整數 的不重疊的範圍，並比較是否存在一定的範圍內[覆蓋]在數據結構中[通過]的數據結構。

例如，在我存儲了（0,9），（10,19），（30,29）， 之後的某個點後，我想檢查範圍（1,11）是否被覆蓋，其中如果 算法給出「是」，而對於範圍（15,25），算法給出「否」，因爲給定範圍未被覆蓋。

許多在此先感謝。

Answer 1

既然你要處理的非重疊整數的範圍內，我想簡單的BST可以做的工作（如AVL或RB-樹平衡，如果你想嚴格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

您可能正在尋找Interval Tree數據結構，該結構旨在快速存儲和搜索間隔。