Informatyka UJ forum

Rogal

Imho dla kogoś kto dobrze programuje i robił takie AVL-e wcześniej takie zadanie jest do zrobienia w czasie 2-5 godzin. De facto można to spokojnie napisać na ok. 400 linii, więc nie jest to nic AŻ tak strasznego.

Natomiast jak ktoś robi to pierwszy raz, ma spore problemy z napisaniem kilku linijek bez błędu (to o mnie), gubi się we wskaźnikach (też o mnie :twisted: ) to może siedzieć 3 dni od rana do nocy i wciąż gdzieś będą jakieś błędy.

jagm

O ile dobrze pamiętam, to nasz ćwiczeniowiec mówił, że sobie musiał przypomnieć przed zajęciami drzewa AVL, bo ostatni raz miał z nimi styczność na I roku :P

Madras

Tak, ale po przypomnieniu i tak długi okres przerwy nie przeszkodziłby mu w dosyć sprawnej implementacji.

jagm

sprawdziłem w rankingu i jeszcze go nie zrobił :P a stara się robić wszystkie ;]

chlebek

Czy moglby ktos zapodac jakis sposob liczenia balancow, po rotacji. Robie Insert z wykladu, ale jakos źle dziala, chcialem zrobic samemu, ale nie wiem jak sprytnie pozniej poustawiac balancy w drzewie, czy ktos robil z wykladu ?

jagm

A nie można było poszukać w tym temacie?

chlebek

jagm

Na przykładzie pojedynczej rotacji w lewo (reszta podobnie na podstawie reszty wzorów)

Przepięcia są tak jak w notatkach z wykładu, czyli na początek
u <- right(w)
teraz pod zmienne pomocnicze sobie podtrawiam balans z u i w.
balans(u)<-old_u_balans-1+min(old_w_balans,0)
balans(w)<-old_w_balans-1+max(old_u_balans,0)
teraz przepięcie wskaźnika na rodzica:
jeśli lewe poddrzewo u nie jest puste, to left(u)^.parent<-w
następnie
u^.parent<-w^.parent
w^.parent<-u
i później dalsze przepięcia jak na wykładzie
right(w)<-left(u)
left(u)<-w
w<-u

Jedyna różnica polega na tym, że balans jest obliczany dla któregoś z balansu równego 2/-2. A na wykładzie robiliśmy w ten sposób, że nie zmienialiśmy tam na 2/-2 tylko sprawdzaliśmy odpowiednie warunki. Więc to trzeba zmienić, albo we wzorze z tą jedynką pokombinowac.
Rotacja w prawo podobnie, a podwójne znów z wykładów można + wzory na balans + przepinanie wskaźnika na rodzica

chlebek

Tzn. ze do tego algorytmu Insert z wykladu nalezy pozmieniac Rotacje wedlug wzoru powyzej, czy tam jest juz wszysko, dlaczego w notatkach nic o tym nie ma ??

jagm

W notatkach masz tylko ogólną ideę. Każdy balans od ostatniego wystąpienia balansu niezerowego aż do miejsca, w którym wstawiasz, zmieniasz o jeden w zależności od tego, czy element wstawiany jest większy czy mniejszy. I ponieważ zaczynałeś sprawdzać od niezerowego, to tam albo dostaniesz -2/2 albo 0. Jeśli 0, to nic nie zmieniasz, a jeśli -2/2, to wykonujesz którąś z rotacji. I w zależności od tego jaki to rodzaj rotacji, ustawiasz balans dla rodzica i dziecka z tych wzorów.
A to, co wcześniej podałem jest zmienione pod mój kod, bo ja robiłem jeszcze ze wskaźnikiem do rodzica, stąd te dodatkowe zamiany. A wzorów rzeczywiście na wykładzie nie było.

exeman

