Witam serdecznie siedze nad tym zadaniem dosyć długo i nie moge ogarnąć co jest źle może ktoś mi pomo<ort>rz</ort>e chodzi mi o metode wstawiania elementu do drzewa avl i balansowania rotacjami zaimplementowałem dodawanie elementu, aktualizacje bf(roznicy wysokosci) jak widac w kodzie zrobiłem najprostsza rotację RR i działa na konkretnym drzewie ze wskazaniem na konkretny wezeł ale gdy używam jej w metodzie addAVL juz nie działa dlatego pozwoliłem sobie sprawdzić nie korzystając z metody tylko pisząc to na sztywno w tej metodzie addAVL i napotykam dziwny problem bo modyfikując jakiś węzeł rotacją i po zmodyfikowaniu wypisując zmodyfikowane węzły od razu pod wykonaną rotacją drukuje mi te węzły dobrze zrotowane ale to moje drzewo jakoś nie zapamiętuje tych zmian szukam i szukam ale nie moge się dopatrzeć o co chodzi miejsce w kodzie gdzie rotuje na sztywno zakomentowalem
import java.util.Stack;
public class MyAVL extends AVL {
public MyAVL (int a)
{
super (a);
}
@Override
public void print(int poziom) {
String o=" ";
String odstep="";
for(int i=0;i<poziom;i++)
odstep=odstep+o;
if(prawy!=null)
prawy.print(poziom+1);
System.out.println(odstep+dane+"("+bf+")");
if(lewy!=null)
lewy.print(poziom+1);
}
@Override
public Pair<AVL, Stack<AVL>> searchBST(int szukany) {
MyAVL pomocnicze=new MyAVL(dane);
boolean warunek= true;
pomocnicze.lewy=lewy;
pomocnicze.prawy=prawy;
Stack <AVL> stos=new Stack<AVL>();
stos.add(pomocnicze);
while (pomocnicze.dane!=szukany&&warunek==true)
{
if(pomocnicze.dane>szukany)
{
if(pomocnicze.lewy!=null)
{
stos.add(pomocnicze.lewy);
pomocnicze=(MyAVL)pomocnicze.lewy;
}
else
warunek =false;
}
else
{
if(pomocnicze.prawy!=null)
{
stos.add(pomocnicze.prawy);
pomocnicze=(MyAVL)pomocnicze.prawy;
}
else
warunek=false;
}
}
Pair para=new Pair(null,stos);
if (warunek==true)
{
para=new Pair(pomocnicze,stos);
}
else if(warunek==false)
{
para=new Pair(null,stos);
}
return para;
}
@Override
public AVL addAVL(int nowy) {
int typRotacji=0;
MyAVL korzen=new MyAVL (dane);
korzen.lewy=lewy;
korzen.prawy=prawy;
Stack <AVL> stos=new Stack<AVL>();
stos.add(korzen);
AVL drzewo;
if(nowy>dane)
{
if(prawy!=null)
{
drzewo=prawy;
stos.add(drzewo);
}
else
{
prawy=new MyAVL(nowy);
drzewo=prawy;
stos.add(drzewo);
}
}
else if(dane==nowy)
{
drzewo=new MyAVL(nowy);
}
else
{
if(lewy!=null)
{
drzewo=lewy;
stos.add(drzewo);
}
else
{
lewy=new MyAVL(nowy);
drzewo=lewy;
stos.add(drzewo);
}
}
while(drzewo.dane!=nowy)
{
if (nowy>drzewo.dane)
{
if(drzewo.prawy!=null)
{
drzewo=drzewo.prawy;
stos.add(drzewo);
}
else
{
drzewo.prawy=new MyAVL(nowy);
drzewo=drzewo.prawy;
stos.add(drzewo);
}
}
else if(nowy<drzewo.dane)
{
if(drzewo.lewy!=null)
{
drzewo=drzewo.lewy;
stos.add(drzewo);
}
else
{
drzewo.lewy=new MyAVL(nowy);
drzewo=drzewo.lewy;
stos.add(drzewo);
}
}
}
//****************************************AKtualizacja bf po wstawieniu wezla
drzewo=stos.pop();
AVL ojciecDrzewa=stos.pop();
while(stos.isEmpty()==false)
{
if(drzewo.dane>ojciecDrzewa.dane)
ojciecDrzewa.bf=ojciecDrzewa.bf-1;
else
ojciecDrzewa.bf=ojciecDrzewa.bf+1;
drzewo=ojciecDrzewa;
ojciecDrzewa=stos.pop();
if (drzewo.bf==-2&&drzewo.prawy.bf==-1)
{
AVL dziadek=ojciecDrzewa; //tu rotuje na sztywno
AVL ojciec=drzewo;
AVL syn=drzewo.prawy;
dziadek.prawy=syn;
ojciec.prawy=syn.lewy;
syn.lewy=ojciec;
syn.bf=syn.bf+1;
ojciec.bf=ojciec.bf+2;
drzewo=syn;
ojciecDrzewa=dziadek;
dziadek.print(2); //wypisuje efekt rotacji bezposrednio pod rotacją i wypisuje dobry wynik ale gdy wywoluje adAVL w mainie to po wydrukowaniu drzewa nie wypisuje drzewa jak nalezy
}
}
if(drzewo.dane>ojciecDrzewa.dane)
bf=bf-1;
else
bf=bf+1;
korzen=new MyAVL(dane);
korzen.lewy=lewy;
korzen.prawy=prawy;
return korzen;
}
public AVL rotacjaRR(AVL OjciecDrzewa,AVL drzewo)
{
AVL Ojciec=drzewo;
MyAVL dziadek=(MyAVL) OjciecDrzewa;
AVL syn=Ojciec.prawy;
syn.lewy=Ojciec;
Ojciec.prawy=null;
dziadek.prawy=syn;
Ojciec.bf=0;
syn.bf=syn.bf-1;
dziadek.bf=dziadek.bf-1;
return dziadek;
}
}
@Override
public AVL removeAVL(int v) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
}
public static void main(String[]arc)
{
MyAVL test2=new MyAVL(3);
test2.addAVL(4);
test2.addAVL(5);
test2.addAVL(6);
test2.print(2) ; //przy wypisaniu tu pokazuje zly wynik
// test2.addAVL(7);
// test2.addAVL(8);
MyAVL test3=new MyAVL(1);
}
}
Sama rotacja powinna działać dobrze więc pewnie coś nie tak w referencjach na elementy poszczególne proszę o pomoc;P