Strukture za sve

kolji~voda~vri · **Poslato:** 07.06.2007. 16:11:44

moze li neko da definise u kratkim crtama ove pojmove:

- BINARY TREE
- B* TREE
- BST TREE
- AVL TREE

beavis · **Poslato:** 07.06.2007. 19:17:10

xXx je napisao:

A 18. zadatak:

15-6-16-18-27

da nije mozda 6-15-16-18-27? jer kad ubacis 15, moras napraviti dvije rotacije, prvo oko 6 (lijevo) pa oko 16 (desno).

VILENJAK · **Poslato:** 08.06.2007. 00:15:27

xXx je napisao:

Ja mislim da je resenje 17. zadatka:

20-10-50-40-45 (znaci ubacimo 45, i onda imamo da izvrsimo 1 rotaciju da bi bilo AVL kod 40, zatim prefiksni prolaz)

A 18. zadatak:

15-6-16-18-27

Ja mislim da je 17. 20-10-45-40-50,a 18. 6-15-16-18-27.Neka me ispravi neko ako gresim.

beavis · **Poslato:** 08.06.2007. 13:07:20

Citiraj:

2. Binarno stablo se naziva HEAP ako za svaki čvor u stablu važi da je njegov sadržaj veći od sadržaja svih ostalih čvorova u njegovim podstablima. Napisati funkciju koja će proveriti da li je dato binarno stablo celih brojeva HEAP.
(20 poena)

Kod:

