Strukture za sve

uzas · **Poslato:** 28.08.2007. 15:44:27

jel moze neko da uradi postupak formiranja AVL stabla sa rotiranjem. odnosno da napise sta se rotira i u koju stranu i oko kog elementa

npr. rotacija oko (90) ulevo...

jer sam prosao celu temu i nigde nema, a na ispitu oduzimaju bodove ako se to ne napise...

Vlacke · **Poslato:** 28.08.2007. 16:04:48

Rotiras oko onog cvora koji ima disbalans, odnosno cija visina nije -1, 0 ili 1. Ako je taj broj (faktor) negativan (npr. -2) onda rotiras u levo, ako je pozitivan onda u desno. Nekad se moze desiti da tim rotacijama ne dobijes nista, odnosno faktor je opet veci od gore navedenih brojeva (prakticno se vrtis u krug, i faktor ostaje isti samo se menja znak, iz - u +), pa onda moras pre prethodno uradjene rotacije, da rotiras njegovo dete i to na suprotnu stranu , i onda uradis rotaciju oko tog cvora koji ima disbalans. Nadam se da si razumeo, ako nisi, valjda ce neko uspet da ti objasni bolje Generalno, samo pohvataj osnove i malo provezbaj. Meni taj zadatak mora da bude sigurica.

Abraxus · **Poslato:** 28.08.2007. 16:08:36

evo ti dva sjajna appleta za vežbanje svega toga - po meni nema boljeg načina da naučiš:

AVL -> http://www.csi.uottawa.ca/~stan/csi2514 ... vl/BT.html

B -> http://slady.net/java/bt/view.php?w=600&h=450

jezgro · **Poslato:** 28.08.2007. 16:23:33

izvinjavam se nisam ti dobro objasnio sa -1. moze i kod listi -1. znaci elemenat u nizu koji je prazan ima vrednost -1. Bitno je sta zelis da uradis u zadatku. samo ukoliko ubacujes u hash tabelu onda ti treba uslov sa -1 a ukoliko pretrazujes ili izbacujes on je nebitan.
zamisli da imas niz npr. 1, 5,9,null, kada izbacujes na primer 5 to ces uraditi tako sto tom clanu niza (tabela[i]=-1)dodas vrenost -1 i onda dobijas nesto kao 1,-1,9,null. znaci imamo drugi clan koji je "prazan" i onda kada ubacujes imas dva uslova setas dok ne dodjes do null ili dok ne dodjes do clana koji ima vrednost -1 i tu ubacujes vrednost. znaci petlja izgleda ovako za ubacivanje

Kod:

public void ubaci (HashTable[] Tabela, int podatak)
int i = podatak % tabela.length; //ovo je primena hash funkcije sa duzinom niza
{  
    while(tabela[i]!=null && tabela[i]!=-1) // znaci -1 dok ne naidjes na prazno mesto
      {
        ++ i; //seta kroz niz
       }
   Tabela[i]=podatak;
}

ovo ce ubaciti novi elemenat transformacijom podatka (kljuca) u adresu.[/code]

Abraxus · **Poslato:** 28.08.2007. 16:27:41

ААААААААААААААААААААААААаааааааааааааааа . . . аli nigde se nije tražilo ubacivanje . . literatura ovog predmeta je tako sredjena . . . :sarkazam:

mada sa druge strane gotivan mi je ceo ovaj zanatski trip

balkan · **Poslato:** 28.08.2007. 16:47:15

Da vas pitam ...kod ovog zadatka:

2. Napisati algoritam za sortiranje niza celih brojeva metodom ubacivanja (insertion sort).
(12 poena)

zna li neko ovo da pojasni?
jel to resavamo metodom PUSH(object arg) ili neki drugi nacin?

uzas · **Poslato:** 28.08.2007. 16:55:20

'fala Abraxus, Vlacke 'fala i tebi, razumem ja kako to ide, samo ne znam kako se to crta i pise

to sa strelicama i rotacijama... ja sam uradio u proslom roku kao sto ima ovde na site-u ali jedva da su mi nesto priznali

(bez da sam pisao rotacije i ulevo udesno)

balkan evo ti ovde imas kodove za sva sortiranja...

http://strukture.labis.fon.bg.ac.yu/dow ... iranje.zip

