Witam,

Aktualnie zajmuję się zagadnieniami związanymi z balansowaniem drzew. Niestety mimo upływu dni i nieprzespanych nocy, nie udało mi się rozwiązać problemów rotacyjnych. Moja wiedza o świecie c++ jest na tyle znikoma, że kończy się na wskaźnikach i przeciążeniach.

Proszę o przejrzenie kodu i danie mi jakiś wskazówek. Jestem już w rozpaczy...

Klasy:

class Node
{
  public:
    int key;
    Node * p;     //rodzic
    Node * left;  //lewy potomek
    Node * right; //prawy potomek
    int height;   //wysokosc drzewa
};
class BST
{
  public:
    Node * root;                           //korzeń drzewa
    int count;                             //liczba węzłów
    BST();                                 //konstruktor domyslny drzewa
    bool   insert(Node * n);               //dodawanie nodow
    int bstheight(Node * p);               //wysokosc drzewa
    Node * rotationL(Node * &p1);          //rotacja pojedyncza LEWA
    Node * rotationR(Node* &p1);           //rotacja pojedyncza PRAWA
    Node * rotationLL(Node * &p1);         //rotacja podwójna Lewa
    Node * rotationRR(Node * &p1);         //rotacja podwójna PRAWA
};

Metoda dodawania nodów:

bool BST::insert(Node * n)
{
    Node * y, * x = root; //x jest wskaznikamni na root

    y = n->left = n->right = NULL; //y jest pustym nodem i n left i n right tez
    int m,t,d;

    while(x)
    {
      if(n->key == x->key) //jesli juz taka wartosc istnieje wyjdz!
      {
         delete n;
         return false;
      }
      y = x; //przypisanie x do y(temp) 
      x = (n->key < x->key) ? x->left : x->right;
    }

    n->p = y; //rodzicem N jest Y

    if(!y) root = n; //jesli Y nie istnieje to korzeniem jest n!!
    else if(n->key < y->key) //jesli n key jest mniejsze od parent key to  n jest lewym potomkiem
    {
        y->left  = n;
         if ((bstheight(n->left) - bstheight(n->right))==2)//tu jest blad. porownuje n-left z n-right ktore nie istnieja
         {
          if (n->key < n->left->key)
          n=rotationL(n);//pojedyncza rotacja lewa
          else
          n = rotationLL(n);//podwojna rotacja lewa
         }
    }
    else        //jesli n key jest mniejsze od parent key to  n jest PRAWYM potomkiem             
    {
        y->right = n;
        if ((bstheight(n->right) - bstheight(n->left))==2)//tu jest blad. porownuje n-right z n-light ktore nie istnieja
        {
          if (n->key > n->right->key)
            n=rotationR(n);//pojedyncza rotacja prawa
          else
            n = rotationRR(n);//podwojna rotacja prawa
         }
    }

     (n->p) ? n->height=n->p->height+1 : n->height=0;

    count++;
    return true;     

}

Rotacje:

Node* BST:: rotationL(Node * &p1)
{
    Node * p2;
    p2 = p1->left;
    p1->left = p2->right;
    p2->right = p1;
    p1->height = max(bstheight(p1->left),bstheight(p1->right)) + 1;
    p2->height = max(bstheight(p2->left),p1->height) + 1;
    return p2;
}
//-------------------------------------------------------------------------
Node * BST:: rotationR(Node* &p1)
{
    Node* p2;
    p2 = p1->right;
    p1->right = p2->left;
    p2->left = p1;
    p1->height = max(bstheight(p1->left),bstheight(p1->right)) + 1;
    p2->height = max(p1->height,bstheight(p2->right)) + 1;
    return p2;
}
//-------------------------------------------------------------------------
Node * BST:: rotationLL(Node * &p1)
{
    p1->left=rotationR(p1->left);//prawa
    return rotationL(p1);//lewa
}
//-------------------------------------------------------------------------
Node * BST::rotationRR(Node * &p1)
{
    p1->right = rotationL(p1->right);//lewa
    return rotationR(p1);//prawa
}

Problem jest taki, że z odejmowania
if ((bstheight(n->left) - bstheight(n->right))==2)
przy czym n jest węzłem świeżo dodanym który nie posiada jeszcze lewego dziecka ani prawego.
jakie dwa Nody powinienem porównywać? X? Y? N?

Jeszcze raz proszę o pomoc.

Ps. Proszę także o ocenienie stylu pisania.