Witam,
Mam następujący problem z wstawianiem do RB-drzewka.Problem postaram się przedstawić na następującym przykładzie.
Mam następujące liczby : 100,200,250,248 . Chcę je w takiej kolejności wstawić do RB-drzewka. Wstawiam 100, wstawiam 200,wstawiam 250. Drzewo wygląda jakoś tak :
100
/ \
NULL < 200>
/ \
NULL < 250 >
/ \
NULL NULL
< > = węzeł czerwony
Jak wiadomo w takim przypadku następuje rotacja,konkretnie prawa,mój kod rotacji prawej :
void drzewo:: prawa_rotacja(drzewo_obiekt* x)
{
drzewo_obiekt* y=x->left;
x->left=y->right;
if( y->right !=NULL)
{
x->right->ojciec=x;
}
y->ojciec = x->ojciec;
if( x->ojciec !=NULL)
{
if (x == x->ojciec->right)
{
x->ojciec->right = y;
}
else
{
x->ojciec->left = y;
}
}
else
{
root=y;
}
y->right = x;
x->ojciec = y;
}
I tu następuje problem,ponieważ gdy spojrzymy na przykładowe drzewo to : Rotacja uruchamiana jest z wezłem x który w naszym przypadku wynosi 200 ( według algorytmu ). X->left to u nas NULL,wobec tego : y=NULL.
Dochodzimy do linijki x->left=y->right; gdzie wskaźnik left ma pokazywać na to na co wskaźnik y->right.Jednak jak wiadomo y jest NULL'em wobec tego debugger wywala Segmention fault.
Chwila myślenia i wpadłem na taki pomysł,podstawmy przy dodawaniu obiektu do drzewa inny obiekt który będzie czarny i to on będzie od tej pory robił za NULL'a . Tak też zrobiłem, stworzyłem nowy obiekt mojej struktury,nazwany NIL ( kod poniżej ) i w miejscu gdzie ustawiam wskaźniki left oraz right mojego nowo wstawionego obiektu,nazwamy NOWY,to zamiast NULL wstawiam NIL
NOWY->left=NIL.
Tak przerobiony program działa jednak gdy próbuje wydrukować drzewo w porządku in-order dostaje śmieszne wartości,wstawiana wartość jest wielkrotonie dublowana i zamiast wstawionych 4 elementów na ekranie pokazuje mi się ich z 30...
Kod klasy wraz z strukturą
class drzewo
{
public:
struct drzewo_obiekt
{
drzewo_obiekt *left;
drzewo_obiekt *right;
drzewo_obiekt *ojciec;
int wartosc;
int glebokosc_wezla;
bool czerwony;
};
drzewo_obiekt* root;
int rozmiar_danych;
int tryb_pracy;
int *tablica;
int skad_dane;
drzewo(int ile_danych,int tryb_pracy,int wybor)
{
rozmiar_danych=ile_danych;
this->tryb_pracy=tryb_pracy;
skad_dane=wybor;
root=NULL;
tablica=new int [rozmiar_danych];
}
// bool czy_drzewo_jest_puste() const { return root==NULL;}
void QS_sort(int,int);
void generuj_dane();
void start();
void Tree_insert(int,drzewo_obiekt*,drzewo_obiekt*);
void drukuj_inorder(drzewo_obiekt *);
void drukuj_strukture_drzewa(drzewo_obiekt *);
void RB_insert(int);
void lewa_rotacja(drzewo_obiekt*);
void prawa_rotacja(drzewo_obiekt*);
void tree_succesor(drzewo_obiekt*);
void tree_minimum(drzewo_obiekt*);
void RB_delete(int);
void tree_delete_fix();
void start_usuwanie();
};
Kod funkcji wstawiających :
void drzewo:: RB_insert(int value) //0 = czerwony kolor 1 = czarny kolor
{
drzewo_obiekt *nowy=new drzewo_obiekt;
drzewo_obiekt *NIL = new drzewo_obiekt; // obiekt ktory mial w założeniu posłużyć w zastępswie NULL;a
NIL->ojciec=NULL;
NIL->left=NULL;
NIL->right=NULL;
NIL->czerwony=false;
NIL->wartosc=0+glebokosc; //taka dzwina wartość bo jak wiadomo w drzewie BST wartośći ni mogą się powtarzać
Tree_insert(value,nowy,NIL);
nowy->czerwony=true;
drzewo_obiekt* wsk;
while( nowy != root && nowy->ojciec->czerwony == true)
{
if( nowy->ojciec == nowy->ojciec->ojciec ->left )
{
wsk = nowy->ojciec->ojciec->right;
if( wsk !=NULL) //NULL czyli czarny lisc ! ! !
{
nowy->ojciec->czerwony=false;
wsk->czerwony=false;
nowy->ojciec->ojciec->czerwony = true;
nowy= nowy->ojciec->ojciec;
}
else
{
nowy=nowy->ojciec;
lewa_rotacja(nowy);
nowy->ojciec -> czerwony = false;
nowy->ojciec -> ojciec -> czerwony = true;
prawa_rotacja( nowy->ojciec->ojciec );
}
}
else
{
wsk = nowy->ojciec->ojciec->left;
if( wsk !=NULL) //NULL czyli czarny lisc ! ! !
{
nowy->ojciec->czerwony=false;
wsk->czerwony=false;
nowy->ojciec->ojciec->czerwony = true;
nowy= nowy->ojciec->ojciec;
}
else
{
nowy=nowy->ojciec;
prawa_rotacja(nowy);
nowy->ojciec -> czerwony = false;
nowy->ojciec -> ojciec -> czerwony = true;
lewa_rotacja( nowy->ojciec->ojciec );
}
}
}
root->czerwony=false;
}
void drzewo::Tree_insert(int value,drzewo_obiekt* nowy,drzewo_obiekt *NIL)
{
drzewo_obiekt *y=NULL;
drzewo_obiekt *x=root;
nowy->left=NIL;
nowy->right=NIL;
while( x != NULL ) //schodzimy w dol drzewa
{
y=x; //y pokazuje na poprzednie wskazanie x,x schodzimy dalej w dol
if( nowy->wartosc < x->wartosc ) //sprawdzamy czy WARTOSC nowego obiektu jest mniejsza lub wieksza od WARTOSCI obiektu pokazywanego przez X
{
x=x->left; //jak mniejsza to idê w lew¹ stronê
}
else if( nowy->wartosc > x->wartosc )
{
x=x->right; //jak wiêksze to idê w praw¹ stronê
}
} //zszed³em na dól drzewka
nowy->ojciec=y; //probowalem nowy->ojciec = y->ojciec zeby ojcem nowego zostal ojciec y czyli normalny wezel,zle
if( y==NULL)
{
root=nowy;
}
else if( nowy->wartosc < y->wartosc ) //probolwame nowy->wartosc < y->ojciec->wartosc,zeby wartosc nowego byla mniejsca niz wartosc ojca sztucenego wezla a wiec normalnego wezla,zle
{//ostatnie porównania,je¿eli WARTOSC nowego obiektu mniejsza ni¿ wartosc obiektu pokazywanego przez Y
y->left =nowy; //to wskaznik LEFT obiektu pokazywanego przez Y pokazuje na Nowego
}
else
{
y->right=nowy; //to wskaznik RIGHT...
}
glebokosc++;
}
Bardzo proszę o pomoc w rozwiązaniu problemu .
Z góry dziękuję.
Pozdrawiam
soyer92
P.S Przepraszam,za zamieszanie z tematami..