drzewo avl

Mam pewien problem z rotacjami w drzewie avl. Oto kod rotacji.

void prawa()
		{
		drzewo *korzen=this;

		drzewo *nowe;		
		nowe=this->l;
		nowe->parent=NULL;
		nowe->p=this;
		nowe->p->parent=this;
		nowe->p->l=NULL;
		nowe->postorder();
		nowe->wagi();		
		}

Jest to kod rotacji w przypadku podania liczb 5,4,3. Funkcja prawa znajduje sie w klasie drzewo. Funkcja ta na podtawie obieltu this generuje nowe drzewo po obrocie i to dziala dobrze ale teraz chcial bym to drzewo podpiac do starego w miejsce this
Tak wyglada stare drzewo a tak wyglada nowe
5 4
/ /
4 3 5
/
3

Obiekt nowe jest tym nowym drzewem ale jak je podstawic teraz w miejsce starego aby wszystkie funkcje korzystaly z nowgo drzewa?

Nie rozumiem do końca tego kodu, ale moim zdaniem źle robisz :p nie musisz tworzyć nowego drzewa wystarczy pozmieniać powiązania. Po prostu piątka teraz ma nie mieć w ogóle synów, czwórka ma mieć piątkę jako prawego syna, do tego wypadałoby zamieniać dla rodzica piątki, że teraz jego synem jest czwórka.

Polecam także rozpatrzeć ogólniejszy przypadek rotacji prawej, mianowicie takie drzewo:

    5
   / \
  3  6
 / \
2   4

zamienia się w:

    3
   / \
  2  5
     / \
    4  6

twoje drzewo jest po prostu takim przypadkiem w ktorym elementy 4 i 6 nie istnieją.

wiem ze wystarczy pozmiwnieac dowiazania ale nie moge sobie z tym poradzic. Drzewo za kazdym razem sie sypie. Jak podpiac to wygnenerowane pod moje glowne drzewo w miejsce this.

http://pl.wikipedia.org/wiki/Algorytm_DSW

Dzieki. Nie znalazlem tego. Bede sie mial czym wesprzec przy pisaniu programu.

Hmm, on ci podał link trochę nie na temat. Owszem rotacje wyglądają podobnie jak w AVL, ba, chyba nawet identycznie, ale ogólnie wstawianie wygląda tam inaczej.

Polecam raczej: http://pl.wikipedia.org/wiki/AVL

qq napisał(a)

Hmm, on ci podał link trochę nie na temat. Owszem rotacje wyglądają podobnie jak w AVL, ba, chyba nawet identycznie, ale ogólnie wstawianie wygląda tam inaczej.
Jakie wstawianie ??? Tam jest samo równoważenie drzewa AVL, całkowicie na temat.

Z tego co wiem wszystkie operacje na drzewie AVL są w czasie logn (co z resztą jest w drugim linku) także nie ma sensu używać tego algorytmu DSW ponieważ psuje się cała jego idea. Sory że odkopuję ale to jest dość ważna sprawa i jeśli ktoś ma zrobić drzewo na jakieś zaliczenie przy jak najlepszej złożoności czasowo pamięciowej to polecą mu punkty.