Strukture za sve

kliford · **Poslato:** 02.07.2006. 16:50:41

Ne razumem u cemu je problem?? :zbun:

U pitanju su dve metode oko kojih svi lupamo glavu sta su i cemu sluze... Ja bih preveo i okacio svima kad bih znao C....

BTW, jos danas sam postavio temu koja bi vas interesovala povodom toga:
http://www.fonforum.org/viewtopic.php?p=190109#190109

kliford · **Poslato:** 02.07.2006. 17:37:13

Scully je napisao:

Evo npr. Stablo za binarno pretrazivanja ima ukupno M cvorova a visinu K. Vreme potrebno za pronalazenje nekog cvora u stablu je proporcionalno sa:
a) M + K
b) M*K
c) M
d) K

E, setio sam se... Posto je u pitanju BST stablo, najgora moguca kombinacija je da dodjes do dna stabla, ali nema sanse da promasis putanju do cvora jer je BST, znas kuda se ide... tako da je vreme proporcionalno samo sa visinom.... K

Savas · **Pridružio se:** 15.11.2004. 21:43:49 **Postovi:** 71

K je definitivno....

O vam je bre ljudi ustavi najgora moguca opcija pretrazivanja....

Logicno je dalje sve...
Ako je u metodi deljenje niza onda ide logN
Ako se prolazi kroz svaki el onda je n
za stablo jednostavno razmislih... najgore je da dodjes do dna stabla... putanja do dna = visina stabla....

Jaka nauka... Sto vise ucim ove str kapiram da mi je bolje da sto manje znam tj da mozgam o tome kako sta radi... Fora je da razmisljas linearno kao masina... Juce 2 sata pokusavam da ukapiram insert u stablo preko nekih appleta... Imao sam probleme sa tim jer sam hteo da razmisljam kao covek (ovako je lakse i logicnije metod) a ne kao komp "ovako pa ovako pa ovako gde je svako ovako jednako jedno drugome"

Ukapirajte sustinu, lako cete sklepati program... Gledam ja neku knjigu za etf, pa njima je pola knjige o stablima (150 str). Listajuci to presao sam za 10 min, jer nama treba stoti deo toga.... Da vi znate kakva se mudrost krije u ovom predmetu nikada ne bi ulazili toliko u dubinu ako vas bas ne zanima... Jednostavno naucite koliko treba.... Sto vise mozgas, vise vremena izgubis...
Sustina je da ce kao iz statistike da nas otkinu u junu sa zadacima, a onda ce dekan da im **re sto niko nije polozio pa ce u semp i okt da daju 17x lakse zadatke...

Dobrodosli na Fax Olaksanih Nauka gde se u prvim rokovima jedu mala pametna deca....

Savas · **Pridružio se:** 15.11.2004. 21:43:49 **Postovi:** 71

e sada gledam nesto za ovaj red (Queue).
Na wikipedii kaze da se red implementira kao povezana lista gde se novi el dodaju na kraj liste, a ovi sto izlaze se skidaju od napred (sa glave). Sto mu u sustini dodje kako LILO algoritam

Kliforde, za ono
array[start = (++start % array.length)] = obj
smo jednako glupi obojica.... a jos gluplji je onaj sto je to smislio...
Razmisaljajuci o ovome provalim da nemam pojma ni cemu start a ni end onda sluzi i onda vidim kljucnu stvar:

import DataStructures.Interfaces.*;

public class ArrayQueue implements IQueue

Sto znaci da je iz APIja uvezen red i da se njime manipulise, a vaaaaaziiii da cu sada to da gledam i proucavam tamo. Ako se secate, i Stack smo tako radili na PP, lepo uvezao listu, i addItem() i removeItem() metode su dalje resavale sve... Glupo je, tj nedosledna su objasnjenja... Ako se nesto objasnjava na jedan nacin, onda treba i drugo...
BTW, sumnjam u ispravnost POP funkcije, tj metode... Nesto nije tu sve ok... Zato sam i gledao kako smo radili na PP

lepo ja kazem haos...
Nije ni cudo sto ne smeju da napisu knjigu... Ko zna koliko miliona gresaka bi imala...