miki47 · **Poslato:** 28.08.2007. 17:41:14

balkan je napisao:

kada nam je dat u zadatku red 4 jel to znaci da je max. br. kljuceva u listu 4-1=3? a minmalni broj 1?

Maksimalan broj kljuceva je 4, a minimalan, 1.

Abraxus · **Poslato:** 28.08.2007. 17:55:25

u slučaju da imaš 4 ti cepaš čvor . .. tako da tri je maximum . . ne?

balkan · **Poslato:** 28.08.2007. 18:31:59

miki47 je napisao:

balkan je napisao:

kada nam je dat u zadatku red 4 jel to znaci da je max. br. kljuceva u listu 4-1=3? a minmalni broj 1?

Maksimalan broj kljuceva je 4, a minimalan, 1.

Slazem se sa Abraxus-om , Miki ja mislim da nije 4 a i da jeste onda bi minimum bio 4div2=2 a ne 1 element...jel ima neko da potvdi ovo?

Takodje jel ume neko ovo dodatno da pojasni,a probao i crtao al uputsvo ne razumem

:

April ONeil je napisao:

Vlacke je napisao:

Zna li neko resenje teorijskog pitanja iz junskog roka? Treba da se objasni pretvaranje VST u binarno i da se da primer.

Objasniti na ovaj nacin (bez crtanja) malo je nezahvalno ali pokusacu...
1. korak: svi cvorovi na istom nivou se spajaju (vezama istim kao dete-roditelj)
2. korak: na svakom od cvorova raskidamo vezu sa roditeljem osim za prvi cvor
3. korak: sada svaki cvor ima 2 veze, jednu sa roditeljem (koji mu je ranije bio brat) i sa svojim bratom (naknadno povezanim)
4. korak: okrecemo stablo i ono izgleda kao klasicno binarno stablo

Preporucila bih da crtate uz ove korake, po mogucstvu u dve boje za nove i stare veze (meni je pomoglo).

uzas · **Poslato:** 28.08.2007. 18:57:58

Ne znam sto komplikujete stvar, minimalni broj kljuceva je po logici uvek 1... (mada ne znam sta ce vam uopste taj podatak)
Max. broj kljuceva je obicno zadat u zadatku, ako nije, odnosno ako je dat red onda se ovaj smanji za jedan... (glupost)

za prebacivanje VST u binarno, ne znam sta ti nije jasno, uzmi olovkom nacrtaj stablo, onda izbrisi sve veze, zatim spoji bracu (sve na istom nivou) i sve uz desnu ivicu, onda rotiras stablo i dobijes

tako sam barem ja skapirao...

balkan · **Poslato:** 28.08.2007. 19:26:02

Evo da zakomplikujem jos malo

u martu kad samo malo nesto spremao Moma je rekao:

http://www.fonforum.org/viewtopic.php?t=9037&start=0

odnosno:

Citiraj:

zavisi sta ti pise u zadatku: nekad pise maksimalni broj kljuceva je n, nekad pise da je red stabla n
da, gleda se ceo deo, to je div

max broj kljuceva,ako je n red, je n a min je n div 2 i ne vazi za koren
max broj podstabla koji moze da ima neki cvor je red stabla + 1 (ova cela prica vazi za B stabla, koja su u stvari balansirana visegranska stabla)

e,sad, mozda ce se javiti neka koleginica da me ispravi ako je potrebno

