Ok, I think my problem has to do with my rotation functions. It is not performing them correctly though I don't see where they are messing up. On a more complicated tree when it performs a rotation the structure of the tree becomes incorrect. Maybe some one can see something I do not.
template <class generic>
void Bst<generic>::RR(Btn<generic> * x)
{
Btn<generic> *y = x->l;
if(x->p!=NULL)
{
y->p = x->p;
if(x->p->l == x)
x->p->l = y;
else
x->p->r = y;
}
else
{
m_data = y;
y->p = NULL;
}
x->p = y;
x->l = y->r;
y->r = x;
cout<<"m_data"<<m_data->data<<endl;
}
template <class generic>
void Bst<generic>::LR(Btn<generic> * x)
{
Btn<generic> * y = x->r;
Btn<generic> * z = y->l;
if(x->p!=NULL)
{
z->p = x->p;
if(x->p->l == x)
x->p->l = z;
else
x->p->r = z;
}
else
{
m_data = z;
z->p = NULL;
}
y->l = z->r;
x->r = z->l;
z->l = x;
z->r = y;
y->p = z;
x->p = z;
cout<<"m_data"<<m_data->data<<endl;
}
template <class generic>
void Bst<generic>::RL(Btn<generic> * x)
{
Btn<generic> * y = x->l;
Btn<generic> * z = y->r;
if(x->p!=NULL)
{
z->p = x->p;
if(x->p->l == x)
x->p->l = z;
else
x->p->r = z;
}
else
{
m_data = z;
z->p = NULL;
}
y->r = z->l;
x->l = z->r;
z->l = y;
z->r = x;
y->p = z;
x->p = z;
cout<<"m_data"<<m_data->data<<endl;
}
template <class generic>
void Bst<generic>::LL(Btn<generic> * x)
{
Btn<generic> *y = x->r;
if(x->p!=NULL)
{
y->p = x->p;
if(x->p->l == x)
x->p->l = y;
else
x->p->r = y;
}
else
{
m_data = y;
y->p = NULL;
}
x->p = y;
x->r = y->l;
y->l = x;
cout<<"m_data"<<m_data->data<<endl;
}
Here are my rotation functions. The passed x is the node which the rotation is performed on.
Here is my insert/balance check/balance factor/and height calculator just in case you think it might be somewhere else
template <class generic>
void Bst<generic>::insert (generic x)
{
bool isInserted = false;
Btn<generic> * temp = m_data;
if(empty())
{
try
{
m_data = new Btn<generic>;
}
catch(std::bad_alloc &)
{
throw Exception(OUT_OF_MEMORY, "OUT OF MEMRORY!");
}
m_data->data = x;
m_data->p = NULL;
m_data->l = NULL;
m_data->r = NULL;
isInserted = true;
}
while(!isInserted && temp->data!=x)
{
if(temp->data > x && temp->l != NULL)
temp = temp->l;
else if(temp->data < x && temp->r != NULL)
temp = temp->r;
else
{
isInserted = true;
if(temp->data > x)
{
try
{
temp->l = new Btn<generic>;
}
catch(std::bad_alloc &)
{
throw Exception(OUT_OF_MEMORY, "OUT OF MEMRORY!");
}
temp->l->data = x;
temp->l->p = temp;
temp->l->l = NULL;
temp->l->r = NULL;
}
else if(temp->data < x)
{
try
{
temp->r = new Btn<generic>;
}
catch(std::bad_alloc &)
{
throw Exception(OUT_OF_MEMORY, "OUT OF MEMRORY!");
}
temp->r->data = x;
temp->r->p = temp;
temp->r->l = NULL;
temp->r->r = NULL;
}
}
}
if(isInserted)
{
m_size++;
balance_check(temp);
}
template <class generic>
int Bst<generic>::height(Btn<generic> * x)
{
if (x!=NULL)
return((height(x->r)>height(x->l) ? height(x->r)+1 : height(x->l)+1));
else return -1;
}
template <class generic>
int Bst<generic>::balancef(Btn<generic> *x)
{
if(x->l!=NULL && x->r != NULL)
{
cout<<x->data<<" "<<height(x->r)<<" "<<height(x->l)<<endl;
return ((height(x->r))-(height(x->l)));
}
else if(x->l==NULL && x->r != NULL)
return (height(x->r)+1);
else if(x->l!=NULL && x->r == NULL)
return ((height(x->l)*-1)-1);
else
return 0;
}
template <class generic>
void Bst<generic>::balance_check(Btn<generic> *x)
{
while(x!=NULL)
{
if(balancef(x) > 1 || balancef(x) < -1)
{
if(balancef(x)==2 && balancef(x->r)==1)
{
cout<<"preforming LL on: "<<x->data<<endl;
LL(x);
}
else if(balancef(x)==-2 && balancef(x->l)==-1)
{
cout<<"preforming RR on: "<<x->data<<endl;
RR(x);
}
else if(balancef(x)==2 && balancef(x->r)==-1)
{
cout<<"preforming LR on: "<<x->data<<endl;
LR(x);
}
else if(balancef(x)==-2 && balancef(x->l)==1)
{
cout<<"preforming RL on: "<<x->data<<endl;
RL(x);
}
}
x = x->p;
}
}
Thanks,
Vince