Zrobilem, nareszcie :)
Porada dla tych co nie zrobili: najpierw zrozumiec, a potem pisac. Ja chcialem isc na latwizne, bez zaglebiania sie w temat przepisywalem, kombinowalem i stracilem jakos 40 godzin. Co prawda deleta oparlem na ksiazce Wirtha, ale insterta napisalem sam :D

Fen

ufff... mi także K przeszło! co prawda będę miał -1/3 pk, ale i tak nie mogę narzekać :)
strony z tutorialami o AVL, które gdzieś były podane na forum TSC + zrozumienie działania(szkoda, że nie do końca ;/) + pascal = OKej dla K na Sprawdzarce :)

oinopion

Nawet mi się udało! I to w jakim czasie:1 dzień i 1 noc przed kompem. Nie ma po jak piękny wschód słońca :)
Najciekawsze, że na moim programie gronostaj się wykłada:

exeman

"Blad gronostaja" to komunikat, gdy nie uda sie wczytac wzorcowych .out'ow, nie mam pojecia czemu cos takiego wyskoczylo. Kierujac sie zasada, ze blad jednorazowy nie jest bledem, mysle, ze mozna to poprostu olac :P

Ewka

exemanie powiedz mi prosze
co jest nie tak z deletem w Wircie
bo chciałabym zaoszczędzić 40 godzin :) ??

kap00ch

wg mnie nic nie jest zle :P bo po zeznaniach exemana sam przegladnalem wirta i nie znalazlem nic co by wzbudzilo moje podejrzenia...;]

exeman

Ewka:
1. zamiast bal1:=p; ma byc bal1:=p1; oraz analogicznie gdziestam pozniej.
2. zamiast skrajnie prawego przy usuwaniu brany jest skrajnie lewy (albo na odwrot).

Chyba tyle :)

Ewka

co do pkt pierwszego to faktycznie te dwie procedury nie byłyby symetryczne :)
oj szukałabym tego baaaaaaaardzo długo! dzieki wielkie

a mógłbyś jeszcze bliżej wyjaśnić pkt 2 ??? :)

kap00ch

pkt2 dotyczy samego usuwania a dokladnie podmiany usuwanego elemtnu z jakims koncowym liscie. Wirt ma wersje z usuwaniem skrajnego prawego czyli najwiekszego z mniejszych (inaczej od odnalezionego liscia idziemy jeden w lewo i do konca w prawo). Natomiast my mamy zrobic wer. z wykladu czyli skrajnie lewy - najmniejszy z wiekszych...czyli idziemy jeden w prawo i do konca w lewo.

tak wiec jedyne co trzeba zrobic to odbic symetrycznie procedure us z wirta i potem juz pod sam koniec prog. wywolywac ja nie dla lewego lecz prawego dzieciaka...aczkolwiek nie pochwalam przeklepywania z wirta a tym bardziej az takiego pomagania...ale mam cos dzisiaj samarytanski dzionek :P i na prawde prosze cie Ewka :] : zrob to sama :P

Ewka

kurde no wiem, masz rację że sama powinnam zrobić,
ale mi się tak strasznie nie chce :(
i do tego gorączke mam
ale inserta sama zrobiłam więc nie jest tak źle :D

wogóle to tak się śpieszyłam, żeby zdążyć na drugi termin,
a podobno drugi termin minął dzisiaj rano
a byłam pewna, że jest do środy :(

kap00ch

no to jak masz goraczke i nic cie nie goni to sugeruje isc spac :>

dzendras

@Ewka: Słuchaj wujka kap00cha jak radzi :lol:

Ewka

heheheheh
no może macie racje:)

Madras

Masz coś zrobić dzisiaj - zrób jutro ;].
Stosując tą zasadę mam -2/3 za K ;].

kap00ch

madras - pomysl ze ta zasada wydluza twoj zywot na tym ziemskim padole...np czarnoskorzy mieszkancy wysp afrykanskich uwazaja ze kierujac sie ta zasada moga zostac niesmiertelni, a raczej wieczni gdyz uplyw swojego zycia mierza iloscia pracy jaka wykonaja:P