Binary search tree with interval as element, simple recursion.


  • 1
    V

    Recursively add interval [e0, e1):

    • case (1), if current tree node p is empty, add new node as [e0, e1);
    • case (2), if current node p is not intersected with [e0, e1), add interval to son of p:
      if (e1 < p->e0) addRange(p->left, e0, e1);
      if (e0 > p->e1) addRange(p->right, e0, e1);
    • case (3), if current node p is intersected with [e0, e1), add the intervals that p not covered to sons of p:
      if (e0 < p->e0) addRange(p->left, e0, e0);
      if (e1 > p->e1) addRange(p->right, p->e1, e1);

    Recursively remove interval [e0, e1):

    • case (1), if current tree node p is empty, do nothing and return;
    • case (2), if current node p is not intersected with [e0, e1), remove interval in son of p:
      if (e1 < p->e0) removeRange(p->left, e0, e1);
      if (e0 > p->e1) removeRange(p->right, e0, e1);
    • case (3), if current node p is intersected with [e0, e1):
      step one: remove interval that are not covered by p in p's sons respectively:
      struct node *l = removeRange(p->left, e0, p->e0);
      struct node *r = removeRange(p->right, p->e1, e1);
      step two: check whether p is fully covered by [e0, e1):
      if p is not fully covered, just truncate p and set its sons respectively:
      if (e1 > p->e0 && e1 < p->e1) { p->e0 = e1; p->left = l;}
      if (e0 > p->e0 && e0 < p->e1) { p->e1 = e0;p->right = r;}
      if p is fully covered, p should be deleted, chose a non-empty l or r and new root node replace p:
      if (l == NULL) { p = r; } else { p = right-most son of l }

    Recursively query interval [e0, e1):

    • case (1), if current tree node p is empty, return false;
    • case (2), if current node p is not intersected with [e0, e1), add interval to son of p:
      if (e1 < p->e0) queryRange(p->left, e0, e1);
      if (e0 > p->e1) queryRange(p->right, e0, e1);
    • case (3), if current node p is intersected with [e0, e1):
      step one: query the intervals that p not covered to sons of p:
      if (e0 < p->e0) queryRange(p->left, e0, e0);
      if (e1 > p->e1) queryRange(p->right, p->e1, e1);
      step two: combine query results of sons:
      return l && r (l, r are initialized as true originally)
    struct node {
        int ends[2];
        struct node *left, *right;
    };
    
    typedef struct {
        struct node *root;
    
    } RangeModule;
    
    RangeModule* rangeModuleCreate() {
        RangeModule *obj;
        obj = (RangeModule *) malloc(sizeof(RangeModule));
        obj->root = NULL;
        return obj;
    }
    
    struct node *addRange(struct node *p, int end0, int end1) {
        if (p == NULL) {
            p = (struct node *) malloc(sizeof(struct node));
            p->ends[0] = end0;
            p->ends[1] = end1;
            p->left = p->right = NULL;  
            return p;  
        } 
    
        if (end1 <= p->ends[0]) {
            p->left = addRange(p->left, end0, end1);
        } else if (end0 >= p->ends[1]){
            p->right = addRange(p->right, end0, end1);
        } else {
            if (end0 < p->ends[0])
                p->left = addRange(p->left, end0, p->ends[0]);
            if (end1 > p->ends[1])
                p->right = addRange(p->right, p->ends[1], end1);
        } 
        return p;
    }
    
    void rangeModuleAddRange(RangeModule* obj, int left, int right) {
        obj->root = addRange(obj->root, left, right);
    }
    
    bool queryRange(struct node *p, int end0, int end1) {
        if (p == NULL)
            return 0;
        if (end0 >= p->ends[0] && end1 <= p->ends[1])
            return 1;
       
        if (end1 <= p->ends[0])
            return queryRange(p->left, end0, end1);
        if (end0 >= p->ends[1])
            return queryRange(p->right, end0, end1);
        
        bool l = 1, r = 1;
        if (end0 < p->ends[0])
            l = queryRange(p->left, end0, p->ends[0]);
        if (end1 > p->ends[1])
            r = queryRange(p->right, p->ends[1], end1);
        return l && r;
    }
    
    bool rangeModuleQueryRange(RangeModule* obj, int left, int right) {
        return queryRange(obj->root, left, right);
    }
    
    struct node *removeRange(struct node *p, int end0, int end1) {
        if (p == NULL)
            return NULL;
    
        if (end1 <= p->ends[0]) {
            p->left = removeRange(p->left, end0, end1);
        } else if (end0 >= p->ends[1]){
            p->right = removeRange(p->right, end0, end1);
        } else if (end0 > p->ends[0] && end1 < p->ends[1]) {
            struct node *tmp = (struct node *) malloc(sizeof(struct node));
            tmp->right = p->right;
            tmp->left = NULL;
            tmp->ends[0] = end1;
            tmp->ends[1] = p->ends[1];
            p->right = tmp;
            p->ends[1] = end0;
            
        } else {
            struct node *l = removeRange(p->left, end0, p->ends[0]);
            struct node *r = removeRange(p->right, p->ends[1], end1);
            if (end1 > p->ends[0] && end1 < p->ends[1]) {
                p->ends[0] = end1;
                p->left = l;
            } else if (end0 > p->ends[0] && end0 < p->ends[1]) {
                p->ends[1] = end0;
                p->right = r;
            } else {
                if (l == NULL)
                    p = r;
                else {
                    struct node *tmp = l;
                    while (tmp->right != NULL)
                        tmp = tmp->right;
                    tmp->right = r;
                    p = l;
                }
            }
        } 
        return p;
    }
    
    void rangeModuleRemoveRange(RangeModule* obj, int left, int right) {
        obj->root = removeRange(obj->root, left, right);
    }
    
    void freeTree(struct node *root) {
        if (root == NULL)
            return;
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
    
    void rangeModuleFree(RangeModule* obj) {
        freeTree(obj->root);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.