CODEWITHSUNDEEP
algorithmmergebinary-search-tree
Petr Kroupa
Petr Kroupa

Reputation: 53

BST - interval deletion/multiple nodes deletion

Suppose I have a binary search tree in which I'm supposed to insert N unique-numbered keys in the order given to me on standard input, then I am to delete all nodes with keys in interval I = [min,max] and also all connections adjacent to these nodes. This gives me a lot of smaller trees that I am to merge together in a particular way. More precise description of the problem:

Given a BST, which contains distinct keys, and interval I, the interval deletion works in two phases. During the first phase it removes all nodes whose key is in I and all edges adjacent to the removed nodes. Let the resulting graph contain k connected components T1,...,Tk. Each of the components is a BST where the root is the node with the smallest depth among all nodes of this component in the original BST. We assume that the sequence of trees Ti is sorted so that for each i < j all keys in Ti are smaller than keys in Tj. During the second phase, trees Ti are merged together to form one BST. We denote this operation by Merge(T1,...,Tk). Its output is defined recurrently as follows:

EDIT: I am also supposed to delete any edge that connects nodes, that are separated by the given interval, meaning in example 2 the edge connecting nodes 10 and 20 is deleted because the interval[13,15] is 'in between them' thus separating them.

For an empty sequence of trees, Merge() gives an empty BST. For a one-element sequence containing a tree T, Merge(T) = T. For a sequence of trees T1,...,Tk where k > 1, let A1< A2< ... < An be the sequence of keys stored in the union of all trees T1,...,Tk, sorted in ascending order. Moreover, let m = ⌊(1+k)/2⌋ and let Ts be the tree which contains Am. Then, Merge(T1,...,Tk) gives a tree T created by merging three trees Ts, TL = Merge(T1,...,Ts-1) and TR = Merge(Ts+1,...,Tk). These trees are merged by establishing the following two links: TL is appended as the left subtree of the node storing the minimal key of Ts and TR is appended as the right subtree of the node storing the maximal key of Ts.

After I do this my task is to find the depth D of the resulting merged tree and the number of nodes in depth D-1. My program should be finished in few seconds even for a tree of 100000s of nodes (4th example).

My problem is that I haven't got a clue on how to do this or where even start. I managed to construct the desired tree before deletion but that's about that. I'd be grateful for implementation of a program to solve this or any advice at all. Preferably in some C-ish programming language.

examples:

input(first number is number of keys to be inserted in the empty tree, the second are the unique keys to be inserted in the order given, the third line containts two numbers meaning the interval to be deleted): 

13    
10 5 8 6 9 7 20 15 22 13 17 16 18  
8 16

correct output of the program: 3 3 , first number being the depth D, the second number of nodes in depth D-1

input:

13
10 5 8 6 9 7 20 15 22 13 17 16 18
13 15

correct output: 4 3

pictures of the two examples

example 3: https://justpaste.it/1du6l correct output: 13 6

example 4: link correct output: 58 9

Upvotes: 0

Views: 803

Answers (1)

Shihab Shahriar Khan
Shihab Shahriar Khan

Reputation: 5475

This is a big answer, I'll talk at high-level.Please examine the source for details, or ask in comment for clarification.

Global Variables :

  • vector<Node*> roots : To store roots of all new trees.
  • map<Node*,int> smap : for each new tree, stores it's size
  • vector<int> prefix : prefix sum of roots vector, for easy binary search in merge

Functions:

  • inorder : find size of a BST (all calls combinedly O(N))
  • delInterval : Main theme is,if root isn't within interval, both of it's childs might be roots of new trees. The last two if checks for that special edge in your edit. Do this for every node, post-order. (O(N))
  • merge : Merge all new roots positioned at start to end index in roots. First we find the total members of new tree in total (using prefix-sum of roots i.e prefix). mid denotes m in your question. ind is the index of root that contains mid-th node, we retrieve that in root variable. Now recursively build left/right subtree and add them in left/right most node. O(N) complexity.
  • traverse: in level map, compute the number of nodes for every depth of tree. (O(N.logN), unordered_map will turn it O(N))

Now the code (Don't panic!!!):

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

int N = 12;

struct Node
{
    Node* parent=NULL,*left=NULL,*right = NULL;
    int value;
    Node(int x,Node* par=NULL) {value = x;parent = par;}
};

void insert(Node* root,int x){
    if(x<root->value){
        if(root->left) insert(root->left,x);
        else root->left = new Node(x,root);
    }
    else{
        if(root->right) insert(root->right,x);
        else root->right = new Node(x,root);
    }
}

int inorder(Node* root){
    if(root==NULL) return 0;
    int l = inorder(root->left);
    return l+1+inorder(root->right);
}

vector<Node*> roots;
map<Node*,int> smap;
vector<int> prefix;

Node* delInterval(Node* root,int x,int y){
    if(root==NULL) return NULL;
    root->left = delInterval(root->left,x,y);
    root->right = delInterval(root->right,x,y);
    if(root->value<=y && root->value>=x){
        if(root->left) roots.push_back(root->left);
        if(root->right) roots.push_back(root->right);
        return NULL;
    }
    if(root->value<x && root->right && root->right->value>y) {
        roots.push_back(root->right);
        root->right = NULL;
    }
    if(root->value>y && root->left && root->left->value<x) {
        roots.push_back(root->left);
        root->left = NULL;
    }
    return root;

}
Node* merge(int start,int end){
    if(start>end) return NULL;
    if(start==end) return roots[start];
    int total = prefix[end] - (start>0?prefix[start-1]:0);//make sure u get this line
    int mid = (total+1)/2 + (start>0?prefix[start-1]:0); //or this won't make sense
    int ind = lower_bound(prefix.begin(),prefix.end(),mid) - prefix.begin();
    Node* root = roots[ind];
    Node* TL = merge(start,ind-1);
    Node* TR = merge(ind+1,end);
    Node* temp = root;
    while(temp->left) temp = temp->left;
    temp->left = TL;
    temp = root;
    while(temp->right) temp = temp->right;
    temp->right = TR;
    return root;
}

void traverse(Node* root,int depth,map<int, int>& level){
    if(!root) return;
    level[depth]++;
    traverse(root->left,depth+1,level);
    traverse(root->right,depth+1,level);
}

int main(){
    srand(time(NULL));
    cin>>N;
    int* arr = new int[N],start,end;
    for(int i=0;i<N;i++) cin>>arr[i];
    cin>>start>>end;

    Node* tree = new Node(arr[0]); //Building initial tree
    for(int i=1;i<N;i++) {insert(tree,arr[i]);}

    Node* x = delInterval(tree,start,end); //deleting the interval
    if(x) roots.push_back(x);

    //sort the disconnected roots, and find their size
    sort(roots.begin(),roots.end(),[](Node* r,Node* v){return r->value<v->value;}); 
    for(auto& r:roots) {smap[r] = inorder(r);}

    prefix.resize(roots.size()); //prefix sum root sizes, to cheaply find 'root' in merge
    prefix[0] = smap[roots[0]];
    for(int i=1;i<roots.size();i++) prefix[i]= smap[roots[i]]+prefix[i-1];

    Node* root = merge(0,roots.size()-1); //merge all trees
    map<int, int> level; //key=depth, value = no of nodes in depth
    traverse(root,0,level); //find number of nodes in each depth

    int depth = level.rbegin()->first; //access last element's key i.e total depth
    int at_depth_1 = level[depth-1]; //no of nodes before
    cout<<depth<<" "<<at_depth_1<<endl; //hoorray

    return 0;
}

Upvotes: 2

Related Questions