b0r0 Temat założony przez niniejszego użytkownika |
[cpp] Drzewo BST, algorytm DSW i rotacja » 2014-12-15 13:44:01 Witam mam problem z rotacja węzłów drzewa BST przy rotacji w prawo dla elementów, które zaraz nad sobą mają korzeń wszystko idzie dobrze. Problem sie zaczyna jak rotuje element na niższym poziomie, po wyjściu z funkcji totate_r nagle gubi powiązanie do nastepnych elementów. sprawdzam na takim zestawie danych: 5,2,3,4,1,6 czyli mam na starcie: 5 / \ / \ / \ / \ / \ 2 6 / \ 1 3 \ 4 i dochodzi do momentu: 1 \ 2 \ 5 / \ 3 6 \ 4 i po rotacji 3 i wyjściu z rotate_r 2 gubi prawego potomka sam nie wiem czy źle przekazuje argumenty czy gdzieś indziej schrzaniłem void rotate_r( wezel * parent, wezel * child )
{
wezel * gparent = NULL;
wezel * gcl = NULL;
wezel * gcr = NULL;
gcl = child->l_syn;
gcr = child->p_syn;
if( parent != root )
{
gparent = znajdz_rodzica( root, parent->wartosc );
if( gparent->l_syn == parent )
{
parent->l_syn = gcr;
child->p_syn = parent;
gparent->l_syn = child;
}
else
if( gparent->p_syn == parent )
{
parent->l_syn = child->p_syn;
child->p_syn = parent;
gparent->p_syn = child;
in_order_tree_level( root, 0 );
cout << endl;
}
else
{
cout << "Blad!" << endl;
}
}
else
{
if( child != root )
{
wezel * tmp = parent;
root = child;
root->p_syn = tmp;
root->p_syn->l_syn = gcr;
}
else
{
cout << "Blad!" << endl;
}
}
}
void rotate_l( wezel * parent, wezel * child )
{
wezel * gparent = NULL;
wezel * gcl = NULL;
wezel * gcr = NULL;
gcl = child->l_syn;
gcr = child->p_syn;
if( parent != root )
{
gparent = znajdz_rodzica( root, parent->wartosc );
if( gparent->l_syn == parent )
{
gparent->l_syn = child;
child->l_syn = parent;
parent->p_syn = gcl;
}
else
if( gparent->p_syn == parent )
{
gparent->p_syn = child;
child->l_syn = parent;
parent->p_syn = gcl;
}
else
cout << "Blad!" << endl;
}
else
{
if( child != root )
{
wezel * tmp = parent;
root = child;
root->l_syn = tmp;
root->l_syn->p_syn = gcl;
}
else
cout << "Blad!" << endl;
}
}
wezel * rotate( struct wezel *& start, int wart )
{
wezel * rot;
if( start == NULL )
{
cout << "Nie ma takiego elementu lub tablica pusta!" << endl;
return start;
}
else
if( wart < start->wartosc )
{
rot = rotate( start->l_syn, wart );
rotate_r( start, rot );
}
else
if( wart > start->wartosc )
{
rot = rotate( start->p_syn, wart );
rotate_l( start, rot );
}
else
{
if( start->wartosc == wart )
{
return start;
}
}
}
|
|
darko202 |
» 2014-12-15 14:32:51 jeśli dobrze zrozumiałem to problem występuje, gdy mamy sytuacę 1 \ 2 \ 5 / \ 3 6 \ 4 i zmieniamy 3 z 5 parent = 5 {3,6} child = 3 {gcl = null, gcr=4} znajdz rodzica dla 5 wtedy gparent = 2 { null, 5} else //parent = 5 {null,6} // child = 3 {gcl = null, 5 } tracimy gcr=4} //gparent = 2 { null, 3} //tracimy 5 void rotate_r( wezel * parent, wezel * child )
{
...
if( parent != root )
{
gparent = znajdz_rodzica( root, parent->wartosc );
if( gparent->l_syn == parent )
{...}
else
if( gparent->p_syn == parent )
{
parent->l_syn = child->p_syn;
child->p_syn = parent;
gparent->p_syn = child;
...
}
po wyszczególnionych operacjach mamy 1 \ 2 \ 3 \ 5 \ 6 zgubiliśmy 4 gdyż nadpisaliśmy ją 5, a nie zaproponowaliśmy nowego miejsca |
|
b0r0 Temat założony przez niniejszego użytkownika |
» 2014-12-15 21:47:05 Niestety nie tu leży problem. Czwórki nie gubiłem tylko to co było po 2 czyli tak jak by 2 nagle zapominała prawego potomka. I to tak jakby dzieje się po wyjściu z funkcji. I tylko po rotacji 3. Lub bardziej ogólnie po rotacji w prawo elementu którego rodzicem nie jest korzeń, czyli ma "dziadka". Wygląda mi jak problem przy przekazywaniu adresów, tyle że, o ile dobrze ogarniam jeszcze wskaźniki, skoro wskazuje mu na adresy które istnieją po za funkcją tom nie powinien nagle ich gubić. Zastanawiam się czy czasem nie mam błędu ze zwracaniem elementu z funkcji szukającej parenta wezel * znajdz_rodzica( struct wezel * start, int wart )
{
wezel * rodzic = NULL;
if( start == NULL )
{
cout << "Nie ma takiego elementu lub tablica pusta!" << endl;
return start;
}
else
if( wart < start->wartosc )
{
rodzic = znajdz_rodzica( start->l_syn, wart );
if( rodzic == start->l_syn && rodzic->wartosc == wart )
return start;
else
return rodzic;
}
else
if( wart > start->wartosc )
{
rodzic = znajdz_rodzica( start->p_syn, wart );
if( rodzic == start->p_syn && rodzic->wartosc == wart )
return start;
else
return rodzic;
}
else
{
return start;
}
}
|
|
darko202 |
» 2014-12-16 09:14:35 wydaje mi się że problem leży w rekurencyjnym wywołaniu funkcji znajdz_rodzica
zastanawiam się nad sensem ich zastosowania w tej funkcji
przecież jak stoisz na szczycie drzewa to idąc po drzewie widzisz wszystkich kolejnych rodziców i ich potomków
a w funkcji rekurencyjnie kolejno szukasz rodzica dla 1->2->...->NULL ten wynik nie jest więc dziwny. to właśnie otrzymałeś
jeśli nie używasz debugera to :
1.
ponumeruj if/else i wyświetlaj je
np.
cout << "rotare_1 iF A" << endl;
2.
wyświetlaj stan zmiennych
3.
możesz też po wyjściu z każdej procedury wyświetlić stan całego drzewa
4.
zobacz też stan wejścia rekurencji znajdz_rodzica
wszystko to pozwoli Ci to dokładnie zobaczyć w którym momencie następuje błąd
|
|
b0r0 Temat założony przez niniejszego użytkownika |
» 2014-12-17 00:16:27 Znalazłem błąd
Tkwił on w funkcji która miała za zadanie odpowiednio wywołać rotate_r lub rotate_l. Problem polegał na tym, że najpierw wywoływała rotate_r a potem (przez to ze nie zadbałem o przerwanie rekurencji) i tak wywoływała rotate_l
Sprawdzę jeszcze to wyszukiwanie rodzica bo być może jeszcze mnie zaskoczy :)
Dzięki za pomoc! |
|
| « 1 » |