P.S.
ako nam se padne kod za sortiranje niza da li je tacan odgovor:
Arrays.sort(niz);

shredder · **Poslato:** 02.07.2006. 21:50:53

Ma kakav API, to su uvezeni interfejsi iz direktorijuma data structures/interfaces koje je napravio u svom projektu onaj ko je sve ono pisao.

Savas · **Pridružio se:** 15.11.2004. 21:43:49 **Postovi:** 71

shredder je napisao:

Ma kakav API, to su uvezeni interfejsi iz direktorijuma data structures/interfaces koje je napravio u svom projektu onaj ko je sve ono pisao.

onda je tragedija jos veca................
:durisha:

kliford · **Poslato:** 02.07.2006. 22:33:47

Muku mucim

Zadatak:
imamo binarno stablo... metoda kao ulaz prihvata pokazivac na root cvor i na neki cvor X... metoda treba da vrati dubinu tog cvora X...
Ovo bi bio boza zadatak da je u pitanju BST stablo, ali nije, vec obicno binarno...

Any ideas?

kliford · **Poslato:** 03.07.2006. 01:26:53

User i ja zakljucismo da je to veorvatno u rokovima stamparska greska i da se misli na BST stablo

Elem, evo metode koja proverava da li je stablo AVL

Primedbe, greske, prilozi, predlozi, zelje, cestitke i pozdravi dobrodosli

Kod:

private static boolean isBST(TNode n){
   if (n==null) return true;
   if ((n.left.data < n.data)&&(n.right.data > n.data))
      return isBST(n.left) && isBST(n.right);
   return false;
   }
 
private static int count(TNode n){
   if (n==null) return 0;
   return 1 + count(n.left) + count(n.right);
   }
 
