间隔树


难度级别 中等
经常问 亚马逊 谷歌 意会 神谕 Qualtrics

在间隔 问题,我们给出了一组间隔和三种查询类型

  1. addInterval(x,y):将间隔(x,y)添加到集合中
  2. removeInterval(x,y):从集合中移除间隔(x,y)
  3. checkInterval(x,y):检查间隔(x,y)是否与某些现有间隔重叠

设计一个数据结构(Interval Tree)以执行上述3个操作。

使用案列

间隔树

输入
插入(5,10)
插入(3,8)
插入(10,15)
插入(16,18)
插入(9,11)
插入(1,1)
CheckOverlap(1、2)
CheckOverlap(7、11)
CheckOverlap(20、25)
删除(1,1)
删除(10,15)
CheckOverlap(12、14)
CheckOverlap(8、15)
CheckOverlap(1、2)
删除(5,10)
删除(1,2)
删除(8,15)
输出
true
true
false
false
true
false

间隔树算法

这个想法是使用增强的自我平衡 二叉树。 每个节点存储以下信息

  • 区间[l,r],其中l是区间的起点,r是区间的终点。
  • max,以此节点为根的左右子树中的最大终点。

插入和删除

间隔的起点(l)用于维护自平衡二分搜索树中的顺序。
插入和删除操作与常规自平衡二进制搜索树相同。

重叠搜寻

在自平衡二进制搜索树中搜索间隔I(x,y)是否与某个间隔重叠,

  1. 从根开始,如果I(x,y)与根重叠,则返回根。
  2. 如果当前节点的最大值大于I的起点,则在左侧子树中搜索。
  3. 否则在右边的子树中搜索。

间隔树的JAVA代码

public class IntervalTree {
    // class representing the node of interval tree
    static class Node {
        int l;
        int r;
        int max;

        Node left, right;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
            this.max = r;
        }
    }

    // Function to insert an interval in interval tree
    public static Node insert(Node root, int l, int r) {
        // Insert like normal BST, by considering root.l as the key element
        if (root == null) {
            return new Node(l, r);
        }

        if (l < root.l) {
            root.left = insert(root.left, l, r);
        } else if (l > root.l) {
            root.right = insert(root.right, l, r);
        } else {
            if (r < root.r) {
                root.left = insert(root.left, l, r);
            } else {
                root.right = insert(root.right, l, r);
            }
        }

        // If current node's max is less than r, then update max
        if (root.max < r) {
            root.max = r;
        }

        return root;
    }

    private static boolean checkOverlap(Node root, int l, int r) {
        // If current node is null, return false
        if (root == null) {
            return false;
        }

        // If overlaps return true
        if (root.l <= r && l <= root.r) {
            return true;
        }

        // If max value of current is greater than starting point of I(l)
        // search in left subtree
        if (root.left != null && root.left.max >= l) {
            return checkOverlap(root.left, l, r);
        }

        // Else search in right subtree
        return checkOverlap(root.right, l, r);
    }

    // Function to delete a binary tree, same as normal delete in a BST
    private static Node delete(Node root, int l, int r) {
        if (root == null) {
            return null;
        }

        if (l < root.l) {
            root.left = delete(root.left, l, r);
        } else if (l > root.l) {
            root.right = delete(root.right, l, r);
        } else {
            if (r < root.r) {
                root.left = delete(root.left, l, r);
            } else if (r > root.r) {
                root.right = delete(root.right, l, r);
            } else {
                if (root.left == null)
                    return root.right;
                else if (root.right == null)
                    return root.left;

                // Find the minimum value in the right subtree of root
                Node curr = root.right;
                while (curr.left != null) {
                    curr = curr.left;
                }
                root.l = curr.l;
                root.r = curr.r;

                root.right = delete(root.right, root.l, root.r);
            }
        }

        return root;
    }

    public static void main(String[] args) {
        Node root = null;
        root = insert(root, 5, 10);
        root = insert(root, 3, 8);
        root = insert(root, 10, 15);
        root = insert(root, 16, 18);
        root = insert(root, 9, 11);
        root = insert(root, 1, 1);

        System.out.println(checkOverlap(root, 1, 2));
        System.out.println(checkOverlap(root, 7, 11));
        System.out.println(checkOverlap(root, 20, 25));

        root = delete(root, 1, 1);
        root = delete(root,10, 15);

        System.out.println(checkOverlap(root, 12, 14));
        System.out.println(checkOverlap(root, 1, 2));
        System.out.println(checkOverlap(root, 8, 15));
    }
}
true
true
false
false
false
true

