Informatyka UJ forum

Pandunia · Gość

[deleted]

Skrobocik

smas

To może się przydać. [link widoczny dla zalogowanych] [trochę się wiesza]
[link widoczny dla zalogowanych] [a ten jest sprawny;)]
Symulacja, jak działają drzewa AVL.

Skrobocik

Ostatnio Lembasik zapodał nam na ćwiczeniach swój program właśnie z afałelami. Fajnie to wygląda

hansu

Hehe, taki w delphi? Pokazywal go na ostatnim wykladzie z WDP... Wie ktos moze skad go wziac?

jagm

Proponuję przeszukać softlaba ;]

Skrobocik

mateo

Jakby ktos byl zainteresowany to dodalem wlasnie do testerki AVLe + generator testow.

Robson

No właśnie - dzięki Mateo - znalazłem multum małych głupich bledów, typu nie zainicjowanie zmiennej czy nie dopiecie wskaxnika, czy chocby pisanie TAK zamiast YES ( :P ) dzieki tym testom... ale delete i tak nie chce działać :(

Robson

Przyrzekam że już nigdy ale to nigdy przenigdy NIE będe KOPIOWAŁ kodu w programi, nawet gdzyby to było 1000 linijek.... ehhh... w koncu sie jednak udało :D

PS. W czasie robienia zadanka udało mi sie zapełnić 5 kartek różnistymi rysunkami z tych drzew. Mam narysowane wszstkie mozliwości i wszystkie przypadki symetryczne. Jesli ktoś by chciał to moge udostepnić, a jak odzew bedzie duzy to moge to na czysto przerysować.
Ale dostepny bede dopiero chyba w poniedizałek...

PS2. Warto sobie zrobic procedurke która rekurencyjnie liczy wysokości drzew i balase, i jak cos sie w drzewku nie zgadza to krzyczy. Mi pomogła bardzo...

ostoj

Robson

No to chyba jednak w wolnej chwili przerysuje to na czysto i bedzie spokój. Mi sie to pewnei tez keidys przyda. Umieszcze to jak bede w domu i bede miał dostep do skanera/aparatu cyfrowego - tak kolo niedzieli moze sie uda :)

ostoj

dzie-ku-je-my :)

Robson

Mam nadzieje ze pomoze:
[link widoczny dla zalogowanych]
Na razie tylko usuwanie ogólne, ale moze za niedługo dam wszystkie mozliwości usuwania dla liści i inserta (insert jest dobrze omowiony na wykladzie, wiec kazdy sobie powinien dać rade na razie).
PS. Proponuje żeby każdy sam sobie rozrysował jak to dziala - tylko tak mozna to zrozumieć całkowicie.

trywialna

Dzieki Robson za te instrukcje:)

Mam jeszcze pytanie, czy to zadanie jest bardzo trudne i czasochłonne? Bo zaczynam je pisać i troche sie go boje=)

Makros

@Robson:

BIG THX !!!

Robson

Trudne nie jest - jest za to bardzo czasochłonne i wymaga wiele ostrożności - każdy mały błędzik czy nie uwzglednienie jednego przypadku sprawia ze wszystko moaze sie wywalić w najbardziej niespodziewanym momęcie. Dlatego tak ważne jest narysowanie sobiw wszystkich mozliwości.

PS. Musze powiedziec ze w czasie robienia tego zadania z każdym krokiem te drzewka coraz bardziej mi sie podobały :)

kap00ch

a mi w cale nie w o juz drugi dzien z rzedu mam inna liczbe rotacji na delete niz trzeba...w dziala dobrze:P

ps. OMG ide sie powiesci! w jednym mijescu mialem 1 zamiast 0 i wszystko poszlo :PPPPP

ps2. uffff....oficjalnie przepchnalem:> coz moge poradzic...po pierwsze wszystkoladnie rozrysowac...nawet jesli robson dal swoje rysunki ktoresa bdb to i tak polecam rozrysowanie chociby zeby lepiej zrozumiec. Po drugie NIE KOPIUJCIE KODU :P zgubilo to jak wiadomo i robsona i rowniez mnie:P.
Po trzecie pamietac o dispose przy delete. Po czwarte nie probowac robic tego ze stosem :P w kazdym razieja robilemi sie zamotalem...latwiej, szybciej i ladniej jest rekurencja. Chyba tyle z ogolnikow...zycze powodzenia;]

trywialna

Hmm czy my mamy napisac procedure rotacji podwojnej, tylko liczyc ilosc rotacji jako 2 pojedyncze? czy 2x uzywac rotacji pojedynczej? bo mi sie wydawalo ze to piersze ale jak teraz patrze na te notatki Robsona to juz\sama niewiem:/

kap00ch

