인터벌 트리


난이도 중급
자주 묻는 질문 아마존 구글 인튜이트 신탁 Qualtrics
나무

간격에서 나무 문제, 우리는 일련의 간격과 세 가지 유형의 쿼리를 제공했습니다.

  1. addInterval (x, y) : 세트에 간격 (x, y) 추가
  2. removeInterval (x, y) : 집합에서 간격 (x, y)을 제거합니다.
  3. checkInterval (x, y) : 간격 (x, y)가 기존 간격과 겹치는 지 확인

위에서 언급 한 3 가지 작업을 수행하기 위해 데이터 구조 (Interval Tree)를 설계합니다.

인터벌 트리

입력
삽입 (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)
산출
참된
참된
그릇된
그릇된
참된
그릇된

인터벌 트리 알고리즘

아이디어는 증강 자기 균형을 사용하는 것입니다. 이진 트리. 모든 노드는 다음 정보를 저장합니다.

  • 간격 [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 (Binary Search Tree)의 높이이고 균형 BST의 경우 h는 log (n)입니다.

검색 :

시간 복잡성 = 오), 여기서 h는 BST (Binary Search Tree)의 높이이고 균형 BST의 경우 h는 log (n)입니다.

참조