don't go by the size of code.
before inserting search function my code was working fine with insert function. but don't know what is wrong with search fn. or declaration of variables in main().
this is what compiler shows.
tree.cpp:316:15: error: cannot convert ‘int*’ to ‘redblacktree<int>*’ in assignment
tree.cpp:318:15: error: cannot convert ‘int*’ to ‘redblacktree<int>*’ in assignment
tree.cpp:320:16: error: cannot convert ‘int*’ to ‘redblacktree<int>*’ in assignment
tree.cpp: In member function ‘T* redblacktree<T>::search(T) [with T = int]’:
tree.cpp:316:15: instantiated from here
tree.cpp:25:11: error: cannot convert ‘redblacktree<int>*’ to ‘int*’ in return
i also googled the syntax of templates but i can't get what is wrong here.
#include<iostream>
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){}
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;
cout<<p->x<<endl;}
else if((y<p->x)&&(p->left!=NULL))
{p=p->left;
cout<<p->x<<endl;}
}
}
void insert(T y)
{
cout<<y <<"next"<<endl;
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=0;
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;
cout<<"entering while loop"<<endl;
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;
cout<<p->x<<endl;}
else if((y<p->x)&&(p->left!=NULL))
{p=p->left;
cout<<p->x<<endl;}
}
cout<<"p->x="<<p->x<<endl;
cout<<"y="<<y<<endl;
if(y==p->x)
{
cout<<"key already presnt"<<endl;
return;
}
else if(y>p->x)
{
p->right=q;
q->parent=p;
cout<<"element"<<y<<"inserted"<<endl;
if(q->parent!=NULL)
{cout<<q->parent->x<<endl;
cout<<q->parent->color<<endl;}
}
else if(y<p->x)
{
p->left=q;
q->parent=p;
while((q->parent!=NULL)&&(q->parent->left==q))
{
q->parent->leftsize+=1;
q=q->parent;
}
q=p->left;
cout<<"element"<<y<<"inserted"<<endl;
if(q->parent!=NULL)
{cout<<q->parent->x<<endl;
cout<<q->parent->color<<endl;}
}
int flag=0;
if((q->parent!=NULL)&&(q->parent->parent!=NULL))
{
redblacktree<T> *pu,*gu;
cout<<"element"<<y<<"coming"<<endl;
cout<<"q-parent->color="<<q-parent->color<<endl;
cout<<"q->color="<<q->color<<endl;
while((q->parent->color)&&(q->color))
{
pu=q->parent;
gu=q->parent->parent;
cout<<"coming"<<endl;
if((q->parent->parent->right==NULL)||(q->parent->parent->right->color==false))
{
cout<<"rotation"<<endl;
if(q->parent->left==q)
{
cout<<"rotation 1"<<endl;
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;
pu->right->parent=gu;
pu->right=gu;
pu->color=false;
gu->color=true;
if(flag==1)
root=pu;
break;
}
else
{
cout<<"rotation 2"<<endl;
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)
{
cout<<"rotation 3"<<endl;
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;
pu->left->parent=gu;
pu->left=gu;
pu->color=false;
gu->color=true;
if(flag==1)
root=pu;
break;
}
else
{
cout<<"rotation 4"<<endl;
if(gu==root)
flag=1;
cout<<flag<<endl;
cout<<"1st stage"<<endl;
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;
cout<<"2nd stage"<<endl;
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))
{
cout<<"eureka 1"<<endl;
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))
{
cout<<"eureka 2"<<endl;
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;
}
}
}
}
}
};
int main()
{
redblacktree<int> rb;
rb.insert(50);
rb.insert(10);
rb.insert(80);
rb.insert(90);
rb.insert(70);
rb.insert(60);
rb.insert(65);
rb.insert(62);
rb.insert(62);
cout<<rb.root->x<<" "<<rb.root->color<<endl;
cout<<rb.root->left->x<<" "<<rb.root->left->color<<endl;
cout<<rb.root->right->x<<" "<<rb.root->right->color<<endl;
cout<<rb.root->right->right->x<<" "<<rb.root->right->right->color<<endl;
cout<<rb.root->right->left->x<<" "<<rb.root->right->left->color<<endl;
cout<<rb.root->left->left->x<<" "<<rb.root->left->left->color<<endl;
cout<<rb.root->left->right->x<<" "<<rb.root->left->right->color<<endl;
cout<<rb.root->left->right->right->x<<" "<<rb.root->left->right->right->color<<endl;
redblacktree<int> *r;
r=rb.search(90);
cout<<r->x<<" "<<r->color<<endl;
r=rb.search(65);
cout<<r->x<<" "<<r->color<<endl;
r=rb.search(100);
}