private static boolean isBalanced(TNode){
   if (n==null) return true;
   if (Math.abs((count(n.left)-count(n.right))<=1)
      return ((isBalanced(n.left) && isBalanced(n.right));
   return false;
   }
 
public static boolean isAVL(TNode n){
   return isBST(n) && isBalanced(n);
   }

Slepac · **Poslato:** 03.07.2006. 02:04:32

Kod:

public int DubinaMax(TreeNode aNode)
   {
      if (aNode == null)
         return 0;
   return 1 + Math.max(DubinaMax(aNode.Left), DubinaMax(aNode.Right));
   }

public TreeNode DubinaMaxNode(TreeNode aNode)
   {
      if (aNode.Left == null && aNode.Right == null)
         return aNode;
      if (DubinaMax (aNode.Left)< DubinaMax (aNode.right))
{
         Return DubinaMaxNode(aNode.Right);
}
Else return DubinaMaxNode(aNode.Left);
   }

Moj prvi post kao doprinos ovoj temici. Znaci stablo ne mora biti BST ovaj kod gore radi i bez toga

Slepac · **Poslato:** 03.07.2006. 02:08:54

Inace trebam pomoc oko puteva u grafu Eulerov put se zove prost, a kako se zove Hamiltonov put

baneizalfe · **Poslato:** 03.07.2006. 02:28:45

kliford je napisao:

User i ja zakljucismo da je to veorvatno u rokovima stamparska greska i da se misli na BST stablo

Elem, evo metode koja proverava da li je stablo AVL

Primedbe, greske, prilozi, predlozi, zelje, cestitke i pozdravi dobrodosli

Kod:

private static boolean isBST(TNode n){
   if (n==null) return true;
   if ((n.left.data < n.data)&&(n.right.data > n.data))
      return isBST(n.left) && isBST(n.right);
   return false;
   }
 
private static int count(TNode n){
   if (n==null) return 0;
   return 1 + count(n.left) + count(n.right);
   }
 
private static boolean isBalanced(TNode){
   if (n==null) return true;
   if (Math.abs((count(n.left)-count(n.right))<=1)
      return ((isBalanced(n.left) && isBalanced(n.right));
   return false;
   }
 
public static boolean isAVL(TNode n){
   return isBST(n) && isBalanced(n);
   }

Nista ja tu ne bi menjao...
Znaci j***li smo chvorka (chedu) danas na ispitu?

User · **Poslato:** 03.07.2006. 02:47:31

kliford je napisao:

User i ja zakljucismo da je to veorvatno u rokovima stamparska greska i da se misli na BST stablo

Dodje li nam na ispitu i ako asistent potvrdi da nije BST (:udri:), ja cu da napisem ovo:

Kod:

public int level(Object object) {
   if (this.root==object) return 0;
   int levelInLeft = ( left==null ? -1 : left.level(object) );
   if (levelInLeft>-1) return 1 + levelInLeft;
   int levelInRight = ( right==null ? -1 : right.level(object) );
   if (levelInRight>-1) return 1 + levelInRight;
   return -1;
} // left i right su takodje BTree, umesto BTNode

Mada su sve sanse da je ipak samo BST.

Tada ce provera za AVL da se svede samo na isBalanced, a za dubinu samo count() dok se ne naidje na cvor koji se trazi.

Piece of cake

Scully · **Poslato:** 03.07.2006. 09:18:08

evo jos:

- kod B* kad se pozajmljuje od brata "bratski" se deli br kljuceva, samo me zanima sta ako je neparan br. jel ovaj koji daje ostaje sa tim jednim vise?
- kompleksnost za jednostruko spregnutu listu? (moze i za DDLN)
- za transpoziciju su na predavanjima rekli jedno a u skripti :zbun:

pise drugo... sta je tacno?

Scully · **Poslato:** 03.07.2006. 09:33:29

kliford je napisao:

User i ja zakljucismo da je to veorvatno u rokovima stamparska greska i da se misli na BST stablo

Elem, evo metode koja proverava da li je stablo AVL

Primedbe, greske, prilozi, predlozi, zelje, cestitke i pozdravi dobrodosli

Kod:

private static boolean isBST(TNode n){
   if (n==null) return true;
   if ((n.left.data < n.data)&&(n.right.data > n.data))
      return isBST(n.left) && isBST(n.right);
   return false;
   }
 
private static int count(TNode n){
   if (n==null) return 0;
   return 1 + count(n.left) + count(n.right);
   }
 
private static boolean isBalanced(TNode){
   if (n==null) return true;
   if (Math.abs((count(n.left)-count(n.right))<=1)
      return ((isBalanced(n.left) && isBalanced(n.right));
   return false;
   }
 
public static boolean isAVL(TNode n){
   return isBST(n) && isBalanced(n);
   }

za proveru balansiranosti poredis visinu levog i desnog podstabla, a ne broj cvorova, pa ti u fji count (istvari bi trebalo da bude height) treba - return 1 + Math.max(count(n.left), count(n.right));

shredder · **Poslato:** 03.07.2006. 09:49:57

Evo kod za AVL

Kod:

 static int height(TreeNode node) {
      if (node == null)
         return 0;
      return 1 + Math.max(height(node.Left), height(node.Right));
   }
   
   static boolean isAVL(TreeNode node) {
      if (node == null)
         return false;
      if (node.Left == null && node.Right == null)
         return true;
      if ((Math.abs(height(node.Left) - height(node.Right))) > 1)
         return false;
      return isAVL(node.Left) && isAVL(node.Right);
   }

gala · **Poslato:** 03.07.2006. 10:45:15

E jel' zna neko ovo:

Citiraj:

Pokazati postupak (korak po korak) kada se u pocetno prazno AVL stablo ubacuje sledeci niz brojeva: 30, 40, 50, 10, 20, 80, 70.

Unapred hvala

User · **Poslato:** 03.07.2006. 11:25:17

Kako da ti neko nacrta to? U paintu?

User · **Poslato:** 03.07.2006. 11:53:12

d uputstvo za AVL (ko ga razume shvatice):

http://www.ptt.yu/korisnici/n/m/nmomo//AVL.pdf

Lske · **Poslato:** 03.07.2006. 19:08:20

Kako je bilo na ispitu? Utisci!!!

Scully · **Poslato:** 03.07.2006. 20:07:19

Meni je bilo bezveze.. bilo je sve sto sam mislila da nece... hashing, ubaci za stak kao DLL (ovo ispadne da nije tesko ali...), stampaj putanju od korena do najveceg u binarnom (ne BST) stablu (i ovo je moglo da se uradi, kasno sam se setila)... i nije uopste bilo teorije kao sto je receno, tu bi moglo nesto da se izvuce.. i radili smo 2 sata a ne 3.. neki su predali odmah, a cini mi se da vecina nece proci sjajno.. mozda se varam.. a asistent pita kao jeste bili vi na vezbama... btw za hashing je rekao da smo kod mogli naci na netu (a jel toliko tesko da ga okace na sajtu).. sa sve vezbama i predavanjima i ne malo (ne i previse) rada ne znam da li cu proci... u svakom slucaju vezbe i predavanja ne mogu da se porede sa ispitom.. kodovi su glavno, a to smo bas forsirali na V/P.. aaaha...

kliford · **Poslato:** 03.07.2006. 20:59:19

Ne znam... meni i nije bilo toliko strashno... Videcemo kad dodju rezultati...

BTW:

shredder je napisao:

Evo kod za AVL

Kod:

 static int height(TreeNode node) {
      if (node == null)
         return 0;
      return 1 + Math.max(height(node.Left), height(node.Right));
   }
   
   static boolean isAVL(TreeNode node) {
      if (node == null)
         return false;
      if (node.Left == null && node.Right == null)
         return true;
      if ((Math.abs(height(node.Left) - height(node.Right))) > 1)
         return false;
      return isAVL(node.Left) && isAVL(node.Right);
   }

Da, pogresno sam protumacio pojam "balansiranosti", ali AVL mislim da je podvrsta BST stabla, a ti nisi proverio ovde da li je BST... sve u svemu, pravo resenje za AVL je kombinacija tvog i mog resenja :lol:

shredder · **Poslato:** 03.07.2006. 21:32:40

kliford je napisao:

...pravo resenje za AVL je kombinacija tvog i mog resenja :lol:

pa da, mada mislim da nam ne bi trazili da sve to ispitujemo.

Vercundus · **Poslato:** 03.07.2006. 21:34:48

Pa nije da nije bilo tesko... Ono za putanju do maximalnog je stvarno bez veze, radio sam ga vise od sat vremena i nisam siguran da je dobro, mada videcemo... Hashing... jedino sto ne naucim i to mi dodje :udri:

Ostalo je manje-vise lagano...

Kad ce rezultati? Nesto se nesecam da je neko nesto rekao danas...

Paf · **Poslato:** 04.07.2006. 00:44:32

Pa, u principu, malo je teze bilo nego sto sam ocekivao.. Mislio sam da ce biti vise onih standardnih kodova koji stalno dolaze, a oni su se potrudili da daju i neke nove. Ali da pogresim kod identicnosti, prosto ne mogu da verujem!!!

Scully · **Poslato:** 04.07.2006. 01:32:54

meni sad samo malo zao sto sam sem tog hashinga ostalo mogla da uradim.. ali i to vreme.. zar nismo trebali da radimo 3h.. meni bi znacilo.. ovako sam lupetala nesto, ne verujem da je to sve na mestu...

Duzina niza 102... jel tad treba %103... Kazite mi sta predstavlja kljuc za neki ceo broj koji trazimo, pa da na njega radimo mod...

Ja nesto nikako da nadjem taj kod na netu... evo neceg.. !?

Kod:

Linear probing hashing:  search 

 int search( key, r )
     typekey key;  dataarray r;

     { int i, last;

     i = hashfunction( key ) ;
     last = (i+n-1) % m;
     while ( i!=last && !empty(r[i]) && r[i].k!=key )
          i = (i+1) % m;
     if (r[i].k==key)  return( i );
          else         return( -1 );
     }


Direct chaining hashing: search 

     datarecord *search( key, ptrs )
     typekey key;  datarecord *ptrs[];

     { int i, last;
       datarecord *p;
     p = ptrs[ hashfunction( key ) ];
     while ( p!=NULL && key!=p->k )   p = p->next;
     return( p );
     }

FONForum

Strukture za sve

Ko je OnLine