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.