Znaci mozda je ipak miky bio u pravu:max=4 :((

A za prebacivanje VST u binarno ako sam razumeo:
...............5
............./ \
.......... 3 7
........ / \ / \
........1 2 6 8

.............<=>
............... 5
.............3-7
.......1-2-6-8
............. <=>
i kako onda rotiram uzas? Sta je ovde roditelj i koja su njegova deca?
Prvi put radim ovo pa se sporije palim

miki47 · **Poslato:** 28.08.2007. 20:29:23

Ne, vi ste u pravu, proucio sam skriptu.
Ako je red stabla 4, svaki cvor moze da sadrzi najvise 3 elementa.
Mada, na ispitu uglavnom kazu:"maksimalan broj elemenata je...", tako da nema zabune.
Izvinjavam se.

uzas · **Poslato:** 28.08.2007. 21:30:19

Kod:

nisi procitao do kraja sta sam ti napisao...

ali evo... spojis sve uz desnu ivicu znaci 5-7-8

              5  
               \ 
             3-7 
                 \ 
         1-2-6-8 

i onda rotiras i dobijes ovako

                 8
                / \
              7    6
             / \     \
           5   3     2
                        \
                         1

tako da bi to trebalo da bude to, jeste malo izdegenerisano i ne balansirano, ali binarno jeste :)

neka me neko ispravi ako ne valja...

malo je izdegenerisan post, ali vidi se  :D 

balkan · **Poslato:** 28.08.2007. 21:34:34

Hvala ti, legenda si!!!
ako je to to onda extra! :cool:

Vlacke · **Poslato:** 28.08.2007. 23:40:09

uzas je napisao:

'fala Abraxus, Vlacke 'fala i tebi, razumem ja kako to ide, samo ne znam kako se to crta i pise

to sa strelicama i rotacijama... ja sam uradio u proslom roku kao sto ima ovde na site-u ali jedva da su mi nesto priznali

(bez da sam pisao rotacije i ulevo udesno)

Pa kako onda treba da se pise?! Sta, e li treba dam im ispisem recima svaki korak i zasto to radim? Ja sma mislio daj edovoljno da nacrtam faktore iznad svakog cvora i strelicu u kom pravcu rotiram. e da, srecno svima danas.

jezgro · **Poslato:** 29.08.2007. 01:33:08

@balkan to sti si ti poceno napisao nije VST stablo nego je vec binarno(doduse nepravilno) sto je dovelo do zbunjivanja.
@uzas
nije ti dobro. napisi pocetno stablo (ne moze ovo koje je gore napisao balkan) pa cu ti reci kako ide; u slucaju da je ovo dole pocetno (uzeo sam brojeve koje ste vi koristili za VST) onda ide ovako:

Kod:

pocetno koje nije binarno    
      5
    /   \
   3      7
 / | \     \
1  2  6     8
nove veze
     5
   /   
  3 -  7
 /        \
1 -2- 6   8
binarno stablo
     1
   /   \
  2     3
 /      / \
6     7    5
      /
     8  

Abraxus · **Poslato:** 29.08.2007. 06:53:01

jel' zna neko tačno šta je infix, šta prefix, šta postfix obilazak?

jezgro · **Poslato:** 29.08.2007. 07:58:00

vec smo govorili da to jeprolaz prolaz kroz stablo.
prefix (koren, levo, desno)
infix(levo, koren, desno)
postfix (levo, desno, koren)

balkan · **Poslato:** 29.08.2007. 09:27:55

@jezgo jasna mi je slika tvoja ali samo jedno pitanje zar kod binarnog stabla ne treba da bude ispunjen uslov da svaki cvor ima dva deteta,posto na ovoj slici vidim vorove bez dece,jel to moze tako?

Vlacke · **Poslato:** 29.08.2007. 11:16:26

?naravno da moze. Ti cvorovi koji nemajbu dece su listovi. Kod binarnog je uslov da bude MAX dvoje dece, ali moze i da nema ili da ima samo jedno.

@jezgro - a zar nije fora da raskines veze sa savima sem sa jednim detetom, a ti u tvom primeru ne raskidas veze 5-ice sa 7-icom ili 6-icom?

jezgro · **Poslato:** 29.08.2007. 11:30:02

evo pogledaj gore ispravio sam, tacno je da sam napravio gresku

uzas · **Poslato:** 29.08.2007. 12:03:31

jedno pitanje zar ne treba 8 da se poveze sa 6 a prekine veza sa 7 :zbun:

kolko ja kapiram raskidaju se veze otac roditelj i spajaju se braca?

6 i 8 su cvorovi na istom niou. :zbun:

jezgro · **Poslato:** 29.08.2007. 12:25:54

ne sme da se prekine jer je on 8 jedini koji je vezan sa 7. evo kada bi se prekinula veza izmedju 7 i 8.

Kod:

        5
    /      \
   3          7
 / | \       /  \
1  2  6     9    8 

e sada bi pukla veza izmedju 7 i 8
7
/
9 - 8

6 i 9 u ovom slucaju ne bi bili povezani jer nisu braca.

balkan · **Poslato:** 29.08.2007. 19:28:54

jel cuo neko kad ce rezultati?

FONForum

Strukture za sve

Ko je OnLine