间隔树的C ++代码

#include <bits/stdc++.h>
using namespace std;

// class representing the node of interval tree
class Node {
    public:
    int l, r, max;
    Node* left;
    Node* right;
    Node(int lVal, int rVal) {
        l = lVal;
        r = rVal;
        max = rVal;
        left = right = NULL;
    }
};

// Function to create a new Node
Node* newNode(int l, int r) {
    Node* node = new Node(l, r);
    return node;
}

// Function to insert an interval in interval tree
Node* insert(Node* root, int l, int r) {
    if (root == NULL) {
        return newNode(l, r);
    }
    
    if (l < root->l) {
        root->left = insert(root->left, l , r);
    } else if (l > root->l) {
        root->right = insert(root->right, l, r);
    } else {
        if (r < root->r) {
            root->left = insert(root->left, l, r);
        } else {
            root->right = insert(root->right, l, r);
        }
    }
    
    // If current node's max is less than r, then update max
    if (root->max < r) {
        root->max = r;
    }
    
    return root;
}

bool checkOverlap(Node *root, int l, int r) {
    // If current node is null, return false
    if (root == NULL) {
        return false;
    }
    
    // If overlaps return true
    if (root->l <= r && l <= root->r) {
        return true;
    }
    
    // If max value of current is greater than starting point of I(l)
    // search in left subtree
    if (root->left != NULL && root->left->max >= l) {
        return checkOverlap(root->left, l, r);
    }
    
    // Else search in right subtree
    return checkOverlap(root->right, l, r);
}

// Function to delete a binary tree, same as normal delete in a BST
Node* deleteInterval(Node* root, int l, int r) {
    if (root == NULL) {
        return NULL;
    }
    
    if (l < root->l) {
        root->left = deleteInterval(root->left, l, r);
    } else if (l > root->l) {
        root->right = deleteInterval(root->right, l, r);
    } else {
        if (r < root->r) {
            root->left = deleteInterval(root->left, l, r);
        } else if (r > root->r) {
            root->right = deleteInterval(root->right, l, r);
        } else {
            // This is the interval to be deleted
            if (root->left == NULL)
                return root->right;
            else if (root->right == NULL)
                return root->left;
                
            // Find the minimum value in the right subtree of root
            Node* curr = root->right;
            while (curr->left != NULL) {
                curr = curr->left;
            }
            root->l = curr->l;
            root->r = curr->r;
            
            root->right = deleteInterval(root->right, root->l, root->r);
        }
    }
    
    return root;
}

int main() {
    Node *root = NULL;
    root = insert(root, 5, 10);
    root = insert(root, 3, 8);
    root = insert(root, 10, 15);
    root = insert(root, 16, 18);
    root = insert(root, 9, 11);
    root = insert(root, 1, 1);
    
    if (checkOverlap(root, 1, 2))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    if (checkOverlap(root, 7, 11))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
    
    if (checkOverlap(root, 20, 25))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    root = deleteInterval(root, 1, 1);
    root = deleteInterval(root,10, 15);
    
    if (checkOverlap(root, 12, 14))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    if (checkOverlap(root, 8, 15))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    if (checkOverlap(root, 1, 2))
        cout<<"true"<<endl;
    else 
        cout<<"false"<<endl;
        
    return 0;
}
true
true
false
false
true
false

区间树的复杂度分析

对于插入和删除:

时间复杂度= 哦),其中h是BST(二进制搜索树)的高度,对于平衡的BST,h是log(n)。

搜索:

时间复杂度= 哦),其中h是BST(二进制搜索树)的高度,对于平衡的BST,h是log(n)。

參考資料