praktycznie jest to bez znaczenia...zamiast podwojnej mozna wykonacdwie pojedyncze..jedyne co sie liczy to zliczanie ilosci rotacji...tak czy siak przy podwojnej liczymy +1lewo +1prawo wiec wychodzi na to samo jakby je miec osobno;]

ostoj

1 - Robson, te przypadki usuwania obejmuja wszystkie mozliwe? (poza liscmi)
2 - jak aktualizujecie balance po rotacjach? jest na to jakis wzorek czy trzeba recznie zawsze ustawiac wszelkie balansy w tych 2-3 wezlach w zaleznosci od tego jakie one maja balanse i rozpatrywac w kazdej rotacji kilka przypadkow? bo zrobilem sobie wstawianie z perfidnym recznym ustalaniem balansow w procedurkach rotacyjnych ale widze ze albo mam za malo przypadkow albo jest jakis wzorek, ktorego juz nie widze...

kg86

wlasnie przepchnalem K :) poszlo zdecydowanie szybciej niz A ;P
tak sobie poradzilem z usuwaniem:
ogolnie:
zmieniamy balans rodzica wtedy, gdy w wyniku usuniecia, oraz rotacji zmniejszyla sie wysokosc poddrzewa... jesli to bylo prawe poddrzewo, to balans rodzica zmniejszamy o 1... jesli lewe poddrzewo, to zwiekszamy o 1 :)
szczegolowo:
chyba najwygodniej stworzyc sobie procedurke, np: zbalansuj(p:wierzcholek) ktora zbada balans rodzica, po tym, jak juz mu ustawimy nowy balans:
1) bal(p)=0 // oznacza to, ze zmienilismy balans z 1-->0 lub z -1-->0 wiec wysokosc drzewa sie zmniejszyla, wiec:
a) jesli p jest prawym synem, to balans(p^.parent) zmniejszamy o jeden i wywolujemy zbalansuj(p^.parent);
b) jesli p jest lewym synem, to balans(p^.parent) zwiekszamy o jeden i wywolujemy zbalansuj(p^.parent);
2) bal(p)=2 // oznacza to, ze zmniejszylismy lewe poddrzewo, a balans zmienilismy z 1-->2, wiec:
a) jesli balans(p^.right)=1 to wykonujemy rotacje pojedyncza w lewo, wysokosc drzewa sie zmniejsza, wiec z rodzicem postepujemy analogicznie jak w 1a lub 1b
b) jesli balans(p^.right)=-1 to wykonujemy rotacje podwojna w lewo, wysokosc drzewa sie zmniejsza, wiec z rodzicem postepujemy analogicznie jak w 1a lub 1b
c) jesli balans(p^.right)=0 to wykonujemy rotacje pojedyncza w lewo, ale z ta roznica, ze po tej rotacji balans(p)=-1, a balans(p^.left)=1 ['normalna' rotacja ustawilaby te balanse na 0], a wysokosc drzewa sie nie zmieni, wiec w tym miejscu przerywamy dzialanie procedury, balans rodzica pozostawiamy bez zmian
3) bal(p)=-2 //oznacza to, ze zmniejszylismy prawe poddrzewo, a balans zmienilismy z -1-->-2, wiec:
a) symetrycznie: balans(p^.right)=1 --> balans(p^.left)=-1; rotacja poj. w lewo --> rotacja poj. w prawo
b) symetrycznie: balans(p^.right)=-1 --> balans(p^.left)=1; rotacja podw. w lewo --> rotacja podw. w prawo
c) symetrycznie: balans(p^right)=0 --> balans(p^.left)=0; rotacja poj. w lewo --> rot poj. w prawo; balans(p)=-1 --> balans(p)=1; balans(p^.left)=1 --> balans(p^.right)=-1
4) bal(p)=+-1 // nic nie robimy, wysokosc drzewa nie ulegla zmianie

x --> y oznacza: tak samo, z tym ze, zamiast x powinno byc y :)

nalezy pamietac, ze jesli p='korzen glowny', to parametrem w rotacji bedzie ten korzen, a nie wskaznik z rodzica na ten element, oraz oczywiscie nie trzeba rozpatrywac warunku, czy p jest lewym, czy prawym synem... bo nie ma ojca ;)

zycze wszystkim powodzenia :)

krzycho

trywialna

:( Właśnie napisałam program, wysłalam i... mam blad RD8:/

Chcialam testowac na virgo i... napisalo mi ze mam za duzy kod zrodlowy.

Okazalo sie ze przez robienie wciec te spacje tak mi zabraly pamiec ze moj program ma 115kb:/

wie ktos moze jak mozna szybko usunac te wciecia bo jakos recznie z 500linijek kodu mi sie nie chce zmieniac, zreszta pewnie by mi sie pomylilo w trakcie:/ help :cry:

Ethlinn

Otwórz plik w edytorze tekstu (Edycja-> Zamień) i podmień dużą ilość spacji na jedną, dwie... czy coś koło tego.