Vincentjames501 0 Newbie Poster

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

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.