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;
}