boolean heap(CvorStabla T){
if (T==null) return true;
if ((T.lijevo.podatak<T.podatak)&&(T.desno.podatak<T.podatak)
     return heap(T.lijevo)&&heap(T.desno);
else return false;
}

da li je to to?

beavis · **Poslato:** 08.06.2007. 13:40:58

Citiraj:

3. Dva binarna stabla su identična ako su ista po strukturi i sadržaju, tj. oba korena imaju isti sadržaj i njihova odgovarajuća podstabla su identična. Napisati funkciju koja će proveriti da li su dva binarna stabla identična.
(15 poena)

Kod:

boolean identicni(CvorStabla k1,CvorStabla k2){
if((k1==null)&&(k2==null)) return true;
if(k1.podatak!=k2.podatak) return false;
if(identicni(k1.lijevo,k2.lijevo)&&identicni(k1.desno,k2.desno)
     return true;
else return false;
}

kako pronaci najdublji cvor?

Abraxus · **Poslato:** 08.06.2007. 14:14:20

Jel vrede štogod domaći ako se izlazi na običan ispit ??

op · **Poslato:** 08.06.2007. 15:03:18

April ONeil · **Poslato:** 08.06.2007. 20:48:22

Jel moze neko da napise sta je Kosta rekao na poslednjim vezbama sta ce biti sad na kolokvijumu? Znam da je pominjao grafove za teorijska pitanja, i da hasing retko dolazi i nesto za sortiranje. Ajde ako je neko vise upucen neka to podeli sa ostalima

xXx · **Poslato:** 08.06.2007. 21:51:08

beavis hvala na saradnji

Izgleda da si me ti jedini ovde ozbiljno shvatio

Prikljucicu ti se od subote i ja sa mojim kodovima :cool:

A domaci ce da vrede nesto na celom ispitu...najverovatnije, Kosta je rekao, da ce da ta 2 domaca menjaju 2 teoretska pitanja sa celog ispita. Tj. sa 2 domaca imas 20 bodova i ne radis 2 teoretska pitanja (koja su u principu i najlaksa).

A sta ce biti na ispitu...govorio je, ali kakve to ima veze - govorio je i za prvi, pa sta je od toga doslo?!!!

Ljudi gledajte ove rokove...svi, ama bas BUKVALNO SVI zadaci na prvom kolokvijumu su bili sa rokova. Evo ja sam uvatio nekih 18. tipova koji su bili najcesce na rokovima...i skoro da mogu da garantujem da ce doci bar 4 od tih zadataka (sigurnost 80%:D)

Grizzly · **Poslato:** 08.06.2007. 22:42:51

Rešen domaći sa detaljnim objašnjenjem na www.nemanjakovacevic.com

Zbog problema sa serverom i mog još klimavog znanja iz web programiranja u javi bilo je problema sa upisom na mial liste. Ako Vam ne stigne obaveštenje o ovom domaćem a prijavili ste se na listu znači da nije uspelo, pa Vas molim pokušajte još jednom. Prijavljivanje je uspelo kad Vam izadje pop up prozor sa odgovarajućom porukom. Javite mi se na admin [at] nemanjakovacevic.com ukoliko i dalje imate takvih problema

poz

JoTzA · **Poslato:** 09.06.2007. 04:00:50

Grizzly ajde pomogni nam malo sa ovim zadacima koji ce biti za kolokvijum, posto ti kako vidim strukture bas idu od ruke

Poz.

VILENJAK · **Poslato:** 09.06.2007. 10:55:31

beavis je napisao:

Citiraj:

2. Binarno stablo se naziva HEAP ako za svaki čvor u stablu važi da je njegov sadržaj veći od sadržaja svih ostalih čvorova u njegovim podstablima. Napisati funkciju koja će proveriti da li je dato binarno stablo celih brojeva HEAP.
(20 poena)

Kod:

boolean heap(CvorStabla T){
if (T==null) return true;
if ((T.lijevo.podatak<T.podatak)&&(T.desno.podatak<T.podatak)
     return heap(T.lijevo)&&heap(T.desno);
else return false;
}

da li je to to?

Razmisljanje je skroz OK,samo mislim da ce baciti exception ako je t.levo=null ili t.desno =null,po meni je kod iz User skripte skroz ok,

Citiraj:

boolean heap(CvorStabla koren)
{
if (koren==null) return true;
if ((koren.levo!=null)&&(koren.levo.podatak>koren.podatak)||!heap(koren.levo))
return false;
if ((koren.desno!=null)&&(koren.desno.podatak>koren.podatak)||!heap(koren.desno))
return false;

return true;
}

ja sam ga prepravio na nacin na koji mi pisemo kod Koste.

NapoleoN · **Poslato:** 09.06.2007. 11:42:20

VILENJAK je napisao:

Ja mislim da je 17. 20-10-45-40-50,a 18. 6-15-16-18-27.Neka me ispravi neko ako gresim.

I ja sam dobio isto rešenje. Za ubacivanje u AVL stabla vam može pomoći aplet http://www.csi.uottawa.ca/~stan/csi2514/applets/avl/BT.html.

xXx · **Poslato:** 09.06.2007. 12:08:20

Jeste...ja sam bio pogresio jer trebaju 2 rotacije

17. je:

20-10-45-40-50

A 18. je:

6-15-16-18-27

Evo vam ovaj link, mnogo je bolji:

http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm

Tu mozete videti resenje za 12. (kada se ubace svi elementi, treba da se izvrsi jedna manja rotacija oko 203 "na levo", pa onda glavna rotacija oko 700 "na desno"...i dobije se cvor kao sto vam taj link pokaze)

6. i 2. takodje mogu da se rese tu

Sandra1986 · **Poslato:** 09.06.2007. 13:25:34

aj ako neko zna one metode za izbacivanje i izbacivanje iz B stabla kada cvor ima vise vrednosti u sebi ako moze nek nam napise kako to ide,posto to stvarno cesto dolazi na ispitu..hvala

kolji~voda~vri · **Poslato:** 09.06.2007. 15:27:17

Kod:

   //broji cvorove stabla
   public static int count(CvorStabla t){
      if (t == null)
         return 0;
      return 1 + count(t.levo) + count(t.desno);
   }
   
   //broji cvorove stabla vece od zadatog broja
   public static int countBigger(CvorStabla t, int v){
      if (t == null)
         return 0;
      if (t.podatak > v)
         return 1 + countBigger(t.levo, v) + countBigger(t.desno, v);
      else
         return countBigger(t.levo, v) + countBigger(t.desno, v);
   }
   
   //stampa infixni prolazak kroz stablo
   public static void stampajInfix(CvorStabla t){
      if (t == null)
         return;
      stampajInfix(t.levo);
      System.out.println(t.podatak);
      stampajInfix(t.desno);
      
   }
   
   //stampa prefiksni prolazak kroz stablo
   public static void stampajStablo(CvorStabla k){
      if (k == null)
         return;
      System.out.println(k.podatak);
      stampajStablo(k.levo);
      stampajStablo(k.desno);
      
   }
   
   //stampa putanju u AVL stablu od cvora do cvora - I nacin
   public static void stampajPutanju(CvorStabla a, CvorStabla b){
      if (a == null || b == null)
         return;
      while (a.podatak != b.podatak){
         System.out.println(a.podatak);
         if (a.podatak > b.podatak)
            a = a.levo;
         else
            a = a.desno;
      }
      System.out.println(b.podatak);
   }

   //stampa putanju u AVL stablu od cvora do cvora - II nacin
   public static void stampajPutanju2(CvorStabla a, CvorStabla b){
      if (a==null || b==null)
         return;
      System.out.println(a.podatak);
      if (a.podatak > b.podatak)
         stampajPutanju2(a.levo, b);
      if (a.podatak < b.podatak)
         stampajPutanju2(a.desno, b);
   }
   
   //racuna zbir putanje u AVL stablu
   public static int zbirPutanje(CvorStabla a, CvorStabla b){
      int zbir = 0;
      while (a.podatak != b.podatak){
         zbir += a.podatak;
         if (a.podatak > b.podatak)
            a = a.levo;
         if (a.podatak < b.podatak)
            a = a.desno;
      }
      zbir += b.podatak;
      return zbir;
   }
   
   //vraca najmanji broj u binarnom stablu (nije BST)
   public static int minimum(CvorStabla t){
      if (t == null)
         return Integer.MAX_VALUE;
      return Math.min(Math.min(minimum(t.levo), minimum(t.desno)), t.podatak);
   }
   
   //vraca najveci broj u binarnom stablu (nije BST)
   public static int maximum(CvorStabla t){
      if (t == null)
         return Integer.MIN_VALUE;
      return Math.max(Math.max(maximum(t.levo), maximum(t.desno)), t.podatak);
   }
   
   //nalazi cvor u binarnom stablu (nije BST) koji sadrzi dati broj (ne hvata exceptione)
   public static CvorStabla nadji(CvorStabla t, int v){
      if (t == null)
         return null;
      if (t.podatak == v)
         return t;
      if (nadji(t.levo, v) == null)
         return nadji(t.desno, v);
      else
         return nadji(t.levo, v);
      
   }

   //vraca roditelja datog cvora (ne hvata exceptione)
   public static CvorStabla nadjiRoditelja(CvorStabla t, CvorStabla a){
      if (t == null)
         return null;
      if ((a.podatak == k.podatak) || (t.levo != null && t.levo.podatak == a.podatak) || 
            (t.desno != null && t.desno.podatak == a.podatak))
         return t;
      if (nadjiRoditelja(t.levo, a) == null)
         return nadjiRoditelja(t.desno, a);
      return nadjiRoditelja(t.levo, a);
   }
   
   //proverava da li su 2 stabla identicna
   public static boolean identicni(CvorStabla a,CvorStabla b){
      if (a == null && b == null)
         return true;
      if ((a==null & b!=null) || (a!=null & b==null))
         return false;
      if (a.podatak != b.podatak)
         return false;
      return identicni(a.levo, b.levo) & identicni(a.desno, b.desno);
   }
   
   //proverava da li su 2 stabla slicna kao u ogledalu
   public static boolean ogledalo(CvorStabla a,CvorStabla b){
      if (a == null && b == null)
         return true;
      if ((a==null & b!=null) || (a!=null & b==null))
         return false;
      if (a.podatak != b.podatak)
         return false;
      return ogledalo(a.levo, b.desno) & ogledalo(a.desno, b.levo);
      
   }
   
   //racuna najvecu dubinu stabla
   public static int maxDubina(CvorStabla t){
      if (t == null)
         return 0;
      if (maxDubina(t.levo) > maxDubina(t.desno))
         return 1 + maxDubina(t.levo);
      return 1 + maxDubina(t.desno);
   }
   
   //vraca cvor sa najvecom dubinom
   public static CvorStabla najdubljiCvor(CvorStabla t){
      if (maxDubina(t) == 1)
         return t;
      if (maxDubina(t.levo) > maxDubina(t.desno))
         return najdubljiCvor(t.levo);
      return najdubljiCvor(t.desno);

   }
   
   //proverava da li je stablo AVL
   public static boolean jeAVL(CvorStabla t){
      if (t == null)
         return true;
      if (Math.abs( maxDubina(t.levo) - maxDubina(t.desno) ) <= 1)
         return jeAVL(t.levo) & jeAVL(t.desno);
      return false;
      
   }
   
   //proverava da li je cvor po sadrzaju veci od svojih potomaka
   public static boolean jeVeciOdPotomaka(CvorStabla t){
      if (t == null)
         return true;
      if (t.levo == null && t.desno == null)
         return true;
      if ((t.levo != null && t.podatak < t.levo.podatak) ||
            (t.desno != null && t.podatak < t.desno.podatak))
         return false;
      return jeVeciOdPotomaka(t.levo) && jeVeciOdPotomaka(t.desno);
      
   }

   //broji cvorove u stablu koji zadovoljavaju neki uslov
   public static int countIf(CvorStabla t){
      if (t == null)
         return 0;
      if (jeVeciOdPotomaka(t)) //OVDE UPISI USLOV
         return 1 + countIf(t.levo) + countIf(t.desno);
      return countIf(t.levo) + countIf(t.desno);
   }
   
   //sledece 4 metode vracaju cvor u stablu ciji je
   //proizvod potomaka iz desnog podstabla najveci ???????
   public static CvorStabla najveciProizvod(CvorStabla t){
      if (t == null)
         return null;
      return veci(t, veci(najveciProizvod(t.levo), najveciProizvod(t.desno)));
   }
   public static CvorStabla veci(CvorStabla a, CvorStabla b){
      if (proizvodDesnogPodstabla(a) > proizvodDesnogPodstabla(b))
         return a;
      return b;
   }
   public static int proizvodDesnogPodstabla(CvorStabla t){
      if (t == null || t.desno == null)
         return 0;
      return proizvodClanova(t.desno);
   }   
   public static int proizvodClanova(CvorStabla t){
      if (t == null)
         return 1;
      return t.podatak * proizvodClanova(t.levo) * proizvodClanova(t.desno);
   }

kolji~voda~vri · **Poslato:** 09.06.2007. 15:29:02

Citiraj:

aj ako neko zna one metode za izbacivanje i izbacivanje iz B stabla kada cvor ima vise vrednosti u sebi ako moze nek nam napise kako to ide,posto to stvarno cesto dolazi na ispitu..hvala

potpuno se slazem...

devojcica · **Poslato:** 09.06.2007. 16:41:25

E ljudi, bas ste super!
Nisam puno ucila, pa imam par pitanja.
Radila sam zadatke iz User-ove skripte,
pa nisam sigurna da su mu sva resenja
tacna, a neke zadatke sam uradila drugacije,
pa me interesuje da li su ok.
Za neke unapred znam da nisam dobro uradila,
ali ne znam zasto nisu dobri...
Hvala unapred za pomoc!

Evo 5 zadataka:

//Dat je pokazivač na koren binarnog stabla
//čiji čvorovi sadrže cele brojeve.
//Napisati funkciju koja će vratiti pokazivač
//na čvor list koji je na najvećoj dubini u stablu.

public int dubina(cvorStabla cvor){
if (cvor == null)
return 0;
if (cvor != null)
return Math.max(dubina(cvor.levo)+1, dubina(cvor.desno)+1);
}

public cvorStabla najdublji(cvorStabla cvor){
if (cvor == null)
return null;
if(cvor != null)
if (dubina(cvor.levo) > dubina(cvor.desno))
return cvor.levo;
else
return cvor.desno;
return null;
}

//Dva binarna stabla su identrična
//ako su ista po strukturi i sadržaju,
//tj. oba korena imaju isti sadržaj i
//njihova odgovarajuća podstabla su identična.
//Napistati funkciju koja će proveriti
//da li su dva binarna stabla identična.

public boolean identicna(cvorStabla cvor1, cvorStabla cvor2){
if (cvor1 == null && cvor2 == null)
return true;
if (cvor1 != null && cvor2 != null)
if (cvor1.podatak == cvor2.podatak)
return identicna(cvor1.levo, cvor2.levo) && identicna(cvor1.desno, cvor2.desno);
return false;
}

//Napišite funkciju int nivo(cvor *k, crvor *p)
//koja prihvata pokazivač na koren binarnog stabla
//i pokazivač na neki čvor u stablu,
//a vraća pokazivač na roditelja čvora p
//(vraća NULL ako roditelj ne postoji).
//Pri tome čvor stabla ima samo pokazivače na svoju decu

public cvorStabla nivo(cvorStabla k, cvorStabla p){
if (k == null)
return null;
if (k.levo == p || k.desno == p)
return k;
else if (k.levo != p && k.desno != p)
return nivo(k.levo, p) && nivo(k.desno, p);
return null;
}

//Napisati proceduru koja štampa sadržaj svih čvorova
//binarnog stabla (nije BST) na putanji
//od korena do najdubljeg čvora.

public void maxPutanja(cvorStabla cvor){
if (cvor == null)
return;
System.out.println(cvor.podatak);
if (dubina(cvor.levo) > dubina(cvor.desno))
maxPutanja(cvor.levo);
else
maxPutanja(cvor.desno);
return;
}

//Binarno stablo se naziva HEAP ako za svaki čvor
//u stablu važi da je njegov sadržaj veći
//od sadržaja svih ostalih čvorova u njegovim podstablima.
//Napisati funkciju koja će proveriti da li je dato
//binarno stablo celih brojeva HEAP.

public boolean HEAP(cvorStabla cvor){
if (cvor == null)
return true;
if (cvor != null)
if (cvor.levo.podatak < cvor.podatak && cvor.desno.podatak < cvor.podatak)
return HEAP(cvor.levo) && HEAP(cvor.desno);
return false;
}

NapoleoN · **Poslato:** 09.06.2007. 17:38:49

Ima dosta apleta na netu i za b-stabla, al za b* nisam našao ni jedan, pa ako neko nadje nek da link...

VILENJAK · **Poslato:** 09.06.2007. 18:13:24

devojcica je napisao:

public int dubina(cvorStabla cvor){
if (cvor == null)
return 0;
if (cvor != null)// treba samo else ili nista.
return Math.max(dubina(cvor.levo)+1, dubina(cvor.desno)+1);
}

samo umesto if (cvor != null) stavi else i radice.Cak moze i bez icega.

devojcica · **Poslato:** 09.06.2007. 18:41:47

a ovaj zadatak:

public cvorStabla nivo(cvorStabla k, cvorStabla p) {
if (k == null)
return null;
if (k.levo == p || k.desno == p)
return k;
else if (k.levo != p && k.desno != p)
return nivo(k.levo, p) && nivo(k.desno, p);
return null;
}

ne mogu da koristim "&&" za tip cvorStabla.
Kako to da resim?

devojcica · **Poslato:** 09.06.2007. 19:06:52

Ovo sam nasla u User-ovoj skripti:

Pitanja (iz prethodnih rokova):

• Šta je potpuno stablo?
Svi listovi na istom nivou.

• Šta je kompletno stablo?
Svaki čvor ili nema dece ili ih ima tačno dvoje (binarno stablo).

• Šta je balansirano stablo?
Visina i levog i desnog podstabla se ne razlikuju za više od 1.

• Kada je data struktura mreža, onda to znači da:
Graf (mreza) G predstavlja uređeni skup (V, E), gde je V skup čvorova (vertices), a E skup ivica (edges), u kome svaka ivica predstavlja par (x, y) čvorova iz V.

• Kada se kaže da je neka struktura podataka linearna, onda to znači da:
Svaki element ima jednog prethodnika i jednog sledbenika.

• Kada se kaže da je neka struktura podataka nelinearna, onda to znači da:
Svaki element ima jednog ili više prethodnika i više sledbenika.

• Stablo za binarno pretraživanja ima ukupno M čvorova a visinu K. Vreme potrebno za pronalaženje nekog čvora u stablu je proporcionalno sa:
Pošto se radi o BST stablu, pronalaženje je proporcionalno sa visinom K.

• Kakva je razlika između binarnog i B stabla?
B-stablo je višegransko stablo reda n, i može imati n-1 ključeva u listu, dok je binarno stablo reda 2 i može imati 1 ključ u listu.

Sandra1986 · **Poslato:** 09.06.2007. 20:56:34

jos samo kad bi neko napisao kako se vrsi ubacivanje i izbacivanje iz B stabla kada cvorovi imaju vise celobrojnih elemenata u sebi..to zaista dolazi na svakom roku..ako neko zna zaista bi nam ucinio veliku uslugu kad bi objavio...

xXx · **Poslato:** 10.06.2007. 00:27:40

Sandra1986 je napisao:

jos samo kad bi neko napisao kako se vrsi ubacivanje i izbacivanje iz B stabla kada cvorovi imaju vise celobrojnih elemenata u sebi..to zaista dolazi na svakom roku..ako neko zna zaista bi nam ucinio veliku uslugu kad bi objavio...

http://en.wikipedia.org/wiki/B-tree <- imas i linkove i sve, pregledaj!

Sandra1986 · **Poslato:** 10.06.2007. 00:51:08

@xxx treba mi resenje kao za onaj tvoj prvi zadatak..konkretno treba nam uradjen kod kao i za sve druge zadatke..taj jedino niko ni ne pominje..ako zna neko kako ide kod za ubacivanje u B stablo,kad cvor ima vise elemenata neka baci kod ovde..

FONForum

Strukture za sve

Ko je OnLine