0

i am working with g++ in linux ubuntu

i am attaching input file for which error occurred. this file tries to insert 1000 numbers and then 250th smallest number.

this code worked well when i inserted less numbers but it is not working for insertion of 1000 numbers.

compiler shows this runtime error:
nchy@ubuntu:~/Desktop$ g++ tree.cpp
nchy@ubuntu:~/Desktop$ ./a.out <in0
terminate called after throwing an instance of 'std::out_of_range'
what(): basic_string::compare
Aborted

input format:

2
insert 0 5 3 5 8 6 0
select 0 2

first line=> number of operations
second line=>
insert =>insert operation
0=> 0th tree
5=>5 insertions
then 5 numbers to be inserted

third line=>
select=>select operation
0=>0th tree
2=>2nd smallest element thus selecting 2nd smallest element in 0th tree.

#include<iostream>
#include<string>
using namespace std;

template <class T>
class redblacktree {
public:
T x;
redblacktree<T> *left, *right, *parent;
int leftsize; // number of nodes in left subtree
int r; // the number of black nodes on any path
// from the current node to a leaf in its subtree
bool color;
redblacktree<T> *root;


redblacktree():root(NULL){}

redblacktree<T>* search(T y) 
{
 redblacktree<T> *p;
 p=root;
 while(1)
   {
   if(y==p->x)
   return p;
   if(((y>p->x)&&(p->right==NULL))||((y<p->x)&&(p->left==NULL)))
   { 
    cout<<"key not present"<<endl;
    break;
   }
   if((y>p->x)&&(p->right!=NULL))
    {p=p->right;
     }
   else if((y<p->x)&&(p->left!=NULL))
    {p=p->left;
     }
   }
}


void insert(T y)
{


 redblacktree<T> *p,*q;
 if(root==NULL)
 {
  q=new redblacktree<T>;
  q->x=y;
  q->left=q->right=q->parent=NULL;
  q->leftsize=0;
  q->r=1;
  q->color=false;
  root=q;
  
 }

 else
 {
  p=root;
  q=new redblacktree<T>;
   q->x=y;
   q->left=q->right=NULL;
   q->leftsize=0;
   q->r=0;
   q->color=true; 
 
  redblacktree<T> *u;

   while(1)
   {
   if(((y>p->x)&&(p->right==NULL))||((y<p->x)&&(p->left==NULL))||(y==p->x))
    break;
   if((y>p->x)&&(p->right!=NULL))
    {p=p->right;
     }
   else if((y<p->x)&&(p->left!=NULL))
    {p=p->left;
     }
   }
 
   if(y==p->x)
   {
    cout<<"key already presnt"<<endl;
    return;
   }
   else if(y>p->x)
    {
    p->right=q;
    q->parent=p;
    
    u=q;
    while((u->parent!=NULL)&&(u->parent->right==u))
    {
     u=u->parent;
    }  
    }
   else if(y<p->x)
    {
    p->left=q;
    q->parent=p;
    u=q;
    
    
  
     
    
       
  
   
    while(u!=root)
    {
    
     
     if(u->parent->left!=NULL)
     
     
     if(u->parent->left==u)
      {
      u->parent->leftsize+=1;
     }
     u=u->parent;
     
    }
     
    
  int flag=0;
   
   if((q->parent!=NULL)&&(q->parent->parent!=NULL))
   {    
      redblacktree<T> *pu,*gu;
        
   
   
    
    while((q->parent->color)&&(q->color))
    {
     pu=q->parent;
      gu=q->parent->parent; 
  
     if((q->parent->parent->right==NULL)||(q->parent->parent->right->color==false))
     {
     
      if(q->parent->left==q)
      {
       
       
       gu->leftsize=gu->leftsize-1-pu->leftsize;
       
       if(gu==root)
        flag=1;
       if(flag==0)
       {
       if(gu->parent->left==gu)
        gu->parent->left=pu;
       else
        gu->parent->right=pu;
       
       }
       pu->parent=gu->parent;
       gu->parent=pu;
       
       gu->left=pu->right;
       if(pu->right!=NULL)  
        pu->right->parent=gu;
                 
       pu->right=gu;
      
       pu->color=false;
       gu->color=true;
      
       if(flag==1)
        root=pu;
      
      break;
      }  
      else
      {
       
       
       gu->leftsize=gu->leftsize-2-pu->leftsize-q->leftsize;
       q->leftsize=pu->leftsize+1+q->leftsize;
       
       if(gu==root)
        flag=1;
       if(flag==0)
       {
       if(gu->parent->left==gu)
        gu->parent->left=q;
       else
        gu->parent->right=q;
   
       }
       q->parent=gu->parent;
       gu->parent=q;
       if(q->left!=NULL) 
        q->left->parent=pu;
       if(q->right!=NULL)
        q->right->parent=gu;
       gu->left=q->right;
       pu->right=q->left;
       q->left=pu;
       q->right=gu;
       pu->parent=q;
       
       q->color=false;
       gu->color=true;
      
       if(flag==1)
        root=q;
      
      break;
      }
     }
     else if((q->parent->parent->left==NULL)||(q->parent->parent->left->color==false))
     {
      if(q->parent->right==q)          
      {
      
       
       pu->leftsize=gu->leftsize+1+pu->leftsize;
             
       if(gu==root)
        flag=1;
      if(flag==0)
      {
       if(gu->parent->left==gu)
        gu->parent->left=pu;
       else
        gu->parent->right=pu;
       
      } 
       pu->parent=gu->parent;
       gu->parent=pu;
       gu->right=pu->left;
       if(pu->left!=NULL)
        pu->left->parent=gu;
       pu->left=gu;
       
       pu->color=false;
       gu->color=true;
      
       if(flag==1)
        root=pu;
      
      break;
      } 
      else
      {
      
       
       pu->leftsize=pu->leftsize-1-q->leftsize;
       q->leftsize=gu->leftsize+1+q->leftsize;
       
       if(gu==root)
        flag=1;
       
       
       if(flag==0)
       {
       if(gu->parent->left==gu)
        gu->parent->left=q;
       else
        gu->parent->left=q;
       
       }
       q->parent=gu->parent;
       gu->parent=q;
       if(q->left!=NULL) 
        q->left->parent=gu;
       if(q->right!=NULL)
        q->right->parent=pu;
     
       gu->right=q->left;
       pu->left=q->right;
       q->right=pu;
       q->left=gu;
       pu->parent=q;
       
       q->color=false;
       gu->color=true;
       
       if(flag==1)
        root=q;
       
       break;
      }
     } 
     else if((q->parent->parent->right->color==true)&&(q->parent->parent->left==q->parent))
     {
      
     
      q->parent->color=false;
      q->parent->parent->right->color=false;
      if(q->parent->parent!=root)
      {
       q->parent->parent->color=true;
       q=q->parent->parent; 
      }
      else
       break;
     }
     else if((q->parent->parent->left->color==true)&&(q->parent->parent->right==q->parent))
     {
      
    
   
       
      q->parent->color=false;
      q->parent->parent->left->color=false;
      if(q->parent->parent!=root)
       {
       q->parent->parent->color=true;
       q=q->parent->parent; 
       }
      else
       break;
     }    
    }
   }   
  }
 }
}
T kthsmallest(int k)
{
 redblacktree<T> *p;
 p=root;
 
 while(1)
 {
  if(k==p->leftsize+1)
   return p->x;
  else if(k>p->leftsize+1)
   {
    k=k-p->leftsize-1;
    p=p->right;
   }
  else if(k<p->leftsize+1)
   p=p->left;
 }
 
}
};

int main()
{


int no_of_trees,tree_no,no_of_insertions,number,k,result;
string s;
cin>>no_of_trees;

redblacktree<int> rb[no_of_trees];

for(int i=0;i<no_of_trees;i++)
{
getline(cin,s,' ');

if(s.compare(1,6,"insert")==0)
{
 
 cin>>tree_no;
 
 cin>>no_of_insertions;
 
 for(int i=0;i<no_of_insertions;i++)
 {
  cin>>number;
  
  rb[tree_no].insert(number);
 }
}
if(s.compare(1,6,"select")==0)
{
 cin>>tree_no;
 
 cin>>k;
 result=rb[tree_no].kthsmallest(k);
}
}
cout<<result<<endl;
}
1
Contributor
1
Reply
2
Views
6 Years
Discussion Span
Last Post by nchy13
0

can anyone tell when this type of exception occur or how to overcome it.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.