Algorytm DSW na drzewie BTS

Witam.

Od dwóch dni siedzę nad tym samym i nie potrafię znaleźć błędu, już mam mętlik w głowie. Mam drzewo BTS i potrzebuję stworzyć funkcję do jego równoważenia. Postanowiłem skorzystać z algorytmu DSW (niestety zastosowanie drzewa już z góry zrównoważonego, np. czerwono-czarne, nie wchodzi rachubę; musi to być "czyste" BTS). No i tak, pierwszy etap algorytmu przechodzi u mnie bez problemu (rotacja w prawo wykonuje się poprawnie, z całego drzewa otrzymuję "listę"). Niestety, wykonanie drugiej fazy DSW przebiega u mnie niepoprawnie. Nie potrafię znaleźć błędu w swoim kodzie (obstawiałem na początku lewą rotację, ale toż to po prostu "odwrócona" rotacja w prawo, która działa mi poprawnie). Dla jakich danych działa niepoprawnie? Praktycznie każdych jakie testowałem, chociażby te z wikipedii: http://pl.wikipedia.org/wiki/Algorytm_DSW

Będę wdzięczny za dokonanie poprawki w kodzie/wskazanie błędów jakie popełniam.
Poniżej podaję kod:

void BST::rotacja_w_prawo(BSTNode *wsk)
{
	BSTNode *tmp;
	
	tmp = wsk -> left;
	wsk -> left = tmp -> left;
	tmp -> left = tmp -> right;
	tmp -> right = wsk -> right;
	wsk -> right = tmp;

	int k = wsk -> key;
	wsk -> key = tmp -> key;
	tmp -> key = k;
}

void BST::rotacja_w_lewo(BSTNode *wsk)
{
	BSTNode *tmp;

	tmp = wsk -> right;
	wsk -> right = tmp -> right;
	tmp -> right = tmp -> left;
	tmp -> left = wsk -> left;
	wsk -> left = tmp;

	int k = wsk -> key;
	wsk -> key = tmp -> key;
	tmp -> key = k;
}

void BST::zrownowaz_drzewo()
{

	BSTNode *wrk = root;
	int licznik = 0;

	while(wrk != 0)
	{
		if(wrk -> left != 0)
		{
			rotacja_w_prawo(wrk);
			licznik++;
		}
		else
		{
			wrk = wrk -> right;
		}
	}
	
	int m = pow(2, (int)log2(ile_wezlow + 1)) - 1;

	wrk = root;
	for(int i = 0 ; i < ile_wezlow - m ; i++)
	{
		if(wrk && wrk -> right)
		{
			rotacja_w_lewo(wrk);
		}
	}

	wrk = root;
	while(m > 1)
	{
		m = m / 2;
		for(int i = 0 ; i < m ; i++)
		{
			if(wrk && wrk -> right)
			{
				rotacja_w_lewo(wrk);
			}
		}
	}
}

BSTNode to węzeł (ze wskaźnikami na left, right, parent oraz kluczem), BST to główna klasa, metody do wstawiania, usuwania itd. z drzewka.

Przy rotacjach nie widzę zmian wskaźnika parent.

Dzięki. Nie jestem dobry w algorytmice, słabo idzie mi to główkowanie.

Przeglądając różne pseudo-kody dotyczące rotacji, tylko w niektórych widziałem aby zmienić rodzica. Tzn, miało to nastąpić tylko wtedy gdy węzeł X nie jest korzeniem. Wtedy węzeł X staje się synem swojego syna (tylko którym? lewym czy prawym?)

Zgodnie z sugestią oczywiście dodałem:

if(wsk != root)
{
	tmp = wsk -> p;
	wsk -> p = wsk -> right; // left?
	wsk -> right -> p = tmp;
}

do funkcji rotacyjnych, ale nie za bardzo rozumiem cel tej zmiany. Już pomijam fakt, że z tym kodem, albo bez niego dla podawanych przeze mnie danych wejściowych, algorytm działa identycznie, ale... Przecież tych zamian dokonuję potem i tak, operując po prostu nie na wskaźniku p (parent), ale left i right.

Jeżeli źle rozumuję, wybacz. Naprawdę już przejrzałem kilka implementacji, szukałem wielu przykładów (pseudo-kodów), ale nadal nie mogę znaleźć błędu. Jeżeli nadal popełniam błąd w rotacji, to byłbym wdzięczny za trochę, hmm, większą wskazówkę, dokładniejszą :).